Random math: 07

Source of most content: Gunhee Cho

Ordered set

Def. Given a set $S$, we call $\leq$ partial order and call $(S, \leq)$ partially ordered set (POSET) if $\leq$ satisfying:

  1. (Reflexibility) $\forall a \in S, a \leq a$.
  2. (Anti-symmetry) If $a \leq b$ and $b \leq a$, then $a=b$.
  3. (Trainsitivity) If $a\leq b, \ b\leq c$, then $a \leq c$.

NB1; Given any set $A$, then $(P(A), \subseteq)$ is POSET.

Def. Given POSET $(S, \leq)$, we call $(S, \leq)$ totally ordered set if $\forall a,b, \in S, a \leq b$ or $b \leq a$.

NB2; Given any set $A$, then $(P(A), \subseteq)$ is not a totally ordered set in general.

Def. Given POSET $(S, \leq)$, we call $\alpha \in S$ maximal (minimal), if $\alpha \leq (\geq) \beta$ then, $\alpha = \beta$.

Def. Given POSET $(S, \leq)$, we call $C \subseteq S$ is a chain if $C$ is totally ordered subset.

Vector space and basis

Zorn’s lemma

\[\text{Given a POSET} (S, \leq), \text{ any chain } C \subseteq S \text{ has upper bound in } S \leadsto \exists \text{maximal } \alpha \in S. \nonumber\]

This holds even when we have infinite chains and this is equivalent to axiom of choice.


\[\text{Given a vector space } V/F, \text{let } S \subseteq V \text{ be linearly independent (L.I.). Then, }\exists \text{maximal L.I. } M \supseteq S. \nonumber\]


Consider $F := \{ A \subseteq V \mid \text{L.I. } A \supseteq S\}$. Since $S \in F, F \ne \emptyset$ and $(F, \subseteq)$ is POSET, take any chain $C \subseteq F$ to apply Zorn’s lemma. Define $U:= \cup_{A \in C} A (\subseteq V)$. If $\forall a_i \in F, \forall v_i \in U, \ a_1 v_1 + \cdots + a_n v_n =0$, then $\exists A_1, \cdots, A_n \in C$ s.t. $v_1 \in A_1, \cdots, v_n \in A_n$ since $v_i \in U = \cup_{A \in C} A$. Since $C$ is a chain, i.e., totally ordered set, we can assume that $A_1 \subseteq A_2, \cdots A_{n-1} \subseteq A_n$ w.l.o.g., i.e., $\forall i = 1, \cdots, n, v_i \in A_n$. Since $A_n \in F$, $A_n$ is linearly independent and $\forall v_i \in A_n \leadsto a_1 = \cdots = a_n = 0$ (L.I.), which implies that $U$ is linearly independent. Thus, by Zorn’s lemma, $\exists$ maximal $M \in F$, i.e., there exists L.I. $M \supseteq S$.


\[\text{Every vector space } V/F \text{ has a basis.} \nonumber\]


Assume that $V\ne \{ 0 \}$ (if $V = \{0\}, V$ is zero-dimensional VS). So, $\exists v \in V - \{0\}$ and let $S:=\{ av \mid a\in F \}$, which is linearly independent. Then, $\exists$ maximal L.I. $M \supseteq S$. Assume that <$M$> $\ne V \Leftrightarrow V \setminus$<$M$>$\ne \emptyset$. Then, $\exists v’\ne 0 \in V \setminus$<$M$>. Since $v’ \not\in$<$M$>, $v’$ cannot be expressed by a linear combination in $M$. Thus, $M\cup \{v’\}$ is linearly independent, i.e., $M \subseteq M \cup \{v’\}$ is L.I. which is a contradiction from the assumption that $M$ is maximal L.I..

NB1; Basis is a maximal independent set.
NB2; Existence of maximal L.I. set is based on the zorn’s lemma which is equivalent to axiom of choice.
NB3; If $\beta, \beta’$ is a basis, then $| \beta | = | \beta’ |$. If not, assume $|\beta | < | \beta’ |$, we know that $\beta, \beta’$ are maximal L.I.. So, $\exists f: \beta \rightarrow \beta’$ s.t. $f$ is injective but not surjective, i.e., $\beta \cong f(\beta) \varsubsetneq \beta’$ which is a contradiction that $\beta$ is maximal.

\[\text{ Given two sets } S_1, S_2, | S_1 | = | S_2 | \Leftrightarrow \exists \text{ bijective } f: S_1 \rightarrow S_2. \nonumber\] \[\text{ Given two sets } S_1, S_2, | S_1 | < | S_2 | \Leftrightarrow \exists \text{ injective but not surjective } f: S_1 \rightarrow S_2. \nonumber\]

Dimension of VS

Def. Given a vector space $V/F$, we call cardinality of any basis of $V$ dimension of $V$ and is denoted by $dimV$ .

  1. If $dimV < \infty$, $V$ is finite-dimensional vector space over $F$.
  2. If not, $V$ is infinite-dimensional vector space over $F$.

Def. Given a finite dimentional vector space $V/F$ where a basis $\beta=\{v_1, \cdots, v_n\}$, then $\forall v \in V, \exists a_1, \cdots, a_n \in F$ s.t. $v=a_1 v_1 + \cdots + a_n v_n$ and $[ v ]_{\beta}=(a_1, \cdots, a_n)$ denotes coordinate of $v$ w.r.t. $\beta$.

\[\text{Given a vector space } V/F, \text{ assume } dimV = n < \infty, \text{ and fix a basis } \beta. \nonumber\] \[\text{ Then, every vector } v \text{ has a unique expression of linear combination by } \beta. \nonumber\]


Let $\beta = \{v_1, \cdots, v_n \}$ be a basis of $V$. Take any $v \in V=$<$\beta$> $\leadsto \exists a_i \in F$ s.t. $a_1 v_1 + \cdots + a_n v_n = v$. If $\exists b_1, \cdots, b_n \in F$ s.t. $a_1 v_1 + \cdots + a_n v_n = b_1 v_1 + \cdots + b_n v_n \Leftrightarrow (a_1 - b_1)v_1 + \cdots (a_n - b_n)v_n =0$. Since $\beta$ is linearly independent, this implies that $a_1 = b_1, \cdots a_n = b_n$.