What is the Set Cardinality Conjecture?

[mathboy]

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?

 

[andytoh]

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.

 

[Hurkyl]

Thus by the Continuum Hypothesis, |B|< aleph(i+1)

How do you know |B| is less than aleph(i+1)?

 

[Hurkyl]

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

Suppose that \mathbb{N} \subseteq A and |\mathbb{N}| &lt; |A| &lt; 2^{|\mathbb{N}|}. Then \mathcal{P}(\mathbb{N}) \subset B, giving |A| &lt; 2^{|\mathbb{N}|} \leq B.

 

[andytoh]

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

 

[Hurkyl]

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.

 

[andytoh]

What's a correct proof then?

 

[Hurkyl]

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


(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

\varphi: C^D \to B

given by

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


Therefore,

|B| \geq \left| C^D \right| = |C|^{|D|} = n^{\mathrm{cf}(n)} &gt; n = |A|.




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

<br /> |B| \leq \sum_{m &lt; n} |A|^m = \sum_{m &lt; n} n^m = \sum_{m &lt; n} n <br /> = n \cdot n = n = |A|<br />


(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?

 

[mathboy]

The cardinality of the set of subsets of A of cardinality m should be n^m.

This is true if m,n are any cardinal numbers? (n=|A|)
Or is it just bounded by n^m?

 

[Hurkyl]

This is true if m,n are any cardinal numbers? (n=|A|)
Or is it just bounded by n^m?

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 \mathcal{P}_m(S) denote the set of subsets of n with cardinality m.

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

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

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

Again, I don't know how essential the axiom of choice is in this theorem.

 

[andytoh]

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

 

[Hurkyl]

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?