Intereting Posts

How to evaluate $\int_{0}^{+\infty}\exp(-ax^2-\frac b{x^2})\,dx$ for $a,b>0$
Method of dominant balance and perturbation
All roots of the quartic equation $a x^4 + b x^3 + x^2 + x + 1 = 0$ cannot be real
Normal Intersection of Parabola
What are the sub-sets of a null set?
How to find the maximum and minimum value of $2^{\sin x}+2^{\cos x}$
irreducibility of a polynomial in several variables over ANY field
Quotient of $\textrm{GL}(2,\textbf{R})$ by the conjugate action of $\textrm{SO}(2,\textbf{R})$
Showing that $\mathbb{R}$ and $\mathbb{R}\backslash\mathbb{Q}$ are equinumerous using Cantor-Bernstein
What are the epimorphisms in the category of Hausdorff spaces?
How to properly use technology for back-of-the-envelope calculations?
Prove triangle inequality using the properties of absolute value
Mystified by Rotman's proof of normality of index-2 subgroups
Number of permutations with a given partition of cycle sizes
Prove that these two fields are isomorphic.

In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I’ve tried to fill in all the details below. Could someone tell me if what I wrote below is valid?

Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: \mathbb{N} \rightarrow T$. And $S \subseteq T = \{ f(n) \ | \ n \in \mathbb{N} \}$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) \in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) \in S$. And because $S$ is infinite, we continue forever. Now consider the function $\beta : \mathbb{N} \rightarrow S$ which sends $k \rightarrow f(n_{k})$.

So in order for $S$ to be countable, $\beta$ would have to be a bijection. $\beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.

- Cardinality of equivalence relations in $\mathbb{N}$
- What's the difference between saying that there is no cardinal between $\aleph_0$ and $\aleph_1$ as opposed to saying that…
- What is the cardinality of the set of all sequences in $\mathbb{R}$ converging to a real number?
- Cardinality of a Hamel basis of $\ell_1(\mathbb{R})$
- Cardinality of the set of all (real) discontinuous functions
- Is there an easy proof for ${\aleph_\omega} ^ {\aleph_1} = {2}^{\aleph_1}\cdot{\aleph_\omega}^{\aleph_0}$?

**Edit:** $\beta$ also needs to be surjective. So for every $r \in S$ there exists a $q \in \mathbb{N}$ such that $\beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) \in \{n_{1}, n_{2}, …, n_{k} … \}$, so we can let $f^{-1}(r) = n_{d}$. Thus $\beta(d) = f(n_{d}) = r$.

- Closing a subcategory under finite colimits by transfinite induction
- Looking for a problem where one could use a cardinality argument to find a solution.
- How to prove cardinality equality ($\mathfrak c^\mathfrak c=2^\mathfrak c$)
- Proving that these two sets are denumerable.
- Does same cardinality imply a bijection?
- Strange set notation (a set as a power of 2)?
- There exists no injective function from the power set of A to A
- Prove that the union of two disjoint countable sets is countable
- Do you need the Axiom of Choice to accept Cantor's Diagonal Proof?
- Order preserving bijection from $\mathbb{Q}$ to $\mathbb{Q}\backslash\lbrace{0}\rbrace$

To fix the last statement:

Suppose that $q=f^{-1}(r)$. Then $\{ 0,1,2,\dots,q\}$ is a finite set. Intersect this with $f^{-1}(S) = \{ n \in \mathbb{N} \;|\; f(n) \in S\}$ and get a finite set. By your definition of the $n_k$’s this set is $\{n_0,n_1,\dots,n_\ell\}$ for some $\ell$. Thus $q=n_\ell$. Therefore, $\beta(\ell)=f(n_\ell)=f(q)=r$. Patched.

The set $A$ is countable if there is $f:A\to\mathbb N$ which is injective.

Suppose $B\subseteq A$ then $f|_B:B\to\mathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.

Suppose that $f:A\to\mathbb N$ is a bijection and $B\subseteq A$ is infinite. Let $N=\{f(b)\mid b\in B\}$, the image of $B$.

Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $\mathbb N$ is countable:

We define inductively a function $g:\mathbb N\to N$, $g(0)=\min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.

It is obvious that $g$ is a bijection between $\mathbb N$ and $N$. Now we have that $g^{-1}\circ f|_B:B\to\mathbb N$ is a bijection, as wanted.

- Proof of “continuity from above” and “continuity from below” from the axioms of probability
- Let $f:\rightarrow \mathbb{R} $ be differentiable with $f'(a) = f'(b)$. There exist a $c\in(a,b)$ such that $f'(c) = \frac{f(c) – f(a) }{c -a}$.
- Is there a way to find all roots of a polynomial equation?
- Rainwater theorem, convergence of nets, initial topology
- Intuitive explanation of Residue theorem in Complex Analysis
- What is the new probability density function by generating a random number by taking the reciprocal of a uniformly random number between 0 and 1?
- Infinite Cartesian product of countable sets is uncountable
- Epigraph of closed convex hull of a function
- Find all natural numbers $n$ such that $21n^2-20$ is a perfect square.
- A question about the relationship between submodule and ideal
- Real Analysis Convergence question
- Proof of another Hatcher exercise: homotopy equivalence induces bijection
- How do the separation axioms follow from the replacement axioms?
- How to show that $\frac{1}{\tan(x/2)}=2 \sum_{j=1}^{\infty}\sin(jx)$ in Cesàro way/sense?
- Looking for a Calculus Textbook