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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s