Set Theory Note

Propositional Logic Note

Propositional Function

Definition

A sentence expressed in a way that would assume the value of true or false.

Link to original

Truth table

Definition

$p$	$q$	$\neg p$	$p\vee q$	$p\wedge q$	$p\to q$	$p\leftrightarrow q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

Facts

$p\to q\equiv \neg p\vee q$

De Morgan's Laws

Definition

$\neg (p\wedge q)\equiv \neg p\vee \neg q$ $\neg (p\vee q)\equiv \neg p\wedge \neg q$

Link to original

Contraposition

Definition

$p\to q\equiv \neg q\to \neg p$

Link to original

Associative Property: $(p\vee q)\vee r\equiv p\vee (q\vee r)$

Distributive Property: $p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$

Link to original

Duality in Logic

Definition

In logic, functions or relations $A$ and $B$ are considered dual if $A(\neg x)=\neg B(x)$. follows are dual

• $\forall \leftrightharpoons \exists$
• $\wedge \leftrightharpoons \vee$
• $p\leftrightharpoons \neg p$
• $<\leftrightharpoons \ge$

Link to original

Tautology

Definition

$t$

A formula or assertion that is true in every possible interpretation

Facts

$\forall$ proposition $p$ $p\vee \neg p\equiv t$ $t\vee p\equiv t$ $t\wedge p\equiv p$

$(p\to q)\wedge (p\to r)\to (p\to r)\equiv t$^[The law of transitivity]

Link to original

Contradiction

Definition

$c$

A formula or assertion that is false in every possible interpretation

Facts

$\forall$ proposition $p$ $p\wedge \neg p\equiv c$ $c\vee p\equiv p$ $c\wedge p\equiv c$

Link to original

Implication

Definition

$p\Rightarrow q$

If the antecedent is true, then the consequent must also be true

Link to original

Necessity

Definition

Suppose $p\Rightarrow q$, then $q$ is necessary for $p$

Link to original

Sufficiency

Definition

Suppose $p\Rightarrow q$, then $p$ is sufficient for $q$

Link to original

Necessary and Sufficient Condition

Definition

$p\Rightarrow q\wedge q\Rightarrow p$

$p$ is necessary for $q$ and $p$ is sufficient for $q$

Link to original

Link to original

Cartesian Product

Definition

$A\times B=\{(a,b)|a\in A\wedge b\in B\}$ where $A,B$ are sets

The set of all ordered pairs $(a,b)$ where $a\in A\wedge b\in B$

Facts

$A\times \varnothing =\varnothing \times A=\varnothing$

$A\times (B\cap C)=(A\times B)\cap (A\times C)$ $A\times (B\cup C)=(A\times B)\cup (A\times C)$

$A\times (B-C)=(A\times B)-(A\times C)$

Link to original

Family of Sets

Definition

A collection of any sets

Operations

Union

$\bigcup F=\bigcup _{A\in F}A=\{x|\exists A\in F,x\in A\}$ $\bigcup F=\bigcup _{i\in I}{A}_i=\{x|\exists i\in I,x\in A_i\}$ where $F$ is an Indexed Family with index set $I$

Intersection

$\bigcap F=\bigcap _{A\in F}A=\{x|\forall A\in F,x\in A\}$ $\bigcap F=\bigcap _{i\in I}{A}_i=\{x|\forall i\in I,x\in A_i\}$ where $F$ is an Indexed Family with index set $I$

Cartesian Product

$\prod A_i=\{({\alpha }_i{)}_{i\in I}|\forall i\in I,{\alpha }_i\in A_i\}$

Facts

$(\bigcup _{A\in F}A{)}^{\complement }=\bigcap _{A\in F}{A}^{\complement }$

$(\bigcap _{A\in F}A{)}^{\complement }=\bigcup _{A\in F}{A}^{\complement }$

$A\cap (\bigcup _{B\in F}B)=\bigcup _{B\in F}(A\cap B)$

$A\cup (\bigcap _{B\in F}B)=\bigcap _{B\in F}(A\cup B)$

Link to original

Relation

Definition

$\mathcal{R}=(X,Y,P(x,y))$ where $P$ is a Propositional Function

A relation over sets $X,Y$ is a new set of ordered pairs $(x,y)$ consisting of $x\in X$ and $y\in Y$.

Solution Set of Relation

$\{(x,y)|x\in X,y\in Y,P(x,y)=\text{true}\}$

A set of ordered pairs for which the result of a Propositional Function is true.

Let $\mathcal{R}:X\to Y$ Domain of $\mathcal{R}$: $\mathrm{Dom}(\mathcal{R})=X$ Codomain of $\mathcal{R}$: $\mathrm{Cod}(\mathcal{R})=Y$ Image of $\mathcal{R}$: $\mathrm{Im}(\mathcal{R})=\{y\in Y|\exists x\in X,x\mathcal{R}y\}$

Operations

Converse

${\mathcal{R}}^{-1}=\{(y,x)|(x,y)\in \mathcal{R}\}$

Composition

Let $\mathcal{R}$ be a relation over sets $X,Y$ and $\mathcal{S}$ be a relation over sets $Y,Z$ $\mathcal{S}\circ \mathcal{R}=\{(x,z)|\exists y\in Y,(x,y)\in \mathcal{R}\wedge (y,z)\in \mathcal{S}\}$

Properties

• Reflectivity
• Symmetricity
• Antisymmetricity
• Transitivity

Classes

• Equivalence Relation
• Partial Order Relation

Facts

$\mathcal{R}\subset A\times B$ A relation is a subset of Cartesian Product

$(F^{-1}{)}^{-1}=F$

$(H\circ G)\circ F=H\circ (G\circ F)$

$(G\circ F{)}^{-1}=F^{-1}\circ G^{-1}$

Link to original

Reflexive Relation

Definition

$\forall x\in X,x\mathcal{R}x$

Link to original

Symmetric Relation

Definition

$x\mathcal{R}y\Rightarrow y\mathcal{R}x$

Link to original

Antisymmetric Relation

Definition

$x\mathcal{R}y\wedge y\mathcal{R}x\Rightarrow x=y$

Link to original

Transitive Relation

Definition

$x\mathcal{R}y\wedge y\mathcal{R}z\Rightarrow x\mathcal{R}z$

Link to original

Equivalence Relation

Definition

A binary Relation $\sim$ on set $X$ that satisfies the following conditions for all $a,b,c\in X$

• Reflective: $a\sim a$
• Symmetric: $a\sim b\Rightarrow b\sim a$
• Transitive: $a\sim b\wedge b\sim c\Rightarrow a\sim c$

Facts

The equivalence relation may be constructed from the Partition

Link to original

Equivalence Class

Definition

$[a]=E_a:=\{s\in S:x\sim a\}$ where $S$ is a set, $\sim$ is a Equivalence Relation on $S$, and $a\in S$

A set of elements that are related to each other by an Equivalence Relation

Facts

Let $X\ne \varnothing$ and $E$ be Equivalence Relation on $X$

• $E_x\ne \varnothing$
• $E_x=E_y\iff xEy$
• $E_x\cap E_y\ne \varnothing \iff xEy$

Link to original

Quotient Set

Definition

Given an Equivalence Relation $(S,\sim )$, $S/\sim :=\{[s]\in S\}$ The set of equivalence classes

Facts

The quotient set form a Partition

Link to original

Partition

Definition

A Family of Sets $P$ satisfies the following conditions, is a partition of $X$

• $\varnothing \notin P$
• $\bigcup _{A\in P}A=X$
• $\forall A,B\in P:A\ne B\Rightarrow A\cap B=\varnothing$

A grouping of its elements into non-empty subsets such that every element is included in exactly one subset.

Facts

${\sim }_P={\mathcal{R}}_P=X/P:=\{(x,y)|\exists A\in P,x,y\in A\}=\{(a,b)|a\in [b]\text{and}b\in [a],x,y\in A\}$ where $P$ is a partition, the result $\mathcal{R}$ is a Equivalence Relation, and $[\cdot ]$ is the element of the partition

The partition may be constructed from the Equivalence Relation

Link to original

Function

Definition

$\forall x\in X,\forall y,z\in Y:((x,y)\in f\wedge (x,z)\in f)\Rightarrow y=z$ where $X,Y$ are sets and $f:X\to Y$

A relation $f:X\to Y$ satisfies following conditions

• $\forall x\in X:\exists y\in Y\text{ s.t. }(x,y)\in f$
• $(x,y)\in f\wedge (x,z)\in f\Rightarrow y=z$

$(x,y)\in f\iff y=f(x)$

$X$ is a Domain of $f$ $Y$ is a Codomain of $f$ $\{f(x)|x\in X\}$ is an Image of a function $f$

Properties

Image and Preimage

Image

$y=f(x)$ is an Image of an element $x$ under $f$ $f(A)=\{f(x)|x\in A\subset X\}$ is an Image of a subset $A$ under $f$

Preimage

$x=f^{-1}(y)$ is a preimage of an element $y$ under $f$ $f^{-1}(B)=\{f^{-1}(x)|x\in B\subset Y\}$ is a preimage of a subset $B$ under $f$

Restriction and Extension

Restriction

$\forall x\in S:f{|}_S(x)=f(x):S\to Y$ where $f:X\to Y$ is a function, $S\subset X$

$f{|}_S(x):S\to Y$ is a restriction of $f$ to $S$

Extension

$f=g{|}_S(x)$

The $g$ is an extension of a function $f$ when $f$ is a restriction of $g$

Injective, Surjective, Bijective Function

Injective

Definition

$\forall a,b\in X:f(a)=f(b)\Rightarrow a=b$

Maps distinct elements of its Domain to distinct elements

Facts

Injective function is an example of an Monomorphism

Link to original

Surjective

Definition

$\forall y\in Y,\exists x\in X,f(x)=y⟺\mathrm{Cod}(f)=Y$ A function is surjective if every element in the function’s codomain is the Image of at least one element of its Domain

Facts

Surjective function is an example of an Epimorphism

If a function $f:X\to Y$ is surjective, then $\forall U\subset Y,f(f^{-1}(U))=U$

Link to original

Bijective

Definition

A function that is both Injective and Surjective

Every element in the Codomain of the function is mapped to by exactly one element in the Domain of the function

Facts

Bijective function is an example of an Isomomorphism

Link to original

Composition

Let $f:X\to Y$ and $g:Y\to Z$ where the Domain of $g$ is the Codomain of $f$ $\forall x:(g\circ f)(x)=g(f(x))$

Classes

• Identity Function
• Constant Function
• Inverse Function
• Inclusion Function
• Indicator Function
• Choice Function

Facts

Even if the function expression is the same, if the Domain is different, is a different function.

e.g. Let $f(x)=x^2$. If $\mathrm{Dom}(f)=\mathbb{R}$, then $f:\mathbb{R}\to {\mathbb{R}}_0^{+}$. On the other hand, if $\mathrm{Dom}(f)=\mathbb{C}$, then $f:\mathbb{C}\to \mathbb{R}$

$g\circ f\ne f\circ g$

Associative Property: $(h\circ g)\circ f=h\circ (g\circ f)$

$f^{-1}\circ f=I_X$

$f\circ f^{-1}=I_Y$

If $f,g$ both are Injective, then $g\circ f$ is also Injective

If $f,g$ both are Surjective, then $g\circ f$ is also Surjective

If $g\circ f$ is Injective, then $f$ is Injective If $g\circ f$ is Surjective, then $g$ is Surjective

$f(\varnothing )=\varnothing$

$\forall x\in X:f(\{x\})=\{f(x)\}$

$f^{-1}(f(A))=A\iff f$ is Injective

$f(f^{-1}(B))\iff f$ is Surjective

$f(\bigcup _{i\in I}{A}_i)=\bigcup _{i\in I}f(A_i)$

$f(\bigcap _{i\in I}{A}_i)\subset \bigcap _{i\in I}f(A_i)$

If $f$ is a Injective, then $f(\bigcap _{i\in I}{A}_i)=\bigcap _{i\in I}f(A_i)$

Link to original

Equinumerosity

Definition

$A\approx B$ or $|A|=|B|$ Two sets $A,B$ are equinumerous if there exists a Bijection $f:A\to B$ between them.

Facts

Equinumerosity is a kind of Equivalence Relation

Link to original

Dedekind-Infinite Set

Definition

$\exists B⊊A,|B|=|A|$

The proper subset $B⊊A$ is equinumeros to $A$

Facts

In ZFC Set Theory, Dedekind-infinite $\iff$ Infinite under

Link to original

Infinite Set

Facts

In ZFC Set Theory, Dedekind-infinite $\iff$ Infinite under

Link to original

$\varnothing$ is a finite set

A set containing an infinite set is infinite

Every subset of finite set is finite

for bijective function $f:X\to Y$, If $X$ is an infinite, then $Y$ is also infinite If $X$ is a finite, then $Y$ is also finite

If the subset of an infinite set, $X\subset Y$ is finite, then $X-Y$ is infinite

Link to original

Countable Set

Definite

$X$ is finite or $|X|=|\mathbb{N}|$

A set is finite or there exists an Injective function from it into the natural numbers

Facts

A subset of a countable set is countable

Any finite union of countable set is countable

$\mathbb{N}\times \mathbb{N}$ is countable

The Cartesian Product of finitely many countable sets is countable

$\mathbb{Z}$ and $\mathbb{Q}$ are countable

Link to original

Cardinal Number

Definition

$|A|$ The number that represents the size of the number of elements in a set. uses a natural number for a finite set, and uses the infinite cardinal number for an infinite set.

Ordering

$|X|\le |Y|\iff \exists 1-1f:X\to Y$

There exist an injective function $f:X\to Y$

Operations

Let $x,y,z$ be cardinal numbers.

Addition

$\forall X,\forall Y,X\cap Y=\varnothing \Rightarrow |X|+|Y|=|X\cup Y|$

$|X|\cdot |Y|=|X\times Y|$ where $\times$ is a Cartesian Product

$(x+y)+z=x+(y+z)$ Associative Property of addition $x+y=y+x$ Commutative Property of addition

Multiplication

$(x\cdot y)\cdot z=x\cdot (y\cdot z)$ Associative Property of multiplication $x\cdot y=y\cdot x$ Commutative Property of multiplication $x\cdot (y+z)=x\cdot y+x\cdot z$ Distributive Property of multiplication over addition

Cardinal Exponential

$|X{|}^{|Y|}=|X^Y|$ where $X^Y=\{f|f:X\to Y\}$

$|2^X|=2^{|X|}$

$x^y{x}^z=x^{y+z}$ $(x^y{)}^z=x^{yz}$ $(xy{)}^z=x^z{y}^z$

Facts

$\forall A:\exists !|A|$

$\forall a,\exists A,|A|=a$ where $a$ is a cardinal number

$A=\varnothing \iff |A|=0$

$A\approx B\iff |A|=|B|$

$|\mathbb{N}|={\aleph }_0$

$|\mathbb{R}|=\mathfrak{c}$

$(\nexists C\subset A,|C|=|B|)\wedge (\exists D\subset B,|D|=|A|)\Rightarrow |A|<|B|$

Cantor-Schroder-Bernstein Theorem

Definition

$|A|\le |B|\wedge |B|\le |A|\Rightarrow |A|=|B|$

Link to original

$|A|\le |B|\wedge |B|\le |C|\Rightarrow |A|\le |C|$

${\aleph }_0+{\aleph }_0={\aleph }_0$

$\mathfrak{c}+\mathfrak{c}=\mathfrak{c}$

${\aleph }_0+\mathfrak{c}=\mathfrak{c}$

${\aleph }_0{\aleph }_0={\aleph }_0$

$\mathfrak{cc}=\mathfrak{c}$

${\aleph }_0\mathfrak{c}=\mathfrak{c}$

$\mathfrak{c}=2^{{\aleph }_0}={\aleph }_0^{{\aleph }_0}={\mathfrak{c}}^{{\aleph }_0}$

$2^{\mathfrak{c}}={\aleph }_0^{\mathfrak{c}}={\mathfrak{c}}^{\mathfrak{c}}$

Link to original

Cantor's Theorem

Definition

$|A|<|2^A|$

The set of all subsets of $A$, the power set of $A$ has strictly greater cardinality than $A$ itself

Proof

Since $A\approx \{\{x\}|x\in A\}\subset \mathcal{P}(A)$ $\Rightarrow |A|\le |\mathcal{P}(A)|$

Let $B=\{x\in A|x\notin f(A)\}$ and $\exists$ a Bijective function $f:A\sim P(A)$ the definition of $B$ implies $\forall x\in A:x\in B\iff x\notin f(x)$

Then, since $f$ is Bijective and $B\subset \mathcal{A}$, $\exists \xi \in A\text{ s.t. }f(\xi )=B$. But by the definition of $B$, $\xi \in B\iff \xi \notin f(\xi )=B$. This is a contradiction. So $f$ can not be Bijective $\Rightarrow |A|\ne |\mathcal{P}(A)|$

$\therefore |A|<|\mathcal{P}(A)|$

Link to original

Cantor's Paradox

Definition

There is no greatest cardinal number

There is no set of all sets

Proof

Let $U$ be the set of all sets and its cardinal number be $k$ Then, by the Cantor’s Theorem, $|\mathcal{P}(U)|=2^k>k=|U|$. It is contradicted to the assumption $|U|\ge |\mathcal{P}(X)|$

Link to original

Russell's Paradox

Definition

There is no set of all sets

Proof

Let $R=\{x|x\notin x\}$, then $R\in R\iff R\notin R$

Let $R$ be the set of all sets that are not members of themselves. If $R$ is not a member of itself, by the definition of itself, that is a member of itself; yet, if it is a member of itself, then it doesn’t satisfy its definition.

Link to original

Continuum Hypothesis

Definition

$\nexists S:{\aleph }_0<|S|<2^{{\aleph }_0}$

There is no set whose cardinality is strictly between that of the $\mathbb{Z}$^[${\aleph }_0$], and $\mathbb{R}$^[$2^{{\aleph }_0}$]

The Generalized Continuum Hypothesis

$\forall \kappa ,\nexists \lambda :\kappa <\lambda <2^{\kappa }$ where $k$ and $\lambda$ are the Cardinal Number of infinite set

Facts

The continuum hypothesis is independent of ZFC Set Theory

Link to original

ZFC Set Theory

Axioms

Axiom of Extensionality

$\forall A,\forall B,(\forall C,(C\in A\iff C\in B)\Rightarrow A=B)$

Two sets are equal if they have the same elements

Axiom of Regularity

$\forall A,(A\ne \varnothing \Rightarrow \exists B,(B\in A\wedge B\cap A=\varnothing ))$

Every non-empty set $A$ contains a member of $B$ such that $A$ and $B$ are disjoint sets

This implies, $\nexists A,A\in A$

Axiom schema of Specification

$\forall \varphi ,\forall A,\exists B,\forall x,(x\in B\iff (x\in A\wedge \varphi (A)))$ where $\varphi$ is a Propositional Function

Every subset of a set, defined by a Propositional Function is itself a set

Axiom of Pairing

$\forall A,\forall B,\exists C,(A\in C\wedge B\in C)$

If $A,B$ are sets, then $\exists$ a set which contains $A,B$ as elements

Axiom of Existence

$\exists A,\forall x,\neg (x\in A)$

There is a set such that no element is a member of it

Axiom of Union

$\forall A,\exists B,B=\bigcup A$ where $A$ is a Family of Sets

The union over the elements of a set exists

Axiom Schema of Replacement

$\forall A,((\forall x\in A,\exists !y,x\mathcal{R}y)\Rightarrow \exists B,\forall y,(y\in B\iff \exists x\in A,x\mathcal{R}y))$ where $\mathcal{R}$ is a relation on $A$

The image of any set under definable function is also a set

Axiom of Infinity

$\exists A,(\varnothing \in A\wedge \forall x\in A,((x\cup \{x\})\in A))$

Guarantees the existence of at least one infinite set

Axiom of Power Set

$\forall A,\exists P,\forall B,(B\subset A\Rightarrow B\in P)$

For every set $A$, there is a set $2^A$ consisting precisely of the subsets of $A$

Axiom of Choice

$\forall S,\left[\neg (\varnothing \in S)\Rightarrow \left(\exists f:S\to \bigcup _{A\in S}A,\forall A\in S,(f(A)\in A)\right)\right]$ where $S$ is a Family of Sets, and $f:\{A_i\}\to X$ is a Choice Function

Given any collection of sets, each containing at least one element, it is possible to construct a new set by the Choice Function that chooses arbitrary one element from each set.

Equivalents

Hausdorff Maximal Principle

Definition

Every Partially Ordered Set has a maximal chain

Link to original

Zorn's Lemma

Definition

Every non-empty Partially Ordered Set in which every chain has an upper bound contains at least one Maximum

Link to original

Well-Ordering Theorem

Definition

Every set can be well-order

Link to original

Link to original

Partial Order Relation

Definition

Partial order relation is a binary Relation $\le$ on set $X$ that satisfies the following conditions:

• Reflectivity: $\forall a\in X,a\le a$
• Antisymmetry: $\forall a,b\in X,(a\le b\wedge b\le a\Rightarrow a=b)$
• Transitivity: $\forall a,b,c\in X,(a\le b\wedge b\le c\Rightarrow a\le c)$

Strict Partial Order Relation

Strict partial order relation is a binary Relation $<$ on set $X$ that satisfies the following conditions:

• Transitivity: $\forall a,b,c\in X,(a<b\text{and}b\le c\Rightarrow a<c)$
• Irreflexivity: $\forall a\in X,\neg (a<a)$
• Asymmetry: $\forall a,b\in X,a<b\Rightarrow \neg (b<a)$

Link to original

Partially Ordered Set

Definition

$(P,\le )$ A set equipped with a Partial Order Relation

Facts

A partial ordinary set can only have one greatest or least element.

If a partial ordinary set has a greatest or least element, it must be the unique maximal or minimal element, respectively. Otherwise, there can be more than one maximal or minimal element.

Link to original

Total Order Relation

Definition

Total order relation is a Partial Order Relation in which any two elements are comparable

• Reflectivity: $\forall a\in X,a\le a$
• Antisymmetry: $\forall a,b\in X,(a\le b\text{and}b\le a\Rightarrow a=b)$
• Transitivity: $\forall a,b,c\in X,(a\le b\text{and}b\le c\Rightarrow a\le c)$
• Comparability: $\forall a,b\in X,(a\le b\text{or}b\le a)$

Strict Total Order Relation

Strict total order relation is a binary Relation $<$ on set $X$ that satisfies the following conditions:

• Transitivity: $\forall a,b,c\in X,(a<b\text{and}b\le c\Rightarrow a<c)$
• Irreflexivity: $\forall a\in X,\neg (a<a)$
• Asymmetry: $\forall a,b\in X,a<b\Rightarrow \neg (b<a)$
• Comparability: $\forall a,b\in X\text{s.t.}a\ne b,a<b\text{or}b<a$

Link to original

Totally Ordered Set

Definition

$(T,\le )$ A set equipped with a Total Order Relation

Chains

A totally ordered subset of Partially Ordered Set

Link to original

Extremum

Definition

Maximum

Definition

Consider an Partially Ordered Set $X$ and a subset $Y\subset X$. The largest element (maximum) $y_0$ of $Y$ is defined as $y_0\text{s.t.}{y}_0\in Y\text{and}\forall y\in Y,y\le y_0$

Link to original

Minimum

Definition

Consider an Partially Ordered Set $X$ and a subset $Y\subset X$. The smallest element (minimum) $y_0$ of $Y$ is defined as $y_0\text{s.t.}{y}_0\in Y\text{and}\forall y\in Y,y\ge y_0$

Link to original

Local Maximum

Definition

Suppose $f:\mathcal{D}\to \mathbb{R}$. The function $f$ has local maximum at $x_0$ if $\exists ϵ>0,(\forall x\in \mathcal{D},|x_0-x|<ϵ)\Rightarrow f(x)\le f(x_0)$

Link to original

Local Minimum

Definition

Suppose $f:\mathcal{D}\to \mathbb{R}$. The function $f$ has local minimum at $x_0$ if $\exists ϵ>0,(\forall x\in \mathcal{D},|x_0-x|<ϵ)\Rightarrow f(x_0)\le f(x)$

Link to original

Link to original

Upper Bound

Definition

Consider an Partially Ordered Set $X$ and a subset $Y\subset X$. The set $Y$ is bounded-above if $\exists x_0\in X,\text{s.t.}\forall y\in Y,y\le x_0$ where $x_0$ is the upper bound of the set $Y$.

Link to original

Lower Bound

Definition

Consider an Partially Ordered Set $X$ and a subset $Y\subset X$. The set $Y$ is bounded-below if $\exists x_0\in X,\text{s.t.}\forall y\in Y,y\ge x_0$ where $x_0$ is the lower bound of the set $Y$.

Link to original

Infimum

Definition

$\inf (A)$ Consider an Partially Ordered Set $X$ and a subset $Y\subset X$. The infimum (largest Lower Bound) $y_0$ of $Y$ is defined as the largest element of the set of lower bounds

Link to original

Supremum

Definition

$\sup (A)$ Consider an Partially Ordered Set $X$ and a subset $Y\subset X$. The Supremum (least upper bound) $y_0$ of $Y$ is defined as the smallest element of the set of upper bounds

Link to original

Well-Order Relation

Definition

A Total Order Relation in which every non-empty subset has a smallest element.

• Reflectivity: $\forall a\in X,a\le a$
• Antisymmetry: $\forall a,b\in X,(a\le b\text{and}b\le a\Rightarrow a=b)$
• Transitivity: $\forall a,b,c\in X,(a\le b\text{and}b\le c\Rightarrow a\le c)$
• Comparability: $\forall a,b\in X,(a\le b\text{or}b\le a)$
• Well-ordering: $\forall A\subset W\text{s.t.}A\ne 0,\exists a\in A\text{s.t.}\forall x\in A,a\le x$

Link to original

Well-Ordered Set

Definition

$(W,\le )$ A set equipped with a Well-Order Relation

Examples

$\mathbb{N}$ set is Well-Ordered Set Every non-empty subset of $\mathbb{N}$ always has minimum element

Link to original

Link to original

Ordinal Number

Definition

$\mathrm{ord}(A)=o(A)$

Operations

Addition

$A\cap B=\varnothing \Rightarrow o(A)+o(B)=o(A\cup B)$

Associative Property: $(\alpha +\beta )+\gamma =\alpha +(\beta +\gamma )$

Multiplication

$o(A)o(B)=o(B\times A)$

Associative Property: $\alpha (\beta \gamma )=(\alpha \beta )\gamma$

left Distributive Property: $\alpha (\beta +\gamma )=\alpha \beta +\alpha \gamma$

Facts

$\forall A:\exists !o(A)$ where $A$ is a Well-Ordered Set

$\forall a:\exists A,o(A)=a$ where $A$ is a Well-Ordered Set and $a$ is an ordinal number

$|A|=|B|\iff o(A)=o(B)$

$A=\varnothing \iff o(A)=0$

$o(\mathbb{N})=\omega$

Link to original