Probability

sample space - $\Omega$ set of all possible outcomes of experiment
- $\omega \in \Omega$ - sample outcome
- $E \subset \Omega$ - Event
definitions
- Let $A_i \subset \Omega$, the sets are increasing if $A_{i} \subset A_{i + 1}$, and $lim_{n \rightarrow \infty} = \bigcup_i A_i$
  - If $A_i \supset A_{i + 1}$, then the sets are decreasing and $lim_{n \rightarrow \infty} = \bigcap_i A_i$
- probability
  - A function $f : \Omega \rightarrow [0,1]$ is a probability measure or a distribution if
    - For each $A \subset \Omega$, $f(A) \geq 0$ (non-neg)
    - $f(\Omega) = 1$
    - Given $(A_i)i, A_i \cap A_j = \emptyset, i \not = j, f(\bigcup{i} A_i) = \Sigma_i f(A_i)$
  - properties
    - $f(\emptyset) = 0$, take $\Omega = \Omega + \emptyset, 1 = f(\Omega \cup \emptyset) = f(\Omega) + f(\emptyset)$
independence
- Let $A, B \subset \Omega$, then $A, B$ are independent, if $f(A \cap B) = f(A)f(B)$
- Disjoint events $A, B, A \cap B = \emptyset$ are not independent, $0 = f(\emptyset) = f(A \cap B) = f(A)f(B) > 0$
conditional prob.
- Let $A, B \subset \Omega$, then $\mathbb{P}(A | B) = \frac{\mathbb{P}(AB)}{\mathbb{P}(B)}$
Bayes
- Let $A_1, \cdots, A_k$ be a partition of $\Omega$, that is $A_i$ are disjoint, and $\Omega \subset \cup_i A_i$
  - $\forall B \subset \Omega, \mathbb{P}(B) = \Sigma_i \mathbb{P}(B | A_i) \mathbb{P}(A_i)$
- theorem
  - Using the same partition above, $\mathbb{P}(A_i | B) = \mathbb{P}(A_iB) / \mathbb{P}(B) = \frac{\mathbb{P}(B | A_i) \mathbb{P}(A_i)}{\Sigma_i \mathbb{P}(B | A_i) \mathbb{P}(A_i)}$
problems
- Let $A_i$ be monotone decreasing collection, i.e $A_i \supset A_{i + 1}$, $lim_{n \to \infty} \mathbb{P}(A_n) \rightarrow \mathbb{P}(A)$
- Toss coin until 2 heads, probability that $k$ tosses are needed
  - $k - 1$ positions, $k - 1 / 2^k$?
- Suppose $\mathbb{P}(A_i) = 1, \forall i$, prove $\mathbb{P}(\bigcap_i A_i)$
  - $P(A_1 | A_2) = P(A_1 A_2)$, notice $A_i = \Omega$, i.e $A\subset \Omega \land \mathbb{P}(\Omega) \leq \mathbb{P}(A_i) \rightarrow \Omega \subset A_i$
- Monty Hall Problem
  - Intuition, first choice $2/3$ chance picked empty door, monty opens, intuition affirmed
  - $\Omega = {(\omega_1, \omega_2) : \omega_i : {1,2,3 }}$, where $\omega_1$ is prize-door, $\omega_2$ is door opened
  - Assuming uniform dist. prob. that door-opened is prize door is $1/3$, on first selection there is $1/3$ chance, on second $1/2$
- Event space $\Omega = {c_1, c_2 : c_i \in {1,2}}$, suppose $c_1$ is front, and is $1$, total of 3 chances of happening $2/3$ chance back is green

Analysis

Inadequacy of rationals,
- no $p \in \mathbb{Q}, p = \sqrt{2}$,
  - otherwise fix $p, q \in \mathbb{Z}$, where $(p,q) = 1$, then $\frac{p}{q}^2 = 2$, and $p^2 = 2q^2$, naturally, $2 | p^2$, and $2 | p$, then $4 | 2q^2$, thus $2 | q^2$, and $2 | q$, and $(p, q) = 2$
- Let $A = {p : \mathbb{Q}: p^2 < 2}$, and $B = {q : \mathbb{Q} : q^2 > 2}$, then $A, B$ have no largest (resp. smallest) element
  - Let $A = {p : p^2 < 2} \subset \mathbb{Q}$, $A$ contains no largest element.
  - For $p = max(A)$, construct $q = p - \frac{p^2 - 2}{p + 2} = \frac{2p + 2}{p + 2}$, $2 - q^2 = 2 - \frac{(2p + 2)^2}{(p + 2)^2} = \frac{2(p + 2)^2 - (2p + 2)^2}{(p + 2)^2}$, and $2p^2 + 8p + 8 - 4p^2 - 8p - 4 = 4 - 2p^2 = 2(2 - p^2) > 0$, and $q \in A$, but $q > p$
- For $p = min(B)$
  - Consider $q = p - \frac{p^2 - 2}{p + 2}$, $q < p$
- $p^2 < 2$, then $(p + a)^2 < 2$?, $p^2 + 2pa + a^2 < 2$,and $2pa + a^2 = a(2p + a) < 2 - p^2$
bounded sets
- Suppose $E \subset S$, where $S$ is an ordered set.
  - $E$ is bounded above if $\exists \beta \in S$, where $\forall x \in E, x \leq \beta$
  - $E$ is bound below if $\exists \beta \in S$, where $\forall x \in E, x \geq \beta$
- least upper bound (supremum)
  - Denote $\beta L \iff \forall x \in E, x \leq \beta$, then $min(L)$ (if it exists) is the lub of $E$ if there
- greatest lower bound(infimum)
  - Define similarly, take $max(L)$ (if it exists)
    - When would it not exist? $E$ has no bounds, consider $B$, notice $\beta \in A$ is lower bound, however, there is no maximal element of $A$, so a glb. does not exist
- least upper bound property
  - Property of $S$ (ordered set), if $E \subset S$, $E \not = \emptyset$, and $\exists \alpha \in S, \forall x \in E, x \leq \alpha$, then $sup(E) \in S$ (it exists)
    - Similar case for glb
- $\mathbb{Q}$ does not have lub/glb- proprty, $A$ is non-empty + bound above, but does not have sup
- Let $S$ be ordered set w/ lub prop., take $B \subset S, B \not= \emptyset$, and $\exists \alpha \in S, \forall x \in B, x \geq \alpha$, let $L$ be set of all lower bounds of $B$, then $\alpha = sup(L) \in S$, and $\alpha = inf(B)$
  - Notice, $\alpha \in L$, thus $L \not= \emptyset$, and $\beta = sup(L) \in S$. Furthermore, take $\beta \in B$, then, fix $x \in L$, then $x \leq \beta$, $\beta$ is upper-bound of $B$, thus $\exists \alpha = sup(L) \in S$ (lub-property).
  - Take $\alpha' > \alpha$, where $\forall x \in B, x \leq \alpha'$, then $\alpha' \in L$, and $\alpha$ is not an upper-bound of $L$ (contradiction), thus $\alpha' \leq \alpha$
ordered field
- Field $S$ which is also ordered set, s.t
  - $x, y, z \in S, y < z \to x + y < x + z$
  - $x, y > 0 \to xy > 0$
- properties
  - If $x > 0 \rightarrow -x < 0$
    - Notice $x > 0 \rightarrow 0 = -x + x > -x + 0 = -x$
  - If $x \not= 0$, $xy = x \to y = 1$
    - $1 = x (1/x) = (1/x)xy = (1/x x) = y$
  - If $x > 0 \land y < z \to xy < xz$
    - $x(z - y) > 0 \rightarrow xz - xy > 0 \rightarrow xz > xy$
  - If $x < 0 \land y < z$ then $xy > xz$
    - inverse of above, show $-x(z - y) = -xz + xy > 0$
  - If $x \not= 0$, $x^2 > 0$
    - $x > 0$ apply axiom of ordered field
    - If $x < 0 \rightarrow (-x) > 0 \rightarrow (-x)^2 = x^2 > 0$
  - If $0 < x < y$ then $0 < 1/x < 1/y$
    - $(1/y) > 0$ (contradiction), suppose otherwise, then $y(1/y) < 0 \rightarrow false$
    - $(1/y) < (1/x)$, $x < y \rightarrow x(1/x)(1/y) < y(1/y)(1/x) = 1/y < 1/x$
There exists a set $R \supset \mathbb{Q}$ that has the lub-property
- If $x \in R, y \in R$, and $x > 0$, then there is a positive integer $n$, where $nx > y$ (archimedian property of $\mathbb{R}$)
  - Suppose otherwise, then consider $x \in L = {nx : n \in \mathbb{N}} \not= \emptyset$, and $y \geq nx, \forall x$. Therefore, via the lub property $\alpha \in sup(L)$ exists. Notice, fix $\beta \in L$, where $\alpha - \beta \leq x$ (notice, that this exists is triv.
    - otherwise, continue incrementing). Notice, $\beta = nx$, thus consider $(n + 1)x > \alpha$ (contradiction)
    - finding $\beta$? where $\alpha - \beta \leq x$
    - Consider $\alpha - x < \alpha$, thus $\exists m, mx > \alpha - x$ (how to find $\beta$)
- If $x, y \in \mathbb{R}$, $x < y$, then there exists $p \in \mathbb{Q}$, where $x < p < y$ ($\mathbb{Q}$ is dense in $\mathbb{R}$ )
  - Intuition
    - If $y > x$, then $(y - x) > 0$ -> we can expand this diff to be as large as we want, say 1. Then $\exists n \in \mathbb{Z}, ny - nx > 1$, thus WTS $\exists m \in \mathbb{Z}, m - 1 < nx < m$,
      - Identify set of $\mathbb{Z}$, where $m' < nx$, and take $m = m' + 1$
Proof of n-th root, take $x \in \mathbb{R}$, $\exists y \in \mathbb{R}, y^n = x$. I.e $\forall x \in \mathbb{R}, x > 0 \rightarrow \forall n \in \mathbb{Z}{>0}, \exists y \in \mathbb{R}{>0}, y^n = x$ (and each such $y$ is unique, denoted $^n\sqrt{x}$)
- Take $\frac{x}{1 + x} = L = {y \in \mathbb{R}: y^n < x}$, notice, $x$ is upper-bound of $L$, thus $\alpha = sup(L)$ exists. Notice $(1 + x)^n > x^n$
  - $\alpha^n < x$
    - Intuitively, want to show that if $y^n < x$ (where $y$ is $sup(L)$) $\exists y' > y, y'^{n} < x$, fix $1 > \epsilon > 0$,
      - Then $(y + \epsilon)^n - y^n < \epsilon n(y + \epsilon)^{n - 1} < \epsilon n(y + 1) < x - y^n$
      - Thus $\epsilon < \frac{x - y^n}{n(y + 1)^{n - 1}}$, apply similar logic above, i.e $$y^n - (y - k)^n = (y - (y - k))(y^{n - 1} + y^{n - 2}(y -k) + \cdots + (y -k)^{n - 1}) < kny^{n -1} < y^n - x^n$$
      - Thus, $0 < k < \frac{y^n - x^n}{ny^{n - 1}}$, and $(y - k) < y$, and $(y - k)$ is an upper-bound of $E$, a contradiction
  - $\alpha^n > x$
    - Show there exists $k > 0, y - k$ is upper bound of $E$ (contradicting earlier statement)
If $a, b \in \mathbb{R}$, and $n \in \mathbb{Z}$, then $(ab)^{1/n} = a^{1/n}b^{1/n}$
- Let $\alpha = a^{1/n}, beta = b^{1/n} \in \mathbb{R}$, that $\alpha, \beta \in \mathbb{R}$ exist / are unique and real is proven above.
- Then $ab = \alpha^n \beta^n = (\alpha \beta)^n$, then $(ab)^{1/n} = \alpha \beta = a^{1/n} b^{1/n}$
decimals
- Take $n_0 \leq x$, where $n_0 \in \mathbb{Z}$ is the largest such integer
  - Then take $n_i \leq x - \Sigma_{j < i} \frac{n_i}{10^i}$ (be the largest such integer)
- Let $E = {\alpha = \Sigma_{j < i} \frac{n_i}{10^i}}$, then $x = sup(E)$
complex field
- Let $\alpha \in \mathbb{C}$, then $\alpha = (a, b)$ (ordered pair)
  - Operations, $(a, b) + (c, d) = (a + c, b + d)$, $(a, b)(c, d) = (ac - bd, ad + bc)$
- field axioms
  - Take $(0, 0)$ as additive identity, and $(1, 0)$ as multiplicative identity
  - addition grp.
    - Triv, $-(a, b) = (-a, -b)$, $(a, b) + (0, 0) = (a, b)$ (inverse)
    - $(a, b), (c, d) \in \mathbb{C} \rightarrow (a, b) + (c, d) = (a + c, b + d) = (c + a, d + b) = (c,d) + (a, b)$ (commutative)
      - Fix $(a,b), (c, d), (e, f) \in \mathbb{C}$, then $(a, b) + ((c, d) + (e, f)) = (a, b) + (c + e, d + f) = (a + c + e, b + d + f) = ((a, b) + (c, d)) + (e, f)$
  - multiplicative
    - Arithmetic
- $i = (0, 1)$, $(0, 1)^2 = (-1, 0)$
- conjugation
  - Let $z \in \mathbb{C}, z = a + bi, \overline{z} = a - bi$
  - $\overline{z + w} = \overline{z} + \overline{w}$
  - $\overline{zw} = \overline{z} \overline{w}$
  - $\overline{z} + z = 2Re(z)$ (similar for $z - \overline{z}$)
- $|z| = \sqrt{z \overline{z}}$
  - $|z| > 0$, unless $(a, b) = (0, 0)$, naturally $z \overline{z} > 0$, thus $\sqrt{x}$ exists (see above)
  - $|\overline{z}| = \sqrt{\overline{\overline{z}} \overline{z}} = \sqrt{z \overline{z}} = |z|$
  - $|zw| = |z||w|$
  - $|Re(z)| \leq |z|$ (triangle inequality)
    - $z = a + bi$, then $Re(z) = a$, then $|Re(z)| = \sqrt{aa} = a \leq \sqrt{a^2 + b^2} = |z|$
  - $|z + w| \leq |z| + |w|$ $$|z + w|^2 = z\overline{z} + w\overline{z} + \overline{w}z + \overline{w}w = z \overline{z} + w \overline{w} + 2 Re(z \overline{w}) \leq |z|^2 + |w|^2 + 2|z \overline{w}| = |z|^2 + |w|^2 + 2|z||w| = (|z| + |w|)^2$$
- schwartz
  - If $a_1, \cdots, a_n, b_1, \cdots, b_n \in \mathbb{C}$, then $|\Sigma_i a_i \overline{b_i}|^2 \leq \Sigma_i |a_i|^2 \Sigma_i |b_i|^2$ (i.e $|xy|\leq |x | |y |$)
  - solution 1
    - Set $A = \Sigma_i |a_i|^2, B = \Sigma_i |b_i|^2, C = \Sigma_i a_i \overline{b_i}$
    - Consider $\Sigma_i |Ba_i - Cb_i|^2 = \Sigma_i (Ba_i - Cb_i)(B\overline{a_i} - \overline{C b_i}) = B^2\Sigma_i |a_i|^2 - B\overline{C}\Sigma_i a_i \overline{b_i} - CB\Sigma_ib_i \overline{a_i} + |C|^2 \Sigma_i |b_i|^2 = B^2A - B|C|^2 = B(AB - |C|^2) > 0$. Thus $(AB - |C|^2) > 0$ (as desired)
  - solution 2
Order $<$ on set $E$ is relation (i.e $\subset E \times E$)
- Where $x < y \lor x = y \lor y < x$ (where $\lor$ is XOR) (def)
- $x < y \land y < z \rightarrow x < z$ (transitive)
problems
- Fix $b > 1$
- Let $E \not= \emptyset$ is ordered, suppose $\alpha = lub(E)$, $\beta = glb(E)$
  - Notice $\forall x \in E, \alpha \leq x \land x \leq \beta \rightarrow \alpha \leq \beta$
- Let $A \subset R, A \not= \emptyset$, where $A$ is bounded below (thus $\alpha = inf(A) \in R$), let $-A = {-x : x \in A}$. Prove $inf(A) = -sup(-A)$
  - Take $\alpha = inf(A)$, notice, $-A$ is then bounded above, i.e $-\alpha$, as $\forall x \in A, x \geq \alpha \rightarrow -\alpha \geq -x$, take $\beta = sup(-A)$, and $\beta \leq -\alpha$ (def of lub). Similar case follows for $-\beta \leq \alpha \rightarrow \beta \geq -\alpha \rightarrow \beta = -\alpha$
- Fix $b > 1$
  - If $m, n, p, q \in \mathbb{Z}$, $n > 0, q > 0$, and $r = m/n = p/q$, thus $(b^m)^{1/n} = b^{m/n}$
    - $(b^m)^{1/n} = (b^p)^{1/q}$, notice $((b^m)^{1/n})^{nq} = b^{mq} = b^{np} = ((b^{p})^{1/q})^{nq}$, thus since $nq$-th roots are unique $(b^{m})^{1/n} = (b^p)^{1/q}$
    - Let $r, s \in \mathbb{Q}, b^{r + s} = b^r + b^s$
      - Let $r = m/n, s = p/q$, then $b^{r + s} = b^{\frac{mp + nq}{np}} = (b^{mp + nq})^{1/np} = (b^{mp}b^{nq})^{1/np} = b^{m/n}b^{q/p} = b^rb^s$
        
        Notice, the 2nd equality follows from the above definition, and the 2nd to last follows from the proof that $ab^{1/n} = a^{1/n}b^{1/n}$
    - If $x \in \mathbb{R}$, define $B(x) = {b^t: t \leq x, t \in \mathbb{Q}}$
      - When $r \in \mathbb{Q}, b^r = sup(B(r))$
        
        Notice, $b^{r - 1} \in B(r)$, thus $B(r) \not= \emptyset$, furthermore, $b^r$ is an upper-bound, thus $sup(B(r))$ exists, naturally $sup(B(r)) \leq b^r$. Furthermore, since $b^r \in B(r)$, $b^r \leq sup(B(r))$, thus $b^r = sup(B(r))$
      - Naturally, for $x \in \mathbb{R}$, $B(r) \not= \emptyset$ ($\mathbb{Q}$ is dense in $\mathbb{R}$), similarly, $B(r)$ has an upper-bound (apply archimedian prop. for some $r \in \mathbb{Q}$), and $sup(B(x))$ exists
    - Prove that $b^{x + y} = b^x b^y$ $\forall x, y \in \mathbb{R}$
      - Notice, for $t \in \mathbb{Q}, t \leq x + y \rightarrow \exists s \leq x, r \leq y, t = s + r \leq x + y$
        
        Trivial, i.e take $t - y, x$ (apply density of rationals) set this as $r, s = t - r$
      - Strategy
        
        Show that $B(x + y) = B(x)B(y)$
        
        Fix, $\alpha \in B(x + y)$, then $\alpha = b^t, t \in \mathbb{Q}, t = r + s \leq x + y$, and $b^r \in B(x), b^s \in B(y), b^{r + s} \in B(x)B(y)$
        
        Fix $b^r \in B(x), b^s \in B(y)$, naturally $b^rb^s = b^{r + s} \in B(x + y)$ ($r + s \leq x + y$)
        
        Then show that $sup(A) = sup(B)sup(c)$ (for all such sets having the above property)
        
        Consider $\alpha \in B(x)B(y)$, then $\alpha = b^rb^s, b^r \in B(x), b^s \in B(y)$, thus $b^rb^s \leq sup(B(x))sup(B(y))$
- Fix $b > 1$, $y > 0$, and prove that there is a unique $x \in \mathbb{R}$, $b^x = y$
  - For $n \in \mathbb{Z}_{>0}$, $b^n - 1 \geq n(b - 1)$
    - Notice $b^n - 1 = (b - 1)(b^{n - 1} + \cdots + 1) \geq (b - 1)n$, notice, $\forall n \in \mathbb{Z}_{\geq 0}, b^n \geq 1$ (from hyp.)
    - $b' - 1 \geq n(b'^{1/n} - 1)$
      - Take above w/ $b' = b^{1/n}$
    - If $t > 1$, and $n > \frac{b - 1}{t - 1}$
      - Apply above, i.e $(t - 1)n < b -1 < n(b^{1/n} -1)$
    - If $w \in \mathbb{R}$, where $b^w > y$, then $b^{w - 1/n} > y$
      - Notice $\frac{b^w}{y} > 1$, thus apply above to find $n$, specifically $\frac{b -1}{\frac{b^w}{y} - 1}$, thus $b^{1/n} < b^{w}/y$, and $y < b^w/b^{1/n}
    - If $b^w < y$, then there exists $n$, where $b^{w + 1/n} < y$,
      - Same principle w/ $t = \frac{y}{b^w}$
    - Let $A = {w : b^w < y}$, and show that $x = sup(A), b^x = y$
      - Suppose $b^x < y$, then $x + 1/n \in A$ (contradiction)
      - Similarly $b^x > y$ is also a contradiction, thus $b^x = y$
    - Uniqueness of $x$?
      - Then $b^{x - x'} = 1$, thus $x - x' = 0$, and $x = x'$
- No order can be defined on $\mathcal{C}$
  - Notice, $1 > 0$, thus $-1 < 0$, and $i < 0$, however, $i^2 < 0$?
  - Suppose $i > 1$, then $-1 > 0$, thus $0 > 0$? ($1 > 0$)
- Suppose $z = a + bi$, $w = c + di$, define $z < w$ if $a < c$ or $a = c$, and $b < d$
  - Notice, fix $z, w \in \mathbb{C}$, then WLOG $a > c$ ($z > w$) or $a = c$, $b = d$ or WLOG $b < d$
  - Suppose $x < w$, and $w < z$ (transitive)
    - Notice if $w.1 = z.1$, then, since $x.1 \leq w.1$ $x.1 \leq z.1$ (thus $x < z$)
  - Subset w/ no lub?
- If $z \in \mathbb{C}$, prove that there exists $r \geq 0$, and $w \in \mathbb{C}, |w| = 1$
  - Suppose $z = a + bi$, then $w = \frac{a}{\sqrt{a^2 + b^2}} + \frac{b}{\sqrt{a^2 + b^2}}i$
- Suppose $k \geq 3$, $\bold{x}, \bold{y} \in \mathbb{R}^k$, $|\bold{x} - \bold{y} = d > 0$, and $r > 0$, then
  - $2r > d$, there are infinitely many $\bold{z} \in \mathbb{R}^k$, where $|\bold{z} - \bold{x}| = | \bold{z} - \bold{y}| = r$
    - Consider all scalar multiples?
  - $2r = d$
    - Then $|z - y| + |x - z| = d = |x - y|$
      - Thus there is only one soln
  - $2r < d$
    - Cannot be satisfied (triangle ineq. violated)

Topology

cardinalities
- For $n \in \mathbb{Z}{>0}$, let $J_n$ be the set ${1, \cdots, n }$, let $J = \cup{n \in \mathbb{Z}_{>0}} J_n$
- For set $A$
  - $A$ is finite if $\exists n \in \mathbb{Z}_{n}$, where $A \sim J_n$ ($A$ is isomorphic to) $J_n$
  - $A$ is infinite if $A$ is not finite
  - $A$ is countable if $A \sim J$
  - $A$ is uncountable if $A$ is neither finite nor countable
  - $A$ is at most countable if $A$ is not uncountable
Every infinite subset of a countable set $A$ is countable
Countable union over countable sets is countable
Let $A$ be a countable set, and let $B_n = A^n = {(a_1, \cdots, a_n) : a_i \in A }$, then $B_n$ is countable
- $B_1 = A$ thus $n = 1$ holds. Assume that $B_n$ is countable, then $B_{n + 1} = \bigcup_{a \in A} \bigcup_{b \in B_n} (b_1, \cdots, b_n, a)$, thus $B_{n +1}$ is a countable union of countable sets, and is thus countable
The set of all rationals is countable
- Apply above to $\mathbb{Z}$, i.e $\mathbb{Q} = \mathbb{Z} \times \mathbb{Z}$

Metric Spaces

Let $X$ be a set, and $x \in X$ is a point
- $X$ is a metric space if for $p, q \in X$, $\exists d(p, q) \in \mathbb{R}$ where
  - $d(p, q) > 0$ ($p \not= q$) or $d(p,p) = 0$
  - $d(p, q) = d(q, p)$
  - $d(p, q) \leq d(p, r) + d(r, q)$
$k$-cell - $A \subset \mathbb{R}^k$, where $x \in A \rightarrow \forall i, a_i \leq x_i \leq b_i$ (i.e each coord lines w/in given bounds)
$A \subset \mathbb{R}^k$ is a ball centered at $x \in \mathbb{R}^k$, where $\forall y \in A, |y - x| < r$ (open), $|y - x| \leq r$ (closed)
Balls are convex
- Let $\alpha, \beta \in A$, where $A$ is a ball around $x \in \mathbb{R}^k$, w/ radius $r$, then $|\alpha - x| \leq r$ and $|\beta - x| \leq r$
- Consider $|\lambda \alpha - (1 - \lambda)\beta - x| \leq \lambda | \alpha - x| + (1 - \lambda)|\beta - x| \leq r$ (notice, $0 < \lambda < 1$)
Same results hold for k-cells.
- take $\alpha, \beta \in A$, then $\forall i, a_i \leq \alpha_i \leq b_i, a_i \leq \beta_i \leq b_i$, then $a_i \leq \lambda \alpha_i + (1 - \lambda)\beta_i \leq b_i$
Let $X$ be a metric space
- neighbourhood - $N_r(p) = {x \in X : |p - x| < r } \subset X$, where $r > 0$
- limit point - $E \subset X$, then $p$ is limit point of $E$, if $\forall r \in \mathbb{R}_{> 0}, N_r(p) \backslash {p} \cap E \not= \emptyset$ every neighbourhood of $p$ intersects $E$ (outside of itself)
  - intuition - $p$ is as close to being a part of $E$ as one can get, $p \in \overline{E}$
- If $p \in E$, and $p$ is not a limit point of $E$, then $p$ is an isolated point
  - I.e there is a neighbourhood of $p$ that does not intersect $E$ apart from itself
  - Think of a set of finite points, each spread $r > 0$ away from each other
- $E$ is closed if all limit points of $E$ are in $E$
- $p \in E$ is an interior point of $E$, if $\exists r > 0, N_r(p) \subset E$
- $E$ is open if $\forall p \in E$ $p$ is an interior point
- $E$ is perfect if $E$ is closed, and if every point of $E$ is a limit point
  - $E$ must be infinite? Closed ball in $\mathbb{R}^k$
- $E$ is bounded if $\exists M \in \mathbb{R}, q \in X$, where $\forall x \in X, d(x, q) < M$
- $E \subset X$ is dense in $X$ if $\forall x \in X$ $x$ is a limit point of $E$ or $x \in E$
Every neighbourhood is an open set
- Consider $N_r(p)$, where $r > 0$. Fix $q \in N_r(p)$, then $d(q, p) < r$, thus $r - d(q, p) = \epsilon > 0$. Notice, $\forall x \in N_{\epsilon}(q)$, $d(q, x) < \epsilon$, thus $d(p, q) < d(p, q) + d(q, x) < r$, and $x \in N_r(p)$, thus $N_{\epsilon}(q) \subset N_r(p)$, and $q$ is interior.
If $p$ is a limit point of a set $E$, then every neighbourhood of $p$ contains infinitely many points of $E$
- Suppose $p$ is a limit point of $E$, then consider $N_r(p)$ where $r > 0$, naturally (since $p$ is a limit point), $N_r(p) \cap E \backslash {p} \not = \emptyset$, if this is finite, i.e $a_1, \cdots, a_n$, take $r' < min_{a_i}(d(p, a_i))$, and $N_{r'}(p) \cap E \backslash {p} = \emptyset$ (contradiction).
A set $E$ is open iff its complement is closed
- Forward
  - Suppose $E$ is open, and suppose $x$ is a limit point of $E^c$, that is, $\forall r > 0$, $N_r(x) \backslash {p} \cap E^c \not = \emptyset$, and $x \not \in E$ ($x$ is not interior point), thus $x \in E^c$, and $E^c$ is closed
- Reverse
  - Suppose $E^c$ is closed. Consider $p \in E$, then $\exists r > 0$, where $N_r(p) \cap E^c = \emptyset$ ($p$ is not a limit point of $E^c$), thus $N_r(p) \subset E$, and $p$ is an interior point. Thus $E$ is open
Let ${G_{\alpha}}$ be a collection of open sets, then $B = \cup_{\alpha} G_{\alpha}$ is open
- Suppose $x \in B$, then $\exists \alpha, x \in G_{\alpha}$, thus $\exists r > 0$, where $N_r(x) \subset G_{\alpha} \subset B$, and $B$ is open.
Let ${G_{\alpha}}$ be a collection of closed sets, then $\cap_{\alpha} G_{\alpha}$ is closed.
- consider $(\cap_{\alpha} G_{\alpha})^c = \cup_{\alpha} G_{\alpha}^c$ is open, thus $\cap_{\alpha} G_{\alpha}$ is closed.
For any finite collection of open sets $G_1, \cdots, G_n$ $\cap_i G_i$ is open.
- Suppose $x \in \cap_i G_i$, then $\forall i \exists r_i > 0, N_{r_i}(x) \subset G_i$ (each $G_i$ is open), then take $r = min_i(r_i)$, and $N_r(x) \subset G_i, \forall i$, thus $N_r(x) \subset \cap_i G_i$
- Notice, above does not hold for infinite collections, i.e $\cap_{n \in \mathbb{N}} (-1/n, 1/n) = 0$ (closed)
If $X$ is metric space, and $E \subset X$, then $\overline{E} = E \cup E'$, where $E'$ is the set of all limit-points of $E$
- $\overline{E}$ is closed
- $\overline{E} = E$ iff $E$ is closed
- $\overline{E} \subset F$ for every closed $F \subset X$ where $E \subset F$
  - fix $F$ (closed), where $E \subset F$
    - WTS: a limit point of $E$ is a limit point of $F$, and is thus in $F$
  - Suppose $x$ is a limit point of $E$, then $\forall r > 0$, $N_r(x) \backslash {x} \cap E \not= \emptyset$, similarly, $N_r(x) \backslash {x} \cap F \not= \emptyset$, thus $x$ is a limit point of $F$, and $x \in F$. Thus $\overline{E} = E \cup E' \subset F$
Let $E \not= \empty, E \subset \mathbb{R}$, where $E$ is bound above (thus $sup(E) \in \mathbb{R}$), then $y \in \overline{E}$
- Suppose otherwise, then $\exists r > 0, N_r(y) \backslash {y} \cap E = \emptyset$, as such, $y - r' < y \in N_r(y)$, and $y - r'$ is upper-bound (contradiction)
Suppose $Y \subset X$, then $E$ is open relative to $Y$ when $\forall x \in E, \exists r \ni d(x, q) < r \land q \in Y \rightarrow q \in E$ (what if $q \not \in Y$?)
- Take $X = E \cup {y}$ (where $y$ is isolated), then $E$ is open rel. $Y$ but not $X$
Finite sets can be open....
Suppose $Y \subset X$, $E \subset Y$ is open rel. $Y$ iff $E = Y \cap G$ for some open $G \subset X$
- Forward
  - Notice, for all $x \in E$, there exists $r_x > 0, \forall p \in N_{r_x}(x) \land p \in Y \rightarrow p \in E$. For each $x \in E$, denote $V_x = N_{r_x}(x)$, let $G = \bigcup_{x \in E}V_x$ (naturally, $G$ is open), furthermore, $E \subset G \cap Y$. Fix $p \in G \cap Y$, then $\exists x \in E, p \in N_{r_x}(x)$, and $p \in Y$, thus $p \in E$, and $E = G \cap Y$
- Reverse
  - Suppose $E = Y \cap G$, where $G \subset X$ is open in $X$. Fix $x \in E \rightarrow x \in G \land x \in Y$, naturally, $\exists r > 0, N_r(x) \subset G$, thus, $p \in N_r(x) \in E \iff p \in Y$. As such, $\forall x \in E$, for $r_x, p \in N_{r_x}(x) \land p \in Y \rightarrow p \in E$, and $E$ is open rel. $Y$.

Compactness

Let $X$ be a metric space, an open cover of $E \subset X$, is a collection of open sets ${G_{\alpha}\subset X}$, where $E \subset \bigcup_{\alpha} G_{\alpha}$.
compactness - $E$ is compact, if every open cover ${G_{\alpha}}$ has a finite sub-cover
intuition
- As noticed above, openness / closedness of $E$ depends on the space in which $E$ is enclosed, (i.e a subset of $E$ can be closed if $E$ is open and vice-versa). However, compactness is a property that is independent of the set in which $E$ is enclosed. I.e if $E$ is compact, all subsets of $E$ are compact
Suppose $K \subset Y \subset X$, then $K$ is compact rel. $X$ iff $K$ is compact rel. $Y$
- Forward
  - Suppose $K$ is compact rel. $X$, then for each open-cover ${G_{\alpha}}$ there is a finite sub-cover. Let ${F_{\alpha}}$ be an open cover of $K$ in $Y$, that is $K = \bigcup_{\alpha} F_{\alpha}$, notice, for each $F_{\alpha} = Y \cap G_{\alpha}$, where $G_{\alpha} \subset X$ is open in $X$, then consider ${G_{\alpha}}$, a cover of $K$ in $X$, thus a finite-subcover ${G_{\alpha}'}$ exists, where $L \subset \bigcup_{\alpha} G_{\alpha}'$, and $K \subset \bigcup_{\alpha} G_{\alpha}' \cap Y = \bigcup_{\alpha} F_{\alpha}'$, a finite sub-cover in $Y$!!
- Reverse
  - Suppose $K$ is compact in $Y$, then consider, ${G_{\alpha}}$, an open-cover in $X$, notice, consider $G_{\alpha} \cap Y = F_{\alpha}$, an open-set in $Y$, and $K \subset \bigcup_{\alpha} F_{\alpha}$, and $K \subset \bigcup_{\alpha'} F_{\alpha'}$ (a finite-subcover of ${F_{\alpha}}$), and ${G_{\alpha'}}$ is an open-cover in $X$!!!
Compact subsets of metric spaces are closed
- Suppose $K$ is compact, prove that $K^c$ is open. Fix $p \in K^c$, and denote $\forall q \in K, r_{q} < d(p, q) /2, W_{q} = N_{r_q}(q), V_q = N_{r_q}(p)$. Notice, $K \subset \bigcup_{q \in K} W_q$ (open cover), thus identify finite $(q_i)$, where ${W_{q_i}}$ is finite open cover. and take $r = min_{q_i}(r_{q_i})$, then $N_r(p) \cap K = \emptyset$, thus, $N_r(p) \subset K^c$, and $K^c$ is open, thus $K$ is closed
Closed subsets of compact sets are compact
- Suppose $L \subset K$, and ${G_{\alpha}}$ is an open cover of $L$, then $\bigcup_{\alpha} G_{\alpha} \cup L^c \supset K$, and $L^c$ is open $L$ is closed, thus ${G_{\alpha}'} \cup L^c$ has a finite sub-cover (since $K$ is covered). Notice, even if $L^c$ is included in the finite-subcover ${G_{\alpha}'}$ it can be covered, and $L \subset \bigcup_{\alpha'} G_{\alpha'}$
If $F \subset X$ is closed, and $K$ is compact then $F \cap K$ is closed
- Notice, $K$ is closed, and $F \cap K \subset K$ is closed, and by the above thm. $F \cap K$ is compact.
If ${K_{\alpha}}$ is a collection of compact subsets of metric space $X$, such that the intersection of any finite collection of sets i non-empty, then $\cap_{\alpha} K_{\alpha}$ is non-empty
- Suppose otherwise, take $K \in {K_{\alpha}}$, and suppose $K \cap \bigcap_{\alpha} K_{\alpha} = \emptyset$, then $K \subset \bigcup_{\alpha}K_{\alpha}^c$, notice, ${K_{\alpha}^c}$ is an open-cover of $K$, and thus there are a finite number of $K_{\alpha'}$, where $K \cap \bigcap_{\alpha'} K_{\alpha'} = \emptyset$, a contradiction.
If $E$ is an infinite subset of compact $K$, then $E$ has a limit point in $K$
- Suppose otherwise, then no $p \in K$ is a limit point of $E$, that is, $\forall p \in K, \exists r_p > 0, N_{r_p}(p) \backslash {p} \cap E = \emptyset$. Notice, $E \subset K \subset \bigcup_{p \in K} N_{r_p}(p)$, thus there are finite ${p_i}$, where $E \subset K \subset \bigcup_{p_i} N_{r_{p_i}}(p_i)$, naturally, $\exists p_i, N_{r_{p_i}}(p_i) \backslash {p_i} \cap E \not=\emptyset$ (otherwise, $E$ is at most finite), a contradiction.
If ${I_n}$ is a sequence of intervals in $R^1$, where $I_n \supset I_{n + 1}$, then $\cap_i I_i \not= \emptyset$
- If $I_n = [a_n, b_n]$, then consider the set $B = {b_i}$, notice, $B$ is non-empty, and bound below, by $a_1$, as $a_i \leq a_{i + 1}$, and $a_i \leq b_i$, thus $\beta = inf(B)$ exists in $R$. Notice, $\forall i, b_i \geq \beta$, similatly, $\forall m, a_i \leq a_{i + m} \leq b_{i + 1} \leq b_m$, thus $a_i \leq \beta$. As such, $\forall n, \beta \in I_n$
Let $k > 0$, and suppose each $I_n$ is a k-cell, where $I_n \supset I_{n + 1}$, then $\bigcap_i I_i \not = \emptyset$
- Apply same theorem above, noticing that each $I_n = I_1 \times \cdots \times I_k$ (intervals), and apply above thm. component-wise
Every $k-cell$ is compact
- Suppose $I = I_1 \times \cdots \times I_k \subset \mathbb{R}^k$, where $I_n = [a_n, b_n]$. Suppose that ${G_{\alpha}}$ is an open-cover of $I$ for which no finite sub-cover exists. That is, for each finite sub-cover of ${G_{\alpha}}$, there exists a sub-k-cell of $I$, defined as follows, for each $I_n = [a_n, b_n]$ take the mid-point of each to obtain, $I_n = [a_n, c_n] \cup [c_n, b_n]$ ($c_n = \frac{a_n + b_n}{2}$), notice, this division returns $2^k$ k-cells whose union is $I$, take $I_1$ as one of the k-cells not covered by any finite sub-cover of ${G_{\alpha}}$ (otherwise $I$ is compact). Also notice that for each, $x, y \in I, |x - y| \leq \begin{bmatrix}\Sigma_i (b_n - a_n)^2 \end{bmatrix}^{1/2}$.
- Notice, $I_1$ is also covered by ${G_{\alpha}}$ but not by any finite-sub cover, thus we can infinitely recurse yielding ${I_i}$ k-cells, where
  - $I_n \supset I_{n + 1}$
  - $I_n$ is covered by ${G_{\alpha}}$ but not by any finite sub-cover
  - $x, y \in I_n$, $|x - y| < 2^{-n} \delta$ (prove by induction or manually),
- Furthermote, no $I_n$ is empty, thus take $x \in I_n$, notice, for some $G_{\alpha}$, $x \in G_{\alpha} \rightarrow \exists r > 0, N_r(x) \subset G_{\alpha}$, take $n$ where $2^{-n} \delta < r$, and $I_n \subset G_{\alpha}$ (a contradiction, this is a finite sub-cover).
heine-borel
- The following statements are equivalent for some subset $E \subset R^k$
  - $E$ is closed and bounded
  - $E$ is compact
  - Every infinite subset of $E$ has a limit point in $E$
- 1 -> 2
  - If $E$ is closed and bounded, then $E \subset I$ where $I$ is a k-cell, and is thus compact. Notice $E$ is closed and is a subset of a compact set, and is thus closed.
- 2 -> 3
  - Follows since $E$ is compact
- 3 -> 1
  - Closed?
    - Suppose otherwise, then take $p$ which is limit point of $E$, and construct the set $E' = {x \in E: |x - p| < 1/n}$, this set is infinite as $p$ is limit point of $E$, whose only limit point is $p$, thus $p \in E$ (contradiction).
  - Bounded?
    - Take $x_n \in E, |x_n| > n$ (that this set is infinite follows from it not being bounded), notice, the set of $x_i$ does not have a limit point in $E$, contradiction.
weierstass
- Every bounded infinite subset of $R^k$ has a limit point in $R^k$
  - Notice, suppose $E \subset R^k$, is bounded, then $E$ is contained in a k-cell which is compact, thus $E$ being infinite subset of a compat set has a limit point in $R^k$ (corollary of above)

Perfect Sets

Let $P$ be a non-empty perfect set in $R^k$, then $P$ is uncountable
- Notice, $P$ is closed and has limit points, thus $P$ is infinite. Label each $x_i \in P$, then for each $x_i$, define $V_i$, where $V_i = N_{r_i}(x_i)$, $V_{i + 1} \subset V_i$, and $V_{i} \cap P \not= \emptyset$, and $x_i \not \in \overline{V_{i + 1}}$
  - Notice, the 2nd to last prop. holds as each $x_i \in P$ is a limit point of $x_i$
  - The last thm. hold again, as all $r > 0$, $N_r(x_i) \cap P \not = \emptyset$, so one can take $r_{i + 1} < d(x_i, x_{i + 1})$
- As such, $\overline{V_i} \supset \overline{V_{i + 1}}$, thus $K_n = \overline{V_n} \cap P$ is compact, and $K_n \supset K_{n + 1}$, and $x_n \not \in K_{n + 1}$, thus $\cap_i K_n = \emptyset$, a contradicton
connected sets
- separated sets - elet $A, B \subset X$, where $X$ is a metric space. Then $A, B$ are separated if $\overline{A} \cap B = \overline{B} \cap A = \emptyset$, then $A, B$ are separated
- Connected sets- $A$ is connected, if it is not the union of 2 separated sets
$E \subset \mathbb{R}$ is connected iff $x, y \in E, x < z < y \rightarrow z \in E$
- Forward
  - Suppose $E$ is connected, and that $x, y \in E, z \in \mathbb{R}$, where $x < z < y$. Then take $E_1 = {x \in E, x < z}, E_2 = {x \in E, x > z}$
  - Notice $E = E_1 \cup E_2$, and $\overline{E_1} \cap E_2 = \overline{E_2} \cap E_1 = \emptyset$
    - Suppose $x \in \overline{E_1} \cap E_2$, then $x > z$, and $N_{x - z}(x) \cap E_1 = \emptyset$ (similarly in other dir.)
- Reverse
  - Prove contrapositive ($E$ separated, then implicant does not hold)
problems
- $\emptyset \subset A$ (where $A$ is any set)
  - Notice, contrapositive always true, i.e $x \not \in A \rightarrow x \not \in \emptyset$

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

analysis.md

analysis.md

Probability

Analysis

solution 2

Topology

Metric Spaces

Compactness

Perfect Sets

Files

analysis.md

Latest commit

History

analysis.md

File metadata and controls

Probability

Analysis

solution 2

Topology

Metric Spaces

Compactness

Perfect Sets