Let $A \subset \mathbb{R}.$

Assume :

$(\star )$ Let A be an infinite set.

Let $f$ be a surjective function $f: \mathbb{N} \rightarrow A.$

The problem:

Show: There exists a bijective function $g: \mathbb{N} \rightarrow A.$

Latest attempt:

Let $A=${$a_1,a_2,a_3, .......$} , $n \in \mathbb{N}.$

Elements of $A$ may appear more than once, I.e. for some $m \not= n$ we have $a_n=a_m.$

Hence there is a subset of $T$ of $N$ such that

$T \sim A,$ i.e.

there is a bijection $g:T \rightarrow A.$

$T$ being a subset of $N$ implies $T$ is countable, i.e there is a bijection $h$:

$h: N \rightarrow T.$

The composition

$F: N\rightarrow A$ defined by

$F= g\circ h$ is a bijection , and we are done.

Note: Used elements of Rudin, Principles , 3rd Edition,Theorem 2.12

Cf. On countable sets

Note: $(\star)$ was not assumed (forgot) in the original version of the problem, hence the answer by Almagast.

  • 4
    $\begingroup$ This can't be true. The assumption implies that $A$ is countable and what you want to prove would imply that it is not. $\endgroup$ – Arnaud Mortier Feb 20 '18 at 10:30
  • 3
    $\begingroup$ Take $A=\{0\}$ if you are not convinced. $\endgroup$ – Arnaud Mortier Feb 20 '18 at 10:32
  • 2
    $\begingroup$ Existence of $f$ says $|A| \leq \aleph_0$. Existence of $g$ says $|A| = \mathfrak{c}$. But $\mathfrak{c}>\aleph_0$, contradiction. $\endgroup$ – Ivo Terek Feb 20 '18 at 10:32
  • $\begingroup$ Mortier.Thanks, The only thing I try is to weed out the multiples to construct a injective fct. $\endgroup$ – Peter Szilas Feb 20 '18 at 10:34
  • $\begingroup$ Sorry. A typo, N!! $\endgroup$ – Peter Szilas Feb 20 '18 at 10:35

The result is false. Take $A=\{1\}$. There is a surjective function $f:\mathbb{N}\to A$ namely $f(n)=1$ for all $n$, but no bijection.

  • $\begingroup$ Almagest.Thank you.Let A be a countably infinite set.The idea here is that the OP defines 'countable ' by f: N \rightarrow A , f surjective, and claims it is easy to see that a bijection exists. I had this in mind in my not very elegant attempt. But forget to specify A.Thanks.+1. $\endgroup$ – Peter Szilas Feb 20 '18 at 16:01
  • $\begingroup$ @PeterSzilas But it is still hard to rescue this question. If you specify that $A$ is a countably infinite set, then you are specifying that there is a bijection between $A$ and $\mathbb{N}$ and there is nothing to prove. If you specify that there is an injection $g$ from $N$ to $A$ and a surjection $f$ from $N$ to $A$, then you are effectively asking for a special case of the Schroder Bernstein theorem. $\endgroup$ – almagest Feb 20 '18 at 17:26
  • $\begingroup$ Almagast. Thank you for your interest.The question is taken from a comment in Foster Analysis. Foster calls a set A(not empty) countable if there is a surjective mapping from N to A., I.e. there is a sequence (x_n) such that A = { x_n, n in N}.Means we could have for some indexes x_n=x_m, n not=m. Now in a note he says one can, for a countable set , find a bijective mapping N to A.Given a surjective mapping f (questions) , I tried clumsily to get rid of the elements x_k=x_i= ., k not =i ,and find a injective mapping g N to A .But cannot easily define an bijective g, given a injective f . $\endgroup$ – Peter Szilas Feb 20 '18 at 17:55
  • $\begingroup$ That is because Schroder Bernstein is quite hard to prove. It sounds absolutely obvious, but not many people manage to prove it without seeing a proof first! $\endgroup$ – almagest Feb 20 '18 at 18:10
  • $\begingroup$ Almagast. Appreciate your support.Thanks for your comments.Greetings, Peter $\endgroup$ – Peter Szilas Feb 20 '18 at 18:17

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.