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

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 oftentimes deal with infinity, whether it be pushing the limits of hardware, optimization, or reasonableness. There are many interesting ways to frame the idea. In school you learned about the sets of counting numbers, integers, and rationals. Each number system contains the previous as:  ⊂  ⊂ . But these are all essentially equally countable sets of numbers.

Consider the set of even numbers E and the set of odd numbers O. Both have the same cardinality, or size, right? You can use a formula 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, 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, but atoms are discrete entities that don’t come close to being infinitely small, so we can move over those distances over a finite time frame.

David Hilbert’s idea of a hotel with countably infinite rooms may reframe our look at number sequences to better show how they apply to computing. 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?


The counting numbers , integers , and rationals  are all bounded by the same infinity, ℵ‎0, because just as you can reach infinity in counting all the positive numbers, they can be systematically mapped to all the integers as 0→0, 1→1, 2→-1, 3→2, 4→-2, etc. Likewise,  maps to  through visualizing a table of all fractions with the numerators incrementing over the columns and the denominators incrementing over the rows.

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