From The Beginning

Before my next post, there are some concepts from mathematics I would like to introduce to you. Math is a game people play that involves symbols. Some say it involves pondering the relationships between objects, such as "equivalence" and "distinction". Mathematicians use foundational concepts such as "sets", "types", and "categories" to play this game. Like most mathematicians, I will use sets.

On Sets

Every good math textbook starts off with a reintroduction to set theory. This is because no mathematicians actually agree on what set theory actually means, and every mathematician is pretentious enough to want to start from the very beginning.

A set is an object that contains elements. Two sets are equal if, and only if, each element of one is also an element of the other. An element is an object that is contained within a set. This is a circular definition. Bear with me for a bit.

$$ X = \{a, b, c\}\\ Y = \{b, c, d\}\\ a \in X, b \in X, b \in Y, d \in Y\\ d \notin X, a \notin Y\\ $$

A subset (of another set) is a set where all its elements are contained in another set, called a superset. A strict subset is a subset where the superset contains at least one element the subset doesn't.

$$ X = \{a, b, c\}\\ Z = \{b, c\}\\ Z \subseteq X $$

The union of two sets is a set composed of each element that is contained in either set. The intersection of two sets is a set composed of each element that is contained in both sets. $$ X = \{a, b, c\}\\ Y = \{b, c, d\}\\ X \cup Y = \{a, b, c, d\}\\ X \cap Y = \{b, c\} $$

An ordered pair $(a, b)$ is a pair of objects for which their order is significant. Sets don't have orders. Ordered pairs do. The set of all ordered pairs $(a, b)$ such that $a \in X$ and $b \in Y$ is called the Cartesian product of $X$ and $Y$.

$$ X \times Y = \{(i, j) \vert i \in X, j \in Y\}\\ (b, d) \in X \times Y\\ (d, a) \notin X \times Y $$

A binary relation between $X$ and $Y$ can be defined as a subset of the Cartesian product of $X$ and $Y$. Here's a binary relation $R$ between the set of the first 9 natural numbers and the first 9 capital letters. Two elements satisfy the binary relation if they both have the same number of holes in the written character, rendered in the font you are currently viewing.

$$ L = \{A,B,C,D,E,F,G,H,I\}\\ D = \{0,1,2,3,4,5,6,7,8\}\\ (A, 6) \in R\\ (B, 8) \in R\\ (C, 1) \in R\\ (D, 3) \notin R $$

We denote $aRb$ as a shorthand for $(a, b) \in R$ for some equivalence relation $R$. An equivalence relation is a binary relation defined between a set $X$ and itself, that obeys each of the following three properties:

  • Reflexivity: $\forall a \in X$, $aRa$.
  • Symmetry: $\forall a, b \in X$, $aRb$ implies $bRa$.
  • Transitivity: $\forall a, b, c \in X$, if $aRb$ and $bRc$, then $aRc$.

An equivalence relation separates the set it is defined on into subsets called "equivalence classes". Within an equivalence class $E$, $\forall a, b \in E, aRb$. $=$ is an example of an equivalence relation.

A function $f: X \rightarrow Y$ is a binary relation that satisfies the additional conditions:

  • For all $x$ in $X$, there exists a $y$ in $Y$, such that $(x, y)$ is in $f$.
  • If $(a, b)$ is in $f$, and $(a, c)$ is in $f$, then $b = c$.

$$ \forall x \in X \exists y \in Y, (x, y) \in f\\ (a, b), (a, c) \in f \implies b = c $$

The first set, $X$, can be called the "domain", and the second set, $Y$, can be called the "codomain". The subset of $Y$ that has elements in ordered pairs in the function can be called the "image". A function "maps" elements of $X$, its domain, to elements of its image, which is a subset of $Y$, the codomain.

$$ S = \{A,B,C,D\}\\ T = \{1,2,3\}\\ f = \{(A, 1), (B, 1), (C, 2), (D,2)\}\\ f(A) = 1\\ f(D) = 2\\ f(C) = 2 $$

A surjective function, or "onto" function, is a function $s: X \rightarrow Y$ where for every element in $Y$, at least one element of $X$ is mapped to that element of $Y$ by an ordered pair in $s$.

$$ S = \{A,B,C,D\}\\ T = \{1,2,3\}\\ s = \{(A, 1), (B, 1), (C, 3), (D,2)\}\\ s(A) = 1\\ s(D) = 2\\ s(C) = 3 $$

An injective function, or "one-to-one" function, is a function $i: X \rightarrow Y$ where for every element in $Y$, at most one element of $X$ is mapped to that element of $Y$ by an ordered pair in $i$.

$$ S = \{A,B\}\\ T = \{1,2,3\}\\ i = \{(A, 1), (B, 3)\}\\ i(A) = 1\\ i(B) = 3 $$

A bijective function is a function that is both surjective and injective.

$$ S = \{A,B,C\}\\ T = \{1,2,3\}\\ b = \{(A, 1), (B, 2), (C, 3)\}\\ b(A) = 1\\ b(B) = 2\\ b(C) = 3\\ $$

If the codomain of an injection were defined as its image, any injection could be redefined as a bijection. Strictly, it would not be the same function.

Every bijective function has an inverse, since every element in the domain is tied to exactly one element in the codomain and vice versa. Bijections can be chained together, or "composed", when the codomain of one is the domain of another, and the entire chain would have an inverse since each of its components have inverses.

On Numbers

I'll skip Peano arithmetic. Let's assume you know how to count. Let's count starting at 0. Those are the natural numbers. Some mathematicians start the natural numbers at 1. They are wrong.

$$\mathbb{N} = \{0,1,2,3,4,...\}$$

I assume you know how to add. The integers are the set of natural numbers and their additive inverses, or "negatives".

$$ a + (-a) = 0\ \mathbb{Z} = \mathbb{N} \cup \{-a\mid a \in \mathbb{N}\} = \{-4,-3,-2,-1,0,1,2,3,4,...\} $$

I also assume you know how to multiply. An integer $b$ (except for $b = 0$) "divides" an integer $a$ if, and only if, there exists an integer c such that $a$ equals $b$ times $c$. This can also be read as "a is divisible by b".

$$b \vert a \iff \exists c \in \mathbb{Z}, a = bc$$

The rational numbers, $\mathbb{Q}$, are equivalence classes on the Cartesian product of the integers with "the integers without zero", $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, such that two rational numbers are equal if $ad = bc$. This also implies that for any integer $p$ where $p \neq 0$, $\frac{a}{b} = \frac{pa}{pb}$.

$$ \frac{a}{b} = \frac{c}{d} \iff ad = bc\\ \frac{a}{b} = \frac{pa}{pb}, a(pb) = b(pa)\\ \frac{2}{3} = \frac{4}{6}, 2 \cdot 6 = 4 \cdot 3 = 12 $$

The absolute value function $\vert x \vert: \mathbb{Q} \rightarrow \mathbb{Q}_+ \cup \{0\}$, defined on only rational numbers for now, is defined as a function that maps numbers greater than 0, or "positive numbers" to themselves, 0 to 0, and numbers less than 0, or "negative numbers", to their additive inverses.

$$x < 0 \implies \vert x \vert = -x, x \geq 0 \implies |x| = x$$

Remember ordered pairs? An ordered sequence is a list of elements where their order matters. Let's index sequences starting from 1, rather than 0, since it's easier for now.

$$ s = (1,2,3,4,5,6,7,...)\\ s_1 = 1\\ s_2 = 2 $$

A rational Cauchy sequence is a sequence, defined on the rational numbers, such that for every rational number $\epsilon > 0$, there exists a natural number $N$ such that for any two natural numbers $m, n$ greater than $N$, $\vert s_m-s_n\vert < \epsilon$.

$$ \forall \epsilon \in \mathbb{Q}_{+} \exists N \in \mathbb{N}\\ \forall (m, n)\in\mathbb{N}, m,n> N, \vert s_m - s_n \vert < \epsilon $$

Two rational Cauchy sequences $s, t$ can be considered equivalent if, and only if, the sequence $\vert s_n - t_n \vert$ converges to 0. If two rational Cauchy sequences are equivalent, they are in the same equivalence class.

$$ s \sim t \iff \forall \epsilon\in\mathbb{Q}_{+},\exists N\in\mathbb{N}\\ \forall n \in \mathbb{N}, n>N \implies |s_n-t_n|<\epsilon $$

The real numbers $\mathbb{R}$ are the set of equivalence classes of rational Cauchy sequences, defined as above. This creates a set where every rational Cauchy sequence determines a real number.