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.