用户: Yao/集合论

1ZF

Extensionality	If $X$ and $Y$ have the same elements, then $X=Y$.
Separation	For any set $X$ and formula $\phi$, there is a set $\{u\in X\mid \phi (u)\}$.	Then $X\cap Y=\{u\in X\mid u\in Y\}$.
Pairing	For any $a$ and $b$, there is a set $\{a,b\}$.	Then $\{a\}=\{a,a\}$, $(a,b)=\{\{a\},\{a,b\}\}$.
Union	For any $X$, there is a set $\bigcup X$.
Power	For any $X$, there is a set $\mathcal{P}(X)$.	Then $X\times Y$ is a subset of $\mathcal{PP}(X\cup Y)$.
Infinity	There is a set $X$ s.t. $\varnothing \in X$ and $x\in X\to x^{+}:=x\cup \{x\}\in X$.	This is called an inductive set.
Replacement	If a class $F$ is a function, then for any $X$ there is a set $\{F(x)\mid x\in X\}$.
Regularity	Every nonempty set has an $\in$-minimal element.	This implies $x\notin x$.
Choice	Every family of nonempty sets has a choice function.	The first eight constitute ZF, and all nine ZFC.

Zorn’s Lemma	A partially ordered set each chain (linearly ordered) of which has a upper bound has a maximal element.
Well–Ordering	Every set can be well–ordered.
Hausdorff	There is a maximal chain for any partially ordered set.

2Cardinal

partial ordering	$p\nless p$ and $p<q,q<r\Rightarrow p<r$
linear ordering	moreover $p<q$ or $p=q$ or $p>q$
well–ordering	moreover every nonempty subset has a least element
transitive	every element of $T$ is a subset of $T$
ordinal	transitive and well–ordered by $\in$
successor ordinal	$\alpha =\beta +1$
limit ordinal	$\alpha =\sup \{\beta \mid \beta <\alpha \}=\bigcup \alpha$
cardinal	$\alpha$ such that $|\alpha |\ne |\beta |$ for all $\beta <\alpha$
$\omega$	the least infinite cardinal
cardinal successor	${\alpha }^{+}$ is the least cardinal greater than $\alpha$
cofinality $\mathrm{cf}\alpha$	the least limit ordinal $\beta$ s.t. there is an increasing $({\alpha }_{\xi }{)}_{\xi <\beta }$ with $\bigcup _{\xi <\beta }{\alpha }_{\xi }=\alpha$
regular cardinal	$\mathrm{cf}\alpha =\alpha$ (singular if $\mathrm{cf}\alpha <\alpha$)
strong limit cardinal	$\lambda <\kappa \to 2^{\lambda }<\kappa$ (example: ${\aleph }_0$)
successor cardinal	${\aleph }_{\alpha +1}$ (limit cardinal otherwise)
weakly inaccessible	uncountable regular limit cardinal (not provable in ZFC)
inaccessible	uncountable regular strong limit cardinal
weakly compact	uncountable and $\kappa \to (\kappa {)}^2$ (is inaccessible)
GCH	$2^{{\aleph }_{\alpha }}={\aleph }_{\alpha +1}$
SCH	$2^{\mathrm{cf}\kappa }<\kappa \to {\kappa }^{\mathrm{cf}\kappa }={\kappa }^{+}$

$\alpha +0=\alpha$	$\alpha +(\beta +1)=(\alpha +\beta )+1$ for all $\beta$	$\alpha +\beta =\bigcup _{\xi <\beta }(\alpha +\xi )$ for limit $\beta$
$\alpha \cdot 0=0$	$\alpha \cdot (\beta +1)=\alpha \cdot \beta +\alpha$ for all $\beta$	$\alpha \cdot \beta =\bigcup _{\xi <\beta }\alpha \cdot \xi$ for limit $\beta$
${\alpha }^0=1$	${\alpha }^{\beta +1}={\alpha }^{\beta }\cdot \alpha$ for all $\beta$	${\alpha }^{\beta }=\bigcup _{\xi <\beta }{\alpha }^{\xi }$ for limit $\beta$
${\aleph }_0=\omega$	${\aleph }_{\alpha +1}={\aleph }_{\alpha }^{+}$	${\aleph }_{\alpha }=\bigcup _{\beta <\alpha }{\aleph }_{\beta }$ for limit $\alpha$

$1+\omega =\omega \ne \omega +1$

$2\cdot \omega =\omega \ne \omega \cdot 2=\omega +\omega$

$\beta <\gamma \Rightarrow \alpha +\beta <\alpha +\gamma ,\alpha \cdot \beta <\alpha \cdot \gamma ,{\alpha }^{\beta }<{\alpha }^{\gamma }$

$\alpha <\beta \Rightarrow \exists !\delta$ s.t. $\alpha +\delta =\beta$

$\alpha \beta =\{\alpha \xi +\eta :\xi <\beta ,\eta <\alpha \}$

if $1\le \alpha <\beta$, then $\exists !\xi$ and $\eta <\beta$ s.t. $\beta =\alpha \xi +\eta$

Represent $\alpha$ in the unique form where $\alpha \ge {\beta }_1>\cdots >{\beta }_n$ and $k_1,\cdots ,k_n\in \mathbb{N}$ $$\alpha ={\omega }^{{\beta }_1}{k}_1+\cdots +{\omega }^{{\beta }_n}{k}_n.$$

For limit ordinal $\alpha$, $\mathrm{cf}\mathrm{cf}\alpha =\mathrm{cf}\alpha$. (Corollary: $\mathrm{cf}\alpha$ is regular.)

${\aleph }_{\alpha +1}$ is regular.

(Hausdorff) ${\aleph }_{\alpha +1}^{{\aleph }_{\beta }}={\aleph }_{\alpha +1}{\aleph }_{\alpha }^{{\aleph }_{\beta }}$.

(Tarski) ${\aleph }_{\alpha +\gamma }^{{\aleph }_{\beta }}={\aleph }_{\alpha +\gamma }^{\gamma }{\aleph }_{\alpha }^{{\aleph }_{\beta }}$ for $\gamma \le {\aleph }_{\beta }$.

For infinite $\kappa$, $\kappa <{\kappa }^{\mathrm{cf}\kappa }$.

(König) ${\kappa }_i<{\lambda }_i$, then $\sum {\kappa }_i<\prod {\lambda }_i$.

Corollary: $\mathrm{cf}({\aleph }_{\alpha }^{{\aleph }_{\beta }})>{\aleph }_{\beta }$.

$\kappa ,\lambda$ are infinite, then $$\{\begin{array}{l}\kappa \le \lambda \to {\kappa }^{\lambda }=2^{\lambda }\\ {\mu }^{\lambda }\ge \kappa \text{ for some }\mu <\kappa \to {\kappa }^{\lambda }={\mu }^{\lambda }\\ \kappa >\lambda ,(<\kappa {)}^{\lambda }<\kappa \to \{\begin{array}{l}\mathrm{cf}\kappa >\lambda \to {\kappa }^{\lambda }=\kappa \\ \mathrm{cf}\kappa \le \lambda \to {\kappa }^{\lambda }={\kappa }^{\mathrm{cf}\kappa }\end{array}\end{array}$$

For uncountable regular $\alpha$ and continuous increasing $f:\alpha \to \alpha$, $\{\gamma <\alpha :f(\gamma )=\gamma \}$ is a club.

Pf: for all $\beta <\alpha$, $\gamma =\bigcup {\beta }_n$ st ${\beta }_0=\beta$, ${\beta }_{n+1}=f({\beta }_n)+1$ satisfies $f(\gamma )=\gamma$.

3Filter

filter on $S$	$S\in F$, $\varnothing \notin F$, $X,Y\in F\to X\cap Y\in F$, $X\in F,X\subset Y\to Y\in F$
examples	trivial $\{S\}$, principal $\{X\supset X_0\}$
$\kappa$-complete	$X_{\alpha }\in F\to \bigcap _{\alpha <\gamma }{X}_{\alpha }\in F$ for $\gamma <\kappa$
ideal on $S$	$\varnothing \in I$, $S\notin I$, $X,Y\in I\to X\cup Y\in I$, $X\in I,Y\subset X\to Y\in I$
examples	trivial $\{\varnothing \}$, principal $\{X\subset X_0\}$, $0$-measure set
ultrafilter	either $X\in U$ or $S-X\in U$ (example: $\{X\ni a\}$)
prime ideal	either $X\in I$ or $S-X\in I$ (example: $\{X\not\ni a\}$)
measurable	uncountable, exist a $\kappa$-complete nonprincipal ultrafilter on $\kappa$
implies	regular, inaccessible
closed	contain all limit points less than $\kappa$, i.e. $\sup (X\cap \gamma )=\gamma <\kappa \to \gamma \in X$
unbounded	$\sup X=\kappa$, i.e. for all $\lambda <\kappa$, exist $\lambda <\xi \in X$
club filter	$\{X\subset \kappa :X$ contains a club$\}$
stationary	$S$ intersects each club of $\kappa$
diagonal intersection	${△}_{\alpha <\kappa }{X}_{\alpha }=\{\xi <\kappa :\xi \in \cap X_{<\xi }\}={\bigcap }_{\alpha }(X_{\alpha }\cup \{\xi \le \alpha \})$
diagonal union	${▽}_{\alpha <\kappa }{X}_{\alpha }=\{\xi <\kappa :\xi \in \cup X_{<\xi }\}={\bigcup }_{\alpha }(X_{\alpha }\cap \{\xi >\alpha \})$
normal filter	closed under diagonal intersections
Fodor	$f$ is regressive on stationary $S\subset \kappa$, then $f{|}_T\equiv \gamma$ for some stationary $T$ and $\gamma <\kappa$
Solovay	for uncountable regular $\kappa$, every stationary subset of $\kappa$ is the disjoint union of $\kappa$ stationary subsets
Mahlo	inaccessible $\kappa$ st $\{$regular $<\kappa \}$ is stationary
weakly Mahlo	weakly inaccessible $\kappa$ st $\{$regular $<\kappa \}$ is stationary
Ramsey	every partition of $[\omega {]}^n$ into $\{X_i{\}}_{i=1,\cdots ,k}$ has an infinite homogeneous set $H$ ($[H{]}^n\subset X_i$), written ${\aleph }_0\to ({\aleph }_0{)}_k^n$
tree	a partially oredered set such that $\{y:y<x\}$ is well–ordered for all $x$
Suslin line	a dense (always $c\in (a,b)$) linearly ordered set with countable chain condition ($⨄(a_{\alpha },b_{\alpha })$ is countable) but not separable
Suslin tree	$\mathrm{height}T={\omega }_1$, every branch (maximal linearly ordered subset) is at most countable, every antichain (incomparable) is at most countable

$u+v=v+u$	$uv=vu$
$u+(v+w)=(u+v)+w$	$u(vw)=(uv)w$
$u(v+w)=uv+uw$	$u+vw=(u+v)(u+w)$
$u(u+v)=u$	$u+uv=u$
$u+(-u)=1$	$u(-u)=0$
$+$ is $\cup$, $\cdot$ is $\cap$, $0$ is $\varnothing$, $1$ is $S$	$+$ is $\vee$, $\cdot$ is $\wedge$, $0$ is wrong, $1$ is true
$u\le v$ means	$u-v:=u(-v)=0$
iff	$u+v=v$; $uv=u$

4Model

${\Delta }_0$ formula	a formula consisting of $\in ,=,\wedge ,\vee ,\neg ,\to ,\leftrightarrow$ or $(\exists x\in y)\phi$ or $(\forall x\in y)\phi$
${\Sigma }_1$ formula	$\exists x_1\cdots \exists x_n\phi$ where $\phi$ is ${\Delta }_0$ (like $|X|\le |Y|$, $|X|=|Y|$)
${\Pi }_1$ formula	$\forall x_1\cdots \forall x_n\phi$ where $\phi$ is ${\Delta }_0$ (like $\alpha$ is a (regular/limit) cardinal)
$(\forall x\phi {)}^M$	$(\forall x\in M){\phi }^M$
$(\exists x\phi {)}^M$	$(\exists x\in M){\phi }^M$
$\phi$ is absolute for model $M$, $M{⪯}_{\phi }V$, $M$ reflects $\phi$	${\phi }^M\leftrightarrow \phi$
elementary embedding $f:\mathfrak{A}⪯\mathfrak{B}$	$\mathfrak{A}\models \phi (a_1,\cdots ,a_n)\leftrightarrow \mathfrak{B}\models \phi (f(a_1),\cdots ,f(a_n))$
Skolem function $h:M^n\to M$	$\exists a,\mathfrak{A}\models \phi [a,a_1,\cdots ,a_n]$ implies $\mathfrak{A}\models \phi [h(a_1,\cdots ,a_n),a_1,\cdots ,a_n]$
$X$ is definable in $\mathfrak{A}$ from $a_1,\cdots ,a_n$	$X=\{x\in M:{\phi }^M(x,a_1,\cdots ,a_n)\}=\{x\in M:\mathfrak{A}\models \phi [x,a_1,\cdots ,a_n]\}$ for some formula $\phi$ and $a_1,\cdots ,a_n\in M$
example	$X\subset$ transitive $M$ is definable as $X=\{x\in M:(M,\in )\models (v_0\in v_1)[x,X]\}$
Reflection Principle	for each $M_0$ there is transitive $M\supset M_0$ st $M$ reflects $\phi$
ibid	for each $M_0$ there is $V_{\alpha }\supset M_0$ for some limit $\alpha$ st $V_{\alpha }$ reflects $\phi$
ibid	assuming AC, for each $M_0$ there is $M\supset M_0$ st $M$ reflects $\phi$ and $|M|\le |M_0|{\aleph }_0$
Generalized RP	$Z_{\alpha }\subset Z_{\beta }$, $Z_{\alpha }=\bigcup _{\beta <\alpha }{Z}_{\beta }$ for limit $\alpha$, $Z=\bigcup _{\alpha \in \mathrm{Ord}}{Z}_{\alpha }$, then there is arbitrarily large limit $\alpha$ st $Z_{\alpha }{⪯}_{{\phi }_1,\cdots ,{\phi }_n}Z$
$\mathrm{def}(M)$	$\{X\subset M:X$ is definable over $(M,\in )\}$
$\mathrm{def}(M)=\mathrm{cl}(M\cup \{M\})\cap \mathcal{P}(M)$	$\mathrm{cl}$ denotes the closure under Gödel operations
$\mathrm{rud}(M)\cap \mathcal{P}(M)=\mathrm{def}(M)$	$\mathrm{rud}(M)$ is the rudimentary closure of $M\cup \{M\}$
$V=\bigcup _{\alpha \in \mathrm{Ord}}{V}_{\alpha }$	$V_0=\varnothing$, $V_{\alpha +1}=\mathcal{P}(V_{\alpha })$, $V_{\alpha }=\bigcup _{\beta <\alpha }{V}_{\beta }$ for limit $\alpha$
$\mathrm{rank}(x)$	$\min \{\alpha :x\in V_{\alpha +1}\}$
$L=\bigcup _{\alpha \in \mathrm{Ord}}{L}_{\alpha }$	$L_0=\varnothing$, $L_{\alpha +1}=\mathrm{def}(L_{\alpha })$, $L_{\alpha }=\bigcup _{\beta <\alpha }{L}_{\beta }$ for limit $\alpha$
inner model of ZF ($L$ is the smallest)	a transitive class that contains all ordinals and satisfies ZF
$J=\bigcup _{\alpha \in \mathrm{Ord}}{J}_{\alpha }$	$J_0=\varnothing$, $J_{\alpha +1}=\mathrm{rud}(J_{\alpha })$, $J_{\alpha }=\bigcup _{\beta <\alpha }{J}_{\beta }$ for limit $\alpha$
if $V=L$	every set is constructible, AC, GCH