Let $\text{SCB}^{\text{op}}$ be the statement that given surjective functions $X\to Y$ and $Y\to X$, we have $X\sim Y$.

(a) Let $X$ be an infinite set. Let $A$ be the set of all (not just nonempty) finite strings of elements of $X$ in which each element appears only once. Let $B=A\cup\{*\}$, where $*\notin A$. Show that there are surjective functions $A\to B$ and $B\to A$.

(b) Let $A$ and $B$ be as in a). Suppose $A\sim B$. Show that there is a 1-1 function $\mathbb{N}\to A$.

(c) For $A,X$ as in a) and a 1-1 function $\mathbb{N}\to A$, show that there is a 1-1 function $\mathbb{N}\to X$.

(d) Show that $\text{SCB}^{\text{op}}$ implies the statement 'if $X$ is an infinite set, then there is an injective function $\mathbb{N}\to X$'.

My attempt:

(a) We have $A = \{ (x_1,\dots,x_n)\mid n\in\mathbb{N}^*, x_i\in X, \forall i,j\le n(i\ne j\Rightarrow x_i\ne x_j)\}\cup\{ (\emptyset)\}$. Now define $f:A\to B$ as $f((\emptyset)) = *, f((x_j)) = \emptyset$ and $f((x_1,\dots,x_{n+1})) = (x_1,\dots,x_n)$. Then, $f$ is surjective, because $X$ is infinite (therefore we will always be able to extend $(x_1,\dots,x_n)\in A$ with an element $x_{n+1}\ne x_i, \forall i\le n$). Now, let $g:B\to A$ with $g(b) = b$ if $b\in A$ and $g(*)=\emptyset$.

(b) I really need some help here. I believe we're just looking for an injection (1-1 function?). I think that the function $g:\mathbb{N}\to A: n \mapsto (x_1,\dots,x_n)$ suffices then, where $x_j\in X$ are arbitrary but all different from each other (since we end up in $A$). I haven't used $A\sim B$ so I'm not sure if this is OK.

(c) Suppose $f:\mathbb{N}\to A$ one-to-one given. Consider $h: A\to X: (x_1)\mapsto x_1$, this is one-to-one, so $h\circ f$ is the function we're looking for.

(d) Let $X$ be an infinite set. Consider $A,B$ as in a). Then by $\text{SCB}^{\text{op}}$ we have $A\sim B$. By b) there is an injection from $\mathbb{N}$ to $A$, and the statement then follows from c).


1 Answer 1


Fix a bijection $b\colon B\to A$, a then define $g(n)=b^{(n+1)}(*)$. Namely, start from $*$, and keep moving, since $b$ is a bijection and it never goes back to $*$, you can show by induction that this is injective.

Your step in (c) is not correct. Maybe $f$ doesn't hit any one-point sequences? Instead, you need to use the fact that the sequences in $A$ are injective (i.e. every $x\in X$ appears at most once). Simply note that if $a_n$ are countably many distinct sequences in $A$, then for every $n$, there is some $m$ such that $a_m$ has some $x$ appearing in it such that $x$ is not in $a_k$ for all $k<n$. Read that again, slowly, it will be fine.

  • $\begingroup$ Thanks! I think your reasoning for (c) assumes that each element of $X$ appears at most once, looking over all sequences of $A$. Meaning, that once $x\in X$ appeared in some sequence, it cannot appear in another one. I think however that $A$ contains finite strings where each sequence has the property that each $x\in X$ appears at most once. So, $x$ can appear in sequence $a_1$, but also in another, $a_5$ for example, as long as it appears only once within these sequences. $\endgroup$
    – MyWorld
    Commented May 20, 2021 at 17:51
  • $\begingroup$ No, that's not what I mean. I know the exercise and the proof very well. $\endgroup$
    – Asaf Karagila
    Commented May 20, 2021 at 21:36
  • $\begingroup$ Just to make sure: the injection would be $n\mapsto (m,x) \in\mathbb{N}\times X$ then, right? ($\mathbb{N}\times X \sim X$, because $X$ is infinite). $\endgroup$
    – MyWorld
    Commented Jun 17, 2021 at 13:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .