Two senses of completeness in first order logic

This is a brief post to explain an issue in response to some youtube videos and comments about Gödel's Incomplete Theorem (henceforth "GIT").

How can it be that Gödel proved that first order logic ("FOL") was complete, yet at the same time proved that decidable consistent axiomatizations of arithmetic within first order logic were necessarily incomplete?  The answer lies in the fact that there are two different (yet closely related) senses of incompleteness being used here.  It is important in understanding the basics of logic to understand the two different senses (not just for GIT, but in general).

One of these senses could be considered more proof-theoretic, and the other more model-theoretic.   More philosophically, one of them is more epistemological, one is more metaphysical.

The first sense is the sense in which FOL is complete.  To say a logic is complete is to say that the methods of proof it supplies are adequate to prove all the logically true statements in that logic.  So, FOL is complete means that whenever you take a set of axioms A, and consider a sentence S,  one will be able to prove S from A if and only if S's truth logically follows from A's truth.  (Best to write this out formally, but I am avoiding that here).

A can be any set of sentences at all, using any "non-logical" symbols (These being the symbols that require interpretation not fixed by the logic: the predicate, function, and constant symbols).

FOL is complete in this sense, but that doesn't mean that *every* sentence you can write in FOL using a given set of non-logical symbols is true or false.  That is because many senses will be neither true or false in all circumstances: they are not logical truths.   Whether they are true or false  depends on the non-logical interpretation given to the symbols.   For example, "(x) (P(x) -> P(x))" is a logical truth, so it is provable in FOL.  "(Ex) (P(x) and not P(x))" is false, so its negation is provable.  However, "(Ex) P(x)" is false with some interpretations of P, and true with others, so it is neither provable nor is its negation.  FOL's theorem proving techniques do all we could possible ask of them here (well, not quite, we might like them to give three answers: provably true, provably false, or not provable because it could be true or false.  Unfortunately this cannot be done: FOL is thus *undecidable* (or more precisely, *semi-decidable*.  Perhaps more later).

So now consider the second sense of incomplete.  What we want to do with FOL is use it to investigate various things of interest to us.   So we set a specific non-logical language, not just P's Q's etc.  In particular, we are interested in arithmetic: the mathematical structure of the natural numbers and the basic operations on them.  Traditionally studied has been the structure you get using the non-logical symbols 0,1,+, and *.   First order arithmetic is the study of arithmetic using first order logic and this non-logical vocabulary (henceforth "FOA")

Now the thing about this structure, is that from our understanding of its "intended interpretation" (the meanings we  give to 0,1,+,*), we expect that every statement we can make in the language will be true or false.   This is essentially a semantic point.  Philosophically, it is a comittment to realism about the natural numbers.  Their objective existence pins down the truth of every statement about them: in particular every statement about them we can make in the language of FOA.  This results in a syntactic fact.  For any P in FOA, either P or ~P will be in the set of true sentences of FOA.  This is what the second sense of complete amounts to: a set of sentences is called complete if for every sentence in the language in question, either P or ~P is in the set.  A syntactic criterion, but motivated by a semantic, or even metaphysical, idea.

The main thing we would like to do in order study of FOA is to give an axiomatization of of the true sentences of FOA that we can "deal with".  What this means precisely is arguably something that cannot be given a definite mathematical expression.   A finite set would be nice, but in reality we would be happy with some set for which we can decide membership in the technical sense of "decide" provided by computability theory. 

GIT then shows that no matter what set of sentences we take for an axiomatization A (in the Youtube thread, this set of sentences is called, R, and considered to be a set of rules for generating theorems in FOA), if that set of sentences is consistent (cannot derive falsehood using the rules of FOL), and decidable, then Th(R), the set of sentences that can be proved from it, is incomplete in the second sense above.

How can this be, when FOL is complete?  It is because the axioms A do not suffice to totally describe the intended interpretation we have in mind, the natural number structure.  No matter what set of axioms we choose, there will be some (really weird (imo)) structure that satisfies it (i.e., in which they are true) and which can be distinguished from the natural numbers.  (In particular, all of these structures will have in them a lot of extra numbers larger than every integer, arranged as an infinite and even dense set of copies of the integers).

The crucial point: since FOL is complete (in the first sense), every sentence S that is true in every one of the structures that satisfy the axioms A, will in fact be provable from A.  Unfortunately, though, since whatever set A we choose be satisfied by some of these weird structures, there will have to be sentences S that are true in the natural numbers, but not true in these weird structures.  They are like the "(x) P(x)" above, true in some cases, not in others, so FOL cannot prove them.

What is the nature of these sentences?  Well, as is popularly known, Gödel found one by using tricks derived from Liars's Paradox, but using provability instead of truth: finding a sentence that can be obliquely interpreted as asserting "I am not provable from the axioms A".   But mathematically speaking, this is not a sentence of any real interest, so some have argued that although any axiomatization will not have a complete theory, Peano Arithmetic ("PA", a particularly power axiomatization) is good enough.   There has been a search, to date of debatable success, for "natural" statements S that are not provable from PA.   The so-called Goodstein's Theorem is one of best-known examples.

One can also explain GIT in less "metaphysical" terms, keeping more just to a proof-theoretic framework, but I believe the above is in some sense more natural and of more philosophical interest, as well as being more psychologically compelling.

Philosophically (and psychologically)  an interesting issue here (imo) is our feeling that we do have an adequate understanding of the natural numbers to insist that the true theory of the natural numbers should be complete.   Personally, I believe that this is nearly a rock solid intuition that has to be accomodated.  GIT is then of great interest because it shows we are in at least semantic contact, if not epistemological contact, with some abstract structure that cannot be completely characterized in computation terms.   If necessary I will do a second post that elaborates on this idea (in particular, laying out the strong intuition that the true theory of arithmetic is indeed complete).

After comments, this post (quick draft) will be edited for clarity where required.

Inmendham on cigarette taxes

Inmendham has repeatedly said the taxes on cigarettes are 800%.  Cigarette taxes are high, but are they anywhere near that high? I tried politely to post the argument that they are not on his channel, but he blocked me and removed all trace of the posts I had made. 

He tells us the cost of name brand cigarettes is at least $7/pack in New Jersey and the cheapest ("no-name"?) packs are $6.50.    I looked up the excise taxes, federal and state, and the NJ sales tax, which I believe to be all the taxes on cigarettes there.   I then computed a tax rate of 146% and 190% for the $7 pack and the $6.50 pack respectively.  High, but a long way from the claimed 800%.

So now Inmendham says that the part of his "taxes" that is taxes is only 500% and the other 300% is things like lawsuit settlements that the tobacco companies have been forced to pay out to the government, and which they "pass on" to the consumer.  Okay, but those are not taxes.  Nevertheless, if we take his word for all this, the taxes are 500%, but I compute 146% on the cheapest brand-name cigarettes.

Inmendham claims the retail "fair market cost" cigarettes would be only $0.75.  But where does he get this from?  In his latest video  (09 Jan 2013) he cites some website (not clear why this site is an authority) which apparently gives some cost figure like this for "the cost of production".

However, "the cost of production" is not the retail cost.  There are many other costs that are included in a retail cost.  Advertising, retail markups, profits.

Perhaps a more authoritative site would be the tobacco companies themselves.  They are unlikely to undercount the amount of money that is going to the government!  So I looked at one of these sites at http://www.rjrt.com/statemsapayments.aspx.

Note that it doesn't talk at all about "taxes" but instead "government profits".  That is a very strange phrase to use for government monies.  Based on the main link to this page, it appears that this phrase refers to the sum of taxes and what they call "tobacco settlement payments" -- presumably those monies the companies have been forced to pay as a result of lawsuits (what Inmendham says makes up 300% of his "taxes").

Here are the numbers for New Jersey:   Government: $5.38 (68%), Cost of manufacture: $1.20 (15%) Markup: $.94 (12%) Profit: $.40 (5%).

This gives a retail price of $7.89, higher than Inmendham's, but working with it, we find that the "tax" (in his words) is 68/32 or 213%.

So according to RJReynolds, the entire government take from the cost of a pack of cigarettes in NJ is 213%, not 800%.

We could compute the percent take for the cheaper cigarettes, and also estimate how much is tax versus settlement payments, but for now, this is pretty useful information.