Today I Learned

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

177: Elementary Embeddings, Elementary Substructures

In logic and model theory, an embedding \gamma : \mathcal{M} \rightarrow \mathcal{N} between \mathcal{L}-structures \mathcal{M, N} is called an elementary embedding if

\mathcal{M} \vDash \phi(a_1, \dots, a_n) \Leftrightarrow \mathcal{N} \vDash \phi(\gamma(a_1), \dots, \gamma(a_n))

for any \mathcal{L}-sentence \phi and a_1, \dots, a_n \in M. A substructure \mathcal{M} \subseteq \mathcal{N} is called an elementary substructure, denoted \mathcal{M} \preceq \mathcal{N}, if the inclusion map is an elementary embedding.


176: Removable Singularities vs. Poles

Let f: \Omega \rightarrow \mathbb{C} be holomorphic on \Omega except at isolated points where it’s undefined. One such isolated point z_0 is said to be removable if f can be extended to include z_0 such that the extension is holomorphic in a neighborhood of z_0. That is, if z_0 is “correctable”.

By contrast, an isolated undefined point is said to be a pole if not removable, but there’s a positive integer n such that z_0 is a removable singularity of the function

f(z)(z - z_0)^n.

In this case, n is called the order of the pole.

175: Tarski’s Theorem

In first-order logic, Tarski’s Theorem states that where \mathcal{M, N} are structures and \mathcal{M} \subseteq \mathcal{N}, the following are equivalent:

  1. \mathcal{M} \preceq \mathcal{N}
  2. For all Y \subseteq N definable over M, if Y \neq \varnothing then Y \cap M \neq \varnothing.


174: Decidability of Recursive, Complete, Satisfiable Theories

It’s pretty much in the title. If T is an \mathcal{L}-theory which is recursive, complete, and satisfiable, then T is decidable. That is, there’s an algorithm which takes an \mathcal{L}-sentence \phi and outputs whether or not T \vDash \phi.

(T being recursive means that there’s an algorithm which similarly takes \phi as input but outputs whether \phi \in T.)

173: Vaught’s Test

In model theory, Vaught’s Test (also known as the Łoś–Vaught test) determines whether certain \mathcal{L}-theories T are complete. It states that if T is satisfiable, has no finite models, and is \kappa-categorical for some \kappa \geq |\mathcal{L}|, then T is complete.

Proof outline Assume T isn’t complete. Then there’s a sentence \phi such that T \nvDash \phi, T \nvDash \neg \phi, meaning T \cup \{\phi\}, T \cup \{\neg \phi \} are satisfiable, meaning both have infinite models (since T has no finite models), so by [172] we can find models \mathcal{M}, \mathcal{N} of cardinality \kappa which respectively satisfy these theories. But since \mathcal{M}, \mathcal{N} disagree on \phi, they are not elementarily equivalent and hence not isomorphic, contradicting the assumption that T is \kappa-categorical. Thus T must be complete.

172: Infinite Models of L-Theories (Variation of Lowenheim-Skolem)

Suppose \mathcal{L} is a first-order language and T is an \mathcal{L}-theory with an infinite model. Then for every infinite cardinal \kappa \geq |\mathcal{L}|, T has a model of cardinality \kappa.

This result — a variation of the Löwenheim–Skolem theorem — implies that theories with infinite models can’t have unique models up to isomorphism.

171: More General Cauchy Integral Theorem

Let \Omega \subseteq \mathbb{C} be open, and let \Gamma \subset \Omega be a cycle which is null homologous. (That is, \Gamma is a collection of closed curves the winding number of which is 0.) Then

\int _\Gamma f(z) dz = 0.

170: Dangling Pointers

Dangling pointers are essentially pointers which are “left hanging” after the memory location they point to has become invalid. More specifically, a dangling pointer is a non-NULL pointer which points to memory which has become deallocated or otherwise has become invalid memory for the pointer to be pointing to.

For instance, an example in C (a language prone to this problem) taken from Wikipedia:

   char *dp = NULL;
   /* ... */
       char c;
       dp = &c;
     /* c falls out of scope */
     /* dp is now a dangling pointer */

If a dangling pointer is attempted to be dereferenced, unpredictable (incorrect/garbage) behavior can result.

169: Finiteness of Logical Implication

Suppose T is an \mathcal{L}-theory and T \vDash \phi. Then \Delta \vDash \phi for some finite \Delta \subseteq T.

Proof Let \Delta \subseteq T be finite and suppose \Delta \nvDash \phi. Then \Delta \cup \{\neg \phi\} is satisfiable, so T \cup \{ \neg \phi \} is finitely satisfiable and by the compactness theorem T \nvDash \phi.

168: Memory Leaks

In computing, a memory leak occurs when a program fails to release memory which is no longer required. For instance, a C program where the programmer dynamically allocates memory for a task but forgets to de-allocate it.

In certain circumstances, memory leakage may not cause big problems or might even be asymptomatic, like in programs with a little memory leakage which never actually run for long enough periods of time that memory usage becomes a problem. However, in worse cases memory leakage can lead to the complete failure of a program.

A couple types of programs at high risk for memory leakage are those in embedded systems (which can run continuously for years at a time, giving even small leaks the potential for being problematic) and those where memory is allocated extremely frequently for one-time tasks (such as rendering in a video or game).

While many languages like Java have built-in garbage collection which automatically cleans up unused or unaccessible memory, other languages like C and C++ require the programmer to be on top of making sure these leaks don’t happen in the first place. However, there are memory management libraries and memory debugging tools written to help with these languages. It should also be noted that automatic garbage collection comes with a performance overhead, so whether it’s desirable varies depending on the situation.