# Opposite Schröder-Cantor-Bernstein to show that there is an injection from $\mathbb{N}$ to any infinite set $X$.

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).

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. Read that again, slowly, it will be fine.
• 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. Commented May 20, 2021 at 17:51
• 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). Commented Jun 17, 2021 at 13:12