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 cardinal exponentiation


    (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: Mar 5, 2008
  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

Have something to add?



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

  2. Poincare conjecture (Replies: 5)

  3. A conjecture (Replies: 9)

Loading...