2
$\begingroup$

I believe that there should exist theorems about finite sets which are not provable without the notion of infinite sets.

I am curious if I am right. What are the examples of such theorems if they ?

The question may be a duplicate of an early question, but I could not find one. I agree this question is vague and does not have a unique answer. Though any useful comment or answer would be appreciated.

P.S. As a possible example I guess one can think of theorems proved by mathematical induction. But I am not sure if it is relevant or not here.

$\endgroup$
4
  • 5
    $\begingroup$ How about Goodstein’s theorem? $\endgroup$ Commented Nov 21, 2022 at 9:26
  • $\begingroup$ Sure, Goodstein’s seems to follow the lines of my question. $\endgroup$ Commented Nov 22, 2022 at 18:24
  • 3
    $\begingroup$ Induction does not require the existence of an infinite set. $\endgroup$ Commented Nov 23, 2022 at 18:02
  • $\begingroup$ @DanielWainfleet Please elaborate more on induction for finite sets. I would grateful if you share some must-know reference (ideal if relatively short but showing the matter of things) $\endgroup$ Commented Nov 24, 2022 at 19:09

1 Answer 1

4
$\begingroup$

A precise version of your question might be: are there statements in Peano Arithmetic (PA) that can't be proved in PA, but can be proved in set theory, say the Zermelo-Fraenkel axioms including Choice (ZFC)?

If you accept this as equivalent to your question, then there are lots of examples. The granddaddy of them all is the statement that PA is consistent. By Gödel's Second Incompleteness Theorem, this cannot be proven in PA, but it is almost trivially provable in ZFC.

As Aphelli commented, Goodstein's theorem is another famous example. So is the Paris-Harrington Principle (discussed here). That's particularly interesting, because the PHP is a slightly modified version of Ramsey's Theorem for finite sets, a famous combinatorial result. Ramsey's Theorem is provable in PA, but the PHP is not.

In other words, in ZFC we have two nearly identical proofs of two very similar statements: the infinite Ramsey theorem, and the infinite Paris-Harrington Principle. Then using compactness, we can use these to prove the finite versions. But within PA, we can prove only the finite Ramsey theorem, not the finite PHP.

It's worth noting that PA can be reformulated as a theory of finite sets. You'll find an extensive discussion of this here. Briefly, replacing the Infinity Axiom with its negation, we obtain a theory (call it ZF$\neg\infty$) that talks only about finite sets---in other words, a very good theory in which to do finite combinatorics. And there are ways to convert proofs "back and forth" between PA and ZF$\neg\infty$, so that any theorem of PA corresponds to a theorem of ZF$\neg\infty$, and vice versa.

You will notice I immediately started talking about theories, and not "notions". That's because the question is about provability. What's provable about a given notion (or mathematical concept) depends on what we assume about it. In other words, the axioms we accept.

$\endgroup$
5
  • $\begingroup$ +1....(1). Although Ramsey's Theorem is provable in PA, it is very easily provable by contradiction in ZFC with a little Model Theory (the Henkin Theorem, a.k.a. the Completeness Theorem: A theory is consistent iff it has a model)....(2). The Henkin Theorem itself is not provable in ZFC-Inf. It is easy to produce a finite selection of some of PA that has no finite model. $\endgroup$ Commented Nov 23, 2022 at 18:35
  • $\begingroup$ @DanielWainfleet Right. And proofs of the Ramsey theorem for infinite sets can be easily tweaked to prove the infinite version of the Paris-Harrington Principle. Then an easy compactness argument proves the finite version. So the interesting fact is that the finite version of Ramsey’s theorem is provable in PA, but not of the PHP. $\endgroup$ Commented Nov 23, 2022 at 18:50
  • $\begingroup$ Are you related to Prof. William Weiss of U. of Toronto? I took some courses from him on Set Theory and Model Theory. $\endgroup$ Commented Nov 25, 2022 at 17:03
  • $\begingroup$ @DanielWainfleet Afraid not. By the way, in your reference to Henkin's theorem, do you basically mean the compactness theorem? That enables us to deduce the finite version of Ramsey's theorem from the infinite version. But I don't see how you can deduce the infinite Ramsey Theorem from the Completeness Theorem. $\endgroup$ Commented Nov 25, 2022 at 18:28
  • $\begingroup$ Yes, with regards to the Ramsey Theorem , I meant to refer to the Compactness Theorem, not the Henkin. $\endgroup$ Commented Nov 25, 2022 at 18:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.