Intereting Posts

$\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges or diverges?
Restriction of vector field tangent to sphere
Is an infinite line the same thing as an infinite circle?
Prove that $AB=BA=0$ for two idempotent matrices.
Prove that a non-positive definite matrix has real and positive eigenvalues
A slightly stranger Hensel's Lemma
$\text{Sup}\{x\geq0:\sum\limits_{n=1}^\infty x^{\sqrt n}<\infty \}$
What is the next picture in this sequence?
Will Division by Zero be Defined Eventually?
When is a recurrence relation linear
number of pairs formed from $2n$ people sitting in a circle
recurrence relation number of bacteria
solve system of two trigonometric equations
Interesting calculus problems of medium difficulty?
How to prove that $b^{x+y} = b^x b^y$ using this approach?

While working on the theorem below, I constructed the following proof:

Theorem.If $\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$ is a sequence of countable sets, then$$

\bigcup_{n\in\mathbb N}E_{n}

$$

- limsup and liminf of a sequence of points in a set
- Is it true or false that $\lvert P() \setminus P((0, 1)) \rvert > \lvert P(\mathbb{N}) \rvert$
- Equivalence relations on classes instead of sets
- Categories with limits for large diagrams
- Is every subset of $\mathbb{Z^+}$ countable?
- Why does one have to check if axioms are true?
is countable.

**Proof.** Let $S=\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$ be a sequence of countable sets. Moreover, let $x_{n,m}$ be the $m$th element of the $n$th set in $S$. Construct a sequence of sequences

$$

\mathcal S=\left\langle\left\langle x_{n-m+1,m}\right\rangle_{m\in\mathcal N_n}\right\rangle_{n\in\mathbb N},

$$

where $\mathcal N_{n}=\left\{k\in\mathbb N:k\leqslant n\right\}$. Then $\mathcal S$ contains all the elements of

$$

T=\bigcup_{n\in\mathbb N}E_{n}.

$$

Observe that $\mathcal S$ is a surjection $\mathbb N\to T$, because for every $n\in\mathbb N$, $\mathcal S$ yields a finite, and thus countable, subsequence. Furthermore, because $\mathcal S$ may contain duplicate elements, an $U\subseteq\mathbb N$ can be found such that $\mathcal S$ is an injection $U\to T$. We have then found a bijection $\mathcal S:U\to T$. Hence, $T$ is countable. $\blacksquare$

Does it sound convincing?

**Edit:** I just realized that I cannot pinpoint duplicates because of how $\mathcal S$ is constructed, can I? 🙁

- An infinite subset of a countable set is countable
- Prove that $\operatorname{Hom}_{\Bbb{Z}}(\Bbb{Q},\Bbb{Z}) = 0$ and show that $\Bbb{Q}$ is not a projective $\Bbb{Z}$-module.
- Does there exist a non-empty set that is a subset of its power set?
- What is the difference between “family” and “set”?
- Prove that $f$ is one-to-one iff $f \circ h = f \circ k$ implies $h = k$.
- Binomial Theorem Proof from Taylor Series
- Asymptotic normal-behaviour of the MLE, question about proof.
- Show finite complement topology is, in fact, a topology
- Why study cardinals, ordinals and the like?
- Evaluating the limit of a sequence given by recurrence relation $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Is my solution correct?

You’re trying to list $T$ as $$\langle x_{1,1},x_{2,1},x_{1,2},x_{3,1},x_{2,2},x_{1,3},\ldots\rangle\;,\tag{1}$$ but instead you’ve constructed the sequence

$$\Big\langle\langle x_{1,1}\rangle,\langle x_{2,1},x_{1,2}\rangle,\langle x_{3,1},x_{2,2},x_{1,3}\rangle,\ldots\Big\rangle\;,$$

a related but definitely different animal. It’s actually easier to say what $n\in\Bbb N$ corresponds to $x_{k,\ell}$ in the list $(1)$ than to go in the forward direction. Count the elements of $(1)$ that precede $x_{k,\ell}$. They certainly include all $x_{i,j}$ such that $i+j<k+\ell$, and there are

$$\sum_{n=2}^{k+\ell-1}n=\frac{(k+\ell-1)(k+\ell)}2-1$$

of those. (The summation starts at $2$ because we always have $i+j\ge 2$.)

Let $m=k+\ell$; it also includes all $x_{m-i,i}$ such that $1\le i\le\ell$, and there are $\ell-1$ of those. Thus,

$$\frac{(k+\ell-1)(k+\ell)}2-1+\ell-1=\frac{(k+\ell-1)(k+\ell)}2+\ell-2$$

terms of $(1)$ precede $x_{k,\ell}$, and $x_{k,\ell}$ is therefore term number

$$\frac{(k+\ell-1)(k+\ell)}2+\ell-1$$

of the sequence $(1)$.

Perhaps one can be more concrete. Assume that the indexing of your $x_{n,m}$ starts at $1$. Let $p_n$ be the $n$-th prime. Map $p_n^m$ to $x_{n,m}$, and the numbers not of the form $p_n^m$ to any fixed object. This gives a surjection from the natural numbers to our union.

Proposition 1: A set $X$ is countable if and only if there exists a surjection $\tau: \mathbb N \to X$.

Proof: See link.

For each countable set in $\left\langle E_{n}\right\rangle_{n\in\mathbb{N}}$, select a surjection $\tau_n: \mathbb N \to E_{n}$ and let $X$ be the union of the $E_n$.

Proposition 2: There exists a surjection $\gamma: \mathbb N \times \mathbb N \to X$.

Proof

Define $\gamma$ by $(n,m) \mapsto \tau_n(m)$.

Cantor’s diagonal argument gives us

Proposition 3: There exists a bijection from $\mathbb N$ to $\mathbb N \times \mathbb N$.

Since the composition of two surjective maps is also surjective, we have shown that the union of the $E_n$ is a countable set.

- How to prove that continuous functions are Riemann-integrable?
- About a paper of Zermelo
- Injection and Bijection of the function $f(x,y)=(\frac{x}{1+x+y},\frac{y}{1+x+y}).$
- How many ways can $r$ nonconsecutive integers be chosen from the first $n$ integers?
- Favourite open problem?
- For each $y \in \mathbb{R}$ either no $x$ with $f(x) = y$ or two such values of $x$. Show that $f$ is discontinuous.
- Trouble in understanding a proof of a theorem related to UFD.
- Is there any matrix notation the summation of a vector?
- Inclusion-Exclusion
- When $L_p = L_q$?
- What exactly IS a line integral?
- Why must the gradient vector always be directed in an increasing direction?
- How to show that $C=C$ is a Banach space
- Is the “domain of discourse” in axiomatic set theory also a “set”?
- Intuition of Addition Formula for Sine and Cosine