Musing
Logic is something we use every single day. Everybody uses it almost without thinking. In physics, logic is the connective tissue that ties together every law, every theory, every theorem, every postulate, every experiment and indeed every description of an observation. In mathematics, this logical connectivity is even more manifest. For physics, we can lean on empiricism. This is not so for mathematics! Every mathematical result can be seen as logical deductions from some set of premises. So, maybe it’s worthwhile to formally analyze logic itself.
Most of what I know about formal first order logic comes from the book “A Friendly Introduction to Mathematical Logic” 1. Of course, just like everyone else, I use logic every day and everywhere without thinking about it formally. Further, I did use some concepts of first order logic before, for example, and are symbols of first order logic used pretty ubiquitously in math and physics.
There’s a short disclaimer: everything I say here will be rather informal and loose by the standards of formal logic. I am not a logician. I would recommend reading Leary’s excellent book. I might also use his notation without explicitly introducing some of it.
The Setup
There is a dichotomy in formal logic which deserves some thought: syntax vs semantics. Syntax is the symbols on the page and how they are arranged. The rules of syntax tells you which string of symbols are valid and which are invalid. For example: “The cat walked past the dog.” is a valid sentence while “ps.t athe dog cat walked” is not. Semantics tells you, given a valid string of symbols, what does it mean? In the sentence “The cat walked past the dog.” what is the cat and what is the dog? What is the cat doing? What’s the dog doing?
Musing
In this view, is it a bit unfortunate that we have the common phrase “you’re just arguing semantics”. For what better thing is there to argue about than meaning?
A language is a set of symbols together with (syntactic) rules for how those symbols are allowed to come together to form valid terms, formulae, and sentences. A structure is a universe together with rules that map symbols and strings of symbols in the language to the universe. What is “a universe”? This might be, at its heart, a philosophical question. But for us, we will just think of it as a set. For example, if we are doing number theory on the natural numbers, the universe is and we’ll call the structure .
A little bit more formally, a language will have the following logical symbols: (equals, not/negation, for all, logical or) along with any number of special symbols in three classes:
- Constants, we will use to mark them when talking abstractly.
- Functions, denoted abstractly by . It is important that we know the “arity” of a function, i.e. how many arguments does it take.
- Relations, denoted abstractly by . Again, arity is important here.
Very importantly, we also need to be able to write down variables, e.g. . Like Fortran, we declare all variables up front and sweep them into the logical symbol set (Leary does this). Unlike Fortran, we’re free to use a (countably) infinite set of them without exploding memory.
An example is worth a thousand (actually probably more) words here. Let’s take the language of number theory as a logician would call it: . A few things to note. First, the 4 logical symbols (and the infinity of variable symbols) I defined earlier are hiding in there. Second, it does help a lot if you think of these as literally just symbols at this point, unattached to their usual meanings, like that means adding numbers. Finally, with these symbols, and rules on how these symbols come together, we will be able to write up all the wonderful sentences of number theory. But writing things in this language is a bit like trying to write in assembler code (or machine code, or whatever lower layers there are down there).
In the language of number theory, is a constant. The successor function is a 1-ary function that takes a single input (e.g. , , etc.). are binary functions that take 2 inputs and is a binary relation. For the constant, function, and relation symbols, we need to define interpretations to what they are and do within the universe. Variables will be assigned values by assignment functions that take the variable and assigns to it an element of . Finally, some sentence being true in , which we will write as , gets reduced down to seeing if the mappings led to the outcome the sentence said it would.
So that we don’t have to always write and tell you how many symbols we used, we will write to mean the numeral, i.e. string of characters in our language, that corresponds to the number a. So if then is . This is short hand notation so that we can discuss things, it is not a new symbol in our language.
W. V. O. Quine
To be is to be a value of a variable.
Hint
There’s a fair amount of keyword collision happening as we write about logic. Often it’s because the same thing can be seen from two different perspectives, though, it’s still important to keep both perspectives clear in one’s head. Sometimes we just don’t have enough words.
So, we have the following notation and concepts: is the element of that points at (we’ll call it zero). The interpretation of is takes an element of the universe and maps it to another element of the universe, commonly called the successor, for example, it maps zero to one, one to two, etc. Another way to look at is as a subset of , or in other words, as a set of tuples . Now we get to — these are addition, multiplication, and exponentiation — as binary functions they can be seen as maps or subsets of .
The relation symbol(s) are special because they bring truth and falsehood into the picture. If we had no relation symbols (including no ) all we would be writing would be terms. Things like one plus two. There’s no way to assign truth values to a term. Once we have a relation symbol, we can write formulae and sentences (a sentence is a formula without any free variables, i.e., without any variables that are not quantified over / bound) and formulae and sentences can start to have truth value. A formula can have a truth value if you use an assignment function directly to assign elements of the universe to its free variables. A sentence will always have a truth value. Relations are so important that often gets added to the logical symbols (as we have) and therefore every language has at least 1 relation symbol. I won’t belabor what means. For the interpretation of is: . In general, any -ary relation is a subset of .
Polish Notation
It is important that our language is unambiguous. But it is also important that our language is at least somewhat readable. Polish notation hits the former requirement but misses somewhat the latter. What is Polish notation? It is a notation where connectives (like ), function symbols and relation symbols come before the arguments. In defining the functions and relations, we need to define their arity. Knowing their arity makes any (valid) string of symbols in Polish notation unambiguous because we can count how many arguments got “eaten” by each of the function and/or relation symbols. So here’s a valid string in Polish notation in :
Can you read it? Unambiguous in this instance doesn’t mean easy to read unfortunately. However, there is a deterministic (unique) way to pair the atomic symbols up in that expression so that the connectives, function and relation symbols are applied correctly and lead to the following, somewhat more human readable:
The Missing Logic Symbols
Some might be wondering where some other often used logical symbols went. So far, we only introduced , what about which we often see and use? As it turns out, these logical symbols can be written using only and so they will be seen as simply short hand notation. It is instructive to do the exercise of turning (or) into (and). But to spoil the ending: can be written as . To convince ourselves of this, we need only to write out the truth tables for the two sides. This fact is called “De Morgan’s law”. Next, we look at which means “there exists a…”, for example, says “there exists an for which (is true).” This can be obtained from via . Saying “there exists an x for which such and such is true” is the same thing as saying “it is not the case that for all x such and such is false” (and vice versa!). Finally, we have the two implication symbols, we will just give them:
- :
- :
Truth vs Proof
How do we know something is true? Because we can prove it? Or can some things be knowably true without proof? Can some things be unknowably true? I will leave the philosophizing for another day, but here in first order logic land truth and provability are 2 distinct notions that showcase a manifestation of the dichotomy between semantics and syntax brought up earlier. Truth in first order logic will mean semantic truth in a structure. In other words, given the structure , we will say that a sentence is true in or satisfies and we denote this, in the metatheory language, using . Very loosely speaking, a sentence will be true in a structure if the relation(s) that are in that sentence contains (as elements) sets which correspond to the relation that the sentence is saying holds. For a crude example, take the sentence in : . Is there an element of that looks like (a lot of symbols to just say )? The answer is yes (at least if we assume the axioms of number theory hold). There are of course much more complicated sentences than the one I just gave. However, if after doing all the semantic mapping one finds that all the relations in the sentence hold, the sentence is true. If they don’t hold, then the sentence is false. The language I’m using might suggest that the semantic mapping is done procedurally, but it’s not. The semantic mapping is not “done” so-to-speak, it just “is”.
A proof in first order logic is a finite sequence of deductions that start at axioms and ends at the theorem being proved. A proof is a purely mechanical procedure following the rules of deduction (sometimes also called rules of inference) that takes all prior steps as input, outputs a new formula (or sentence) and proceeds forward until the theorem being proved shows up as the final step. A proof is a purely syntactical exercise and that’s why proof checkers like Lean or Coq can exist. Lean and Coq are languages for coding deterministic programs that can take every step in a proof and validate that it follows the rules of deduction. It should be emphasized again that a proof is finite. Simply saying “give me until eternity to prove it for you” does not work as a proof.
We introduce a bit of notation here. We will use the symbol for a (general) set of axioms—it should be seen as a set of sentences like and a model of is a structure (say, ) such that each is true in the model and we will write . We will say if and only if is satisfied in every model of . Note that is not a symbol of the language. It is a symbol in the metalanguage and indeed, we could consider “English” to be part of that metalanguage. So when you see show up, you know that we are talking in the metalanguage, not in the language of first order logic that we are discussing. The same is true for the structure symbols themselves like and .
For proving things, we typically use the symbol . Recall that a proof is a finite list of deductions following our rules of deduction. We will write if and only if there is a valid proof (also called deduction) of from the axioms .
Musing
We haven’t talked much about what axioms are up to this point. We just said they are a set of sentences using the symbols of the language. We also haven’t talked much about rules of inference. Both of them are needed because we need to avoid infinite regress. A proof has to start from somewhere. If we keep asking “why” ad infinitum we can never start a proof. So axioms are the bedrock sentences that we choose. Sometimes it’s a matter of taste which axioms we choose, sometimes it’s a matter of necessity, but we do want to be good at choosing them, for example, we wouldn’t want a set of axioms that are obviously inconsistent. You need at least some rules of inference to tell you, once you finished writing down a formula, what are the valid next formulae to write. One example of such a rule of inference might be listing a particular axiom is always a valid proof step. A less trivial one might be modus ponens: if and are in your prior deductions, then you may add as a deductive step.
We often also split axioms into the logical axioms (Leary calls these ) which always hold, no matter what theory you’re talking about, and the non-logical axioms (e.g. the axioms of Peano Arithmetic). The logical axioms form part of your deductive system while the mathematical axioms are the ones you are exploring with your theory building so-to-speak. Logical axioms basically look the most like tautologies. An example of one might be “universal instantiation” which in FoL is written assuming t is substitutable for x. Maybe there is some deep meaning to this axiom, as its name suggests, or maybe it’s just a tautology (in the philosophical sense). Here we use the notation to mean “replace every free instance of x in with t” and we needed the “assuming…” caveat in case the substitution leads to a variable naming collision or something like that.
The final remark here is an interesting historical one. Russell and Whitehead, in their Principia Mathematica tried to reduce all of mathematics down to pure logic. If they were successful, then there wouldn’t be any mathematical axioms since the logical axioms would be all you need. They got pretty close, but ultimately there were a few axioms they needed which didn’t seem purely logical in nature.
Soundness Theorem
One of the properties of a deductive system that one would like to have would be soundness. In plain English, soundness just says that if you can prove a sentence from some axioms then that sentence is true in every model of those axioms. In other words, we wouldn’t generally like to be able to prove something that was false. The soundness theorem gives us that reassurance.
The statement of the theorem is extremely simple:
Which just says in symbols exactly what we said above. The proof of the soundness theorem, of course, requires us to know details of our deductive system since the whole purpose is to say that our deductive system, the logical axioms and the rules of inference, are sound. As we have essentially glossed over all the details at that level (how exactly assignment functions work, for example), we won’t try to give any proof here. But just to give a little color, you essentially start at the axioms (each axiom is trivially true in every model of the axioms) and then you show that every step of inference, governed by your rules of inference, must preserve truth. Then you tie it together to show that the whole proof will preserve the truth.
The theory of a set of axioms are all of the sentences that are true in every model of the axioms: . The “theorems” of those axioms are those sentences that are deductively provable from them: . Showing the proof of Soundness then amounts to showing .
There is also a closely related notion of the theory of a structure which are all the sentences true in a structure. In fact, this is the theory that we often use in our discussions. One should not think that the two theories are identical as in general they are not. In fact, we shall see next that is the same set as (the completeness theorem). The possible gap between and , given , assuming certain properties of is actually the content of Gödel’s incompleteness theorems.
Musing
What if the axioms are inconsistent, i.e. proves a contradiction? In that case, there are no models of the axioms and is vacuously satisfied for every and the principle of explosion (from a contradiction, everything can be proved) tells us that for every sigma. And even in that scenario, the Soundness theorem still applies.
Completeness Theorem
The converse of the soundness theorem is the completeness theorem. It says that truths which hold in every model of a set of axioms can be provable from that set of axioms:
The proof of this theorem for first order logic was given by Gödel in his 1929 dissertation. The version of the proof provided by Leary is actually from Leon Henkin 1947. The proof of the completeness theorem, given by either author, is rather daunting, filled with technical details, and will not be supplied here. There’s perhaps an interesting tangent that’s worth discussing at this point.
The tangent is the question “didn’t Gödel prove the incompleteness theorem?” And indeed he did. Gödel proved completeness first in 1929 and then proved incompleteness in 1931. There is no contradiction because the sense of “completeness” in the completeness theorem and its sense in the incompleteness theorem is different. The completeness theorem is concerned with the provability of sentences which are true in every model of the axioms while the incompleteness theorem is concerned with provability for sentences which are true in only certain model(s) of the axioms. In other words, there could be sentences which are true in some models of the axioms and not true in others and that gap is where the incompleteness theorem lives, i.e., that such a gap always exists if the axioms fulfill certain conditions.
We give a little bit of color here for the proof of the Completeness theorem. The proof starts by making a hypothesis: we expect that if then . Here is a symbol used for the contradiction sentence which is false in every model. If we can prove this hypothesis, then actually we can prove the general case (with replaced by arbitrary sentence ). For suppose we are given an arbitrary sentence such that . Then we know that . Why? This comes from the definition of which says is true in every model of , therefore, there are no models of and if there are no models, we can put any sentence we want on the right of . We choose because that’s the sentence we need for our purposes here. Now we apply our hypothesis to get . We know from proofs by contradiction that if then and we have what we need: that for arbitrary sentence, assuming our hypothesis. Hence, all we need is to prove our hypothesis.
Another way to look at our hypothesis is that it is saying the sentence “if there are no models of then proves a contradiction”. The contrapositive of this sentence is “if doesn’t prove a contradiction (i.e. is consistent) then there is a model of . The rest of Henkin’s lengthy proof of the completeness theorem goes to build a specific model given any consistent . One might wonder, since we don’t know anything about other than that it is consistent (I haven’t give you any actual sentences it contains), how can I build a model? We actually construct the model as a Henkin structure where the universe consists of all variable free terms of the language itself. After that, the steps get very technical. We have to expand our axiom set in a consistent manner while simultaneously expanding our language so that witnesses for the truth of sentences will exist in our universe. Then we have to prove that our entire construction is done consistently so that what we end up with is a legitimate model of . Since a legitimate model of is constructed, we prove the contrapositive which proves our hypothesis which proves the completeness theorem. No further details will be given here.
Compactness Theorem
The compactness theorem is essentially a corollary of soundness and completeness plus the fact that our deductive system permits only finite deductions.
(Compactness Theorem). For any set of axioms , there is a model of if and only if every finite subset of has a model.
proof:
For the “only if” direction: if has a model then that model also models every finite subset of by the definition of “model”.
For the “if” direction: suppose the opposite, that every finite subset of has a model but yet itself has no model. By the completeness theorem we just outlined, this would mean . Since our deductive system requires that any deduction is finite, that deduction of must take only a finite number of steps and use a finite number of sentences in . Let’s call that finite set . Then by soundness (remember the musing that says it applies in this case too). Hence, has no models, a contradiction with our supposition. Hence, it must be that has a model.
One can use compactness to show that it is, in some sense, impossible to fully characterize some given structure using some set of axioms. Slightly more precisely, if we look at a structure which models a set of axioms, we will be able to find another structure where every sentence of is true but is not isomorphic to .
Löwenheim-Skolem Theorem
The core concepts here are substructures and elementary substructures. A substructure of a structure , for which which we will write , is basically a structure whose universe is a subset of ‘s universe, uses the same constants, and has its relations and functions restricted to its own universe appropriately. I.e. for every n-ary relation symbol and for every n-ary function . The elementary substructures are the ones which preserve truth, i.e. (” is an elementary substructure of ”) if for every formula and every assignment function (note the there) we have . We call an elementary extension of .
Given those preliminaries, we will state and not prove the following:
(Downward) Löwenheim Skolem: A structure of a countable language has a countable elementary substructure.
proof: (omitted)
(Upward) Löwenheim Skolem: An infinite structure of a countable language has an elementary extension of size or greater for every cardinal .
proof: (omitted)
Skolem’s Paradox
We discuss the Löwenheim-Skolem theorem here because it leads to an interesting paradox in ZFC set theory. ZFC set theory is one of the popular foundational theories of all of mathematics. Very roughly speaking (and without getting too philosophical), we can encode pretty much all of the mathematics that we do (Groups, Topologies, Differential Geometry, etc.) ultimately into set theory + a bunch of definitions which add more structure. The axioms of ZFC are given in set-theory-axioms.
Now, if ZFC is consistent (which, admittedly, we can’t prove from “inside ZFC” by Gödel’s second incompleteness theorem), then it will have a model. Given the downward Löwenheim Skolem theorem, we know that this model has a countable elementary substructure which also models ZFC (for elementary substructures preserve truth). By the axioms of ZFC there exists a countably infinite set (the axiom of infinity) and the power set of any set is also a set (the axiom of power). Cantor gave a proof, which follows from the axioms of ZFC, that the power set of a countably infinite set is uncountable. But we just said there’s a countable model of ZFC! Paradox.
Musing
A historical note is in order. Cantor gave his diagonalization argument and proof before Zermelo and Fraenkel axiomatized set theory. However, Cantor’s theorem, that there is no bijective map between a countably infinite set and its power set is a theorem of ZFC, one need not worry there.
The resolution of this paradox requires us to think about what a bijection means. Let’s first add a little bit of notation. Cantor’s theorem says there is no bijection between the sets and the power set (incidentally ). A bijection is a one-to-one onto map between two sets and . But in ZFC the only relation symbol is and there is no primitive concept of a map. So when we say “there is a map” what we can only mean is there is a consistent way in which we can encode the concept of a map into sets, and such a set corresponding to the map exists (is an element of the universe). So, for example, we can encode a map of sets via the following procedure. We create a set (of sets) such that gets encoded into for all and . The set is an element of , the set encoding the whole map requires one more (talk about lack of efficiency). This is not the only possible encoding, but it is a sensible one.
Let’s call the uncountable model of ZFC and the countable one . In there exists “its versions” of and . Both of those objects are countable since the universe of is countable (and hence Löwenheim Skolem is satisfied). However, for any consistent encoding of maps to sets, there is no element of the universe of which encodes a bijective map between and . And hence, from the perspective of , the power set is truly uncountable. If one wishes to stop here, then I would say one has resolved Skolem’s paradox. Countable from the perspective of metatheory, uncountable from the perspective of .
There is, however, another puzzling observation if we want to dig a little deeper. Every element of the universe of is an element of the universe of , this is by definition of subset. So, the elements and also exist inside the universe of . By the fact that , we know that the sentence (we will write this in English, but assume I translated it into the appropriate sentence in first order logic) “there is no bijection between and ” is true in both and . So even from the perspective of , the thing we called is uncountable. Only in the metatheory is it countable. The resolution to this lies in the definition of the word subset and in the restriction that had to happen: ( here is the universe of ). Membership is what defines a set, but that membership gets restricted when we go to . Subset says “every member of is a member of ” but it looks no deeper. The things we called and , their internal structure, looks different in vs because the definition of membership is different. The sentence “there is no bijection between and ” is true in both models, but what and are internally could look different between and ( is the real culprit). In , the thing we called looks like a proper uncountable set (it looks like ).
Incompleteness
See: godel-incompleteness
Footnotes
-
Leary, C. C., and Kristiansen, L. A Friendly Introduction to Mathematical Logic. 2nd ed., Milne Library, SUNY Geneseo, 2015. ISBN 978-1-942341-07-9. ↩︎