# Class of all finite sets

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?

• – Zev Chonoles Jun 12 '13 at 1:59
• 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. – Andrés E. Caicedo Jun 12 '13 at 2:01
• (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.) – Andrés E. Caicedo Jun 12 '13 at 2:04
• 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. – Taladris Jun 12 '13 at 2:07
• Thank you for the responses, Zev, Andres and Taldres! I think I understand now. – Train Heartnet Jun 12 '13 at 5:17

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.

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