Today I Learned

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

Monthly Archives: October 2017

180: Software Aging and Rejuvenation

Software aging is the degradation of a software system’s ability to perform correctly after running continuously for long periods of time. Common causes include memory bloating, memory leaks, and data corruption.

To prevent undesirable effects of software aging, software rejuvenation can be done proactively. This can take many forms, the most well-known of which is a simple system reboot. Other forms include flushing OS kernel tables, garbage collection, or Apache’s method of killing and then recreating processes after serving a certain number of requests.

Advertisements

179: Universal Axiomatization and Substructures

Definition universal sentence is a first-order sentence of the form \forall \bar{v} \phi (\bar{v}), where \phi has no quantifiers.

Definition We say an \mathcal{L}-theory T has a universal axiomatization if there’s a set \Gamma of universal \mathcal{L}-sentences such that \mathcal{M} \vDash T if and only if \mathcal{M} \vDash \Gamma.

With the above definitions, an \mathcal{L}-theory  T has a universal axiomatization if and only if wherever \mathcal{M} \vDash T and \mathcal{N \subseteq M} we have that \mathcal{N} \vDash T. In the words of Marker’s Model Theory, “a theory is preserved under substructure if and only if it has a universal axiomatization.”

178: The Residue Formula

In complex analysis, the residue formula states that where f is a holomorphic function on an open set containing a circle C and its interior except for finitely many poles z_1, \dots, z_n in the interior of C,

\int _C f(z) dz = 2 \pi i \sum _{k = 1} ^n \text{res}_{z_k} (f).

That is, the integral of the circe is completely determined by the residues of f about the poles in its interior.

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.