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 cardinality conjecture.

  1. Mar 5, 2008 #1
    Well, it's a conjecture to me because I don't know (yet) if it's true or false.

    Let |A|=n, where n is an infinite cardinal. Let B be the collection of all subsets of A with cardinality less than n. Then |B|=n. Is it true first of all? And will the proof be short or long?
     
    Last edited: Mar 5, 2008
  2. jcsd
  3. Mar 5, 2008 #2
    Let n = aleph i. The collection of ALL subsets subsets of A has cardinality 2^n = aleph(i+1). Thus by the Continuum Hypothesis, |B|< aleph(i+1) <= aleph i = n. Clearly, n<=|B|. So your conjecture is true.

    Did you want to prove it without appealing to the Continuum Hypothesis? I'm not fully convinced by my proof either. Perhaps try transfinite induction.

    Edit: Try this: A = {a_i|i in I}, where |I|=n. Well-order I, and let f:B->A^m, given by f(S)=(a_i1, a_i2, ... ), where a_i1 < a_i2 < ... and m < n. Clearly, f is injective, so |B|<= mn. We know that mn=n, so you are done (since n<=|B|). I think this works. The result (aleph i)^(aleph j) = aleph i if j<i was used.

    Edit: You must sum up over all m such that m < n. So its back to using aleph0, aleph1, ..., aleph (i-1) again (Continuum hypothesis). The sum will be be (aleph0)n+(aleph1)n+...+(aleph(i-1))n = n+n+...+n = n. I can't get out of the Continuum hypothesis.

    Edit: This proof also only works if |A|=aleph i for some integer i. It doesn't work if i itself is infinite.

    Let me think of using transfinite induction, which doesn't rely on integers.
     
    Last edited: Mar 5, 2008
  4. Mar 5, 2008 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    How do you know |B| is less than aleph(i+1)?
     
  5. Mar 5, 2008 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It's easy to construct a counterexample if you assume CH is false.

    Suppose that [itex]\mathbb{N} \subseteq A[/itex] and [itex]|\mathbb{N}| < |A| < 2^{|\mathbb{N}|}[/itex]. Then [itex]\mathcal{P}(\mathbb{N}) \subset B[/itex], giving [itex]|A| < 2^{|\mathbb{N}|} \leq B[/itex].
     
  6. Mar 5, 2008 #5
    Your right. CH is required. Here's my attempt at a proof using transfinite induction, avoiding the use of integer indices for alephs (and not mentioning alephs at all):

    Let A={x_i|i in I}, where |I|=n. Well-order I. Let I_0 be the set of all elements of I such that the collection B(I_0) of all subsets of A (with cardinality less than |A|) with elements indexed by I_0 satisfies |B(I_0)|<=|A|. Suppose S_i is a subset of I_0, where S_i is the section of I less than i. Then the collection of new subsets created by introducing x_i is
    {K U {x_i}| K belongs to B(I_0)}
    which clearly has the same cardinality as B(I_0) (the obvious bijection being K<->K U {x_i}). So then we have
    |B(I_0 U {i})| <= |B(I_0)| + |B(I_0)| = |B(I_0)| <= |A|
    Thus a belongs to I_0 so by Transfinite Induction we have I_0 = I. Consequently |B|=|B(I)|<=|A|. Since |A|<= |B| is already true, then |B|=|A|. How's that? This proof does not rely on the aleph index of |A|.
     
    Last edited: Mar 6, 2008
  7. Mar 5, 2008 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There are enough problems with the presentation that I can't figure out what you're trying to do (e.g. your definition of I_0 is circular). Given that... nothing you've said is obviously inapplicable to computing the actual power set, so I suspect there's a serious error in there.
     
  8. Mar 5, 2008 #7
    What's a correct proof then?
     
    Last edited: Mar 5, 2008
  9. Mar 5, 2008 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Aha, I've finally dug up the information I need for a disproof.

    References:
    . The wikipedia article on cofinality.
    . The PlanetMath article on http://planetmath.org/encyclopedia/CardinalExponentiationUnderGCH.html [Broken]


    (I'm assuming the axiom of choice)

    Suppose that n is a singular cardinal, meaning cf(n) < n.

    Let C be a set with cardinality n
    Let D be a subset of C with cardinality cf(n)
    Let A = CxC.


    We have an injective map

    [tex]\varphi: C^D \to B[/tex]

    given by

    [tex]\varphi(f) = \left\{ \, (d, f(d)) \mid d \in D \, \right\}.[/tex]


    Therefore,

    [tex]|B| \geq \left| C^D \right| = |C|^{|D|} = n^{\mathrm{cf}(n)} > n = |A|.[/tex]




    However, if I further assume GCH, then I can prove the conjecture when n is a regular cardinal:

    [tex]
    |B| \leq \sum_{m < n} |A|^m = \sum_{m < n} n^m = \sum_{m < n} n
    = n \cdot n = n = |A|
    [/tex]


    (I'm not sure how essential choice and GCH are to these conclusions)



    The two main points in these calculations are:

    . The cardinality of the set of subsets of A of cardinality m should be n^m.
    . For m < n, when do we have n^m = n, and when do we have n^m > n?
     
    Last edited by a moderator: May 3, 2017
  10. Mar 5, 2008 #9
    This is true if m,n are any cardinal numbers? (n=|A|)
    Or is it just bounded by n^m?
     
    Last edited: Mar 5, 2008
  11. Mar 5, 2008 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, for infinite n.

    I think the trick I used in my disproof works to prove my conjecture: (and I hope you won't mind me being a little sloppy)

    Assume the axiom of choice.

    Let n be an infinite cardinal
    Let m be a cardinal less than or equal to n
    Let [itex]\mathcal{P}_m(S)[/itex] denote the set of subsets of n with cardinality m.

    There is an injective map [itex]n^m \to \mathcal{P}_m(m \times n)[/itex] that sends each function to its graph.

    There is an injective map [itex]\mathcal{P}_m(n) \to n^m[/itex] that sends each set to an enumeration.

    Therefore, [itex]n^m = |\mathcal{P}_m(n)|[/itex].

    Again, I don't know how essential the axiom of choice is in this theorem.
     
    Last edited: Mar 5, 2008
  12. Mar 5, 2008 #11
    So the assertion is true if |A| is a regular cardinal.

    I'm still trying to get a correct proof by transfinite induction. I'm following the recipe for transfinite induction: First I let Let A={x_i|i in I}, where |I| is a regular cardinal. In transfinite induction, we well-order I and let I_0 be a subset of I. We are supposed to show that if whenever the section s_i is a subset of I_0, then i is in I_0, then the principle of transfinite induction states that I_0 = I. Ok, so my I_0 definition in post #5 had circular problems. What should I define I_0 to be so that the conclusion I_0 = I would complete the proof?

    My original attempt:
    Let A={x_i|i in I}, where |I|=n. Well-order I. Let I_0 be the set of all elements of I such that the collection B(I_0) of all subsets of A (with cardinality less than |A|) with elements indexed by I_0 satisfies |B(I_0)|<=|A|. Suppose S_i is a subset of I_0, where S_i is the section of I less than i. Then the collection of new subsets created by introducing x_i is
    {K U {x_i}| K belongs to B(I_0)}
    which clearly has the same cardinality as B(I_0) (the obvious bijection being K<->K U {x_i}). So then we have
    |B(I_0 U {i})| <= |B(I_0)| + |B(I_0)| = |B(I_0)| <= |A|
    Thus a belongs to I_0 so by Transfinite Induction we have I_0 = I. Consequently |B|=|B(I)|<=|A|. Since |A|<= |B| is already true, then |B|=|A|.
     
    Last edited: Mar 6, 2008
  13. Mar 6, 2008 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It sounds like it would be hard to write a direct proof, since the conclusion of your proof has to be that |B|=|A| when |A| is regular, and |B|>|A| when |A| is singular. But then, I've never actually used cofinality before, so I don't know how easy or hard it is to use.


    Specific problems with the definition of I_0 you gave before was:
    (upon review, circular wasn't the right term)

    . As you stated it, indicated you were going to list the property that the elements of I_0 were going to satisfy, but instead gave a property that I_0 must satisfy.
    . So, I thought maybe you meant to define I_0 axiomatically... however, there is not a unique set satisfying the condition you gave.
    . So, I thought maybe you meant for I_0 to be the largest such set... but you have not demonstrated that there is a largest one!

    (e.g. Zorn's lemma doesn't immediately apply, because the condition |B(X)| < n describes an 'open' collection of sets. Given a chain of sets satisfying such a condition, their supremum might satisfy |B(sup X)| = n)

    Have you considered building I_0 via transfinite recursion, rather than trying to explicitly state it at the beginning of your proof?
     
    Last edited: Mar 6, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Set cardinality conjecture.
  1. Equal Cardinality (Replies: 11)

  2. Poincare conjecture (Replies: 5)

  3. A conjecture (Replies: 9)

Loading...