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 nth 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 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 for latex?

<br /> <br /> Works as it always did.<br /> <br /> S_{n+1} = \{S_n\} \cup S_n<br /> <br /> There is a problem with your other statement - AFAICT you don&#039;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 for latex?

<br /> <br /> I&#039;m sorry, but I&#039;m not able to understand this (probably because of the Latex malfunction). But in the text I&#039;m using, 0 is not constructed along with the natural numbers. So, there is no S_0.<br /> <br /> 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 <b>non-empty</b> finite sets (somehow missed that word earlier <img src="https://www.physicsforums.com/styles/physicsforums/xenforo/smilies/oldschool/redface.gif" class="smilie" loading="lazy" alt=":redface:" title="Red Face :redface:" data-shortname=":redface:" />). 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