Completeness with Reference to

Have you felt at one with the Universe before? Maybe not, if you’re preoccupied with day-to-day hassles. But even if you have, that state is inherently not stable. We’ve developed a sort of disconnect with reality as humanity has grown with the complexity that comes with language, society, and even still: globalization. Mathematically too, nothing can ever be unified or “complete”, as Kurt Gödel shows.

In 1929, he published his completeness theorem, showing that truth is provable on the fundamental bases of logic. You will note this concept, called meta, to often have confusing self-referential uses: doesn’t illustrate meta until the phrase follows its quotation. This is an example of Douglas Hofstadter’s original quine: yields falsehood when preceded by its quotation. It’s weird to use assertions to prove the very logic of logic, but Gödel essentially stated that 1) any model with rules and elements, such as addition and integers, can itself be associated with a number that can systematically be enumerated by a function that (recursively) calls itself, and 2) the axioms of a model can provably result in no contradictions, and so give a consistent model. In short:

Every consistent theory of first-order logic has a recursively enumerable model.

That is not to say that any theory of first-order logic is complete. You can merely determine a model to be consistent at best. The usual desriptive model we use for maths is Zermelo-Frankel set theory, which seems consistent as far as I’ve noticed. It resolves some issues in Peano arithmetic, which I covered not too long ago.

Two years after his dissertation on completeness, Gödel published his incompleteness theorems, which dictate that there will always be a contradiction in any consistent model… wait what?

Didn’t I just say you can enumerate any consistent theory? That is true, but the Completeness theorem says the theories a given model produces can be proven valid, but not true. We have to consider what the notion of truth even is, and maybe assert the truth of axioms as truth itself, in true spirit of meta.

Advertisements

Turing Machine Language

A computer is a physical implementation of an idea called the Turing Machine, named after Father of Computing Alan Turing. It can come in several states {S0, S1, S₂, … Sn} where each state has a set of rules telling what should be written into memory where the read/write head is pointing and where to move next.

For most computers the output would be a screen and the input would be a pointer or key press, but for a Turing Machine, the output and input is a symbol from an alphabet such as {A, B, C} or {0, 1} written at the location of the head on a (theoretically infinite) strip of memory. The input tells the machine what state to go into, and the state says what symbol to write to memory and whether to move the head left or right, or stay put. Here’s an example of a 2-state Turing machine (excluding the halting state H where it does nothing) using an alphabet of binary:

State On 0 On 1
S0 Write 1, go right, change to S1 Write 1, go left, change to S1
S1 Write 1, go left, change to S0 Write 1, go right, change to H

What does it do? Well, let’s take a look at the memory over time T starting from state 0 over a blank tape:

T0
S0
T1
S1
0 0 0 0 0 0 0 0 0 1 0 0
T₂
S0
T₃
S1
0 0 0 1 1 0 0 0 0 1 1 0
T₄
S0
T5
S1
0 0 1 1 1 0 0 1 1 1 1 0

Notice how the machine alternates between states 0 and 1. However, after reading the first 1 while the machine is in state 1 (at time T5), the head will move right and halt. Given a two-symbol alphabet and two-state space, this is essentially the Turing machine which prints the most 1s onto an initially blank memory, called a “Busy Beaver”. If you gave it another state to go into, it would have more decision-making options available and could be programmed print out six 1s. Or if you gave its alphabet another symbol to work with, it could print nine 1s. But if you gave this machine a three-symbol alphabet and three-state space, it could print over 347 million 1s before halting.


Let’s switch tracks for a bit and think about how people think. We’re not sure how subjective thought works, but communication can tell us a lot about the state of things objectively.

Consider interfacing between human and computer communications. Human languages tend to be high-level and difficult to dissect, whereas computer languages tend to be low-level and exact with their instructions. Part of programming is being able to find middle ground where you specify a task at the level where both the programmer and the computer can understand it. Whenever you write in a high-level language and test code on a computer, it compiles the source code into an object program that can be executed on that machine.

Whenever we communicate in a high-level language, not all of the details are gone over one-by-one the way computers do so to interpret them. We tend to communicate through our voices, and these sounds can be ordered as linguistic symbols (phonemes), which can be translated into a grammatical language, which can then be interpreted into high-level programming that the computer can begin to come to understand. “Give me that box”, for example, can translate from speech into a more detailed, reorganized syntax of labels such as: “[subject]-me [command]-give [direct object]-box [qualifier]-that [indirect object]-them”. This will itself be compiled into machine code for running the task of recognizing the box and speaker, then actually moving the box carefully into their possession.

Breaking down this syntax into executable commands runs


The lambda calculus ignores the state of the process used to get the answer, given certain variables; the syntax λx. 2x is a function that takes in x and spits out 2x for any value of x; similarly, (λx λy. x)(5, 12) is a function that takes in x and y and spits out x for the values x=5 and y=12; there is no internal mechanism, like you can see in a Turing machine, but the two representations of basic calculations are isomorphic. That is, they can translate between each other.

Y = λf.(λx. f (x x)) (λx. f (x x)) is called the Y Combinator, which allows for programming languages to encode recursion. See Raúl Rojas’ tutorial for a step-by-step guide to the lambda calculus. Turing Machine language

There are many ways to break down a problem into fundamental components. Hopefully I’ve shown how all complex tasks in a computer are essentially broken down into bit manipulation and simple instructions that can be represented through a Turing machine or the lambda calculus

Axioms & Choice

 

Peano arithmetic is founded upon rules called axioms, which dictate how numbers (or groups of numbers represented as one entity, like those in the set of Complex numbers ℂ) can behave. For the set of natural numbers  including 0, there are 9 such axioms.

0. 0 is a member of the set of numbers ( 0 )
1. For all numbers ( ∀x ), x equals x=x )
2. For all numbers x and y ( ∀xy ), if x=y, then y=x
3. ∀xyz if x=y and y=z, then x=z
4. ∀x∀y if x∈ and x=y, then y∈
5. ∀x there exists a successor number x+1 ( ∃S(x)  )
6. ∀xy S(x)=S(y) if and only if ( iff ) x=y S(x)=S(y)x=y )
7. It is not true that there exists an x where S(x)=0 ( ∄x S(x)=0 )
8. If 0 is a member in X0X ) and if being a member in X implies the successor is a member of XxXS(x)X ), then X contains the set of all numbers ( X )

Pretty foundational mathematics, no? Set theory needs a lot of shorthand to keep track of what injections (preserving unique mappings from on set to another) are actually being made.

The last axiom is really infinitely many, patterning a recursive definition for the set of all natural numbers. These axioms define 2 as S(S(0)) and infinity as S(S(S(…S(0)…))). I should draw the distinction that  is used for elements constituting a set, while  or  is used for sets within sets. The former is used to distinguish proper subsets, like {1, 3, 5} being strictly only part of {0, 1, 2, 3, 4, 5}, while the latter includes redundant subsets, like {8} being a subset of {8}. Notably enough though, there is an empty set or null set {} (sometimes written ∅), which is a subset of everything because it includes nothing.

So why all this material on Piano Peano arithmetic (PA)? It relates in part to Object-Oriented Programming with the “is-a” parental relationship in class hierarchies, but the second-order logic of the Peano axioms is, in fact, not as strong as the Zermelo-Frankel (ZF) system of axioms that we use for most of mathematics. David Hilbert posed the question of PA’s consistency as the second of his 23 Problems.

ZF does not include the Axiom of Choice (AC), which states that given an infinite set of sets of elements, you can make a new set consisting of one element from each set. In other words, if I have infinite sock drawers each with at least one sock, I can take a sock out of each one and put that into a new sock drawer. That makes sense, right? We define the set ZFC to include the axioms of both ZF and AC. But this leads to

Russel’s Paradox

Banach-Tarski Paradox

Representing Infinities

Computers can oftentimes be thought of as dealing with infinity, whether it be pushing the limits of hardware, optimization, or reasonableness. There are many interesting ways to frame the idea, but here we’ll discuss sets. In school, you learned about the set of natural (counting) numbers, the set of integers (positive and negative numbers and zero), and the set of rational numbers (fractions or decimals). The sets are all infinite, but the infinity that represents the naturals (ℕ) is the same as the one that represents the integers (ℤ), which is the same as the one that represents the rationals (ℚ). Even though each number system contains the previous one (ℕ ⊆ ℤ ⊆ ℚ), these all have the same size, or cardinality, of infinity.

infinity-3680677_960_720

Consider the set of even numbers E and the set of odd numbers O. Both have the same cardinality, right? You can use a function to map every element in E to exactly one element in O (e.g., 0→1, 2→3, 4→5, etc.) without having extras or leaving out elements. Likewise, you can map one set of numbers from  to another set of numbers from , as with 1→3, 2→4, 3→5, etc., where the second set does not include the elements {1, 2}. Because the mapping is consistent, both sets have the same cardinality, ‎ℵ0 (pronounced “aleph naught” or “aleph null”). This is countable infinity, the smallest kind of infinity.

Infinities are not something we can innately observe; the universe may go on forever at scales large and small, but there are bounds on what we can see and do. Zeno’s Paradox states that motion is impossible because we have to travel over infinitely small distances to get anywhere. He argues that in order to travel a meter, you first have to travel half a meter, and in order to travel half a meter, you have to travel a quarter of a meter, and etc. But since atoms are discrete entities that don’t come close to being infinitely small, we actually can move over those distances over a finite timeframe by ‘jumping over’ Zeno’s infinitesimal singularities.

The counting numbers , integers , and rationals  are all bounded by the same infinity, ℵ‎0, because just as you can reach infinity in counting the set of all positive numbers, you can reach it by counting the set of all positive and negative numbers. These sets are the same size because the elements of ℕ can be systematically mapped to elements of  as 0→0, 1→1, 2→-1, 3→2, 4→-2, etc. There may be twice as many integers, but for every one, there is exactly one counting number, so really the sets are the same size of infinity. Essentially, ∞+∞=∞.

Likewise,  maps to  through the visualization of a table of all fractions with the numerators incrementing over the columns and the denominators incrementing over the rows.

1/1 ① 2/1 ③ 3/1 ④ 4/1 ⑨
1/2 ② 2/2 3/2 ⑧ 4/2
1/3 ⑤ 2/3 ⑦ 3/3 4/3
1/4 ⑥ 2/4 3/3 4/4

Make a “Dedekind” cut along the rational number line and define even more numbers that are irrational because they fall just between the cut and the next rational. For example, the Dedekind cut between numbers n such that n2<=2 and n2>2 marks the upper boundary of the rationals just below s2, so s2 is included along with infinitely many other real numbers in , a set of cardinality ‎ℵ1.

Cantor’s Diagonal argument

Continuum Hypothesis

bijective (injective and surjective)

David Hilbert’s idea of a hotel with countably infinite rooms may reframe our look at number sequences. If this hypothetical hotel were fully booked, then the set of rooms R could have a corresponding set of customers C mapped to it as 1→1, 2→2, 3→3, etc. Both C and R have cardinality ‎ℵ0. If two additional people each want rooms, the fact that there are no vacancies doesn’t stop the front desk from making room for them. By asking the customers to move from their room n to room n+2, they remap C to R as 1→3, 2→4, 3→5, etc., making the rooms 1 and 2 available. There is no room numbered ∞ where this mapping stops. It just keeps on going…

What if instead of two people demanding rooms in the fully booked infinite hotel, there was an infinite bus full of a set of people P each demanding a room? Well, we now know that ∞+2=∞, so why not try ∞2=∞? Mapping C to R through 1→2, 2→4, 3→6, etc., makes room in all of the odd-numbered rooms for the elements of P. If there were n buses each with infinite passengers, then the mapping of C is 1→2n, 2→3n, 3→4n, etc. and the mapping of each bus Pn (i.e., P1, P2, etc.) is 1→n, 2→2n+1, 3→3n+2, 4→4n+3, 5→5n+4, etc.

Now what if there were instead an infinite number of infinite buses B each filled with an infinite amount of people demanding rooms in this infinite hotel? What can you do?