# Cardinality of infinite sets and bijections

I have the following exersice:

Let $A$ be a set and $f: A \to \mathbb N$ a bijective function. Show that a set $B\subset A, B\neq A$ and a bijective function $g: A\to B$ exists.

Solution:

Let $A$ be any set and $F: A\to\mathbb N$ a bijective function.

Claim: $\exists B \subset A, B\neq A$ s.t. $\exists g: B\to A$ which is bijective.

Proof: Let $A$ be an arbritary set and $f$ as above. We define $B$ to be the set that contains every second element of $A$. Since $f$ is a bijection, we have $|A|=|B|=|\mathbb N|=\infty$ (1)

let now $g$ be a function from $B$ to $A$: $g:B\to A$

Since $|A|=|B|$ it follows, that $g$ is bijective.

q.e.d

Does my proof hold like that? E.g. I'm not sure if $A$ could be the empty set.

• What do you mean by “every second element of $A$”? Suppose that $A=\mathbb Q$. What is $B$ then? – José Carlos Santos Jan 17 '18 at 16:26
• $A$ can't be empty since it has the same cardinality as $\mathbb{N}$. I haven't read the rest of your question. – Ethan Bolker Jan 17 '18 at 16:27
• What is $\infty$? – Asaf Karagila Jan 17 '18 at 16:29
• $|B| = |A|$ does not imply that $g$ is bijective. For example, take $A = \mathbb{Q}$ and $B = \mathbb{N}$. We know $|A| = |B|$ but if we let $g(x) = 1$ for any $x$ in $\mathbb{Q}$ this is a function from $A$ to $B$ but it certainly not a bijection. – Sean Haight Jan 17 '18 at 16:29
• Thanks to everyone, solved. – xotix Jan 17 '18 at 16:46

Wow! the OP make the comment -

Thanks to everyone, solved.

Regardless, I suspect the OP will find the following answer of interest.

Define $B$ to be $f^{-1}[2\mathbb N]$. Define the mapping $g$ on $B$ by

$\tag 1 b \mapsto \frac{f(b)}{2}$

Exercise: Show that $g$ is a bijective mapping of $B$ with $\mathbb N$.

The general idea is good, but some details still need to be fleshed out.

First, what is "every second element of $A$"? The elements of $A$ aren't given an order, so we can't refer to "every second element." Of course, you could use the order induced by the bijection to $\mathbb{N}$ (and I assume this is what you had in mind), but this should be spelled out.

Finally, you let $g: B \to A$ but don't give any other information about $g$. If $g$ is arbitrary, $g$ need not be a bijection; it could be a constant map to a single element of $A$. Better to try to construct $g$ explicitly, using the bijections you already have.