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.


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.


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

  • 2
    $\begingroup$ What do you mean by “every second element of $A$”? Suppose that $A=\mathbb Q$. What is $B$ then? $\endgroup$ – José Carlos Santos Jan 17 '18 at 16:26
  • $\begingroup$ $A$ can't be empty since it has the same cardinality as $\mathbb{N}$. I haven't read the rest of your question. $\endgroup$ – Ethan Bolker Jan 17 '18 at 16:27
  • $\begingroup$ What is $\infty$? $\endgroup$ – Asaf Karagila Jan 17 '18 at 16:29
  • $\begingroup$ $|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. $\endgroup$ – Sean Haight Jan 17 '18 at 16:29
  • $\begingroup$ Thanks to everyone, solved. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.