Set of all finite sets

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⋃S_2⋃S_3⋃....$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$ 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?

Last edited:

Office_Shredder
Staff Emeritus
Gold Member
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?

An obvious collection of sets is ∅, {∅}, {{∅}}, {{{∅}}}, etc. Each of these sets is finite (in fact has one element) so is contained in S, and therefore S is infinite

Sorry if this sounds stupid (I'm a beginner in the subject), but don't you have to prove that your collection of sets goes on till infinity? I mean, intuitively, I can see that it goes on, but how do you prove it? In other words, how do you show that your collection of sets is "obvious"?

Remember that the construction of the natural numbers with sets starts from the bottom up. S_0 = 0 (empty set), S_{n+1} = \{S_n\} \cup S_n. So S_5 is not the set of all sets with five things, it's specifically this one S_5 = {0,{0},{0,{0}},{0,{0},{0,{0}},{0,{0},{0,{0}},{0,{0},{0,{0}}}}

What the hell happened to $$for latex? Last edited: Stephen Tashi Science Advisor In other words, how do you show that your collection of sets is "obvious"? That's a good question. I'm not familiar with the set of assumptions in your book. If $S$ was finite, then $S$ would be equivalent to one of the $S_k$. Does that get you anywhere? Borek Mentor Remember that the construction of the natural numbers with sets starts from the bottom up. S_0 = 0 (empty set), S_{n+1} = \{S_n\} \cup S_n. So S_5 is not the set of all sets with five things, it's specifically this one S_5 = {0,{0},{0,{0}},{0,{0},{0,{0}},{0,{0},{0,{0}},{0,{0},{0,{0}}}} What the hell happened to [tex] for latex? Works as it always did. [tex]S_{n+1} = \{S_n\} \cup S_n$$

There is a problem with your other statement - AFAICT you don't close all the curly braces.

Remember that the construction of the natural numbers with sets starts from the bottom up. S_0 = 0 (empty set), S_{n+1} = \{S_n\} \cup S_n. So S_5 is not the set of all sets with five things, it's specifically this one S_5 = {0,{0},{0,{0}},{0,{0},{0,{0}},{0,{0},{0,{0}},{0,{0},{0,{0}}}}

What the hell happened to [tex] for latex?

I'm sorry, but I'm not able to understand this (probably because of the Latex malfunction). But in the text I'm using, $0$ is not constructed along with the natural numbers. So, there is no $S_0$.

EDIT: Truly sorry, I guess I should have mentioned this in the beginning. I just re-read the text and it says $S$ is the class of all non-empty finite sets (somehow missed that word earlier ). So, it clearly states that the empty set is excluded.

Last edited:
That's a good question. I'm not familiar with the set of assumptions in your book. If $S$ was finite, then $S$ would be equivalent to one of the $S_k$. Does that get you anywhere?

Oh, I think I understand yours and Office_Shredder's posts now. I came up with a proof, and I'd be grateful if you could check if its correct.

Proof that the class $S$ of all non-empty finite sets is infinite.

Assume that $S$ is finite. Now, for every set $T \in S$, there exists a set {$T$} $\in S_1$ (since $S$ is partitioned in such a manner).

$\Rightarrow$ $n(S_1) = n(S)$
$\Rightarrow$ $S \approx S_1$, which is a contradiction by our partitioning.

Hence, our assumption that $S$ is finite, is false.
∴, $S$ is indeed infinite.

If $S$ were finite, then $S \in S_k \in S$ for some $k$, which contradicts the axiom of regularity.

If $S$ were finite, then $S \in S_k \in S$ for some $k$, which contradicts the axiom of regularity.

Well, that's not really helpful since nobody says that ##S## is a set in the first place!! We're talking about ##S## as a class, it will never be a set. And the axiom of regularity is only for sets.

You're right, I was thinking hereditarily finite sets.

Well, that's not really helpful since nobody says that ##S## is a set in the first place!! We're talking about ##S## as a class, it will never be a set. And the axiom of regularity is only for sets.

Come to think of it, I do not know what set of axioms the text assumes. It hasn't mentioned anything so far about it (I'm still in the first chapter!). The text is A Concrete Introduction to Higher Algebra, by Lindsay N. Childs.

This question isn't part of the text exercise, but I thought of proving it nevertheless, as it is used in the construction of the natural numbers.

Is my above proof correct? I also thought of an alternate proof, but it assumes the existence of the class of all sets, which I do not know how to prove.

Office_Shredder
Staff Emeritus