### Introduction to Real Analysis pt 1

Hi everyone, here are my notes for the real analysis course I have been taking.

The book I have referred to:

Elementary Analysis: The Theory of Calculus Book by Kenneth A. Ross

## Review

Theorem: [ Rational Root Theorem]

Suppose $c_0,c_1,\dots, c_n$ are integers and $r$ is a rational number satisfying the polynomial equation $$c_nx^n+c_{n-1}x^{n-1}+\dots+c_1x+c_0=0$$ where $n\ge 1,c_n\ne 0, c_0\ne 0.$ If $r=\frac{c}{d}$ where $c,d$ are integers and $(c,d)=1$. Then $c|c_0, d|c_n$.

Example: Prove that $\sqrt[3]{6}$ is not a rational number.

Proof: Note that $\sqrt[3]{6}$ is solution of $x^3-6=0$. But by rational root theorem, the only possible rational solutions of $x^3-6=0$ are $\pm 1, \pm 2, \pm 3, \pm 6$. But none of these eight numbers satisfies $x^3-6=0$.

Example: All numbers of the form $5^n-4n-1$ are divisible by $16$.

Proof: Our $n$th proposition is $$P_n: 5^n-4n-1 \text{ is divisible by } 16$$ The basis for induction $P_1$ is clearly true, since $5^1-4\cdot 1-1=0.$ Proposition $P_2$ is also true because $5^2-4\cdot 2-1=16$. For the induction step, suppose $P_n$ is true. Then $$P_{n+1}= 5^{n+1}-4(n+1)-1=5(5^n-4n-1)+16n.$$ Since $5^n-4n-1$ is divisible by $16$ by induction hypothesis, it follows that $P_{n+1}$ is also divisible by $16.$

## Absolute  values and inequalities

Define: For numbers $a$ and $b$ we define $dist(a,b)=|a-b|$. It represents distance between $a$ and $b$.

•  $|a|\ge 0$ for all $a\in \Bbb{R}$
•  $|ab|=|a|\cdot |b|$ for all $a,b\in \Bbb{R}$
•  Triangle inequality: $|a+b|\le |a|+|b|$ for all $a,b \in \Bbb{R}$

Theorem: $$\text{dist}(a,c)\le \text{dist}(a,b)+\text{dist}(b,c)$$

Proof:  It is enough to show that $$|a-c|\le |a-b|+|b-c|.$$

Note that $$|(a-b)+(b-c)|\le |a-b|+|b-c|.$$ And we are done.

### Exercise:

Problem 1: Prove that $$||a|-|b||\le |a-b|.$$

Proof: It is enough to show that $$(||a|-|b||)^2\le (|a-b|)^2$$ or show $$|a|^2+|b|^2-2|a||b|\le a^2+b^2-2ab$$

or show $$-2|a||b|\le -2ab$$

which is true.

Problem 2: Prove that $$|a+b+c|\le |a|+|b|+|c|.$$

Proof: $$|a+b+c|\le |a+b|+|c|\le |a|+|b|+|c|$$

Remark: Similarly $$|a_1+a_2+\dots +a_n|\le |a_1+a_2+\dots+ a_{n-1}|\le \dots |a_1|+|a_2|+\dots+|a_n|.$$

Problem 3: Let $a,b\in \Bbb{R}$. Show if $a\le b_1$ for every $b_1>b$, then $a\le b$.

Proof: Suppose not. Then $a-b=\epsilon_0>0$. Then consider $b_1=b+\epsilon_0/2$.

## The Completeness Axiom

Definition: Let $S$ be a nonempty subset of $\Bbb{R}$.

•  If $S$ contains a largest element $s_0$ i.e $s_0$ belongs to $S$ and $s\le s_0$ for all $s\in S$, then we call $s_0$ the maximum of $S$ and write $s_0= \text{max } S$.
•  If $S$ contains a least element $s_0$ i.e $s_0$ belongs to $S$ and $s_0\le s$ for all $s\in S$, then we call $s_0$ the minimum of $S$ and write $s_0= \text{min } S$. \end{definition}

Definition: Let $S$ be a non-empty subset of $\Bbb{R}$

• If a real number $M$ satisfies $s\le M$ for all $s\in S$, then $M$ is called an $\textit{upper bound}$ of $S$ and the set $S$ is said to be $\textit{ bounded above}$.
• If a real number $m$ satisfies $s\ge m$ for all $s\in S$, then $m$ is called an $\textit{lower bound}$ of $S$ and the set $S$ is said to be $\textit{ bounded below. }$
•  The set $S$ is said to be $\textit{bounded}$ if it is bounded above and bounded below. Thus $\exists$ $m,M$ st $S\subseteq [m,M]$.

Definition:  Let $S$ be a non-empty subset of $\Bbb{R}$.

• If $S$ is bounded above and has a least upper bound, then we will call it the $\textit{supremum}$ of $S$ or $\text{sup}S$.
•  If $S$ is bounded below and has a maximum lower bound, then we will call it the $\textit{infimum}$ of $S$ or $\text{inf}S$.

Theorem: [Completeness Axiom for $\Bbb{R}$]Every nonempty subset $S$ of $\Bbb{R}$ that is bounded above has a least upper bound i.e  $\text{Sup}S$ exists.

Remark: [Completeness Axiom fails for $\Bbb{Q}$] Consider the set $A=\{r\in \Bbb{Q}:0\le r\le \sqrt{2}\}$. This doesn't have any supremum over $\Bbb{Q}$.

Corollary: Every nonempty subset $S$ of $\Bbb{R}$ that is bounded below has a greatest lower bound $\text{inf}S$.

Proof: Let $-S:=\{-s:s\in S\}$. Since $S$ is bounded below such that there is a $m\in \Bbb{R}$ such that $m\le s\in S$ , we get that $-S$ is bounded above by $-m$. Hence by $\textbf{Completeness axiom}$, we get that $\text{sup}S$ exists.

We claim that $\text{inf}S=-\text{sup}S$.

Let $s_0=\text{sup}(-S)$, we need to prove $-s_0\le s, \forall s\in S$.

If $\text{inf}S\ne -\text{sup}S$ then $\exists$ $t$ such that $t> s_0, t\not\in S, t\le s,\forall s\in S$. But then again consider the negatives, we done.

## Archimedean Property

Theorem: If $a>0$ and $b>0$, then for some positive integer $n$, we have $na>b$.

Proof: [This proof is magical]

Assume that archimedean property fails. Then $\exists a>0, b>0$ such that $na\le b, \forall n\in \Bbb{N}$. Then note that $S=\{na: n\in \Bbb{N}\}$ is bounded by $b$. Using completeness axiom, we get that $\exists s_0$ such that $s_0=\text{sup}S$.

Note that $s_0-a<s_0 \implies \exists n_1\in \Bbb{N}$ such that $s_0-a<n_1a\implies s_0<(n_1+1)a$. Contradiction.

Useful to know.

Claim: If $a>0,$ then $\frac{1}{n} <a$ for some positive integer $n$

Proof: When $b=1$ in the archimedean property.

Claim: If $b>0$, then $b<n$ for some positive integer $n$

Proof:  When $a=1$ in the archimedean property.

Remark: There are many ordered fields which do not satisfy the above two claims.

## Denseness of $\Bbb{Q}$

Theorem: If $a,b\in \Bbb{R}$ and $a<b$, then there is a rational $r\in \Bbb{Q}$ such that $a<r<b$.

We need to show $a<\frac{m}{n}<b$ for some integers $m$ and $n$ where $n>0$, thus we need $an<m<bn$.

Note that $(b-a)>0\implies \exists n$ such that $n(b-a)>1$. So there exists an integer between $nb$ and $na$. And we are done.

### Exercises

Problem 1: Prove that if $a>0$, then there exists $n\in \Bbb{N}$ such that $\frac{1}{n}<a<n$.

Proof: We use the archimedean property which states that

Claim: If $A>0$ and $B>0$, then for some positive integer $n$, we have $nA>B$

Taking $B=1,A=a$ we get that $\exists n_1$ such that $a>\frac{1}{n_1}$.

Taking $B=a, A=1$, we get $\exists n_2$ such that $n_2>a$.

Taking $n=\max(n_1,n_2)$ we are done.

Problem 2: Let $A$ and $B$ be nonempty bounded subsets of $\Bbb{R}$, and let $A+B$ be the set of all sums $a+b$ where $a\in A$ and $b\in B$. Prove that $$\text{sup}(A+B)= \text{sup}(A)+\text{sup}(B)$$

Proof: For all $a\in A, b\in B$, $$a+b\le \text{sup}(A+B)\implies a\le \text{sup}(A+B)-b$$

Hence we have $\text{sup}(A+B)-b$ the upper bound of $A$. So $$\text{sup}A\le \text{sup}(A+B)-b\implies b\le \text{sup}(A+B)-\text{sup}A$$ $$\implies \text{sup}B\le \text{sup}(A+B)-\text{sup}A$$$$\implies \text{sup}A+\text{sup}B\le \text{sup}(A+B).$$

And for the other direction, we clearly have $a\le \text{sup}A, b\le \text{sup}B\implies \max(a+b)\le \text{sup} A+\text{sup} B$

Problem 3: Let $a,b\in \Bbb{R}$. Show that if $a\le b+1/n$ for all $n\in \Bbb{N}$, then $a\le b$.

Proof: Suppose not. Then $a-b>0.$ So by the archimedean property, we get that $a-b>1/n$ for some $n$. Which is a contradiction.

Problem 4: Show $\text{sup}A=\{r\in \Bbb{Q}:r<a\}=a$ for each $a\in \Bbb{R}.$

Proof: If $\text{sup}A=a_0\ne a$, then by denseness of $\Bbb{Q}, \exists a_0<r_0<a.$

Well, yeah that's it for this blog post! Stay tuned for part two :)!

~Sunaina Pati

### The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

### LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

### Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong