Title: Math and science / Analysis / Tao / 08. Infinite sets

Title: Countable sets
Q: A set \( X \) is said to be countably infinite (or just countable) iff [...].
We also have the terms: at most countable and uncountable.
- A set is at most countable if it is [...].
- A set is uncountable if it is [...].
The relationship is shown below:
A: it has equal cardinality with with the natural numbers \( \mathbb{N} \); either finite or coutable; infinite and not countable
BackOnlyText: Countably infinite sets are also called denumerable sets.
Note that a countable set must be infinite as it has the same cardinality as \( \mathbb{N} \).
Know your bijection
To understand the nature of countable sets, it is crucial to understand the nature of the bijection and how it operates on the infinite set \( \mathbb{N} \). Recap below:
One-to-one functions
A function \( f \) is one-to-one (or injective) if different elements map to different elements:
\[ x \neq x' \implies f(x) \neq f(x') \]
Onto functions
A function \( f \), \( f : X \rightarrow Y \) is onto (or surjective) if every element in \( Y \) can be obtained from applying \( f \) to some element in \( X \):
\[ \text{For every } y \in Y \text{, there exists an } x \in X \text{ such that } f(x) = y \]
Bijective functions
A function which is both injective and surjective is called bijective or invertable.
Example: We know that if \( X \) is finite and \( Y \) is a propper subset of \( X \), then \( Y \) does not have the same cardinality as \( X \). This does not apply to infinite sets. For example, \( \mathbb{N} \) has the same cardinality as \( \mathbb{N} - \{0\} \), and thus, the latter is countable. This is so as we can have a bijection \( f: \mathbb{N} \rightarrow \mathbb{N} - \{x\} \) from \( \mathbb{N} \) to \( \mathbb{N} - \{x\} \). (why? Look at the bijective definition above)
The set of even natural numbers, \( \{2n : n \in \mathbb{N} \} \), is also countable.

Title: Count all the things (countability propositions)
A number of propositions related to countable sets:
- All subsets of the natural numbers are at most countable.
- Let \( Y \) be a set, and let \( f: \mathbb{N} \rightarrow Y \) be a function. Then the image \( f(\mathbb{N}) \) is at most countable.
- Let \( X \) be a countable set, and let \( f : X \rightarrow Y \) be a function. Then \( f(X) \) is at most countable.
- Let \( X \) and \( Y \) be countable sets. Then \( X \cup Y \) is a countable set.
- The integers \( \mathbb{Z} \) are countable.
- The set \( A := \{(n, m)\ \in \mathbb{N} \times \mathbb{N} : 0 \le m \le n\} \) is countable.
- The set \( \mathbb{N} \times \mathbb{N} \) is countable.
- The rationals \( Q \) are countable.
- The set of all functions from \( {0, 1} \) to \( \mathbb{N} \) is countable.
- The set of all functions from \( \mathbb{N} \) to \( {0, 1} \) is uncountable, representing an arbitrary binary string.
Maybe some of these should be split up and their proofs outlined.
BackOnlyText: Once we have a bijection from \( \mathbb{N} \) to \( \mathbb{N} \times \mathbb{N} \), we can have a bijection to the rationals, which are defined as a pairing of two numbers to make a quotient.
Source: p185-188

Title: Series on countable sets, definition
Previously, summation over finite sets were defined:
With some bijection \( g: \{i \in \mathbb{N} : 1 \le i \le n\} \rightarrow X \), the sum over \( X \) is defined as:
\[ \sum_{x \in X} f(x) := \sum_{i=1}^{n} f(g(i)) \]
We can extend this notion to summation over an infinite set \( X \), as long as we have a bijection between \( \mathbb{N} \) and \( X \)—in other words, \( X \) is countable. In addition, our notion of summation is limited to absolute convergence; we have previously shown that a rearrangement of terms of a conditionally but not absolutely convergent series does not necessarily converge to the original sum.
Series on countable sets
Let \( X \) be a countable set, and let \( f: X \rightarrow \mathbb{N} \) be a function. We say that the series \( \sum_{x \in X}f(x) \) is absolutely convergent iff for some bijection \( g : \mathbb{N} \rightarrow X \), the sum \( \sum_{n=0}^{\infty}f(g(n)) \) is absolutely convergent. We then define the sum of \( \sum_{x \in X}f(x) \) by the formula:
\[ \sum_{x \in X}f(x) = \sum_{n=0}^{\infty}f(g(n)) \]
Tao later notes that this definition is sufficient for it to be true for any bijection \( g \).
Source: p189

Title: Fubini's theorem for infinite series
Q: The extension of Fubini's theorem to infinite series is not a straightforward process. The proof acts as a summary of concepts including infinite series, series, limits, supremum and functions.
Let \( f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} \) be a function such that \( \sum_{(n,m) \in \mathbb{N} \times \mathbb{N}} f(n, m) \) is absolutely convergent. Then we have
\[ \begin{aligned}
\sum_{n=0}^{\infty} \left( \sum_{m=0}^{\infty} f(n, m) \right) &= [...] \\
&= [...] \\
&= \sum_{m=0}^{\infty} \left( \sum_{n=0}^{\infty} f(n, m) \right)
\end{aligned} \]
In other words, we can switch the order of infinite sums provided that the entire sum is absolutely convergent.
A: \sum_{(n,m) \in \mathbb{N} \times \mathbb{N} } f(n, m); \sum_{(m,n) \in \mathbb{N} \times \mathbb{N} } f(n, m)
BackOnlyText: If you have time, it's worth working through the proof.
Source: p190

Title: Series on uncountable sets (a special case)
Q: We have a definition for series on countable sets (defined as a sum remapped over the natural numbers). In general, this definition doesn't extend to uncountable sets; however, there is a special case where we can make this extension.
Note: the following definitions have a flaw that is examined on the flip side. Understanding the flaw is probably the highlight of this card.
Let \( X \) be a set (which could be uncountable), and let \( f : X \rightarrow \mathbb{R} \) be a function. Consider every subset of \( X \) and consider the sum over each of these subsets. The set of all of these sums—if its supremum is less than \( \infty \), then the set [\( \{x \in X: \, ? \} \)] is at most countable*. In this case, we make the definition
\( \sum_{x \in X}f(x) \) is absolutely convergent, and the sum is given by:
\[ \sum_{x \in X}f(x) := [...] \]
So, we have found a case where it makes sense to represet the sum over an uncountable set as a sum over a countable one.
*This requires [what axiom?].
A: \( \{x \in X: f(x) \ne 0\} \); \sum_{x \in X: f(x) \ne 0} f(x); the axiom of choice
BackOnlyText: More precisely
It is good to clean up the above definition so as to make clear what is an if and what is an iff relationship—we need to reshuffle the presentation. The next presentation uses the order given by Tao.
Firstly, we want to be able to refer to the antecedent of the first conditional. To give a name to the antecedent we make an iff definition:
We say that the series \( \sum_{x \in X}f(x) \) is absolutely convergent iff
\[ \sup \left\{ \sum_{x \in A} |f(x)| : A \subseteq X, A \text{ is finite} \right\} < \infty \]
We then say that, if the series \( \sum_{x \in X}f(x) \) is absolutely convergent, then the set \( \{ x \in X: f(x) \ne 0 \} \) is at most countable and we define the value of \( \sum_{x \in X}f(x) \) by:
\[ \sum_{x \in X}f(x) := \sum_{x \in X: f(x) \ne 0} f(x) \]
This presentation avoids two potential problems:
1. Not having the convergence of the series \( \sum_{x \in X}f(x) \) imply that the set \( \{ x \in X: f(x) \ne 0 \} \) is countable.
2. Not having the convergence of the series \( \sum_{x \in X}f(x) \) imply that the above supremum is finite.
The below image shows how the two presentations differ in what they are describing.
Source: p192

Title: Infinite series and summation on infinite sets (summation laws III and IV)
The three main laws, all present for finite series and summaton on finite sets, are:
- Linearity (part I and part II)
- Triangle inequality
- Comparison test
In addition, summation on sets has additional laws:
- Substitution (via bijection)
- Set union
- Fubini's theorem
Substitution and set union laws have some, albeit limited, correspondence with index shifting and range merging present only for standard series.
Moving from finite to infinite
Infinite series
For infinite series, the triangle inequality and the comparison test laws both have tweaks from their finite counterparts.
- Triangle inequality becomes the absolute convergence test. The law includes a condition based on the series convergence.
- The comparison test requires the less series to be less absolutely, so as to rule out non-convergence.
Infinite sets
The definition of summation on infinite sets only covers absolute convergence, as conditional convergence cannot be defined due to the ability to rearrange the summation to achieve arbitary sums. As a result we cannot define the triangle inequality law. The comparison test also would get a bit weaker--Tao doesn't even list it, so maybe it's not possible or useful.
BackOnlyText: TODO: add the actual laws
Source: p169
p193

Title: Bernhard Riemann's rearrangement theorem
Q: Let \( \sum_{n=0}^{\infty} a_n \) be a series of reals which is conditionally convergent, but not absolutely convergent, and let L be any real number. Then there exists a bijection \( j : \mathbb{N} \rightarrow \mathbb{N} \) such that [...].
A supporting lemma can be defined to design the proof:
In a conditionally (but not absolutely) convergent series, both the sum of the positive terms and the sum of the negative terms are [...].
A: \( \sum_{m=0}^{\infty}a_{j(m)} \) converges conditionally to L; divergent series
BackOnlyText: An interesting thing to still investigate is how the proof confirms convergence in such a way that you cannot prove the absolute convergence of the original series.
Intuition
The supporting lemma can be understood from contradiction:
If either (but not both) of the series of positive terms or the series of negative terms are divergent, then their sum would be divergent (cannot be so, as the sum is conditionally convergent). If neither are divergent, then the sum would be absolutely convergent (also not true). So they must both be divergent.
The rest of the proof can be understood as follows:
The formal proof is a little more involved.
Source: p194
History of rearrangement
https://sites.math.washington.edu/~morrow/335_16/history of rearrangements.pdf

Title: Cantor's theorem
Q: Let \( X \) be an arbitrary set (finite or infinite). Then the sets [...].
A: \( X \) and \( 2^X \) cannot have equal cardinality
BackOnlyText: Proof, from Tao
Suppose for sake of contradiction that the sets \( X \) and \( 2^X \) had equal cardinality. Then, by the definition of cardinality, there exists a bijection \( f : \rightarrow 2^X \) between \( X \) and the power set of \( X \). Now consider the set:
\[ A := \{ x \in X : x \notin f(x) \} \]
This set is well defined since \( f(x) \) is an element of \( 2^X \) and is thus a subset of \( X \).
Clearly, \( A \) is a subset of \( X \), hence it is an element of \( 2^X \). Since \( f \) is a bijection, there must therefore exist \( x \in X \) such that \( f(x) = A \). There are now two cases:
- If \( x \in A \), then by definition of \( A \), we have \( x \notin f(x) \), hence \( x \notin A \), a contradiction.
- If \( x \notin A \), then \( x \notin f(x) \), which is sufficient for \( x \in A \), a contradiction.
In either case, a contradiction.
Russell's paradox
This proof is very similar in spirit to Russell's paradox; the essence being that a bijection between \( X \) to \( 2^X \) would come dangerously close to the concept of a set containing itself.
Example: A consequence of Cantor's theorem is that the reals are uncountable.
The outline of a proof of this is:
- Take the uncountable set \( 2^\mathbb{N} \) and create a function \( f: 2^\mathbb{N} \rightarrow R \) from it to the reals.
- If you can choose \( f \) such that it is injective, then it will be a bijection from \( 2^\mathbb{N} \) to it's image, \( f(2^\mathbb{N}) \).
- The existance of the bijection is sufficient for \( 2^\mathbb{N} \) and \( f(2^\mathbb{N}) \) to have the same cardinality.
- But \( f(2^\mathbb{N}) \) is a subset of \( \mathbb{R} \), so \( \mathbb{R} \) must have cardinality greater than or equal to \( 2^\mathbb{N} \), and thus be uncountable.
Finding such a function \( f \) is the bulk of the work of the proof. An example function is:
\[ f(A) := \sum_{n \in A} 10^{-n} \text{, where } A \in 2^\mathbb{N}  \]
This function can be imagined as creating a number represented in decimal:
Input: \( A \in 2^\mathbb{N} \).
Output: X.XXXXXXX.....
Example: \( f(\{1, 3, 5, 6, 7, 10\}) = 0.1010111001 \)
For every natural number \( i \), if \( i \in A \), then set the i^th digit to be a 1, otherwise set it to 0.
This function is injective as no two non-equal subsets of the natural numbers can produce the same decimal number.
Proof 2, diagonal argument
A table where each row is are the entries of a function from natural numbers to infinite sequences of digits (so we are investigating the cardinality of \( N \) and \( 2^N \)). Taking a diagonal through the table and adding 1 to each entry produces a sequence that can't possibly be in any row. (Might need to clean this up...)
\[
\begin{matrix}
0.& \color{red}9 & 7& 0& 6& \dots\\
1.& 8 & \color{red}2& 4& 3& \dots\\
2.& 4 & 5& \color{red}2& 8& \dots\\
3.& 1 & 2& 5& \color{red}3& \dots\\
\vdots & \vdots & \vdots& \vdots& \vdots& \dots\\
\hline\\
0.& 8 & 1& 1& 4& \dots\\
\end{matrix}
\]
youtube 1
youtube 2

Title: The Continuum Hypothesis
Q: Cantor's theorum leads to the reals having strictly larger candinality than the natural numbers. What about sets with strictly larger cardinality to the natural numbers but strictly less than the reals?
The Continuum Hypothesis asserts that [...].
Kurt Godel and Paul Cohen separately showed that the Continuum Hypothesis is [...] other axioms of set theory; it can neither [...]
A: no such sets exist; independent of the; be proved nor disproved in that set of axioms (unless those axioms are inconsistent, which is highly unlikely).
BackOnlyText: Kurt Godel's and Paul Cohen's opinion was that the Continuum Hypothesis was false. (Unprovability of a statement doesn't abrogate people's ability to hold an opinion on what it should be, or what is 'is' in some broader sense).
Source: p198

Title: Axiom of Choice
There are a few different ways of presenting this axiom differing in their readability.
1: choice function (brilliant.org)
Let \( \mathcal{I} \) be a set (which we will use for indexing). For each \( i \in \mathcal{I} \) let \( S_i \) be a set. We call the set of these sets a collection, denoted as \( \{ S_i \}_{i \in \mathcal{I} } \). So the collection contains one set for each element in \( \mathcal{I} \).
A choice function is a function
\[ f : \mathcal{I} \rightarrow \bigcup_{i \in \mathcal{I}} S_i \]
such that \( f(i) \in S_i \text{ for all } i \in \mathbb{I} \). The axiom of choice states that for any indexed collection of nonempty sets, there exists a choice function.
2: Cartesian product of indexed collection (brialliant.org)
The Cartesian product of an indexed collection of nonempty sets is nonempty:
\[ S_i \neq 0 \; \forall i \in \mathcal{I} \implies \prod_{i \in \mathcal{I}} S_i \neq 0 \]
It's worth noting that the axiom of choice is only an interesting statment when the indexing set \( \mathcal{I} \) is infinite; it is easy to show that the finite case is true without using the axiom of choice.
3: binary predicates
Let \( X \) and \( Y \) be sets, and let \( P(x, y) \) be a binary predicate pertaining to an object \( x \in X \) and \( y \in Y \) such that for every \( x \in X \) there is at least one \( y \in Y \) such that \( P(x, y) \) is true. [How can one assert the existance of such a predicate?] Then there exists a function \( f : X \rightarrow Y \) such that \( P(x, f(x)) \) is true for all \( x \in X \).
Example: Another way of viewing AC was considered here: https://twitter.com/gro_tsen/status/1471204761747738628?s=21
Here is some notes of this argument:
Source: p200

Title: Maximal and minimal elements, definition
Q: Let \( X \) be a partially ordered set, and let \( Y \) be a subset of \( X \).
Minimal element
We say that \( y \) is a minimal element of \( Y \) if [...].
Maximal element
We say that \( y \) is a maximal element of \( Y \) if [...].
A: \( y \in Y \) and there is no element \( y' \in Y \) such that \( y' \le y \); \( y \in Y \) and there is no element \( y' \in Y \) such that \( y \le y' \)
BackOnlyText: The definition cannot be: for all \(y \in Y\) \(y' \le y\), as this would force there to be a total order (fully connected graph).
Maximal element vs supremum
A maximal element can be thought of as an endmost element in a directed acyclic graph. The relation that defines this graph can be anything that meets the criteria needed to produce partial or total ordering. The maximal element must exist in the set. A set may have zero, one or multiple maximal elements (image multiple connected components of a directed graph).
Supremum is a concept defined only for sets of reals using the predicate \( x \le y \iff ((x - y) \text{ is nonpositive}) \). The supremum of a set of reals does not need to be within the set. A set can only have one supremum, and it always has one supremum (\( \infty \) is used for sets when there is no least upper bound).
Example: \( X = \{ \{1, 2\}, \{ 2 \}, \{2, 3\}, \{2, 3, 4\}, \{ 5 \} \} \) and the set inclusion relation \( \subseteq \) has the following minimal and maximal elements:
minimal
\( \{2\}, \{5\} \)
maximal
\( \{1, 2 \}, \{ 2, 3, 4\} \)
both
\( \{5\} \)
neither
\( \{2, 3\} \)
Source: p204

Title: Well-ordered sets
Q: Let \( X \) be a partially ordered set, and let \( Y \) be a totally ordered subset of \( X \). We say that \( Y \) is well-ordered iff [...].
A: every non-empty subset of \( Y \) has a minimal element, \( \min(Y) \)
BackOnlyText: Every finite totally ordered set is well-ordered (proved in Ex. 8.5.8). Every subset of a well-ordered set is also well-ordered (why?)
One advantage of well-ordered sets is that they automatically obey the principle of strong induction.
Possible interpretation
Take a table representing an order on \( X \). There will be missing entries in the table representing an ordered pair of elements of \( X \) which is not in the domain of the ordering function. Let \( Y \) be a subset of \( X \) such that there are no such holes for the elements of \( Y \). Imagine this by moving all the columns/rows of the table for \( X \) and it's comparison function such that all of \( Y \)'s elements are bunched together. Then there will be a square in the table that is fully filled with values. All these elements are in \( Y \). Now, there still can be characteristics of these values. For example: the presence of cycles. This is where well-ordering comes in. Take any set of elements of \( Y \) and impose that there is a minimal element. Then, there cannot be cycles.
Example: The natural numbers \( \mathbb{N} \) are well-ordered (see Prop. 8.1.4). The integers \( \mathbb{Z} \), the rationals \( \mathbb{Q} \),and the reals \( \mathbb{R} \) are not.
Source: p205