Title: Math and science / Analysis
Tags: copyright blog

Title: Order relations, visualized on graphs
Order relations can be visualized by how they can be represented by graph models. Partial orders, total orders, strict partial orders and strict total orders are introduced below property-by-property.
Starting from a set and a relation
The most general case begins with a set, \( A \), and a binary relation, \( R \), defined for \( A \). We will consider the binary relation to be defined as a function \( R : A \times A \rightarrow \{True, False\} \). For any elements \( a \) and \( b \) of \( A \), the value of the relation \( R \) is given by \( R(a, b) = a \le b \). Visualize this as a 2D table of boolean entries.
Directed graphs, enumerated
For two elements of \( A \), there are two possible values for \( R(a, b) \). As a graph, True can be encoded as the presence of a directed edge from \( a \) to \( b \).
There are four possible values of the pair of \( R(a, b) \) and \( R(b, a) \). If we include \( R(a, a) \) and \( R(b, b) \), we have 16 possible combinations. These combinations represent all possible directed graphs with two nodes where self-cycles are allowed.
Compressed representations
As we place restrictions on the possible combinations, more structure can be introduced into the graph model to compress the representation. The four types of order relations correspond to the following graph representations:
Partial order
Directed acyclic graph (with R(a, a) = True).  Note that (I think) branching (in or out) is possible (e.g. R(a,b) = R(b,a) = False, while R(a,c) = R(b,c) = True).
Restricted partial order
There are many restrictions that can be introduced that introduce more structure, without becoming a total order. For example, a semi-lattice is a partial order with the rule that any two nodes must have common 'parent'. A semi-lattice is a slight generalization of a tree. In a semi-lattice, if direction of paths are ignored, then all nodes are connected.
Total order
The graph from a partial order with a significant restriction: there is only a single path, and it contains all nodes.
Strict partial order
Directed acyclic graph, (with R(a, a) = False)
Strict total order
All rules from strict partial order and total order.
Partial order
Starting from the general case. We introduce the following:
Reflexivity
Reflexivity removes the need represent self-cycles, as R(a, a) is always true.
Transitivity
Transitivity almost reduces the need for the graph model to have any cycles. In each connected component, there can be a single cycle. A graph can use paths to represet all relations: all nodes on a directed path have the relation \( a \le b \) where \( b \) is downstream of \( a \). Nodes within different connected components represent all elements \( n \) and \( m \) for which both \( R(n, m) \) and \( R(m, n) \) are false.
Antisymmetry, if \(R(a,b) \) and \( R(b,a) \) then \( a = b \) 
Removes the need for any cycles. Our model becomes a true acyclic graph. There can be multiple connected components.
Total order
Carrying on from a partial order, we introduce one more restriction:
- (What is the name for this?): for every \( a \) and \( b \) in \( A \), either \( a \le b \) or \( b \le a \).
This extra rule means that all elements of the set exist in a single connected component describing the relation.
Strict partial order
Strict partial order begins like partial order, but removes self-cycles in a different way, such that we don't later need antisymmetry in order to prevent cycles.
Irreflexivity
irreflexivity ( \( a \nless a \) for every \( a \) in \( A \)) removes the need for any loops, including self-loops. If \( a \) were in a loop, we would have \( a < a \), which this rule prohibits.
Transitivity
transitivity just like with the partial order case, transitivity allows paths to represent all values of the relation.
Strict total order
Like with the case of total order, we force all elements of the set to be part of the same connected component by introducing the restriction:
- trichotomy: \( a < b \), \( a=b \), or \( a > b \) for every \( a \) and \( b \) in \( A \).
Pre-order
It's worth touching on pre-orders and where they fit in. A pre-order has even less restrictions than a partial order, and thus, the concept is more general.Specifically, we remove anti-symmetry.
BackOnlyText: Some visuals:
Zero restrictions:
Transitivity almost removes all cycles:
Example of cycles that are permitted when there is no antisymmetry rule:
Relationship between partial and total order
The following two theorems reveal the close relationship between the two orders.
Theorem
Suppose ≤ is a partial order on a domain A. Define a<b to mean that a≤b and a≠b. Then < is a strict partial order. Moreover, if ≤ is total, so is <.
Theorem
Suppose < is a strict partial order on a domain A. Define a≤b to mean a<b or a=b. Then ≤ is a partial order. Moreover, if < is total, so is ≤.

Title: 18 analysis theorems
The following propositions about an ordered field \(R\) (and about associated structures such as \([a,b]=[a,b]_R=\{x \in R:\ a \leq x \leq b\}\)) are true when the ordered field \(R\) is taken to be \(\mathbb{R}\), the field of real numbers.
1. The Dedekind Completeness Property (Supremum)
Suppose \(S\) is a nonempty subset of \(R\) that is bounded above. Then there exists a number \(c\) that is an upper bound of \(S\) such that every upper bound of \(S\) is greater than or equal to \(c\).
We refer to this as completeness.
2. The Archimedean Property
For every \(x > 0, x  \in R\) there exists \(n \in \mathbb{N}\) with \(n > x\). Equivalently, for every \(x > 0, x \in R\) there exists \(n \in \mathbb{N}\) with \(1/n < x\).
Doesn't imply completeness.
3. The Cut Property
Suppose \(A\) and \(B\) are nonempty disjoint subsets of \(R\) whose union is all of \(R\), such that every element of \(A\) is less than every element of \(B\). Then there exists a cutpoint \(c \in R\) such that every \(x < c\) is in \(A\) and every \(x>c\) is in \(B\). (Or, if you prefer: Every \(x \in A\) is \(\leq c\), and every \(x \in B\) is \(\geq c\). It's easy to check that the two versions are equivalent.) Since this property may be unfamiliar, we remark that the Cut Property follows immediately from Dedekind completeness (take \(c\) to be the least upper bound of \(A\)).
Does imply completeness.
4. Topological Connectedness
Say \(S \subseteq R\) is open if for every \(x\) in \(S\) there exists \(\epsilon > 0\) so that every \(y\) with \(|y-x| < \epsilon\) is also in \(S\). Then there is no way to express \(R\) as a union of two disjoint nonempty open sets. That is, if \(R = A \cup B\) with \(A,B\) nonempty and open, then \(A \cap B\) is nonempty.
Does imply completeness.
5. The Intermediate Value Property
If \(f\) is a continuous function from \([a,b]\) to \(R\), with \(f(a) < 0\) and \(f(b) > 0\), then there exists \(c\) in \((a,b)\) with \(f(c) = 0\).
Does imply completeness.
6. The Bounded Value Property
If \(f\) is a continuous function from \([a,b]\) to \(R\), then there exists \(B\) in \(R\) with \(f(x) \leq B\) for all \(x\) in \([a,b]\).
Doesn't imply completeness.
7. The Extreme Value Property
If \(f\) is a continuous function from \([a,b]\) to \(R\), then there exists \(c\) in \([a,b]\) with \(f(x) \leq f(c)\) for all \(x\) in \([a,b]\).
Does imply completeness.
8. The Mean Value Property
Suppose \(f: [a,b] \rightarrow R\) is continuous on \([a,b]\) and differentiable on \((a,b)\). Then there exists \(c\) in \((a,b)\) such that \(f'(c) = (f(b)-f(a))/(b-a)\).
Does imply completeness.
9. The Constant Value Property
Suppose \(f: [a,b] \rightarrow R\) is continuous on \([a,b]\) and differentiable on \((a,b)\), with \(f'(x) = 0\) for all \(x\) in \((a,b)\). Then \(f(x)\) is constant on \([a,b]\).
Does imply completeness.
10. The Convergence of Bounded Monotone Sequences
Every monotone increasing (or decreasing) sequence in \(R\) that is bounded converges to some limit.
Does imply completeness.
11. The Convergence of Cauchy Sequences
Every Cauchy sequence in \(R\) is convergent.
Doesn't imply completeness.
12. The Fixed Point Property for Closed Bounded Intervals
Suppose \(f\) is a continuous map from \([a,b] \subset R\) to itself. Then there exists \(x\) in \([a,b]\) such that \(f(x) = x\).
Does imply completeness.
13. The Contraction Map Property
Suppose \(f\) is a map from \(R\) to itself such that for some constant \(c < 1\), \(|f(x) - f(y)| \leq c|x-y|\) for all \(x,y\). Then there exists \(x\) in \(R\) such that \(f(x) = x\).
Does imply completeness.
14. The Alternating Series Test
If \(a_1 \geq a_2 \geq a_3 \geq \dots\) and \(a_n \rightarrow 0\), then \(\sum_{n=1}^{\infty} (-1)^n a_n\) converges.
Doesn't imply completeness.
15. The Absolute Convergence Property
If \(\sum_{n=1}^\infty |a_n|\) converges in \(R\), then \(\sum_{n=1}^\infty a_n\) converges in \(R\).
Doesn't imply completeness.
16. The Ratio Test
If \(|a_{n+1}/a_n| \rightarrow L\) in \(R\) as \(n \rightarrow \infty\), with \(L < 1\), then \(\sum_{n=1}^{\infty} a_n\) converges in \(R\).
Does imply completeness.
17. The Shrinking Interval Property
Suppose \(I_1 \supseteq I_2 \supseteq \dots\) are bounded closed intervals in \(R\) with lengths decreasing to 0. Then the intersection of the \(I_n\)'s is nonempty.
Doesn't imply completeness.
18. The Nested Interval Property
Suppose \(I_1 \supseteq I_2 \supseteq \dots\) are bounded closed intervals in \(R\). Then the intersection of the \(I_n\)'s is nonempty. (Another name for this property is "spherical completeness''.)
Doesn't imply completeness.
BackOnlyText: It's amazing to realize than many of these properties are equivalent to the supremum property, which is usually introduced first. It is also interesting to see which of these properties are not sufficient to imply completeness; and yet they are sufficient in the presence of the Archimedean property.
The original text has short proofs and interactions for each of these. An exerpt:
Source: James Propp, "Real Analysis in Reverse"
https://arxiv.org/pdf/1204.4483.pdf

Title: The Cantor Set
The Cantor set is important for understanding Topology (open and closed sets) and measure.
Cantor set
Let \( C_0 \) be the closed interval \( [0, 1] \) and define \( C_1 \) to be the set that results when the open middle third is removed:
\[ C_1 = C_0 \setminus (\frac{1}{3}, \frac{2}{3} ) = [0, \frac{1}{3}] \cup [\frac{2}{3}, 1 ] \]
This process continued gives us the Cantor set:
\[ C = \bigcap_{n=0}^{\infty} C_n \]
Or alternatively:
\[ C = [0,1] \setminus \big( (\frac{1}{3},\frac{2}{3}) \; \cup \; (\frac{1}{9},\frac{2}{9}) \; \cup \;  (\frac{7}{9},\frac{8}{9}) \; \cup \; ...\big) \] \]
Properties of the Cantor set
Below are some properties of the Cantor set, with explanations on the reverse side.
The cantor set...
- has zero measure
- is uncountably infinite
- has dimension of \( \sqrt[3]{2} \)
- is closed
- is compact
- is perfect
- is nowhere dense
BackOnlyText: Dimension \( \sqrt[3]{2} \)
Scaling the Cantor set by 3 makes 1 copy into 2 copies of the set. If the dimension of a set is defined as being the exponent by which a scaling is raised to to count the number of copies, then the Cantor set has a dimension of \( \sqrt[3]{2} \). In other words, \( 3^d = 2 \implies d = \sqrt[3]{2} \).
Consider the set \([0,1]\), and magnify it three times to produce [0,3]. When beginning the construction of the Cantor set on the set \([0,3]\), we come upon \( C_1=[0,1]\cup [2,3]\), which contains two copies of the original set (and therefore will produce two copies of the Cantor set, with the following step in the construction being equivalent to the first step of the construction of the Cantor set in both \([0,1] \) and \([2,3]\). Therefore, if the Cantor set has dimension \(x\), then \(2=3x\), and \(x=0.63\).
Source: Abbott, p88
https://www.youtube.com/watch?v=gB9n2gHsHN4

Title: Heine-Borel Theorem
Q: Heine-Borel Theorem for \( \mathbb{R} \)
A set \( K \subset \mathbb{R} \) is compact iff [...].
If you have forgotten some of the formulations of compactness, here is a recap of one:
Compactness
A set \( K \subseteq \mathbb{R} \) is compact iff [...].
A: it is closed and bounded; every sequence in \( K \) has a subsequence that converges to a limit that is also in \( K \)
BackOnlyText: Heine-Borel Theorem, proof
Below is a copy of Abbott's proof:
Source: Abbott, p84

Title: Exercise: nested sequences of sets
Q: The following statement is [true or false?]
If \( F_1 \supseteq F_2 \supseteq F_3 \supseteq F_4 \supseteq ... \) is a nested sequence of nonempty closed sets, then the intersection \( \bigcap_{n=1}^{\infty} F_n \neq \emptyset \).
A: false
BackOnlyText: The statement is false. Consider the nested sequence of closed sets: \( \mathbb{R}, \mathbb{R} \setminus [0, 1], \mathbb{R} \setminus [0, 2], \mathbb{R} \setminus [0, 3], ... \). The infinite intersection is empty.
If this seems to contradict the nested interval property, recall its details to see why there is no contradiction:
Nested Interval Property
For each \( n \in \mathbb{N} \), assume we are given a closed interval
\[ I_n = [a_n, b_n] = \{x \in \mathbb{R} : a_n \le x \le b_n \} \]
Assume also that each \( I_n \) contains \( I_{n+1} \). Then, the resulting nested sequence of closed intervals:
\[ I_1 \supseteq I_2 \supseteq I_3 \supseteq I_4 ... \]
has a nonempty intersection; that is \( \bigcap_{n=1}^{\infty} I_n \neq \emptyset \).
This property can be generalized by replacing "closed interval" with "compact set". But it can't be replaced with "closed set", as the above counter-example shows. The issue is that \( \mathbb{R} \) is closed, and other half-open sets like \( [0, \mathbb{R}) \) are also closed.
Source: Abbott, p18, p88 (1st edition)

Title: Perfect Sets
Q: The concept of a perfect set tries to generalize the idea of a closed interval whose end points [what?].
Perfect sets
A set \( P \subseteq \mathbb{R} \) is perfect iff [...].
The following theorem highlights the importance of perfect sets. (Abbott actually introduces this theorem in order to motivate the concept of perfect sets. See the reverse side for more details.)
A nonempty perfect set is [...].
A: are not equal; it is closed and contains no isolated points; uncountable
BackOnlyText: Motivation: a generalization
The nature of intervals that are closed and bounded allow for many interesting statements of the form:
if \( A \subseteq \mathbb{R} \) is an interval that is closed and bounded, then the proposition \( P \) holds.
For example, \( P \) could be: all open covers have a finite sub-cover. What makes closed bounded intervals special can be generalized into the concept of compactness, and in doing so, we see that we can drop the requirements for such sets to be intervals at all–closed and bounded is sufficient.
In a similar way, consider the implication:
if \( A \subseteq \mathbb{R} \) is a non-empty closed interval \( [a, b] \), then it is uncountable.
It turns out that the antecedent can be generalized into the concept of perfect sets; A perfect set which is nonempty is uncountable.
Proof
Copied directly from Abbott:
Example: Some examples:
- Closed intervals are perfect (other than singleton sets, \( [a, a] \)).
- The Cantor set is perfect.
- What else?
Source: Abbott, p102 (2nd edition)