Drawing Blanks

Premature Optimization is a Prerequisite for Success

From Compactness to non-standard models

leave a comment »

Alright, I have had enough reflection on Compactness and I want to smoothly transition to another topic. Nothing comes to mind but logic, so in this transitional post I’d like to quickly apply the Compactness Theorem to build a non-standard model of Arithmetic.

Let’s add a new constant symbol ω (omega) to Arithmetic. And let’s add an axiom schema: ω > 0, ω > 1, ω>2, … Any finite subset of this new theory has a model that interprets ω as some large enough natural number. Hence, by the Compactness Theorem, the whole thing has a model. That model is a model of Arithmetic and all arithmetic theorems are true in it. And in addition it contains a number ω that is greater than any standard integer. This is a non-standard model of Arithmetic.

Please note that the existence of this model has absolutely nothing to do with the Gödel’s incompleteness theorems or any other manifestation of incompleteness of Peano Arithmetic. I didn’t even say I was constructing my theory from Peano Arithmetic. We could take the complete True Arithmetic and achieve the same result. 

One curious thing about this new theory is that it proves all sentences of the form  ω > n, but it does not prove ∀n: ω > n. If it proved that, it would prove a contradiction, because ∀n ranges over all natural numbers defined by the theory, not just over the standard naturals. And the non-standard naturals must include S(ω) – the successor that is greater than ω. But if our theory proved a contradiction it would not have a model.

So this theory is ω-inconsistent. Per Wikipedia, “T is ω-consistent if it is not ω-inconsistent”. In the next post I’m planning to write about relationships between various consistency and soundness conditions. And Model Theory is an other melody.

Advertisements

Written by bbzippo

03/02/2011 at 7:45 am

Posted in math

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: