Set Theory - HackMD

--- title: Set Theory description: METU Math 320 tags: math, set --- [![hackmd-github-sync-badge](https://hackmd.io/c3dcxX9dReuuEee3TAzggQ/badge)](https://hackmd.io/c3dcxX9dReuuEee3TAzggQ) We first define the language to be used later. $$ \forall\; \exists\; \neg\; \lor\; \land\; \rightarrow\; \leftrightarrow\; (\; )\; $$ Also, $a, b, \cdots$ are sets Applying following two rules repeatively would get a _well formed_ sentence - $x \in y$ or $x = y$ - Given formula $\varphi$ and $\psi$, following sentences are _well formed_ $$ \neg\varphi, \exists x\;\varphi, \forall x\;\varphi, \varphi \land \psi, \varphi \lor \psi, \varphi\rightarrow\psi, \varphi\leftrightarrow\psi $$ **Note** that for convenient, we write - $x \not\in y$ instead of $\neg x \in y$ - $x \neq y$ instead of $\neg x = y$ This **doesn't** mean that we actually introduce such notations into our system. :::success **Definition** Classes $$ C = \{x: \varphi(x, p, q, \cdots)\} $$ $C$ is a class, where - $\varphi$ is a formula - $p, q, \cdots$ are parameters ::: We also define the equality for future usage. :::success **Definition** The equality of classes $$ C = D \leftrightarrow \forall z\;(\varphi(z) = \psi(z)) $$ Where - $C = \{x: \varphi(x)\}$ - $D = \{x: \psi(x)\}$ ::: We could see that **every set is a class, while not every class is a set**. :::success **Definition** Proper classes Given a class $C$, if it is not a set, then $C$ is called a **proper class**. ::: :::info **Theorem** Rossell's Paradox $$ R = \{x: x \not\in x \} $$ Given such a class $R$, $R$ is not a set. More precisely, we are saying that $$ \neg\exists x\; \forall y\; (y \in x \leftrightarrow y \not\in y) $$ There doesn't exist such $x$ that any member of it doesn't belong to itself. **Proof** _Assume_ to the contrary that $\exists x\; \forall y\; (y \in x \leftrightarrow y \not\in y)$. Letting $y$ to be the $x$, i.e., considering itself, we get something like $x \in x \leftrightarrow x \not\in x$, which is a contradiction. ::: :::danger **Axiom** The Existence of empty sets $$ \exists x\;\forall y\;(y \not\in x) $$ No set is in an empty set. ::: **Note** that the uniqueness could still not be comfirmed. To do so, we'll have to introduce the following axiom. :::danger **Axiom** Extensionality 外延公理 $$ \forall x\; \forall y\; \forall z\;(z \in x \leftrightarrow z \in y) \leftrightarrow x = y $$ Two sets are identical iff a member of one set also is the member of another set. ::: This axiom could show that **sets are characterized by their elements**. :::info **Theorem** The uniqueness of empty set **Proof** _Assume_ there are two empty sets $x$ and $y$, also $x \neq y$. Then, $\neg(\forall z(z \in x \leftrightarrow z \in y))$, which means $\exists z$ either $z \not\in x$ but $z \in y$ or $z \in x$ but $z \not\in y$, which leads to contradiction that both sets are empty (containing no element). ::: By confirming the uniqueness of the empty set, we denote the empty set as $\varnothing$ from now on. :::danger **Axiom** Pairing 配对公理 $$ \forall x\; \forall y\; \exists z\; (x \in z \land y \in z) $$ There must be a set built up by the current two sets. ::: With the help of this axiom, we are now able to construct two more sets other than $\varnothing$, which is - $\{\varnothing\}$ - $\{\varnothing, \{\varnothing\}\}$ :::success **Definition** (Kuratowski) Order Pair $$ (x, y) := \{x, \{x, y\}\} $$ ::: :::info **Lemma** $$ (x, y) = (x', y') \leftrightarrow x = y, x' = y' $$ **Proof** ==TODO== ::: :::danger **Axiom** Union $$ \forall x\; \exists y\; \exists z\; (z \in y \leftrightarrow \exists s\; (s \in x \land z \in s)) $$ For every set $x$ there exists a set $y$ that consists of exactly the elements of elements of $x$. ::: :::success **Definition** Union & Intersection $$ \bigcup x = \{z: \exists s \in x \rightarrow z \in s\} $$ There is also a dual operator for union named intersection, which could be defined as $$ \bigcap x = \{z: \forall s \in x \rightarrow z \in s\} $$ ::: :::success **Definition** Union (Intersection) as binary operator $$ x \bigcup y := \bigcup\{x, y\} \\ x \bigcap y := \bigcap\{x, y\} $$ ::: We are now sure that a union is a set, while there is no way to prove if an intersection of an arbitrary set is a set. It is not provable until we introduce the seperation axiom scheme. :::danger **Axiom Scheme** Seperation $$ \forall p\; \forall x\; \exists y\; \forall z (z \in y \leftrightarrow (z \in x \land \varphi(z, p))) $$ Given any set $x$, there exists a set $y$ which consists of elements of $x$ and also satisfy the property $\varphi(\cdot, p)$. ::: Basically, if a class is in form of $$ \{x: x \in y \land \varphi (x, p, q, \cdots)\} $$ it's a set. By the seperation axiom scheme, we could now get the following lemma. :::info **Lemma** The intersection of a non-empty set is a set $$ \forall x \neq \varnothing\; \exists y\; (y = \bigcap x) $$ **Proof** According to the definition of intersection, we could rewrite the intersection as the following form $$ \bigcap x = \{z: z \in x \land \forall s\;(s \in x \rightarrow z \in s )\} $$ We could see that this form match exactly the form given by the seperation axiom. ::: For the intersection of the empty set, we have :::info **Lemma** Every set is the member of the intersection of the empty set $$ \forall x \in \bigcap \varnothing $$ **Proof** $$ \bigcap \varnothing = \{z: \forall s \in \varnothing \rightarrow z \in s\} $$ Where $\forall s \in \varnothing$ will always be true, resulting to a tautology. ::: This would remind of us the existence of universal set, which could be easily carried out by the above lemma and the Rossell's Paradox. :::info **Theorem** There does not exist a universal set. **Proof** _Assume_ There exists such a universal set $U$, we could now use the seperation axiom to construct the following class. $$ R = \{x: x \in U \land x \not\in x\} $$ Since $U$ is, according to the assumption, a universal set, so the class could be rewritten as the following form. $$ R = \{x: x \not\in x\} $$ Which according to the Rossell's Paradox, is not a set. So the assumption is against to the seperation axiom. ::: :::success **Definition** Difference, Symmetric difference $$ x - y := \{z: z \in x \land z \not\in y\} $$ $$ x \triangle y := (x - y) \bigcup (y - x) $$ ::: It's easy to prove that both of these two are sets, according to the seperation axiom and the union operator definition. :::success **Definition** Subset & Superset $$ x \subseteq y := \{z: z \in x \rightarrow z \in y\} $$ For such $x$ and $y$, we say $x$ is the subset of $y$, or $y$ is the superset of $x$. $$ x \subset y := \{z: x \neq y \land z \in x \rightarrow\ z \in y\} $$ For such $x$ and $y$, we say $x$ is the proper subset of $y$, or $y$ is the proper superset of $x$. ::: We also list some common relations for sets. For all $x$, $y$, $z$ and non-empty $w$, we have that - $\varnothing \subseteq x$ and $x \subseteq x$ - $\{t: t \in x \land \varphi(t)\} \subseteq x$ for any property $\varphi$ - $(x \subseteq y \land y \subseteq x) \leftrightarrow x = y$ - $(x \subseteq y \land y \subseteq z) \rightarrow x \subseteq z$ - $\bigcap w \subseteq \bigcup w$ - $y \in x \rightarrow \bigcap x \subseteq y \subseteq \bigcup x$ :::danger **Axiom** Power Set 幂集公理 $$ \forall x\; \exists y\; \forall z\;(z \subseteq x \leftrightarrow z \in y) $$ We say that $y$ is the power set of $x$, denoted as $\mathcal P(x)$. ::: :::success **Definition** Relation & Inverse relation $$ \forall z\; \in R.\; \exists x\; \exists y\; z = (x, y) $$ We say the $R$ is a relation if it consists of ordered pairs. $$ R^{-1} = \{(b, a): (a, b) \in R\} $$ We say $R^{-1}$ is the inverse relation of $R$. ::: :::success **Definition** Domain & Range $$ dom(R) = \{a: \exists b\; (a, b) \in R\} $$ $$ ran(R) = \{b: \exists a\; (a, b) \in R\} $$ Where $R$ is a relation. ::: :::success **Definition** Image & Inverse image $$ R[A] = \{y: \exists x\; \in A, (x, y) \in R\} $$ $$ R^{-1}[B] = \{x: \exists y\; \in B, (x, y) \in R\} $$ Where $A$ and $B$ are two sets and $R$ is a relation. ::: :::info **Lemma** $(R^{-1})[A] = R^{-1}[A]$ **Proof** ==TODO== ::: :::success **Definition** Cartesian product of two sets $$ A \times B = \{(a, b) \in \mathcal P(\mathcal P(A \cup B)): a \in A \land b \in B\} $$ Where $A$ and $B$ are two sets. ::: We could also generalize th concept of cartesian product to arbitrarily many sets. :::success **Definition** Product of the indexed system $$ \prod_{i \in I}F_i = \{f: I \rightarrow \bigcup\{F_i\}_{i \in I}\; |\; \forall i \in I. f(i) \in F_i\} $$ Where $\{F_i\}_{i \in I}$ is an indexed system of sets with index set $I$. ::: Note that we could check that $$ a \in A \land b \in B \rightarrow (a, b) \in \mathcal P(\mathcal P(A \cup B)) $$ (By pairing axiom, $(a, b) = \{a, \{a, b\}\}$) With the help of the cartesian product, we could now express the _relation_ in the following form. :::success **Definition** Relation Given $$ R \subseteq A \times B $$ We say that $R$ is a relation from $A$ to $B$. Given $$ R \subseteq A \times A $$ We say that $R$ is a relation on $A$. ::: :::success **Definition** Composition $$ S \circ R = \{(a, b): \exists c\; (a, c) \in R \land (c, b) \in S\} $$ Where $S$ and $R$ are two relations. ::: Now we define two kinds of special reation. :::success **Definition** Membership relation $$ \in_A = \{(a, b) \in A \times A : a \in b\} $$ ::: :::success **Definition** Identity relation $$ \Delta_A = \{(a, b) \in A \times A : a = b\} $$ ::: Moreover, we introduce the _function_, which requires the uniqueness of function value. :::success **Definition** Function or Well defined relation Given $$ \forall a\;\forall b\;\forall c.\;(a, b) \in R \land (a, c) \in R \rightarrow b = c $$ We say $R$ is a function (well defined relation). ::: We could note that the simplest function is the empty set $\varnothing$. :::success **Definition** Domain & Codomain Given $dom(R) = A$ and $ran(R) \subseteq B$, where $R$ is a function from $A$ to $B$ and $A$, $B$ are two sets. We say that $R$ has the _domain_ $A$ and _codomain_ $B$. Also, we denote it as $R: A \rightarrow B$. ::: Note that since domain is a subset of $B$, we shall always specify the codomain of a function. :::success **Definition** Value of function Given a function $R$ and $x \in dom(R)$. The unique element $y \in ran(R)$ where $(x, y) \in R$ is called the value of $R$ at $x$. Denoted as $y = R(x)$. ::: :::success **Definition** Injective, Surjective & Bijective For $f: A \rightarrow B$, Given $\forall a\; \forall b$ $$ f(a) = f(b) \rightarrow a = b $$ Then we say that $f$ is _injective_. We could also generalized this idea to arbitrary relations, without requiring the function value to be unique. If $$ ran(f) = f[A] = B $$ Then we say that $f$ is _surjective_. If $f$ met both _injective_ and _surjective_, then we say that $f$ is _bijective_. ::: :::info **Lemma** $R$ is an injective function iff the inverse relation $R^{-1}$ is an injective function. **Proof** ==TODO== ::: :::success **Definition** Restriction of function ($f|_A$ or $f\upharpoonright_A$) $$ f \upharpoonright_A = \{(a, b) \in f: a \in A\} $$ Where $f$ is a function and $A$ is a set. ::: :::success **Definition** Function compatible We say two functions $f$ and $g$ are _compatible_ if all $x \in dom(f) \cap dom(g)$ . ::: :::info **Lemma** Given a set $S$ containing pairwise compatible functions, then $$ \bigcup {dom(f): f \in S} $$ is a function. **Proof** ==TODO== ::: :::info **Lemma** The composition of two functions is a function Given $f$ and $g$ are two functions, then $g \circ f$ is a function **Proof** ==TODO== ::: :::danger **Axiom** Choice For all sets $I$ and indexed systems of set $\{A_i\}_{i \in I}$ with $A_i \neq \varnothing$ where $i \in I$, $\prod_{i \in I} A_i$ is non-empty. ::: :::success **Definition** Equivalence relation Given a set $X$ and a relation on set $E \subseteq X \times X$, $E$ is said to be an _equivalence relation_ if it is - reflexive, i.e., $\forall x \in X. (x, x) \in E$ - symmetric, i.e., $\forall x, y \in X. (x, y) \in E \rightarrow (y, x) \in E$ - transitive, i.e., $\forall x, y, z \in X. (x, y) \in E \land (y, z) \in E \rightarrow (x, z) \in E$ ::: We could see that the identity relation $\Delta_X$ is an ER on $X$ for any set $X$. And $\varnothing$ could be referred as the _empty relation_ and is an ER on any set, including itself. :::success **Definition** Equivalence class $$ [x]_E := \{y \in X : (y, x) \in E\} $$ Where, - $X$ is a set - $E$ is an ER on $X$ - $x \in X$ We say that $[x]_E$ is the EC of $x$ modulo $E$. ::: :::info **Lemma** ::: :::success **Definition** Quotient set $$ X / E = \{[x]_E: x \in X\} $$ ::: :::success **Definition** Partition set Given $S \subseteq \mathcal P(X)$, if - $\forall A \in S. A \neq \varnothing$ - $\forall A, B \in S. A \neq B \rightarrow A \cap B = \varnothing$ - $\bigcup S = X$ We said that $S$ is the partition of $X$. ::: :::info **Theorem** $$ X / E $$ :::