Intereting Posts

Monotonicity and convergence of the sequence $a_n=\sum_{k=1}^{n}\frac{1}{k+n}$
So can anybody indicate whether it is worthwhile trying to understand what Mochizuki did?
2 heads or more in 3 coin toss formula
Eigenvalues of $\operatorname{ad}x$
Are Complex Substitutions Legal in Integration?
what does ∇ (upside down triangle) symbol mean in this problem
Subsets of the reals when the Continuum Hypothesis is assumed false
The number of solutions to $\frac{1}x+\frac{1}y+\frac{1}z=\frac{3}n,x,y,z\in\mathbb N$
The staircase paradox, or why $\pi\ne4$
Bernoulli Number analog using Cosine
Eigenvalues of a matrix of $1$'s
Does $\lim_{n\rightarrow\infty}\sin\left(\pi\sqrt{n^{3}+1}\right)$ exist?
How to solve this equation for x? $0 = (x+k)e^{-(x+k)^2}+(x-k)e^{-(x-k)^2}$
An infinite nested radical problem
Fourier Analysis textbook recommendation

This is a theorem proved in Rudin.

Theorem.Let $E_n, n=1,2,3,\ldots$ be a sequence of countable sets, and put $S=\bigcup_{n=1}^\infty E_n$. Then $S$ is countable.

Proof.Let every set $E_n$ be arranged in a sequence $x_{nk}, k=1,2,3,\ldots$, and consider the infinite array $$\begin{array}{cccc}

x_{11}&x_{12}&x_{13}&\cdots\\

x_{21}&x_{22}&x_{23}&\cdots\\

x_{31}&x_{32}&x_{33}&\cdots\\

\vdots&\vdots&\vdots&\ddots

\end{array}$$

in which elements of $E_n$ form the $n$th row. The array contains all elements of $S$. As indicated by the arrows in this picture —

- Set notation confusion (Empty Sets)
- If $(f\circ g)(x)=x$ does $(g\circ f)(x)=x$?
- Is an Anti-Symmetric Relation also Reflexive?
- Why is the Kleene star of a null set is an empty string?
- Number of subsets of a set $S$ of n elements , is $2^n$
- Am I allowed to use distributive law for infinitely many sets?
— these elements can be arranged in a sequence $$x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32},x_{23},x_{14};\ldots.\qquad(17)$$

If any two of the sets $E_n$ have elements in common, these will appear more than once in $(17)$. Hence there is a subset $T$ of the set of all positive integers such that $S\sim T$, which shows that $S$ is at most countable (Theorem 2.8). Since $E_1\subset S$ and $E_1$ is infinite, $S$ is infinite, and thus countable.

I’ve a hard time visualizing/understanding the last part of the proof though[(17) onwards], will someone please give an intuitive explanation/description of the last paragraph to help me in understanding the proof?

- Is $\aleph_0 = \mathbb{N}$?
- Relations (Binary) - Composition
- Size of a union of two sets
- Image of a union of collection of sets as union of the images
- Bijection between an open and a closed interval
- Is the function $f:\mathbb{R}^2\to\mathbb{R}^2$, where $f(x,y)=(x+y,x)$, one-to-one, onto, both?
- If $A$ is a non-empty set, then $A \notin A$
- Cardinality of separable metric spaces
- Let $f:A \to B$ and $g:B\to A$ be arbitrary functions.
- How many ways to merge N companies into one big company: Bell or Catalan?

The idea in the last paragraph is that in this sequence we many name the same element twice. This can happen if some $x$ is in two of the $E_k$ sets. Hence the author points out that the function that sends every natural number $n$ to the $n$th element of that sequence is not bijective. To make it bijective, we have to restrict its domain to some subset of the natural numbers (such that not two natural numbers are sent to the same element). Hence, $S$ is equinumerous with a subset of natural numbers.

Now we know (and I assume this is theorem 2.8) that every subset of the natural numbers is either countably infinite or finite. Therefore up until now we have only shown that $S$ is either countably infinite or finite. But, we already know that it contains at least countably infinite elements, the elements of $E_1$. Hence it cannot be finite. This implies that it is countable.

What Rudin is saying is that in the sequence which he writes down, every element of every $E_n$ appears **at least** once. By definition, this shows that there exists a surjection $\mathbb{N} \to S$. Hence $S$ can be identified with a subset of the positive integers: for each $s \in S$, $s$ appears at some point in the sequence and we can let $m(s)$ denote any one of those integers such that the $m(s)$-th element in the sequence is $s$. Hence $S$ is either finite or countably infinite. The first case is excluded since $S$ contains the infinite set $E_1$.

- Product and Box Topologies
- Finding supremum of all $\delta > 0$ for the $(\epsilon , \delta)$-definition of $\lim_{x \to 2} x^3 + 3x^2 -x + 1$
- Multiplicative group $(\mathbb R^*, ×)$ is group but $(\mathbb R, ×)$ is not group, why?
- One-to-one function from the interval $$ to $\mathbb{R}\setminus\mathbb{Q}$?
- Difference Between Tensoring and Wedging.
- What is $f_\alpha(x) = \sum\limits_{n\in \mathbb{N}} \frac{n^\alpha}{n!}x^n$?
- Right and left inverse
- Does path-connected imply simple path-connected?
- Finding out an arc's radius by arc length and endpoints
- Why it is important to find largest prime numbers?
- Prime elements in $\mathbb{Z}$
- Is $\Bbb Q(\sqrt 2, e)$ a simple extension of $\Bbb Q$?
- Can the golden ratio accurately be expressed in terms of e and $\pi$
- Correspondence theorem for rings.
- Compact operator on $l^2$