1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set of all finite sets

  1. Jun 11, 2013 #1
    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: Jun 12, 2013
  2. jcsd
  3. Jun 11, 2013 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
  4. Jun 11, 2013 #3
    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"?
  5. Jun 12, 2013 #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: Jun 12, 2013
  6. Jun 12, 2013 #5

    Stephen Tashi

    User Avatar
    Science Advisor

    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?
  7. Jun 12, 2013 #6


    User Avatar

    Staff: Mentor

    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.
  8. Jun 12, 2013 #7
    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: Jun 12, 2013
  9. Jun 12, 2013 #8
    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.
  10. Jun 12, 2013 #9
    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.
  11. Jun 12, 2013 #10
    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.
  12. Jun 13, 2013 #11
    You're right, I was thinking hereditarily finite sets.
  13. Jun 13, 2013 #12
    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.
  14. Jun 13, 2013 #13


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook