Set Theory

[an error occurred while processing this directive]

This is a review of set theory. This needs a lot of work.

Topics

Set Theory

set $$ A = \set{1, a, \bigstar, \triangle} $$ membership $$ 1 \in A $$ $$ 2 \notin A $$ cardinality $$ \nn{A} =\,\text{number of elements} $$ quantifiers $$ \forall x \in A [\fn{Predicate}(x)] $$ $$ \exists x \in A [\fn{Predicate}(x)] $$ $$ \neg \forall x \in A [\fn{Predicate}(x)] \Leftrightarrow \exists x \in A [\neg \fn{Predicate}(x)] $$ $$ \neg \exists x \in A [\fn{Predicate}(x)] \Leftrightarrow \forall x \in A [\neg \fn{Predicate}(x)] $$ subset $$ A \subseteq B \Leftrightarrow \forall x \in A [x \in B] $$ set equality $$ A = B \Leftrightarrow A \subseteq B \wedge B \subseteq A $$ proper subset $$ A \subset B \Leftrightarrow A \subseteq B \wedge A \neq B $$ universal set $$ A \subseteq U $$ null set $$ \varnothing \equiv \set{} $$ set builder $$ A = \set{x \in B | \fn{Predicate(x)}} $$ power set set of all subsets $$ \mathcal{P}(A) \equiv \set{B \subseteq A} $$ for finite sets, the power set contains $2^|A|$ element subsets. set union $$ A \cup B \equiv \set{x \in U | x \in A \vee x \in B} $$ set intersection $$ A \cap B \equiv \set{x \in U | x \in A \wedge x \in B} $$ $$ A \cap [B \cup C] = [A \cap B] \cup [A \cap C] \\ A \cup [B \cap C] = [A \cup B] \cap [A \cup C] $$ set subtraction $$ A - B \equiv \set{x \in U | a \in A \vee a \notin B} $$ ordered pair (tuple) $$ (a, b) \equiv \set{\set{a}, \set{a, b}} $$
Show $(a, b) = (c, d) \Leftrightarrow a = c$ and $b = d$ Suppose $(a, b) = (c, d)$. Then $\set{\set{a}, \set{a, b}} = \set{\set{c}, \set{c, d}}$. Consider the case where $\set{a} = \set{c} and \set{a, b} = \set{c, d}$ Then $a = c$. Then either $b = d$ or $b = c$ if $b = c$ then $a = b = c = d$ thus $a = c$ and $b = d$ consider the case where $\set{a} = \set{c, d}$ and $\set{a, b} = \set{c}$ then $a = c = d$ and $b = c$ thus $a = c$ and $b = d$ suppose $a = c$ and $b = d$ then $\set{\set{a}, \set{a, b}} = \set{\set{c}, \set{c, d}}$ because $\set{a} = \set{c}$ and $\set{a, b} = \set{c, d}$ thus $(a, b) = (c, d)$ done
Cartesian product $$ A \times B \equiv \set{(a, b) | a \in A \wedge b \in B} $$ $$ A^n \equiv \!\bigtimes_{i=1}^n\!\! A = \underbrace{A \cross A \cross \dots A}_{n \text{ times}} $$ relation $$ a R b \in R \subseteq A \times B $$ equivalence relation $$ \begin{matrix} &a \sim a &\text{(reflexive)} \\ &a \sim b \Rightarrow b \sim a &\text{(symmetric)} \\ &a \sim b \wedge b \sim c \Rightarrow a \sim c &\text{(transitive)} \\ \end{matrix} $$ partition $$ \bigcup_{i \in I} P_i = A \\ \bigcap_{i \in I} P_i = \oslash $$ total order $$ \begin{matrix} &a \leq b \vee b \leq a &\text{(connex)} \\ &a \leq b \wedge b \leq a \Rightarrow a = b &\text{(antisymmetric)} \\ &a \leq b \wedge b \leq c \Rightarrow a \leq c &\text{(transitive)} \\ \end{matrix} $$ $$ a < b \equiv a \leq b \wedge a \neq b $$ $$ a \geq b \equiv b \leq a $$ $$ a > b \equiv b \leq a \wedge a \neq b $$ interval $$ [a,b] \subset A \equiv \set{x \in A | a \leq x \leq b} $$ function $$ \forall a \in f [a f b \wedge a f c \Rightarrow b = c] $$ $$ f(a) = b $$ function mapping from domain A to range B $$ f: A \rightarrow B $$ unary operation $$ f: A \rightarrow A $$ binary operation $$ f: A \times A \rightarrow A $$

Relations

Let $X$ and $Y$ be sets. Any subset $R$ of the cartesian product $X \times Y$ is called a relation from $X$ to $Y$ $$ R \subset X \times Y. \nonumber $$ An element of a relation is an ordered pair $(x, y) \in R$. This ordered pair is commonly denoted $xRy$ which is read "x relate y". A relation from a set $X$ to itself is called a relation in $X$. The empty set is always a relation and is called the empty relation.

Let $R$ be a relation from $X$ to $Y$. The inverse relation $R^{-1}$ is the relation from $Y$ to $X$ such that $$ R^{-1} \equiv \set{(y, x) \in Y \times X : xRy}. \nonumber $$

Let $R$ be a relation from $X$ to $Y$. The image of $A \subset X$ is defined as the set $$ R(A) \equiv \set{y \in Y : \exists x \in A , xRy}. \nonumber $$ The image of $X$ is called the domain $D_R$ $$ D_R \equiv R(X). \nonumber $$ The preimage of $B \subset Y$ is defined as the inverse relation's image of $B$ $$ R^{-1}(B) \equiv \set{x \in X : \exists y \in B , xRy}. \nonumber $$ The preimage of $Y$ is called the range $R_R$ $$ R_R \equiv R^{-1}(Y). \nonumber $$

Let $R$ be a relation from $X$ to $Y$ and $S$ be a relation from $Y$ to $Z$. The composition $S \circ R$ is the relation from $X$ to $Z$ such that $$ S \circ R \equiv \set{(x, z) \in X \times Z : (x, y) \in R \wedge (y, z) \in S}. \nonumber $$

Let $R$ and $S$ be relations such that $S \subset R$. Then $S$ is called a restriction of $R$, and $R$ is called an extension of $S$.

Functions

A function $f$ is a relation from $X$ to $Y$ such that $$ \forall x \in X , xRy \wedge xRz \Rightarrow y = z \nonumber $$ and is denoted $f: X \rightarrow Y$. This is a concise way of saying that each element of $X$ relates to exactly one element of $Y$. Singletons. The function is said to map elements of $X$ into $Y$. $f(x) = y$.

The inverse relation $f^{-1}$ is not necessarily a function. This is because more than one element in $X$ may relate to the same element of $Y$. A function $f$ with the property that $$$$

Consider functions $f: X \rightarrow Y$ and $g: Y \rightarrow Z$. The composition $g \circ f$ from $X$ to $Z$ is also a function. Moreover, functional composition is associative $$h \circ [g \circ f] = [h \circ g] \circ f. \nonumber$$

The behavior of the image and preimage of unions and intersections of collections of sets is important in the study of functions. The preimage of the union/intersection of sets is the union/intersection of the preimages of sets. $$f^{-1}\pp{\bigcup_{i \in I} B_i} = \bigcup_{i \in I} f^{-1}(B_i), \nonumber$$ $$f^{-1}\pp{\bigcap_{i \in I} B_i} = \bigcap_{i \in I} f^{-1}(B_i). \nonumber$$ The image of the union of a collection is the union of the images of the sets in the collection $$f\pp{\bigcup_{i \in I} A_i} = \bigcup_{i \in I} f(A_i). \nonumber$$ However, the image of the intersection of a collection is a subset of the intersection of the images of the sets in the collection $$f\pp{\bigcap_{i \in I} A_i} \subset \bigcap_{i \in I} f(A_i). \nonumber$$

use extistential quantifiers

Sources