Today I Learned

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

Monthly Archives: January 2017

105: Loitering Objects (Java)

In Java (and possibly other languages, not sure), loitering objects refers to objects in memory which are no longer desired or will no longer be used in the future but still have pointers pointing to them, preventing garbage collection from freeing their place in memory. It’s generally good form to not waste memory in this fashion, but in extreme cases loitering objects can even lead to unwanted program termination due to a \texttt{java.lang.OutOfMemoryError}.

Advertisements

104: Bijectivity of Left- or Right-Multiplication by Group Elements

Let G be a group and x be any element of that group. Then the functions

f: a \mapsto xa

g: a \mapsto ax

are bijective.

Proof:

Consider the function f. By the left-cancellation property of groups, if ab = ac, then b = c. This means that if b \neq c, then ab \neq ac, and it follows that f is injective. Since the domain and codomain of f are the same (G), this means that f is in fact bijective.

The proof for bijectivity of g is identical, but uses the right-cancellation property instead.

The intuitive significance of this is that left- or right-multiplication by a given element always sends distinct elements to distinct elements, which is pretty neat.

103: Dedekind Cuts

The Dedekind cut is a method of constructing \mathbb{R} from \mathbb{Q}. A cut is first defined to be a partition of \mathbb{Q} into 2 non-empty subsets A, B such that

  1. if p \in A and q < p, then q \in A
  2. if p \in A, then there is a q \in A such that q > p (meaning A has no maximum element)

A cut can be equivalently determined solely by A alone, rather than the pair (A, B).

Cuts can then be used to construct \mathbb{R} by defining any r \in \mathbb{R} to be the cut where A is the set of all members q of \mathbb{Q} such that q < r. That is, r is simply defined as the subset of rationals smaller than itself, and \mathbb{R} is the set of all such subsets.

102: Kernel Space vs. User Space

Kernel space and user space are separate regions of virtual memory distinguished from each other in an operating system for purposes of security, stability, and centralizing control. Typically, user space is the space which user applications have direct access to and can work with, while kernel space is a privileged space which only especially stable and trustworthy programs, such as the kernel, can access. This barrier essentially insulates possibly insecure or unstable applications from power, preventing them from doing things like crashing the system or messing with other applications’ memory.

101: Non-Commutativity of Symmetric Groups

In general, the symmetric group S_n (the set of permutations of n distinct objects under permutation composition) is non-abelian. The somewhat trivial exception is when n \leq 2.

100: Primitive Types vs. Reference Types (Java)

In the Java programming language, values either have a primitive type or a reference type. The primitive types are:

  • boolean
  • byte
  • short
  • char
  • int
  • long
  • float
  • double

All other types not in this list are reference types.

A value with a primitive type stores the information determining the value itself, such as the binary code for a given integer or character. By contrast, a value with a reference type stores the address of the location in memory where this information can be found. For instance, after declaring and instantiating a variable

\texttt{String s = "string";}

the variable \texttt{s} doesn’t store the code for the String itself, but rather a ‘pointer’ to where this code can be found.

This has important consequences for how primitive values are assigned to variables or passed as parameters, as opposed to reference values. A primitive value passed or assigned will have the bits describing the value itself copied to the target, whereas a reference value will merely have the address of these bits copied.

99: Non-Orientable Surfaces and the Möbius Strip

The Möbius strip is a canonical and minimal example of a non-orientable surface, in the sense that

  1. a surface is non-orientable if and only if it has the Möbius strip as a topological subspace, and
  2. the Möbius strip is the only surface with this property.

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.]