5
$\begingroup$

Assume that the empty set $X_0$ exists. Assume furthermore that I can form power-sets, so that I can form $X_1:=2^{X_0}$, $X_2:=2^{X_1}$, etc.. Cantor's diagonalization argument (which should not require the Axiom of Infinity) will show that $|X_m|<|X_{m+1}|$, and in particular all of these sets are distinct. Thus, I have an infinite collection of sets. $$X_0,X_1,X_2,\ldots $$

Now, certainly, if I list a collection of sets for you, I should be able to form the set of all things in that list, no? How could one reasonably object that simply putting braces around things which are sets is not itself a set: $$\{ X_0,X_1,X_2,\ldots \}$$ But, sure enough, this does not constitute a proof that the above is a set (with the usual axioms of ZF set theory (without the Axiom of Infinity itself of course)). In fact, one cannot prove that any infinite set exists: the hereditarily-finite sets constitute a model of ZF without Infinity.

This bothers me quite a bit for the following reason. I view the axioms of set theory as a formalization of our intuitive notion of naive set theory, and as such, naive constructions which do not result in paradoxes should be able to be formalized in any 'reasonable' axiomatization. I realize this is subjective, but I suspect one would be hard-pressed to find a mathematician that seriously believed that the above construction is not 'valid', and as such, IMHO, a 'good' set of axioms would have the property that you could turn the above naive argument into a proof.

This thus yields the question:

Are there axioms for set theory which allow one to prove the existence of an infinite set without simply putting one in 'by hand'?

UPDATE: For what it's worth, some of the comments and answers eventually had me stumble upon Tarski-Grothendieck Set Theory, which implies the Axiom of Infinity. In some sense I suppose this technically constitutes an answer to the question, but still isn't as satisfying as one might like.

$\endgroup$
  • 1
    $\begingroup$ But the axiom of infinity does just that. It tells you that you can put braces around $0,1,2,3,\dots$. (It says something different, but it's more or less the same.) Can you say why the axiom of infinity doesn't capture your naive understanding of this, or is not intuitive to you? Also, have you heard of finitism or ultrafinitism? $\endgroup$ – martin.koeberl Mar 22 '17 at 21:38
  • 1
    $\begingroup$ The set whose existence is guaranteed by Infinity is not necessarily $\omega$. The axiom of infinity just says there is an inductive set (a set containing $\emptyset$ and $S(x)$ whenever $x$ is in there). One option is to fix this set $I$ and use comprehension to get the set $\{x\in I\mid \forall y(y$ is inductive$\rightarrow x\in y\}$ (It is not too hard to see that a.) this is just the intersection of all inductive sets; and b.) that this is equal to $\omega$, and c.) still an inductive set). From there, using replacement one could get the set you described above. $\endgroup$ – martin.koeberl Mar 22 '17 at 22:15
  • 3
    $\begingroup$ You can see Dedekind's proof of the existence of an infinite progression : "66. Theorem. There exist infinite systems." $\endgroup$ – Mauro ALLEGRANZA Mar 22 '17 at 22:19
  • 3
    $\begingroup$ Do you have a similar objection to the axiom of pairing? If you have $a$ and $b,$ how can one object that simply putting braces around them is not a set? $\endgroup$ – bof Mar 22 '17 at 23:15
  • 1
    $\begingroup$ @bof I suppose the issue is that I consider the construction $\{ a,b\}$ from $a$ and $b$ to be so fundamental as to be unquestionably true, and so don't mind simply assuming it as an axiom. Indeed, this very construction that seems to be almost unquestionably true is exactly what one would like to apply to deduce the existence of an infinite set. On the other hand, while I wouldn't say I "question" the existence of an infinite set, it is still desirable to me to be able to prove this from more 'fundamental' axioms. $\endgroup$ – Jonathan Gleason Mar 23 '17 at 0:07
5
$\begingroup$

The problem is how to axiomatize your assertion that

Now, certainly, if I list a collection of sets for you, I should be able to form the set of all things in that list, no?

What do we mean by a collection of sets? One might answer that we mean a set of sets, but that presupposes the definition of a set, and so it is unsuitable for foundational purposes.

One might say that if we have a collection of sets $s_i$, where $i$ ranges over the elements of some set $I$, then we can form the set $\{s_i\;\colon\;i\in I\}$. This is the Axiom of Replacement (so long as the map $i\mapsto s_i$ can be defined in your set theory). You can use this axiom to construct the set in your question, but you do need $I$ to be a set, and in particular it should be an infinite set. So you need the axiom of infinity.

Perhaps we could go one step further, and say that if we have some predicate $\phi$ on sets, then we can form the set of all sets that satisfy $\phi$. This is Frege's Axiom of (unrestricted) Comprehension. As you probably know, this axiom is inconsistent - just take $\phi$ to be $x\not\in x$: this is Russell's Paradox.

Now, there are axiomatizations of set theory besides ZFC that try and get round this problem in different ways. In Quine's New Foundations (NF), we are allowed to form the set $\{x|\phi\}$ as long as $\phi$ is stratifiable - loosely speaking, as long as we can assign natural numbers $l(x)$ to the variables $x$ occurring in $\phi$ such that if $x=y$ occurs in $\phi$ then $l(x)=l(y)$ and if $x\in y$ occurs in $\phi$ then $l(y)=l(x)+1$. In particular, $x\not\in x$ is not stratifiable, so we do not run into Russell's Paradox.

You can construct a stratifiable formula that is satisfied by your sets $X_i$, and by no other sets. Thus, you can construct your set $\{X_1,\dots\}$ in NF. (Update: see comments - the previous statement is untrue. However, NF can be used to construct similar countably infinite sets.) Indeed, the axiom of infinity is not needed in NF.

NF is not used as often as ZFC in mathematics, and it has a few undesirable properties (for example, it does not give you a Catesian closed category of sets). But I think it is worth keeping in mind.

Actually, I think that the way ZFC does things is rather elegant. In ZFC, we avoid Russell's paradox by declaring that the set of all sets is 'too large' to be a set. Once we have the axiom of infinity, we can construct enormously large sets within ZFC, but none that are so big that they lead to a contradiction in the set theory itself.

Once we have built up our hierarchy of sets, we can use the Axiom of Replacement to carry out precisely the procedure you described. So in ZFC, your rule is modified slightly to:

If I list a collection of sets for you, and if that collection is no larger than any set that can be constructed using the axioms of Infinity, Power Set, Union and Replacement, then I can form the set of all things in that list.

Notably, in ZFC you cannot form the set of all sets, so your original claim is untrue in ZFC, but this modified form is true.

$\endgroup$
  • 1
    $\begingroup$ Strictly speaking, the OP's sequence of sets doesn't have a stratifiable description, though the Frege naturals do. The stratifiable version of the OP's sequence is actually a funny creature, and can terminate after a finite number of steps in NF. $\endgroup$ – Malice Vidrine Mar 23 '17 at 1:23
  • 1
    $\begingroup$ Unrestricted comprehension is not just inconsistent with the Axiom of Separation; it is inconsistent in itself -- its instance $(\exists z)(\forall x)(x\in z\leftrightarrow x\notin x)$ is a contradiction as a matter of pure logic. $\endgroup$ – Henning Makholm Aug 15 '17 at 14:39
  • $\begingroup$ @HenningMakholm - Thanks. You're right, of course - Russell's Paradox has nothing to do with separation. I'll edit this now. $\endgroup$ – John Gowers Aug 16 '17 at 19:30
  • $\begingroup$ I know almost nothing about NF. But in "Set Theory: An Introduction to Independence Proofs", by K.Kunen, in the (small) section "Other Set Theories" he says that the negation of the Axiom of Choice was shown to be a theorem of NF, and this may be one reason why it lacks popularity. $\endgroup$ – DanielWainfleet Aug 22 '17 at 3:54
2
$\begingroup$

Not all "collections" of sets can be sets (see e.g. Russell's paradox). If you want to be able to refer to arbitrary collections, you need a more inclusive concept such as "classes"; classes that aren't sets are called proper classes. The axiom of infinity says not only that there are infinitely many sets, but that there are sets with infinitely many elements. Your $\left\{ X_k|k\ge 0\right\}$ could be a proper class, for all we know without the axiom of infinity.

$\endgroup$
0
$\begingroup$

You could have phrased your argument differently in a much weaker logical system, namely Peano axioms. Thus, we have the number $0$, its successor $1$, its successor $2$, etc. Doesn't that result in an infinite collection? The answer is it doesn't and in fact the existence of an infinite set has interesting foundational consequences for models of the Peano axioms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.