Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm currently reading a little deeper into the Axiom of Choice, and I'm pleasantly surprised to find it makes the arithmetic of infinite cardinals seem easy. With AC follows the Absorption Law of Cardinal Arithmetic, which states that for $\kappa$ and $\lambda$ cardinal numbers, the larger infinite and the smaller nonzero, then $\kappa+\lambda=\kappa\cdot\lambda=\max(\kappa,\lambda)$.

I was playing around with the equation $k+\aleph_0=\mathfrak{c}$ for some cardinal $k$. From the above, it follows that $\mathfrak{c}=k+\aleph_0=\max(k,\aleph_0)$, which implies $k=\mathfrak{c}$.

I'm curious, can we still show $k=\mathfrak{c}$ without the Axiom of Choice? Is it maybe possible to bound $\mathfrak{c}-\aleph_0$ above and below by $\mathfrak{c}$? But then I'm not quite sure such algebraic manipulations even mean anything, or work like that here. Certainly normal arithmetic does not! Thanks.

share|improve this question

4 Answers 4

up vote 11 down vote accepted

There is a general argument without choice: Suppose ${\mathfrak m}+{\mathfrak m}={\mathfrak m}$, and ${\mathfrak m}+{\mathfrak n}=2^{\mathfrak m}$. Then ${\mathfrak n}=2^{\mathfrak m}$. This gives the result.

The argument is part of a nice result of Specker showing that if CH holds for both a cardinal ${\mathfrak m}$ and its power set $2^{\mathfrak m}$, then $2^{\mathfrak m}$ is well-orderable. This shows that GCH implies choice, and that the proof is "local". It is still open whether CH for ${\mathfrak m}$ implies that ${\mathfrak m}$ is well-orderable.

Anyway, here is the proof of the statement above: Note first that $2^{\mathfrak m}\cdot 2^{\mathfrak m}=2^{{\mathfrak m}+{\mathfrak m}}=2^{\mathfrak m}={\mathfrak m}+{\mathfrak n}$.

Let $X$ and $Y$ be disjoint sets with $|X|={\mathfrak m}$, $|Y|={\mathfrak n}$, and fix a bijection $f:{\mathcal P}(X)\times{\mathcal P}(X)\to X\cup Y$.

Note that there must be an $A\subseteq X$ such that the preimage $f^{-1}(X)$ misses the fiber $\{A\}\times {\mathcal P}(X)$. Otherwise, the map that to $a\in X$ assigns the unique $A\subseteq X$ such that $f^{-1}(a)$ is in $\{A\}\times {\mathcal P}(X)$ is onto, against Cantor's theorem.

But then, for any such $A$, letting $g(B)=f(A,B)$ gives us an injection of ${\mathcal P}(X)$ into $Y$, i.e., $2^{\mathfrak m}\le {\mathfrak n}$. Since the reverse inclusion also holds, we are done by Schroeder-Bernstein.

(Note the similarity to Apostolos's and Joriki's answers.)

The original reference for Specker's result is Ernst Specker, "Verallgemeinerte Kontinuumshypothese und Auswahlaxiom", Archiv der Mathematik 5 (1954), 332–337. A modern presentation is in Akihiro Kanamori, David Pincus, "Does GCH imply AC locally?", in "Paul Erdős and his mathematics, II (Budapest, 1999)", Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413–426.

Note that assuming that ${\mathfrak m}$ is infinite is not enough for the result. For example, it is consistent that there are infinite Dedekind finite sets $X$ such that ${\mathcal P}(X)$ is also Dedekind finite. To be Dedekind finite means that any proper subset is strictly smaller. But if $2^{\mathfrak m}$ is Dedekind finite and $2^{\mathfrak m}={\mathfrak n}+{\mathfrak l}$ for nonzero cardinals ${\mathfrak n},{\mathfrak l}$, then we must have ${\mathfrak n},{\mathfrak l}<2^{\mathfrak m}$.

share|improve this answer
    
Hi yunone. Yes, exactly. The Kanamori-Pincus paper is available at Kanamori's website, by the way, in case you want to take a look. It is nicely written and there are some interesting questions there. –  Andres Caicedo Apr 1 '11 at 22:47

Given a set $K$ with $\lvert K \rvert=k$ and a bijection $f:\mathbb{R}\to K\cup \mathbb{N}$ (assuming without loss of generality that $K$ is disjoint from $\mathbb{N}$), pick some $x\in\mathbb{R}$ such that $f$ maps no element of $x+\mathbb{N}\subset\mathbb{R}$ to $\mathbb{N}$ (this is just one choice and it's possible since only countably many elements are mapped to $\mathbb{N}$), and define a bijection $g:\mathbb{R}\to K$ by mapping $f^{-1}(\mathbb{N})$ to $f(x+2\mathbb{N})$, mapping $x+\mathbb{N}$ to $f(x+1+2\mathbb{N})$, and mapping $\mathbb{R}\setminus\left((x+\mathbb{N})\cup f^{-1}(\mathbb{N})\right)$ as in $f$. This bijection establishes without choice that $k=\lvert K \rvert=\lvert\mathbb{R}\rvert=\mathfrak{c}$.

share|improve this answer
    
Good answer. I think this can be generalized slightly to have that $|a|+|x| = |P(x)|$ then $|a|=|P(x)|$ under certain conditions (such that $x$ can be split into two disjoint sets of same cardinality as $x$, for example). –  Asaf Karagila Apr 1 '11 at 8:22
    
A beautiful answer always inspires people. –  awllower Apr 1 '11 at 15:35
    
Thanks joriki, much appreciated as always. –  yunone Apr 1 '11 at 20:24

There's another way apart from joriki's answer that I think is a bit easier and is usually considered the "standard" way to show what you are asking:

First of all we have that $\mathfrak{c}\times\mathfrak{c}=\mathfrak{c}$. To see this using subsets of natural numbers (for example) observe that given $X,Y\in\mathcal{P}(\omega)$ the function $(X,Y)\mapsto\{2n : n\in X\}\cup\{ 2n+1 : n\in Y\}$ is an injection.

Thus we need to show that given a countable set $X\subset\mathbb{R}\times\mathbb{R}$ we have that $|\mathbb{R}\times\mathbb{R}\setminus X|=\mathfrak{c}$. Take the projection of $X$, $\pi(X)$. $\pi(X)$ is at most countable. This doesn't use the axiom of choice since $X$ is well orderable (because it's countable). Therefore, there exists $x\in\mathbb{R}$ such that $x\notin\pi(X)$. Then the set $\{x\}\times\mathbb{R}$ (that has cardinality $\mathfrak{c}$) is disjoint from $X$ and thus a subset of $\mathbb{R}\times\mathbb{R}\setminus X$. Apply Cantor-Bernstein theorem and you are done.

share|improve this answer
    
Thank you Apostolos for this other look at it. –  yunone Apr 1 '11 at 20:26

I think that without AC you can show that $a\ge\aleph_0$ implies $\aleph_0+a = a$.

First, you can find a bijection $f$ between $\mathbb N\times\{1\}\cup\mathbb N\times\{2\}$ and $\mathbb N$. (You can write down an explicit formula for it, no choice needed.)

Now, you assume that there is an injection $g: \mathbb N \to A$, where $|A|=a$.

Then you can define $h: \mathbb N\times\{1\}\cup A\times\{2\} \to A$ by

$h(n,1)=g(f(n,1))$

$h(g(n),2)=g(f(n,2))$

$h(x,2)=x$ if $x\in A \setminus g[\mathbb N]$.

EDIT: The basic idea is just that if you have a bijective copy of the set $\mathbb N$ in the set $A$, you can make two copies of $\mathbb N$ from it. I just tried to write it down formally, so that we can check whether AC is used somewhere.

EDIT: As Apostolos correctly pointed out, this does not answer the original question yet. (I kind of misread the question.) It remains to show that $k+\aleph_0=\mathfrak c$ $\Rightarrow$ $\aleph_0\le k$. This can be down similarly as in joriki's answer - which show that it is much more elegant (more to the point) than my attempt.

share|improve this answer
1  
I think in the first line you mean $\aleph_0+a=a$? –  joriki Apr 1 '11 at 7:59
    
@joriki Thanks, I've corrected the typo. –  Martin Sleziak Apr 1 '11 at 8:03
1  
And in the third and second lines from the end, I think you mean $f(n,1)$ and $f(n,2)$, respectively? –  joriki Apr 1 '11 at 8:04
2  
Martin there is a simple way of doing that, if $|a|\ge\aleph_0$ then you can find a copy of the natural numbers there, move it within itself to be only on the even numbers, and copy the additional countable set over the odd numbers of the original copy. –  Asaf Karagila Apr 1 '11 at 8:17
1  
I don't think this answers the question at hand though. –  Apostolos Apr 1 '11 at 11:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.