5
$\begingroup$

In a higher algebra book that I'm working through, the natural numbers are constructed in the following manner:-

Consider the class $S$ of all finite sets. Now, $S$ is partitioned into equivalence classes based on the equivalence relation that two finite sets are equivalent if there exists a one-to-one correspondence between them, i.e. if they are equipotent. And each of these equivalence classes are given a label, corresponding to the number of one-to-one correspondences.

So, $S= S_1 \bigcup S_2 \bigcup S_3 \bigcup....$where $S_1, S_2, S_3,$ etc are disjoint equivalence classes, and to $S_n$, we give the label of the $n$th natural number. This is how the natural numbers are constructed.

Now, as I understand it, the number of elements of $S_n$ for any $n$, has to be infinite. For instance, the number $5$ is the label given to $S_5$. But $5$ can be represented in an infinite number of ways: five chairs, tables, coins, pencils, pens, etc. So, this means that $S_5$ is an infinite class, and so is any $S_n$.

The only way I see this possible is, the class $S$ that we started out with, has to be an infinite class. Is this true? Basically, what I'm asking is: Is the class of all finite sets infinite? How do you prove this?

$\endgroup$
  • 2
    $\begingroup$ The class of all finite sets. $\endgroup$ – Zev Chonoles Jun 12 '13 at 1:59
  • $\begingroup$ In the usual axiomatization of set theory, there is no set of all finite sets. This means that "there are too many" finite sets. The collection of all finite sets is a proper class, which means it is larger than any set, so in particular it is infinite. $\endgroup$ – Andrés E. Caicedo Jun 12 '13 at 2:01
  • $\begingroup$ (As for how to show that it is infinite, one way is to note that we have the empty set, and that if $X$ is finite, so is $\mathcal P(X)$, the power set of $X$, that is, the collection of all subsets of $X$. But $\mathcal P(X)$ is strictly larger than $X$, and iterating taking power sets gives us larger and larger elements of $S$. Of course, there are other ways.) $\endgroup$ – Andrés E. Caicedo Jun 12 '13 at 2:04
  • $\begingroup$ It depends a lot on your axioms. For instance, you could say that $\emptyset$ is in $S$ (actually, it is the only representant of $S_0$) and that, for any $X$ in $S$, $f(X)=X\cup\{X\}$ is also in $S$ and different from $X$. By the way, $S$ is not a set but a proper class. Better (or worse), $S_1$, the class of all singletons, is not a set. $\endgroup$ – Taladris Jun 12 '13 at 2:07
  • $\begingroup$ Thank you for the responses, Zev, Andres and Taldres! I think I understand now. $\endgroup$ – Train Heartnet Jun 12 '13 at 5:17
3
$\begingroup$

Proof that $S$ in indeed infinite:

The class of all sets is obviously infinite. Now for every set $M$ there exists a set $\{M\}$ containing $M$ as only element. But $\{M\}$ is a one-element set, that is, element of $S_1$. Therefore $S_1$ has as many elements as the class of all sets. Obviosly, then $S$ must also have as many elements as the class of sets, since all elements of $S_1$ are also elements of $S$.

Edit:

Andres Caicedo requested that I add also the proof that the class of all sets is infinite, so there it is:

In the proof above, I've given a bijection between the class of all sets and the class $S_1$ of one-element sets, $M\mapsto\{M\}$. Now $S_1$ is a proper subclass of the class of all sets (all its members are sets, but there exist sets — for example the empty set — which are not in $S_1$). However a finite class cannot have a bijection to a proper subclass, therefore the class of all sets cannot be finite.

$\endgroup$
  • $\begingroup$ If we are worried about the infinitude of $S$ to begin with, we should also address why the class of all sets is infinite. $\endgroup$ – Andrés E. Caicedo Jun 12 '13 at 14:40

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.