01 Introduction, Real Numbers, Completeness

Lecture from: 19.02.2024 | Video: Video ETHZ

“Mathematics, you see, is not a spectator sport” George Pólya

Analysis: Introduction and Foundations

Analysis is the rigorous study of continuous quantities, changing processes, and approximations, along with assessing the quality of those approximations.

What is Analysis about?

• Continuous Problems: A primary focus is on problems involving continuous variables, such as those found in differential equations (e.g., modeling the motion of a pendulum or the flow of heat).
• Discrete vs. Continuous: Sometimes, discrete problems (like integer programming) are significantly harder than their continuous counterparts (like linear programming). Analysis provides tools to understand and bridge these differences.
• Approximations: In real-world applications, exact solutions are often unattainable. Analysis provides the framework for understanding and quantifying the errors introduced by approximations.

Why is Analysis relevant to Computer Science?

• Complexity Analysis: Big-O notation and related concepts used to analyze the efficiency of algorithms have their roots in analysis.
• Machine Learning: Core concepts in machine learning, such as gradient descent and backpropagation, are deeply rooted in the principles of calculus and analysis. Numerical methods, optimization, and error analysis are all crucial.
• Numerical Methods: Solving differential equations and other problems where continuous math is needed

Real Numbers, Euclidean Spaces, and Complex Numbers

This section lays the groundwork by defining the fundamental number systems used in analysis.

The Field of Real Numbers ($\mathbb{R}$)

We start with familiar number systems:

• Natural Numbers: $\mathbb{N}=\{0,1,2,\dots \}$ (Includes 0 in this context).
• Limitations: We encounter equations with no solutions in $\mathbb{N}$, e.g., $x+1=0$.
• Integers: $\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}$
• Limitations: Still, equations like $2x+1=0$ have no solutions.
• Rational Numbers: $\mathbb{Q}=\{\frac{p}{q}\mid p\in \mathbb{Z},q\in \mathbb{Z},q\ne 0\}$
• Limitations: Equations like the pythagorean theorm $x^2=2$ for the diagonal of an unit square, $x^2=2=a^2+b^2$, cannot be solved.
• Real Numbers: $\mathbb{R}$ extends $\mathbb{Q}$ to include solutions to equations like $x^2=2$. Instead of constructing $\mathbb{R}$ (as is done in advanced real analysis courses), we’ll introduce it axiomatically.

Axiomatic Definition of $\mathbb{R}$

The real numbers, $\mathbb{R}$, are defined as a set with two binary operations:

• Addition: $+:\mathbb{R}\times \mathbb{R}\to \mathbb{R}$
• Multiplication: $\cdot :\mathbb{R}\times \mathbb{R}\to \mathbb{R}$

and a total order relation $\le$ on $\mathbb{R}$, satisfying the following axioms:

Theorem 1.1.2: $\mathbb{R}$ is a commutative, ordered field that is order-complete (ordnungsvollständig). $\mathbb{R}$ is non-trivial ($0\ne 1$).

Axioms of Addition (A):

• (A1) Associativity: $\forall x,y,z\in \mathbb{R}:(x+y)+z=x+(y+z)$
• (A2) Neutral Element: $\exists 0\in \mathbb{R},\forall x\in \mathbb{R}:x+0=x$
• (A3) Inverse Element: $\forall x\in \mathbb{R},\exists y\in \mathbb{R}:x+y=0$. This $y$ is denoted as $-x$.
• (A4) Commutativity: $\forall x,y\in \mathbb{R}:x+y=y+x$

Axioms of Multiplication (M):

• (M1) Associativity: $\forall x,y,z\in \mathbb{R}:(x\cdot y)\cdot z=x\cdot (y\cdot z)$
• (M2) Neutral Element: $\exists 1\in \mathbb{R},\forall x\in \mathbb{R}:x\cdot 1=x$
• (M3) Inverse Element: $\forall x\in \mathbb{R}\setminus \{0\},\exists y\in \mathbb{R}:x\cdot y=1$. This $y$ is denoted as $x^{-1}$ or $\frac{1}{x}$.
• (M4) Commutativity: $\forall x,y\in \mathbb{R}:x\cdot y=y\cdot x$

Distributivity (D):

• $\forall x,y,z\in \mathbb{R}:x\cdot (y+z)=x\cdot y+x\cdot z$

Order Axioms (O):

• (O1) Reflexivity: $\forall x\in \mathbb{R}:x\le x$
• (O2) Transitivity: $\forall x,y,z\in \mathbb{R}:(x\le y\wedge y\le z)\Rightarrow x\le z$
• (O3) Antisymmetry: $\forall x,y\in \mathbb{R}:(x\le y\wedge y\le x)\Rightarrow x=y$
• (O4) Totality: $\forall x,y\in \mathbb{R}:x\le y\vee y\le x$

Compatibility Axioms (K):

• (K1) $\forall x,y,z\in \mathbb{R}:x\le y\Rightarrow x+z\le y+z$
• (K2) $\forall x,y\in \mathbb{R}:(x\ge 0\wedge y\ge 0)\Rightarrow x\cdot y\ge 0$

Order Completeness (V) (Vollständigkeitsaxiom):

This is the crucial axiom that distinguishes $\mathbb{R}$ from $\mathbb{Q}$.

• Let $A\subseteq \mathbb{R}$ and $B\subseteq \mathbb{R}$ be non-empty sets such that:

  1. $A\ne \varnothing$, $B\ne \varnothing$
  2. $\forall a\in A,\forall b\in B:a\le b$

  Then there exists a $c\in \mathbb{R}$ such that $\forall a\in A,\forall b\in B:a\le c\le b$.

Interpretation of Order Completeness: This axiom states that there are no “gaps” in the real number line. Every set bounded above has a least upper bound (supremum), and every set bounded below has a greatest lower bound (infimum).

Connections to Abstract Algebra/Discrete Math:

• (A1-A4): $(\mathbb{R},+)$ is an abelian group.
• (M1-M4): $(\mathbb{R}\setminus \{0\},\cdot )$ is an abelian group.
• (A1-A4, M1-M4, D): $\mathbb{R}$ is a field.
• (O1-O4): $\le$ defines a total order on $\mathbb{R}$.
• (A1-A4, M1-M4, D, O1-O4, K1-K2): $\mathbb{R}$ is an ordered field (angeordneter Körper).
• (A1-A4, M1-M4, D, O1-O4, K1-K2, V): $\mathbb{R}$ is a complete ordered field (ordnungsvollständiger angeordneter Körper). This final property is unique to the real numbers.

This axiomatic foundation allows us to rigorously derive all the familiar properties and theorems of real analysis.

Corollaries of the Real Number Axioms and their Proofs

Corollary

1. Uniqueness of Inverses: Additive and multiplicative inverses are unique.
2. Zero Property: $\forall x\in \mathbb{R}:0\cdot x=0$
3. Negative Multiplication: $\forall x,y\in \mathbb{R}:(-x)\cdot y=-(x\cdot y),(-x)(-y)=x\cdot y$. In particular, $(-1{)}^2=1$.
4. Non-negativity and Negatives: $\forall y\in \mathbb{R}:y\ge 0⟺-y\le 0$
5. Squares are Non-negative: $\forall y\in \mathbb{R}:y^2\ge 0$. In particular, $1=1^2>0$.
6. Adding Inequalities: $\forall x,y,u,v\in \mathbb{R}:x\le y\wedge u\le v\Rightarrow x+u\le y+v$
7. Multiplying Inequalities: $\forall x,y,u,v\in \mathbb{R}:0\le x\le y\wedge 0\le u\le v\Rightarrow x\cdot u\le y\cdot v$
8. Reciprocal Inequality: $\forall x,y\in \mathbb{R}:0<x\le y⟺0<y^{-1}\le x^{-1}$

Proofs

1. Uniqueness of Inverses:

   • Additive Inverse: Suppose $x\in \mathbb{R}$ has two additive inverses, $y$ and $z$. Then $x+y=0$ and $x+z=0$. Therefore, $y=y+0=y+(x+z)=(y+x)+z=(x+y)+z=0+z=z$. Thus, $y=z$, and the additive inverse is unique.

   • Multiplicative Inverse: Suppose $x\in \mathbb{R}\setminus \{0\}$ has two multiplicative inverses, $y$ and $z$. Then $x\cdot y=1$ and $x\cdot z=1$. Therefore, $y=y\cdot 1=y\cdot (x\cdot z)=(y\cdot x)\cdot z=(x\cdot y)\cdot z=1\cdot z=z$. Thus, $y=z$, and the multiplicative inverse is unique.

2. Zero Property:

   Let $x\in \mathbb{R}$. Then $0\cdot x=(0+0)\cdot x$ (by A2). Using distributivity (D), we get $0\cdot x=0\cdot x+0\cdot x$. Adding the additive inverse of $0\cdot x$ to both sides, we get $0\cdot x+(-(0\cdot x))=(0\cdot x+0\cdot x)+(-(0\cdot x))$. By associativity (A1) and the inverse property (A3), this simplifies to $0=0\cdot x+(0\cdot x+(-(0\cdot x)))=0\cdot x+0=0\cdot x$ (by A2). Therefore, $0\cdot x=0$.

3. Negative Multiplication:

   • Part 1: $(-x)\cdot y=-(x\cdot y)$ We want to show that $(-x)\cdot y$ is the additive inverse of $x\cdot y$. Consider $x\cdot y+(-x)\cdot y$. By distributivity (D), this is $(x+(-x))\cdot y=0\cdot y=0$ (using A3 and the Zero Property). Since the additive inverse is unique (from part 1), we conclude that $(-x)\cdot y=-(x\cdot y)$.

   • Part 2: $(-x)(-y)=x\cdot y$ Using Part 1 twice, we have $(-x)(-y)=-(x\cdot (-y))=-((-y)\cdot x)=-(-(y\cdot x))=y\cdot x=x\cdot y$ (by commutativity M4).

   • In particular: When $x=y=1$, Part 2 gives us $(-1)(-1)=1\cdot 1=1$, and thus $(-1{)}^2=1$.

4. Non-negativity and Negatives:

   • ($\Rightarrow$): Suppose $y\ge 0$. Adding $-y$ to both sides and using K1, we get $y+(-y)\ge 0+(-y)$. This simplifies to $0\ge -y$ (by A3 and A2).

   • ($\Leftarrow$): Suppose $-y\le 0$. Adding $y$ to both sides and using K1, we get $-y+y\le 0+y$. This simplifies to $0\le y$ (by A3 and A2), or equivalently, $y\ge 0$.

5. Squares are Non-negative:

   Let $y\in \mathbb{R}$. We have two cases:

   • Case 1: $y\ge 0$: By K2, $y\cdot y\ge 0$, so $y^2\ge 0$.

   • Case 2: $y<0$: By O4, we must have that $y\le 0$. This implies, from the previous property (4), that $-y\ge 0$. Then, by K2, $(-y)\cdot (-y)\ge 0$. From part 3, $(-y)(-y)=y\cdot y=y^2$. Therefore, $y^2\ge 0$.

   • In particular: Because $1\ne 0$ by axiom, and $1\in \mathbb{R}$, we have that $1=1^2\ge 0$, and by totality (O4), since $1\ne 0$, we must actually have $1>0$.

6. Adding Inequalities:

   Given $x\le y$ and $u\le v$. By K1, we can add $u$ to both sides of the first inequality to get $x+u\le y+u$. Similarly, we can add $y$ to both sides of the second inequality to get $u+y\le v+y$. By commutativity (A4), $y+u=u+y$, so we have $x+u\le y+u$ and $y+u\le y+v$. By transitivity (O2), $x+u\le y+v$.

7. Multiplying Inequalities:

   Given $0\le x\le y$ and $0\le u\le v$. Since $x\le y$ and $u\ge 0$, by K2 and distributivity, we have $x\cdot u\le y\cdot u$ (multiplying both sides by u). Since $u\le v$ and $y\ge 0$ (because $y\ge x\ge 0$), by K2, we have $y\cdot u\le y\cdot v$ (multiplying both sides by y). By transitivity (O2), $x\cdot u\le y\cdot v$.

8. Reciprocal Inequality:

   • ($\Rightarrow$): Given $0<x\le y$. Since $x>0$, its multiplicative inverse $x^{-1}$ exists and $x\cdot x^{-1}=1>0$. We first want to show that $x^{-1}>0$. Assume for the sake of contradiction that $x^{-1}\le 0$. Since $x>0$, by K2, $x\cdot x^{-1}\le 0$. But $x\cdot x^{-1}=1>0$, a contradiction. Thus, $x^{-1}>0$. Similarly, $y^{-1}>0$. Now, multiply both sides of $x\le y$ by $x^{-1}$ (which is positive). By (a generalized form of) K2, we get $x\cdot x^{-1}\le y\cdot x^{-1}$, which simplifies to $1\le y\cdot x^{-1}$. Next, multiply both sides of $1\le y\cdot x^{-1}$ by $y^{-1}$ (which is positive). We get $y^{-1}\le y^{-1}\cdot y\cdot x^{-1}=1\cdot x^{-1}=x^{-1}$. Thus, $0<y^{-1}\le x^{-1}$.

   • ($\Leftarrow$): Given $0<y^{-1}\le x^{-1}$. By a similar argument as above, $x>0$ and $y>0$. Multiplying both sides of $y^{-1}\le x^{-1}$ by $y$ gives $1\le x^{-1}\cdot y$. Multiplying both sides by $x$ gives $x\le y$. Thus, $0<x\le y$.

The Archimedean Principle

Statement: Let $x\in \mathbb{R}$ with $x>0$, and let $y\in \mathbb{R}$. Then there exists an $n\in \mathbb{N}$ such that $y<n\cdot x$.

Proof

Not that important IMO…

The idea is to use proof by contradiction, leveraging the order completeness (V) of the real numbers.

1. Assume the opposite: Suppose, for the sake of contradiction, that the Archimedean Principle is false. This means there exists some $x>0$ and some $y\in \mathbb{R}$ such that for all $n\in \mathbb{N}$, we have $n\cdot x\le y$.

2. Define a set: Consider the set $A=\{n\cdot x\mid n\in \mathbb{N}\}$. Our assumption implies that $A$ is bounded above by $y$ (i.e., every element of $A$ is less than or equal to $y$). Also, $A$ is non-empty since, for example, $0=0\cdot x\in A$ (as $0\in \mathbb{N}$).

3. Apply Order Completeness (V): Since $A$ is a non-empty subset of $\mathbb{R}$ that is bounded above, by the order completeness axiom (V), $A$ has a least upper bound (supremum). Let $s=\sup (A)$. This means:

   • $s$ is an upper bound for $A$: $n\cdot x\le s$ for all $n\in \mathbb{N}$.
   • $s$ is the least upper bound: If $t<s$, then $t$ is not an upper bound for $A$ (meaning there exists some $n\in \mathbb{N}$ such that $t<n\cdot x$).

4. Derive a contradiction: Since $x>0$, we have $s-x<s$. Because $s$ is the least upper bound, $s-x$ cannot be an upper bound for $A$. Therefore, there exists some $m\in \mathbb{N}$ such that $s-x<m\cdot x$.

5. Rearrange and find a larger element: Adding $x$ to both sides of the inequality $s-x<m\cdot x$, we get $s<m\cdot x+x=(m+1)\cdot x$. Since $m\in \mathbb{N}$ and $1\in \mathbb{N}$, we have $m+1\in \mathbb{N}$. Let $n=m+1$. Then $n\in \mathbb{N}$, and we have $s<n\cdot x$.

6. Contradiction: We now have $n\cdot x\in A$ (because $n\in \mathbb{N}$), and $s<n\cdot x$. But this contradicts the fact that $s$ is an upper bound for $A$ (since $s$ should be greater than or equal to every element of $A$).

7. Conclusion: Our initial assumption that the Archimedean Principle is false must be incorrect. Therefore, the Archimedean Principle holds: for any $x>0$ and any $y\in \mathbb{R}$, there exists an $n\in \mathbb{N}$ such that $y<n\cdot x$.

Intuition: The Archimedean Principle essentially states that no matter how small a positive number $x$ is, and no matter how large a number $y$ is, you can always add $x$ to itself enough times (a finite number of times, $n$) to exceed $y$. This principle is a fundamental property of the real numbers and reflects the lack of “infinitely small” or “infinitely large” elements in $\mathbb{R}$ (in the standard sense).

Theorem: Existence of Square Roots

Theorem 1.1.8:

For every $t\in \mathbb{R}$, $t>0$, the equation $x^2=t$ has a solution in $\mathbb{R}$.

Remark: For $t\ge 0$, there exists exactly one solution of $x^2=t$ with $x\ge 0$. This unique non-negative solution is denoted by $\sqrt{t}$.

Proof

For $t=0$, the statement is trivially true since $x=0$ is a solution. Therefore, let’s assume $t>0$.

We define two sets:

• $A=\{y\in \mathbb{R}\mid y\ge 0,y^2\le t\}$
• $B=\{z\in \mathbb{R}\mid z>0,z^2\ge t\}$

We will apply the order completeness axiom (V) to sets $A$ and $B$. To do this, we need to verify the preconditions:

Preconditions

1. Non-emptiness

• $A\ne \varnothing$: Since $0^2=0\le t$ and $0\ge 0$, we have $0\in A$.
• $B\ne \varnothing$: By the Archimedean Principle, there exists an $n\in \mathbb{N}$ with $n\ge 1$ and $n\ge t$. Therefore, $n^2\ge n\cdot 1=n\ge t$ by transitivity, and $n$ is positive by construction, which means that $n\in B$, so $B$ cannot be empty.

2. Condition for Completeness Axiom (V)

We need to show that $\forall y\in A,\forall z\in B:y\le z$.

Let $y\in A$ and $z\in B$. Then $y^2\le t\le z^2$.

Since $y\ge 0$ and $z>0$, consider $(z-y)(z+y)=z^2-y^2\ge 0$. Since $z+y>0$ (as both are positive), we can divide by $z+y$ and maintain the inequality, implying that $z-y\ge 0$. This is true since K2 (compatibility axiom) states that $(x\ge 0\wedge y\ge 0)⟹xy\ge 0$ and since the multiplicative inverse is unique, and $z+y$ is positive (and therefore $z+y\ne 0$), if we assume $z-y<0$ then multiplying by $(z+y)$ we have $(z-y)(z+y)<0$ by K2, which is a contradiction.

Thus $z-y\ge 0$, so $z\ge y$.

Apply the Completeness Axiom (V)

Since $A$ and $B$ are non-empty and satisfy the condition that every element of $A$ is less than or equal to every element of $B$, by the order completeness axiom (V), there exists a $c\in \mathbb{R}$ such that $\forall y\in A,\forall z\in B:y\le c\le z$. The provided proof is mostly correct, but there’s a subtle issue in Case 2 that needs to be addressed for complete rigor. The reasoning for $c-\frac{1}{n}>0$ is not entirely sufficient and needs to be more explicit. Also, the use of '$d$' in both cases is not ideal, as they represent different quantities.

Show $c^2=t$:

We will prove $c^2=t$ by showing that both $c^2<t$ and $c^2>t$ lead to contradictions.

Case 1: Assume $c^2<t$:

This implies $c\in A$. Define $d_1=t-c^2>0$. By the Archimedean Principle, there exists an $n\in \mathbb{N}$ with $n>1$ and $2c+1\le n\cdot (t-c^2)=n\cdot d_1$. Therefore, $\frac{2c+1}{n}\le d_1$. Now consider $(c+\frac{1}{n}{)}^2$:

So, $(c+\frac{1}{n}{)}^2\le t$. Since $c+\frac{1}{n}>c\ge 0$, this means $c+\frac{1}{n}\in A$. But $c+\frac{1}{n}>c$, which contradicts the fact that $c$ is an upper bound for $A$.

Case 2: Assume $c^2>t$:

This implies $c\in B$. Define $d_2=c^2-t>0$. By the Archimedean Principle, there exists an $n\in \mathbb{N}$ such that $2c<n(c^2-t)=n\cdot d_2$. Also, since $c>0$ (because $c\in B$), the Archimedean principle also guarantees we can choose $n$ large enough so that $n>\frac{1}{c}$, which implies $c>\frac{1}{n}$, and therefore $c-\frac{1}{n}>0$. We can satisfy both Archimedean conditions by choosing $n$ large enough.

Now consider ${\left(c-\frac{1}{n}\right)}^2$:

So, ${\left(c-\frac{1}{n}\right)}^2>t$. Since $c-\frac{1}{n}>0$ (as shown above), this means $c-\frac{1}{n}\in B$. But $c-\frac{1}{n}<c$, which contradicts the fact that $c$ is a lower bound for $B$ (since $c\le z$ for all $z\in B$).

Since both $c^2<t$ and $c^2>t$ lead to contradictions, we must have $c^2=t$. Therefore, a solution to $x^2=t$ exists in $\mathbb{R}$.

Continue here: 02 Real Numbers, Min, Max, Bounds, Supremum, Infimum, Cardinality, Euclidian Space