Set Theory

$ % macros % MathJax \newcommand{\bigtimes}{\mathop{\vcenter{\hbox{$\Huge\times\normalsize$}}}} % prefix with \! and postfix with \!\! % sized grouping symbols \renewcommand {\aa} [1] {\left\langle {#1} \right\rangle} % <> angle brackets \newcommand {\bb} [1] {\left[ {#1} \right]} % [] brackets \newcommand {\cc} [1] {\left\{ {#1} \right\}} % {} curly braces \newcommand {\mm} [1] {\lVert {#1} \rVert} % || || double norm bars \newcommand {\nn} [1] {\lvert {#1} \rvert} % || norm bars \newcommand {\pp} [1] {\left( {#1} \right)} % () parentheses % unit \newcommand {\unit} [1] {\bb{\mathrm{#1}}} % measurement unit % math \newcommand {\fn} [1] {\mathrm{#1}} % function name % sets \newcommand {\setZ} {\mathbb{Z}} \newcommand {\setQ} {\mathbb{Q}} \newcommand {\setR} {\mathbb{R}} \newcommand {\setC} {\mathbb{C}} % arithmetic \newcommand {\q} [2] {\frac{#1}{#2}} % quotient, because fuck \frac % trig \newcommand {\acos} {\mathrm{acos}} % \mathrm{???}^{-1} is misleading \newcommand {\asin} {\mathrm{asin}} \newcommand {\atan} {\mathrm{atan}} \newcommand {\atantwo} {\mathrm{atan2}} % at angle = atan2(y, x) \newcommand {\asec} {\mathrm{asec}} \newcommand {\acsc} {\mathrm{acsc}} \newcommand {\acot} {\mathrm{acot}} % complex numbers \newcommand {\z} [1] {\tilde{#1}} \newcommand {\conj} [1] {{#1}^\ast} \renewcommand {\Re} {\mathfrak{Re}} % real part \renewcommand {\Im} {\mathrm{I}\mathfrak{m}} % imaginary part \newcommand {\abs} [1] {\nn{#1}} % quaternions \newcommand {\quat} [1] {\tilde{\mathbf{#1}}} % quaternion symbol \newcommand {\uquat} [1] {\check{\mathbf{#1}}} % versor symbol \newcommand {\gquat} [1] {\tilde{\boldsymbol{#1}}} % greek quaternion symbol \newcommand {\guquat}[1] {\check{\boldsymbol{#1}}} % greek versor symbol % vectors \renewcommand {\vec} [1] {\mathbf{#1}} % vector symbol \newcommand {\uvec} [1] {\hat{\mathbf{#1}}} % unit vector symbol \newcommand {\gvec} [1] {\boldsymbol{#1}} % greek vector symbol \newcommand {\guvec} [1] {\hat{\boldsymbol{#1}}} % greek unit vector symbol % special math vectors \renewcommand {\r} {\vec{r}} % r vector [m] \newcommand {\R} {\vec{R}} % R = r - r' difference vector [m] \newcommand {\ur} {\uvec{r}} % r unit vector [#] \newcommand {\uR} {\uvec{R}} % R unit vector [#] \newcommand {\ux} {\uvec{x}} % x unit vector [#] \newcommand {\uy} {\uvec{y}} % y unit vector [#] \newcommand {\uz} {\uvec{z}} % z unit vector [#] \newcommand {\urho} {\guvec{\rho}} % rho unit vector [#] \newcommand {\utheta} {\guvec{\theta}} % theta unit vector [#] \newcommand {\uphi} {\guvec{\phi}} % phi unit vector [#] \newcommand {\un} {\uvec{n}} % unit normal vector [#] % vector operations \newcommand {\inner} [2] {\left\langle {#1} , {#2} \right\rangle} % <,> \newcommand {\outer} [2] {{#1} \otimes {#2}} \newcommand {\norm} [1] {\mm{#1}} \renewcommand {\dot} {\cdot} % dot product \newcommand {\cross} {\times} % cross product % matrices \newcommand {\mat} [1] {\mathbf{#1}} % matrix symbol \newcommand {\gmat} [1] {\boldsymbol{#1}} % greek matrix symbol % ordinary derivatives \newcommand {\od} [2] {\q{d #1}{d #2}} % ordinary derivative \newcommand {\odn} [3] {\q{d^{#3}{#1}}{d{#2}^{#3}}} % nth order od \newcommand {\odt} [1] {\q{d{#1}}{dt}} % time od % partial derivatives \newcommand {\de} {\partial} % partial symbol \newcommand {\pd} [2] {\q{\de{#1}}{\de{#2}}} % partial derivative \newcommand {\pdn} [3] {\q{\de^{#3}{#1}}{\de{#2}^{#3}}} % nth order pd \newcommand {\pdd} [3] {\q{\de^2{#1}}{\de{#2}\de{#3}}} % 2nd order mixed pd \newcommand {\pdt} [1] {\q{\de{#1}}{\de{t}}} % time pd % vector derivatives \newcommand {\del} {\nabla} % del \newcommand {\grad} {\del} % gradient \renewcommand {\div} {\del\dot} % divergence \newcommand {\curl} {\del\cross} % curl % differential vectors \newcommand {\dL} {d\vec{L}} % differential vector length [m] \newcommand {\dS} {d\vec{S}} % differential vector surface area [m^2] % special functions \newcommand {\Hn} [2] {H^{(#1)}_{#2}} % nth order Hankel function \newcommand {\hn} [2] {H^{(#1)}_{#2}} % nth order spherical Hankel function % transforms \newcommand {\FT} {\mathcal{F}} % fourier transform \newcommand {\IFT} {\FT^{-1}} % inverse fourier transform % signal processing \newcommand {\conv} [2] {{#1}\ast{#2}} % convolution \newcommand {\corr} [2] {{#1}\star{#2}} % correlation % abstract algebra \newcommand {\lie} [1] {\mathfrak{#1}} % lie algebra % other \renewcommand {\d} {\delta} % optimization %\DeclareMathOperator* {\argmin} {arg\,min} %\DeclareMathOperator* {\argmax} {arg\,max} \newcommand {\argmin} {\fn{arg\,min}} \newcommand {\argmax} {\fn{arg\,max}} % waves \renewcommand {\l} {\lambda} % wavelength [m] \renewcommand {\k} {\vec{k}} % wavevector [rad/m] \newcommand {\uk} {\uvec{k}} % unit wavevector [#] \newcommand {\w} {\omega} % angular frequency [rad/s] \renewcommand {\TH} {e^{j \w t}} % engineering time-harmonic function [#] % classical mechanics \newcommand {\F} {\vec{F}} % force [N] \newcommand {\p} {\vec{p}} % momentum [kg m/s] % \r % position [m], aliased \renewcommand {\v} {\vec{v}} % velocity vector [m/s] \renewcommand {\a} {\vec{a}} % acceleration [m/s^2] \newcommand {\vGamma} {\gvec{\Gamma}} % torque [N m] \renewcommand {\L} {\vec{L}} % angular momentum [kg m^2 / s] \newcommand {\mI} {\mat{I}} % moment of inertia tensor [kg m^2/rad] \newcommand {\vw} {\gvec{\omega}} % angular velocity vector [rad/s] \newcommand {\valpha} {\gvec{\alpha}} % angular acceleration vector [rad/s^2] % electromagnetics % fields \newcommand {\E} {\vec{E}} % electric field intensity [V/m] \renewcommand {\H} {\vec{H}} % magnetic field intensity [A/m] \newcommand {\D} {\vec{D}} % electric flux density [C/m^2] \newcommand {\B} {\vec{B}} % magnetic flux density [Wb/m^2] % potentials \newcommand {\A} {\vec{A}} % vector potential [Wb/m], [C/m] % \F % electric vector potential [C/m], aliased % sources \newcommand {\I} {\vec{I}} % line current density [A] , [V] \newcommand {\J} {\vec{J}} % surface current density [A/m] , [V/m] \newcommand {\K} {\vec{K}} % volume current density [A/m^2], [V/m^2] % \M % magnetic current [V/m^2], aliased, obsolete % materials \newcommand {\ep} {\epsilon} % permittivity [F/m] % \mu % permeability [H/m], aliased \renewcommand {\P} {\vec{P}} % polarization [C/m^2], [Wb/m^2] % \p % electric dipole moment [C m], aliased \newcommand {\M} {\vec{M}} % magnetization [A/m], [V/m] \newcommand {\m} {\vec{m}} % magnetic dipole moment [A m^2] % power \renewcommand {\S} {\vec{S}} % poynting vector [W/m^2] \newcommand {\Sa} {\aa{\vec{S}}_t} % time averaged poynting vector [W/m^2] % quantum mechanics \newcommand {\bra} [1] {\left\langle {#1} \right|} % <| \newcommand {\ket} [1] {\left| {#1} \right\rangle} % |> \newcommand {\braket} [2] {\left\langle {#1} \middle| {#2} \right\rangle} $

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