# Today I Learned

Some of the things I've learned every day since Oct 10, 2016

## 98: Top Type, Bottom Type

Given a type system, the top type $\top$ is the type which contains every possible value in that type system, making every other type a subtype of $\top$.

By contrast, the bottom type $\bot$ is the type which contains no values, making every other type a supertype of $\bot$.

## 97: The Archimedean Property of the Reals

$\mathbb{R}$ has the Archimedean property, which states that for any positive $x, y \in \mathbb{R}$ there exists an $n \in \mathbb{N}$ such that

$nx > y$.

Intuitively, this means that $\mathbb{R}$ contains neither infinitely large nor infinitesimally small numbers. (The property would not hold if $y$ was infinite, or if $x$ was infinitesimal.)

#### Proof:

Finding an $n$ such that $nx > y$ is equivalent to finding one such that $n > \frac{y}{x}$. If there is no such $n$, this means that $n \leq \frac{y}{x}$ for all $n$ and thus the number $\frac{y}{x}$ is an upper bound on $\mathbb{N}$. However, $\mathbb{N}$ has no upper bound, so this is a contradiction, meaning such an $n$ must exist.

## 96: Euler’s Theorem (Number Theory)

Euler’s Theorem is a sort of extension of Fermat’s Little Theorem. One way of stating Fermat’s is that where $n$ is prime and $a$ is any integer,

$a^{p-1} \equiv 1 (\textrm{mod } n)$,

whereas Euler’s Theorem makes the more general statement that if $a, n$ are simply two coprime integers and $\varphi (n)$ is Euler’s totient function,

$a^{\varphi (n)} \equiv 1 (\textrm{mod } n)$.

The reason Fermat’s is a valid special case of Euler’s is because when $n$ is prime, $\varphi (n) = n - 1$.

[The congruence in the statement of Euler’s theorem is actually equivalent (‘if and only if’) to $a, n$ being coprime.]

## 95: Static Variables and Methods (Java)

In the Java programming language, both variables and methods within a class can be static or non-static. For a variable or method to be static means that it can be accessed without referencing an instance of the containing class.

If something is non-static, for example a method $\texttt{m}$ belonging to a class $\texttt{C}$, one must use an instance of $\texttt{C}$ to call $\texttt{m}$:

$\texttt{C c = new C();}$

$\texttt{c.m();}$

whereas if $\texttt{m}$ was static, it could simply be called with reference to the class itself:

$\texttt{C.m();}$

Static methods can be called with reference to class instances, but this is generally considered poor form.

## 94: The Liskov Substitution Principle

The Liskov Substitution Principle makes the intuitive generalization that if $A, B$ are types and $A <: B$ ($A$ is a subtype of $B$), then in a program with this type system, objects from $B$ can be substituted with objects from $A$ without certain properties of the program being affected.

## 93: Subtypes (Programming)

Let $A, B$ be data types in the type system of a programming language. To say that $A$ is a subtype of $B$, often written $A < : B$, means that objects of type $A$ can be used where objects of type $B$ are expected. That is, $A$ is a more specific version of $B$ in some sense. (Equivalently, $B$ is said to be a supertype of $A$.)

Subtyping forms a reflexive and transitive relation on a given set of types.

An (non-technical) example would be $P < : F < : B$, where $P$ is the type of penguins, $F$ is that of flightless birds, and $B$ is that of birds. A penguin is acceptable where a bird or even a flightless bird is expected, but conversely not any bird will do when a penguin is expected.

## 92: Order (Groups)

The order of a group $G$, often denoted $|G|$, is the cardinality of its underlying set. If the order is finite, then $G$ is called a finite group, and likewise for infinite order.

An example of a group with finite order would be the dihedral group $D_n$ for some $n$. An example of one with infinite order would be the group of $\mathbb{Z}$ together with addition.

## 91: Categorical Distribution (Probability)

categorical distribution is one which describes a random variable which can take $k$ possible values, the probability of each possible outcome being known. For instance, the Bernoulli distribution is a special case of the categorical distribution, where $k = 2$ (one outcome being ‘success’, the other ‘failure’). The distribution of the outcomes of rolling a (not necessarily fair) 6-sided die would also be an example, with $k = 6$.

## 90: The Standard (Unit) Simplex

The standard $n$-simplex, sometimes denoted $\Delta^n$, is the $n$-simplex in $\mathbb{R}^{n + 1}$ with its vertices at the $n + 1$ ‘unit’ points

$e_0 = (1, 0, 0, \dots, 0)$

$e_1 = (0, 1, 0, \dots, 0)$

$e_2 = (0, 0, 1, \dots, 0)$

$\dots$

$e_n = (0, 0, 0, \dots, 1)$.

For example, $\Delta ^0$ is the point $1$ in $\mathbb{R}^1$$\Delta ^1$ is the line segment from $(0, 1)$ to $(1, 0)$ in $\mathbb{R}^2$, and so on. A formal description is

$\Delta ^n = \{(x_0, x_1, \dots, x_n) \in \mathbb{R}^{n+1} | \sum _{i = 0} ^{n} x_i = 1, x_i \geq 0 \}$.

One possible interpretation of $\Delta ^n$ is as the set of possible probability distributions of a categorical distribution on $n+1$ variables.

## 89: Functors

In category theory, a functor is a map between categories $\mathcal{C}, \mathcal{D}$ consisting of two components:

1. a map $f$ from the objects of $\mathcal{C}$ to those of $\mathcal{D}$
2. a map from each morphism $g: X \rightarrow Y$ in $\mathcal{C}$ to a morphism $g': f(X) \rightarrow f(Y)$ in $\mathcal{D}$.

This map must preserve the identity morphisms and composition. That is, it must satisfy the following properties:

1. $f(1_X) = 1_{f(X)}$ for objects $X$ in $\mathcal{C}$
2. $f(a \circ b) = f(a) \circ f(b)$

Functors can be thought of as kinds of homomorphisms between categories. With functors as arrows, categories can then form a category called $\mathbf{Cat}$, the category of categories.