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

  • Context: Graduate 
  • Thread starter Thread starter Ryuzaki
  • Start date Start date
  • Tags Tags
    Finite Set Sets
Click For Summary

Discussion Overview

The discussion revolves around the construction of natural numbers from the class of all finite sets, focusing on the nature of this class and whether it is infinite. Participants explore various aspects of set theory, including equivalence classes, the properties of finite sets, and the implications of assuming the class is finite.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants propose that the class S of all finite sets is infinite, as it can be partitioned into equivalence classes based on one-to-one correspondences.
  • Others argue that the existence of sets like ∅, {∅}, {{∅}}, etc., supports the idea that S is infinite.
  • A participant questions how to formally prove that the collection of finite sets is infinite, seeking a rigorous argument rather than relying on intuition.
  • Some clarify that the construction of natural numbers starts from the empty set, leading to confusion about the definition of S, particularly regarding whether it includes the empty set.
  • A proof is presented by one participant, suggesting that if S were finite, it would lead to a contradiction with the partitioning of sets, thus concluding that S must be infinite.
  • Another participant mentions the axiom of regularity and its implications if S were finite, but this is challenged on the grounds that S is a class, not a set.
  • There is a discussion about the assumptions in the text being referenced, with some participants expressing uncertainty about the axioms being used.
  • One participant appreciates another's proof, describing it as "slick," while also presenting an alternative proof based on the uniqueness of sets defined by their number of elements.

Areas of Agreement / Disagreement

Participants generally agree that the class of all finite sets is likely infinite, but the discussion includes multiple competing views and uncertainties regarding the formal proofs and assumptions involved.

Contextual Notes

Limitations include the lack of clarity on the axioms assumed in the text being referenced, as well as the distinction between classes and sets, which complicates the discussion about the properties of S.

Ryuzaki
Messages
46
Reaction score
0
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?
 
Last edited:
Physics news on Phys.org
Ryuzaki said:
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:
Ryuzaki said:
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?
 
Dragonfall said:
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.
 
Dragonfall said:
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.
 
Last edited:
Stephen Tashi said:
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.
 
  • #10
Dragonfall said:
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.
 
  • #11
You're right, I was thinking hereditarily finite sets.
 
  • #12
micromass said:
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.
 
  • #13
I like your proof, it's really slick. The one I was thinking of was more low-brow: Let Tk = {{{..{∅}}...} with k curly braces (k=0 is the empty set), Claim: if j is not equal to k then Tk is not equal to Tj 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 Tn+1 = {Tn} and if j=0, it's obvious this is not the empty set, otherwise for j < n+1 Tj = {Tj-1}. By the inductive hypothesis we know Tn is not equal to Tj-1 so these two one element sets are not equal
 

Similar threads

Graduate Minimal Covering Set: System of Distinct Representatives
  • · Replies 1 ·
Replies
1
Views
1K
Graduate Formal axiom systems and the finite/infinite sets
  • · Replies 10 ·
Replies
10
Views
2K
Graduate How could the set of natural numbers not be finite?
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Somewhat difficult set theory proof
  • · Replies 6 ·
Replies
6
Views
2K
High School Natural Numbers and Odd Numbers
  • · Replies 17 ·
Replies
17
Views
2K
MHB Proof of Unique Equivalence Relation on Set w/ Partition Classes
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Is coutnable unions of finite sets an infinite set?
  • · Replies 3 ·
Replies
3
Views
7K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Prove that the proper subset E of a finite set F can never be equivalent to F.
  • · Replies 3 ·
Replies
3
Views
5K
Graduate Number of unequal integers with sum S
  • · Replies 12 ·
Replies
12
Views
2K