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$
6
  • 2
    $\begingroup$ The class of all finite sets. $\endgroup$
    – Zev Chonoles
    Jun 12, 2013 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, 2013 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, 2013 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, 2013 at 2:07
  • $\begingroup$ Thank you for the responses, Zev, Andres and Taldres! I think I understand now. $\endgroup$
    – Train Heartnet
    Jun 12, 2013 at 5:17

1 Answer 1

Reset to default
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$
1
  • $\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, 2013 at 14:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .