[Lecture Summary] 01 Real Anaysis : Set

This contents is based on Lecture of 18.100A of MIT Open Course. Coverage will be Lecture from 1 to 3. link

Definition and Symbols

Basics

• set: collection of objects(or elements)
• empty set($\emptyset$) : set with no elements
• $’:=’$ : define
• …

Set Relation

• subset : $A\subset B$ which means $a\in A \implies a\in B$
• equal : $A=B$ which means $A \subset B$ and $B \subset A$
• proper subset : $A\subsetneq B$ which means $A \subset B$ and $A \neq B$

Building notation

• all $x \in A$ that satisfies property $P(x)$
• $\lbrace x \in A \mid P(x) \rbrace$
• $\lbrace x \mid P(x) \rbrace$

Function $f: A\to B$

• mapping that assigns each $x \in A$ to unique element $f(x)$ in B
• For $C \subset A$,
  • $\lbrace y\in B \mid \exists x in C of y=f(x) \rbrace$
  • $\lbrace f(x) \mid x\in C\rbrace$
• Injective(1-1) : $f(x_1)=f(x_2) \Rightarrow x_1 = x_2$
• Surjective(onto) : $f(A)=B$
• Bijective : 1-1 and onto

Keyt sets

• Natural Numbers $\mathbb{N}=\lbrace 1, 2, 3, \cdots \rbrace$
• Integer $\mathbb{Z}=\lbrace 0, 1, -1, 2, -2, \cdots \rbrace$
• rational numbers $\mathbb{Q}=\lbrace {m\over n} \mid m, n \in \mathbb{Z} \mbox{ and } n \neq 0 \rbrace$
• real numbers $\mathbb{R}$
• imaginary numbers $\mathbb{C}$

Among the above sets, following relatoion satisfies: $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$

Operator

• union : $A\cup B = \lbrace x \mid x\in A \mbox{ or } x \in B\rbrace$
• intersection : $A \cap B = \lbrace x \mid x\in A \mbox{ and } x \in B\rbrace$
• set difference : $A \setminus B = \lbrace x \in A \mid x\notin B\rbrace$
• disjoint : $A^c = \lbrace x \mid x \notin A\rbrace$

De Morgan’s Law

Skipped!

Mathematical Induction

• Problem definition: statement $P(n)$ depending on $n\in N$
• Base Case: prove P(1)
• Inductive step : $P(m) \Rightarrow P(m+1)$

Cardinality

How to be say that two sets have the same size?
According to the Cantor, make pairs of elements!

Definition

• two set $A$ and $B$ has the same size if there exists bijection from $A$ to $B$

Sample and solution

• $\mid A \mid = \mid B \mid$
  • find bijection
• $\mid A \mid$ = n
  • find bijection from $A$ to $\mathbb{N}$
• $\mid A \mid \ge \mid B \mid$
  • find injection from $A$ to $B$
• $\mid A \mid < \mid B \mid$
  • find $\mid A \mid \ge \mid B \mid$ (injection from $A$ to $B$) but $\mid A \mid \ne \mid B \mid$

Countably infinite

• $\mid A \mid = \mid \mathbb{N} \mid$
• if A is finite or countably infinite, then A is countable! O.W., A is uncountable

Examples

Find a bijective function!

• $\mid \lbrace 2n \mid n \in \mathbb{N} \rbrace \mid = \mid \mathbb{N} \mid$
  • $f(n) = 2n$(prove 1-1 and onto!)
• $\mid \lbrace 2n-1 \mid n \in \mathbb{N} \rbrace \mid = \mid \mathbb{N} \mid$
• $\mid \mathbb{N} \mid = \mid \mathbb{Z} \mid$
• $\mid \lbrace q \in \mathbb{Q} : q>0 \rbrace \mid = \mid \mathbb{N} \mid$
  • Use it is a set of rational numbers! It can be represented with ratio of prime numbers.

As to the first and second examples, cardinality is independent of set operation(Cardinality is the same even if it seems twice of the cardinality of natural numbers)

There are twice as many numbers as numbers by Feynman

Theorem

• $\mid A \mid = \mid B \mid$ and $\mid B \mid = \mid A \mid$
• $\mid A \mid = \mid B \mid$ and $\mid B \mid = \mid C \mid$ then $\mid A \mid = \mid C \mid$

Power set

For a given set $A$, the power set of $A$ is
$ \mathcal{P}(A) = \lbrace B: B\subset A \rbrace $. Therefore, if $\mid A \mid = n$, then $\mid \mathcal{P}(A)\mid = 2^n$

Theorem

• If A is a set, then $\mid A \mid < \mid \mathcal{P}(A)\mid$
• $\mid \mathbb{N} \mid < \mid \mathcal{P}(\mathbb{N})\mid < \mid \mathcal{P}(\mathcal{P}(\mathbb{N}))\mid < \cdots$
  • infinite number of infinite sets!
  • infinity of infinitives

Problems

Is anything bigger than $\mathbb{N}$?

• $\exists \mbox{ set } A s.t. \mid \mathbb{N} \mid< \mid A\mid < \mid \mathcal{P}(A)\mid$?
  • continum hypothesis!

For all $n \in \mathbb{N}\cup \lbrace 0 \rbrace, n<2^n$

Real Numbers

Definition

• Ordered set is a set $S$ with relation $<$ which is called ordering s.t.
  • $\forall x, y \in S, x<y , y<x or x = y$
  • If $x<y \mbox{ and }y<z, \mbox{ then } x<z$
• Bounded Above/Below
  • If $\exists b\in S s.t. \forall x \in E, x\le b$, then $E$ is bounded above and b is uppoer bound for $E$
    • $S$ is an ordered set and $E \subset S$
• least upper bound or Supremum
  • $\forall \mbox { upper bound }b, \mbox{ least upper bound } b_0 \le b$
  • $b_0 = \sup E$
• greatest lower bound or infinimum
  • $\forall \mbox { lower bound }c, \mbox{ greatest lower bound } c_0 > c$
  • $c_0 = \inf E$
• Least Upper Bound Property
  • For ordered set $S$, it has the least upper bound property if
    • $\forall E \subset S s.t. E $ is nonempty and bounded above, supremum is in itself $S$

As to the finimums and supremums, they do not have to belong to the original set. Open interval! Moreover, they do not have to exist always.

Examples

• $\mathbb{Z}$ is an ordered set with $m>n \iff m-n \in \mathbb{N}$
• $\mathbb{Q}$ is an ordered set with $p>q \iff \exists m,n \in \mathbb{N} s.t. p-q = {m\over n}$
• $\mathbb{Q}\times\mathbb{Q}$ is an ordered set with $(q,r)>(s,t) \iff q>s \mbox{ or } q=s \mbox{ and } r>t$
• $-\mathbb{N}$ has least upper bound property!
  • According to the Well-ordering principle of natural numbers, that set has supremum which belongs to that set at the same time.
• $\mathbb{Q}$ does not have least upper bound property!
  • we can find bigger one who belong to $\mathbb{Q}$