Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given info: $|A|=\mathfrak{c}$ , $|B|=\aleph_0$ in ZF (no axiom of choice).

Prove: $|A\cup B|=\mathfrak{c}$

If $B \subset A\implies|A \backslash B|=\mathfrak{c}$?

I have found several places proving that for $|\mathbb{R} \backslash \mathbb{Q}|,$ but none of the solutions appears to work for arbitrary sets. Maybe one should prove it for $|\mathbb{R} \backslash \mathbb{Q}|$ and then show that it will work for arbitrary $A$ and $B$ as well?

Here Showing that $\mathbb{R}$ and $\mathbb{R}\backslash\mathbb{Q}$ are equinumerous using Cantor-Bernstein David has a very nice idea (constructing bijection), but it requires that infinite set has countably infinite subset, which again!? needs some choice axiom.

In some sources I even saw statements that these can't be proved in ZF.

From what my teacher said I percieved that solution has something to do with Cantor–Bernstein theorem and that knowing how to prove $\mathfrak{c}+\mathfrak{c}=\mathfrak{c}$ would help as well.


share|cite|improve this question
If you know how to prove that $\mathfrak{c}+\mathfrak{c}=\mathfrak{c}$ then you can get the rest of the way by C-B: you can provide a very explicit (indeed, nearly trivial) inclusion of $\omega$ into $\mathfrak{c}=2^\omega$. Just combine this with your result on $\mathfrak{c}+\mathfrak{c}$ to get $A\cup B$ as a subset of something of size $\mathfrak{c}$... – Steven Stadnicki Mar 4 '13 at 21:37
this is a possible duplicate of this question. – robjohn Mar 4 '13 at 22:12

Prove it first for disjoint $A$ and $B$, relaxing the condition on $B$ to $|B|\le \aleph_0$. You then recover the full statement by considering $A\cup B = A\cup(B\setminus A)$.

You can restrict your attention even further to, say $A=(0,1)$ and $B$ being a subset of the integers. Once you have proved it for that case, the definition of "same cardinality" guarantees that it will be true for every other choice of disjoint $A$ and $B$ of the appropriate cardinalities.

It is true without any choice axiom that a set of size continuum has a countably infinite subset. By definition, because it has size continuum, there's a bijection from $\mathbb R$, and the image of $\mathbb N$ under that bijection is a countably infinite subset.

share|cite|improve this answer
It wasn't said that the set is of size continuum, what is known is that it is infinite and uncountable. Here… it is stated one can't prove it without AC. – Karlis Olte Mar 5 '13 at 7:02
@user64985: You wrote $|A|=\mathfrak{c}$¸ which means not only that it is uncountable, but specifically that it has size continuum. – Henning Makholm Mar 5 '13 at 9:01
Yes, but i never said I am referring to set $A$, (it is $A\backslash B$ for which the stated result is used.) – Karlis Olte Mar 25 '13 at 6:51

Note that if $A$ has cardinality $\frak c$ then $A$ has a countably infinite subset. This does not require the axiom of choice. $|\mathcal P(\Bbb N)|=\frak c$ and $|X|<|\mathcal P(X)|$.

As for the suggestion to use the fact $\frak c+\frak c=\frak c$, this is again helpful because you can replace $B$ with its power set and you have: $$\mathfrak c=|A|\leq |A|+|B|\leq |A|+|\mathcal P(B)|=\frak c+c=c.$$

share|cite|improve this answer

By assumption, there exist bijections $a\colon A\to \mathbb R $ and $b\colon B\to\mathbb N_0$. We can define the injective map $b'\colon B\setminus A\to\mathbb N_0$, $x\mapsto\lvert\{y\in B\setminus A\mid b(y)<b(x)\}\rvert$. If $b'$ is a bijection, we can define $c\colon A\cup B\to\mathbb R$ by $$c(x)=\begin{cases}a(x)&\text{if }x\in A\text{ and }a(x)\notin\mathbb N_0,\\ 2a(x)&\text{if }x\in A\text{ and }a(x)\in\mathbb N_0,\\ 2b'(x)+1&\text{if }x\in B\setminus A.\end{cases} $$ If on the other hand $b'$ is not a bijection, let $N=\min(\mathbb N\setminus b'(B\setminus A))$. Then clearly $b'(A\setminus B)= \{k\in\mathbb N_0\mid k<N\}$ and $b'$ is a bijection with this set so that we can define $c\colon A\cup B\to\mathbb R$ by $$c(x)=\begin{cases}a(x)&\text{if }x\in A\text{ and }a(x)\notin\mathbb N_0,\\ a(x)+N&\text{if }x\in A\text{ and }a(x)\in\mathbb N_0,\\ b'(x)&\text{if }x\in B\setminus A.\end{cases} $$ In both cases, $c$ is readily seen to be a bijection.

share|cite|improve this answer

Your Answer


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.