Monday Notes 9–3–18

What I’m Reading

Mathematical Logic, Chiswell & Hodges pages 78–96

This section of the book covers the remarkable Post’s Theorem, which states that every possible truth table admits at least one formula. Post’s Theorem gives us an algorithm for calculating such a formula.

  1. For every predicate that the desired formula is T, create a formula of only conjunctions (AND, ∧) which results in T
  2. Combine all of these formulas with disjunctions (OR, ∨)

Consider the truth table below

The results of the algorithm are therefore

  1. Row 2: ( p ¬q ); Row 3: ( ¬p q )
  2. ( p ¬q ) ∨ ( ¬p q )

Using De Morgan’s laws, we can immediately find another formula which also satisfies the table. In our table, that formula is

¬(¬( p ¬q ) ∧ ¬( ¬p q )), which is equivalent to

¬( (¬p q) ∨ (p ¬q) )

The formula we computed in step 2 and the immediately previous formula are said to be conjunctive normal form (CNF) and disjunctive normal form (DNF) respectively. More formally stated, a formula is in CNF if it is the conjunction of one more formulas which are DNF. DNF is defined by the converse; the disjunction of one or more formulas in CNF.

nb: Every “simple” formula, consisting of either φ or ¬φ is considered to be in both CNF and DNF. This allows the recursive definitions of DNF and CNF to terminate.

In prepositional calculus, every formula admits a truth table and every truth table admits a formula in CNF and DNF. Therefore, it follows that for every formula there exists at least two logically equivalent formulas in DNF and CNF.


Natural Numbers

Tying back to the Hydra Game, which I discussed in my first Monday Notes, I’ve begun some investigation into ordinal numbers. The theory of ordinals is an extension of the natural numbers that allows one to make statements about infinite quantities, such as “the smallest ordinal which is larger than everything in {1,2,3,…}.”

To begin, we have to understand the way that traditional arithmetic is expressed in the language of set theory. Peano’s Axioms for the Naturals are as follow:

  1. There exists a set N with a distinguished element z and a function S mapping N to itself.
  2. If n is in N then S(n) is in N
  3. n + S(m) = S(n + m)
  4. n * S(m) = n * m + n
  5. (Induction Property) If a set P contains z, and n in P implies S(n) is in P, then all of N is in P.

The above can look quite daunting to the uninitiated. However, by noticing that z can be replaced with Zero and S with Successor, it is straightforward to show how the remaining properties fall into place, with perhaps the exception of 5. If you aren’t familiar with Peano’s Axioms, I recommend taking a moment to convince yourself that the properties 3 and 4 make sense. If you get tired of writing S over and over, try incorporating some new symbols — perhaps ‘1’ for S(z) and ‘2’ for S(S(z)).

Using some clever set theory, it is possible to express the natural numbers using only sets.

  • Let z be ∅
  • Let S(n) = n ∪ {n}

Then our first few naturals are

‘0’ : ∅

‘1’ : {∅}

‘2’ : {∅,{∅}}

‘3’ : {∅,{∅},{∅,{∅}}}

These sets exhibit a property called transitivity. The property is expressed as follows: If x is in a transitive set X, then x is a subset of X. Expressed symbolically, (xX) →(xX). We can prove the succession operation expressed above preserves this property:

Base Case: ‘0’ is transitive.

Proof: ‘0’=∅, which contains no elements; therefore there can be no contradiction and the property holds.

Inductive Case: If n is transitive, then S(n) is transitive.

Proof: Let x S(n) = n ∪ {n}. Then (x n) ∨ (x ∈ {n}).

Case 1: x n

n is transitive by induction hypothesis, so xn and x ⊂ (n ∪ {n})

Case 2: x ∈ {n}

Since {n} only contains one element, we conclude that x = n. We may then substitute x for n in the definition of S(n) = n ∪ {n}.

x ∪ {x} = {x, {x}}. By inspection, x ⊂ {x, {x}}.

By the above, transitivity satisfies the Induction Property of Peano’s Axioms and therefore all naturals are transitive. ■

Transitivity is a convenient property as it allows us to express ordering by means of set inclusion. If we have two naturals n and m such that n<m, then their respective representations n’ and m’ satisfy n’ m’. The proof is again by induction, so I’ll save you the details.

Extending to Infinity

I am not going to handle this rigorously, but I’d like to point in the direction of how we might extend the above definitions and properties to infinite numbers. We call the sets ∅, {∅}, {∅,{∅}}, {∅,{∅},{∅,{∅}}},… the Von Neumann ordinals. We also introduce an additional property and axiom:

ω-property: A set 𝜒 is said to satisfy the ω-property if (α ∈ 𝜒) →(S(α) ∈ 𝜒)

Existence of ω: There exists exactly one ordinal that contains 0, satisfies the ω-property, and contains no other ordinals.

The ordinal described above is the first infinite ordinal and is referred to as ω. By definition, it is larger than any successor of a finite ordinal. However, this does not mean that is the largest ordinal. In fact, we can simply the the successor of ω, which is expressed by our definition of the successor function as ω ∪ {ω}. It is clear by inspection that ω ∈ (ω ∪ {ω}). So the successor of ω is a valid ordinal which contains ω and so our semantic interpretation is that the successor of ω is larger than ω.

The Von Neumann ordinals are a syntactic method for describing the properties of certain infinite quantities. They allow us to extend our definition of the natural numbers as “successors” up to and beyond finite iterations of that successor function.

nb: The Buzz Lightyear joke is a bit overdone, so I’ve held off on it.