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.

Problem statement:

Let A be an uncountable set, B a countable subset of A, and C the complement of B in A. Prove that there exists a one-to-one correspondence between A and C.

My thoughts:

There's a bijection between A and A (the identity function). There's a bijection between C and C (the identity function). There's a bijection between B and $\mathbb{N}$. That's all I know.

share|improve this question
    
I take it you don't have cardinal arithmetic on hand yet? –  Arturo Magidin Mar 6 '11 at 3:07
    
Cardinal numbers are in the next chapter, so I guess not. This chapter proves that a countable union of countable sets is countable, $\mathbb{N}$ is countable, $\mathbb{Q}$ is countable, the algebraic numbers are countable, and $\mathbb{R}$ is not countable. –  Matt Gregory Mar 6 '11 at 3:08

1 Answer 1

up vote 6 down vote accepted

Since $A\setminus B$ is uncountable, assuming countable choice it has a countably infinite subset $B'$. Then $B'\cup B$ is countable, so there is a bijection $g:B'\cup B\to B'$. Define $f:A\to A\setminus B$ by $f\vert_{B'\cup B}=g$ and $f(a)=a$ for $a\in A\setminus(B'\cup B)$.

Basically, you just take chunks off of $A$ and $A\setminus B$ that have equal size, respectively $B'\cup B$ and $B'$, leaving the remaining sets equal to $A\setminus(B'\cup B)$, then piece together the two bijections.

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.