Set of all finite sets

  • Thread starter Ryuzaki
  • Start date
  • #1
46
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 [itex]S[/itex] of all finite sets. Now, [itex]S[/itex] 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, [itex]S=S_1⋃S_2⋃S_3⋃....[/itex]where [itex]S_1,S_2,S_3,[/itex] etc are disjoint equivalence classes, and to [itex]S_n[/itex], we give the label of the [itex]n[/itex]th natural number. This is how the natural numbers are constructed.

Now, as I understand it, the number of elements of [itex]S[/itex] for any [itex]n[/itex], has to be infinite. For instance, the number [itex]5[/itex] is the label given to [itex]S_5[/itex]. But [itex]5[/itex] can be represented in an infinite number of ways: five chairs, tables, coins, pencils, pens, etc. So, this means that [itex]S_5[/itex] is an infinite class, and so is any [itex]S_n[/itex].

The only way I see this possible is, the class [itex]S[/itex] 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:

Answers and Replies

  • #2
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,755
724
The only way I see this possible is, the class [itex]S[/itex] 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
 
  • #3
46
0
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"?
 
  • #4
1,030
4
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?
 
Last edited:
  • #5
Stephen Tashi
Science Advisor
7,713
1,519
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 [itex] S [/itex] was finite, then [itex] S [/itex] would be equivalent to one of the [itex] S_k [/itex]. Does that get you anywhere?
 
  • #6
Borek
Mentor
28,824
3,342
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[/tex]

There is a problem with your other statement - AFAICT you don't close all the curly braces.
 
  • #7
46
0
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, [itex]0[/itex] is not constructed along with the natural numbers. So, there is no [itex]S_0[/itex].

EDIT: Truly sorry, I guess I should have mentioned this in the beginning. I just re-read the text and it says [itex]S[/itex] is the class of all non-empty finite sets (somehow missed that word earlier :redface:). So, it clearly states that the empty set is excluded.
 
Last edited:
  • #8
46
0
That's a good question. I'm not familiar with the set of assumptions in your book. If [itex] S [/itex] was finite, then [itex] S [/itex] would be equivalent to one of the [itex] S_k [/itex]. 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 [itex]S[/itex] of all non-empty finite sets is infinite.

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

[itex]\Rightarrow[/itex] [itex]n(S_1) = n(S)[/itex]
[itex]\Rightarrow[/itex] [itex]S \approx S_1 [/itex], which is a contradiction by our partitioning.

Hence, our assumption that [itex] S [/itex] is finite, is false.
∴, [itex] S [/itex] is indeed infinite.
 
  • #9
1,030
4
If [itex]S[/itex] were finite, then [itex]S \in S_k \in S[/itex] for some [itex]k[/itex], which contradicts the axiom of regularity.
 
  • #10
22,129
3,298
If [itex]S[/itex] were finite, then [itex]S \in S_k \in S[/itex] for some [itex]k[/itex], 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
1,030
4
You're right, I was thinking hereditarily finite sets.
 
  • #12
46
0
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
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,755
724
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
 

Related Threads on Set of all finite sets

  • Last Post
2
Replies
30
Views
4K
  • Last Post
Replies
5
Views
2K
Replies
2
Views
2K
Replies
1
Views
3K
Replies
3
Views
5K
Replies
2
Views
611
Replies
4
Views
2K
Replies
25
Views
1K
Replies
25
Views
2K
  • Last Post
Replies
3
Views
614
Top