How are Natural Numbers Constructed from the Class of All Finite Sets?

[Ryuzaki]

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?

 

[Office_Shredder]

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

 

[Ryuzaki]

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"?

 

[Dragonfall]

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?

 

[Stephen Tashi]

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]

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.

$$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.

 

[Ryuzaki]

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.

 

[Ryuzaki]

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.

 

[Dragonfall]

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

 

[micromass]

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.

 

[Dragonfall]

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

 

[Ryuzaki]

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]

I like your proof, it's really slick. The one I was thinking of was more low-brow: Let T_k = {{{..{∅}}...} with k curly braces (k=0 is the empty set), Claim: if j is not equal to k then T_k is not equal to T_j as sets.

Proof on the maximum value of j/k. If max(j,k) = 1 then it's obvious that ∅ is not equal to {∅} as they have a different number of elements. Otherwise, if it's true for max(j,k) = n, suppose WLOG k = n+1. Then T_n+1 = {T_n} and if j=0, it's obvious this is not the empty set, otherwise for j < n+1 T_j = {T_j-1}. By the inductive hypothesis we know T_n is not equal to T_j-1 so these two one element sets are not equal