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 have problem to solve:

Let $a,b$ and $c$ be cardinal numbers. Prove that $a+b=b$, $b \le c$ implies $a+c=c$.

And trying to prove this I got couple questions:

  1. For infinite cardinal $c$, is $c+c=c$ always? And how to prove it? (Is $c \cdot c=c$?)
  2. From $a+b=b$ can I conclude that $a \le b$ since $a \ge b$ and 1. will imply $a+b=a$? I know that statement that every two cardinals are comparable leads to AC (we can use it when solving problems)

(I apologize if my questions are too simple, I tried to google it, but Google is not math-friendly tonight for me =D)

P.S. Is there solution without using AC?

share|improve this question
    
To make it clear: you are in fact allowed to use the Axiom of Choice? (1) is implied by AC but won't always hold when Choice doesn't hold. –  Steven Stadnicki Jun 18 '13 at 20:48
    
(And if you are allowed to use Choice, try writing $a+b+c$ in two different ways using associativity...) –  Steven Stadnicki Jun 18 '13 at 20:49
    
@StevenStadnicki Note that the question says "cardinal numbers", i.e. alephs. For those, no choice is needed. –  Lord_Farin Jun 18 '13 at 20:49
    
I am allowed to use Axiom of Choice. But I still don't see how that will help in proving 1.? –  Meow Jun 18 '13 at 20:50

3 Answers 3

up vote 3 down vote accepted

Since $b\le c$, then there is a $d$ such that $c=b+d$. Then $$a+c=a+(b+d)=(a+b)+d=b+d=c.$$ Note that this proof does not use the axiom of choice.

If you assume the axiom of choice, then $c+c=c$ for all infinite cardinals $c$. Without choice, it is consistent that this fails in general (see the comments here), though of course it holds in particular cases (for any well-ordered $c$, or for $c=\mathfrak c:=|\mathbb R|$, for example).

That $c\cdot c=c$ for all infinite $c$ is equivalent to choice. To prove that choice gives us this, it suffices to argue that $c\cdot c=c$ whenever $c$ is well-orderable. Typically, one uses some kind of pairing function to achieve this. See for example here. The point is that pairing functions give us explicit bijections between $\kappa\times \kappa$ and $\kappa$ for any infinite well-ordered cardinal $\kappa$. Since $\kappa\le\kappa+\kappa\le \kappa\cdot \kappa$, it follows from this that $\kappa+\kappa=\kappa$ as well.

To see that $c\cdot c=c$ for all infinite $c$ gives us choice, see here.

And yes, if $a+b=b$, then $a\le b$. On the other hand, without assuming choice, just knowing that $a\le b$ does not suffice to conclude that $a+b=b$. For example, if $b$ is infinite and Dedekind finite, then $1<b<b+1$.

share|improve this answer

First let me answer your two questions:

  1. If $c$ is infinite, assuming the axiom of choice, it is possible to show that $c+c=c\cdot c=c$. This is true, without the axiom of choice, for $\aleph$ cardinals. In the presence of choice all cardinals are $\aleph$ cardinals so it is simply true for all sets.

    However without the axiom of choice it is consistent that $c+c=c$ for all cardinals, and the axiom of countable choice fails (this is the Ph.D. work of Sageev). On the other hand, if $c\cdot c=c$ for every infinite cardinal then the axiom of choice holds. That is a theorem of Tarski.

  2. Note that for every cardinals $a,b$ we have $a\leq a+b$. In particular if $a+b=b$ then $a\leq b$. This does not require the axiom of choice at all. This is simply true because we can compose the obvious injection from $a$ into $a+b$ with the bijection of $a+b$ and $b$.

Lastly, there is a solution for the general question which does not use the axiom of choice. This is because if $b\leq c$ then we can write $c=b+x$ for some $x$, regardless to its size, then we have $$a+c=a+b+x=b+x=c.$$

share|improve this answer

You asked how to prove (1). Assuming the axiom of choice, every cardinal is an aleph.

Let $\kappa=\aleph_\gamma$ for some $\gamma$. To prove that $\kappa+\kappa=\kappa$, note that every ordinal $\alpha$ can be written uniquely in the form $\alpha=\eta+n$, where $\eta$ is $0$ or a limit ordinal, and $n\in\omega$. Say that $\alpha$ is even if $n$ is even and odd if $n$ is odd. Let $K_0=\{\alpha\in\kappa:\alpha\text{ is even}\}$ and $K_1=\{\alpha\in\kappa:\alpha\text{ is odd}\}$. Then

$$\varphi_0:\kappa\to K_0:\alpha=\eta+n\mapsto\eta+2n$$

and

$$\varphi_1:\kappa\to K_0:\alpha=\eta+n\mapsto\eta+2n+1$$

are bijections, and $\kappa=K_0\sqcup K_1$, so

$$\varphi:2\times\kappa\to\kappa:\langle k,\alpha\rangle\mapsto\varphi_k(\alpha)$$

is a bijection from $2\times\kappa$ onto $\kappa$.

share|improve this answer

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.