# Do there exist bijections between the following sets?

Let $A$ be an infinite set.

Do there exist bijections between the following sets?

1. $A$ and $A\setminus B$ where $B$ is a finite subset
2. $A$ and $A\times \{1, 2, \dots, n\}$
3. $A$ and $A\times A$
-
Yes to the three of them. What have you tried? Where are you stuck? –  DonAntonio Feb 3 '13 at 12:35
For $\mathbb{N}$ I know they hold because I can order $\mathbb{N}$. But for a general infinite set I tried to order it in some way and got stuck. –  Montez Feb 3 '13 at 12:38
@Montez Assume the Axiom of Choice, you can well-order to every set. –  tetori Feb 3 '13 at 12:40
I assume Cantor-Bernstein and/or cardinal arithmetic cannot be used? –  DonAntonio Feb 3 '13 at 12:53
I do know Cantor-Bernstein but do not know cardinal arithmetic. –  Montez Feb 3 '13 at 13:00

All the answers depend on your definitions of "infinite" and whether or not you assume the axiom of choice.

If your definition of infinite means "not finite" then all answers are positive assuming the axiom of choice, and all answers might be "no" if the axiom of choice fails.

However if we assume the axiom of choice the following holds:

1. Every infinite set has a countably infinite subset. Namely $A=A'\cup\{a_n\mid n\in\mathbb N\}$ where $A'$ is disjoint of the aforementioned sequence. If we removed $x_1,\ldots,x_n$ then by rearranging we may assume $x_i=a_i$ for all $i$, and then $$f(x)=\begin{cases} x& x\in A'\\a_{k+n} & x=a_k\end{cases}$$ is a bijection between $A$ and $A\setminus\{a_1,\ldots,a_n\}$.

2. This argument is slightly more difficult in the general case, so instead of proving this directly I will use the next part and deduce the following: $$|A|\leq|A\times\{0,\ldots,n\}|\leq|A\times A|=|A|$$ and therefore equality holds.

3. This is a non-trivial theorem whose proof is usually given by well-ordering the set $A$ and proving that every infinite well-ordered set has a bijection with its square. You can find the details here: About a paper of Zermelo

Of course even without any assumptions all the three claims are true for $\mathbb N$ and $\mathbb R$, and other well-behaved objects. In some introductory courses they omit the axiom of choice, and others do mention it. The axiom itself is not difficult, and it allows us to "tame" (to a certain degree) the behavior of infinite sets. If you are unfamiliar with it, don't worry. It will certainly come into action if you continue with mathematics.

-
1. Yes. The set $A\setminus B$ is infinite, hence there is an injective map $f\colon \mathbb N\to A\setminus B$. Also there is some bijection $g\colon \{1,\ldots,n\}\to B$. Define \begin{align}h\colon A\setminus B &\to A\\x&\mapsto\begin{cases} g(k)&\text{if }x=f(k), k\le n\\f(k-n)&\text{if }x=f(k), k>n\\x&\text{otherwise.}\end{cases}\end{align}
-