Paradoxes, Completeness, and Skolem

I'm going to present technical results, and mention their impact in the philosophy of mathematics, but, in fact, the picture presented by the technical results is central to late 20th Century philosophy and to what has followed insofar as it is a reaction to the philosophical concerns of late 20th Century philosophy. (To put it provocatively, much of Rorty's work is a reaction to the Löwenheim-Skolem theorem.)

Cantor's theorem

• The set of all subsets of a set is of cardinality greater than that of the original set.

Proof. For the sake of deriving a contradiction, assume that for some set %$S$% the set of all subsets of %$S$% is of cardinality less than or equal to that of %$S$%. Then there is a function %$f$% from %$S$% onto all the subsets of %$S$%.

To show that that is impossible, it suffices to exhibit a subset %$C$% of %$S$% such that %$C$% is not in the range of %$f$%, that is, a %$C$% such that for all %$s$% in %$S$%, %$f(s)\ne C.$% Here it is: let %$C$% be %$\{s\in S:s\notin f(s)\}$%.

To show that the set %$C$% is as claimed, suppose that %$c$% is such that %$f(c)=C$%. Is %$c$% in %$C$%?

• Suppose %$c$% is in %$C$%. Then, since %$C=f(c)$%, %$c$% is in %$f(c)$%. But, since %$c$% is in %$C$%, %$c$% is not in %$f(c)$%, by the definition of %$c$%.
• Suppose %$c$% is not in %$C$%. Then, by the definition of %$C$%, %$c$% is in %$f(c)$%. But, since %$f(c)=C$%, that means that %$c$% is in %$C$%, contrary to assumption.

Thus, %$c$% is neither in %$C$% nor not in %$C$%, which is a contradiction. Thus, there is no %$c$% such that %$f(c)=C$%, and so %$C$% is not in the range of %$f$%, as required.

Paradoxes

All of these paradoxes were discovered and popularized by Russell. He named some of them after other people.

• Russell's %$\{x:x\notin x\}\in\{x:x\notin x\}$%?

By Cantor's theorem, the set of all subsets of the set of all sets is bigger than the set of all sets. But that seems obviously to be false: The function that maps every set that is a set of sets to itself and every other set to, say, the empty set, must, it seems, map the sets onto the subsets of the sets. The set %$C$% of the proof of Cantor's theorem is, in this case, the Russell set %$\{x:x\notin x\}$%, and that is essentially how Russell came up with the paradox.

• The original: Does the extension of the concept "is the extension of a concept whose extension does not fall under itself" fall under itself?
• Cantor's The class of all subclasses of the class of absolutely everything is a subclass of the class of absolutely everything, but it is larger than the class of absolutely everything (by Cantor's theorem, proved below).
• Burali-Forti What is the well-order type of the class of all well-order types?

Here are some other paradoxes. It is disputed how closely related they are to important ones above, but they are in some ways easier to think about, and therefore helpful.

• The barber (Russell): The barber in a town shaves all and only those who do not shave themselves. Who shaves the barber?
• A predicate is heterological if it does not describe itself. Example: monosyllabic, colorful, palindrome, red. Is heterological heterological?
• Grelling's paradox: Consider the least number not describable in fewer than 100 words. I have just described it in fewer than 100 words.

Cantor's theorem The set of all subsets of a set is larger than the set.

Proof: Let %$S $% be a set, and let %$F $% be a function mapping all subsets of %$S $% one-to-one into %$S $%. Let %$R $% be %$\{x\in S: \text{ if } F(T)=x \text{ then } x\notin T\}$%. The set %$R $% is not in the domain of %$F $%, contradiction.

Philosophical importance: Not every concept has an extension, at least not if extensions are objects. Deeply held central logical intuitions may be inconsistent. Contextual definition is at least sometimes logically defective.

Proof Theory and Model Theory

Complete change of topic.

Proof theory

Fix a set of symbols and define some set of strings of those symbols, the set of sentences. (Example: %$A $%, %$A\rightarrow B$% and %$B$% are sentences.)

Fix a set of rules that associate with some definite number of sentences a sentence. (Example: Associate %$B $% with %$A $% and %$A\rightarrow B$%.)

• A sentence (a theorem) is derivable from a set of sentences (axioms) if it is in the closure of the set according to the rules.

Everything here is completely syntactic: it just involves looking at sequences.

Model theory

Take the usual set of symbols. Fix a domain (a set of objects) and associate an object in the domain with every constant symbol and a set of %$n$%-tuples of elements of the domain with every %$n$%-placed relation symbol. We then know for each sentence, whether it is true or false. Call the data a model.

• A sentence is a logical consequence of a set of sentences if it is true in every model in which all of those sentences are true.

Everything here is completely semantic. It is the interpretations of symbols that do all the work, not just string patterns.

The sharp contrast between syntax and semantics that is always assumed by philosophers of language just is the distinction between proof theory and model theory.

Completeness

For the usual first-order predicate logic with equality, a sentence is a logical consequence of a set of sentences (axioms) if and only if it is a theorem based on those axioms.

Right to left is called soundness, and it is "obvious." The left to right direction is completeness (Gödel's completeness theorem), and it is a deep result.

The result makes first-order predicate logic with equality logic.

Skolem

Löwenheim-Skolem Theorem

Take any model. Take the set of all sentences of first-order predicate logic with equality true in the model. That set of sentences has a model with a countable domain.

The example that Skolem discussed: Let the model be genuine set theory. The set of all truths about sets has a countable model. That is sometimes called Skolem's paradox.

Why is that serious? Because it means that we do not have the capacity to characterize what it is we are talking about. The idea that abstract objects can be introduced via language is in deep trouble. In fact, as Putnam noted (Models and Reality), the problem extends to characterizing any objects via language. This is just as much a problem for ordinary language and physical objects as it is for mathematics. This result is historically deeply related to claims about the indeterminacy of translation, inscrutability of reference, and the underdetermination of theory by experiment.

Hollywood

You can make a movie in which there are entire fictional planets with billions of inhabitants. How do you do that? You only need to build the part of the world that is on camera. Now, think about what you get evidence of in a movie. Only the part of the world that is on camera. All the evidence we can have is just evidence that there is some partial world of what we actually see or report. (Nagle. Barn façades.)

How does all that translate to mathematics? Take the true model of set theory. Take all the true sentences. Some of them state that something exists. For each such sentence choose exactly one such thing. Take the stuff you get that way, and throw away the rest. There is your countable model.

-- ShaughanLavine - 17 Oct 2006

Hilbert's epsilon calculus

Whenever we prove a formula of the form %$(\exists x)\phi (x)$%, we are entitled to say, "let %$a$% be such an %$x$%" and then use %$\phi (a)$% in the rest of our proof. In fact, the method is more general: whenever we prove a formula of the form %$(\exists x)\phi (x,y_{1},\ldots ,y_{n})$%, we are entitled to say, "let %$f(y_{1},\ldots ,y_{n})$% be such an %$x$%" and then use %$\phi (f(y_{1},\ldots ,y_{n}),y_{1},\ldots ,y_{n})$% in the rest of our proof.

Hilbert exploited that as follows: for any formula %$(\exists x)\phi (x)$% with one free variable, we introduce a new constant symbol, %$\epsilon _{\phi (x)}$%, and for any formula %$(\exists x)\phi (x,y_{1},\ldots ,y_{n})$% with %$n+1$% free variables, we introduce a new function symbol, %$\epsilon _{\phi (x,y_{1},\ldots ,y_{n})}(y_{1},\ldots ,y_{n})$%. The symbols are called Hilbert's epsilon symbols. We take sentences of the following form to be logical axioms: %\[(\phi (x,y_{1},\ldots ,y_{n}))\rightarrow \phi (\epsilon _{\phi (x,y_{1},\ldots ,y_{n})}(y_{1},\ldots ,y_{n}),y_{1},\ldots ,y_{n}))).\]% Note that such axioms do not make use of any quantifiers.

One can now define the quantifiers as follows;

• %$(\exists x)\phi (x,y_{1},\ldots ,y_{n})$% if and only if, by definition, %$\phi (\epsilon _{\phi (x,y_{1},\ldots ,y_{n})}(y_{1},\ldots ,y_{n}),y_{1}.\ldots ,y_{n}))$%.
• %$(\forall x)\phi (x,y_{1},\ldots ,y_{n})$% if and only if, by definition, %$\lnot\phi (\epsilon _{\lnot\phi (x,y_{1},\ldots ,y_{n})}(y_{1},\ldots ,y_{n}),y_{1}.\ldots ,y_{n}))$%.

It is tedious, though in principle straightforward, to check that that gives the quantifiers their familiar logical properties.

The reason that the Hilbert epsilon symbols are of interest to us is that if a quantificational theory has a model, then so does the same theory re-expressed in terms of epsilon symbols, and set of all objects of the original model that are denoted by closed terms form the domain of a countable submodel of the original model. The epsilon symbols provide a reasonably intuitive way of making the Hollywood argument precise: the objects we need are just enough of the original objects to make our original theory true, and the ones denoted by epsilon symbols are enough.

You may wish to consult the [[http://plato.stanford.edu/entries/epsiywood argument precise: the objects we need are just enough of the original objects to make our original theory true, and the ones denoted by epsilon symbols are enough.

You may wish to consult the Stanford Encyclopedia of Philosophy for additional information about epsilon symbols, which have many other applications as well.

Compactness

An extended aside about completeness

• Say that a set of sentences is satisfiable if it has a model.
• Say that a set of sentences is inconsistent if there is some sentence %$\phi$% such that both %$\phi$% and %$\lnot\phi$% are derivable from the set.
• Say that a set of sentences is consistent if it is not inconsistent.

We introduced the following theorems above.

• Soundness. If a sentence %$\phi$% can be derived from a set %$\Gamma$% of sentences, then %$\phi$% is a logical consequence of %$\Gamma$%.
• Completeness. If a sentence %$\phi$% is a logical consequence of a set %$\Gamma$% of sentences, then %$\phi$% is derivable from %$\Gamma$%.

The following two equivalences are elementary, but not the first thing you would think of.

• %$\phi$% is derivable from %$\Gamma$% if and only if %$\Gamma\cup\{\lnot\phi\}$% (that is, the set of sentences formed by adding %$\lnot\phi$% to %$\Gamma$%) is inconsistent. * %$\phi$% is a logical consequence of %$\Gamma$% if and only if %$\Gamma\cup\{\lnot\phi\}$% is not satisfiable.

Using them, we obtain the following alternative versions of soundness and completeness. (The "%$\Gamma$%" of these versions is the %$\Gamma\cup\{\lnot\phi\}$% of the old ones.)

• Soundness. Every satisfiable set of sentences is consistent.
• Completeness. Every consistent set of sentences is satisfiable (that is, has a model).

To get to understand this better, it is a useful exercise to

1. assume the first version of soundness and use it to prove the second version,
2. assume the second version of soundness and use it to prove the first,
3. assume the first version of completeness and use it to prove the second, and, finally,
4. assume the second version of completeness and use it to prove the first.

I shall not actually assign those problems as homework, but, if you do them, or attempt to do them and get stuck (I expect you will), feel free to talk to me about them. Consider it extra credit.

Compactness

• Theorem. If every finite subset of a set of sentences has a model, then the whole set of sentences has a model.

Proof. If every finite subset of a set of sentences has a model, then, by the second version of soundness, every finite subset of the set is consistent.

But then the whole set of sentences is consistent: We prove the contrapositive: if it is inconsistent, there are, for some sentence %$\phi$%, proofs of %$\phi$% and %$\lnot\phi$% from the set. Pick such proofs. Since proofs are of finite length, the proofs only used a finite subset of the set of sentences, and so there is a finite subset of the set of sentences that is inconsistent.

Finally, since the whole set of sentences is consistent, it has a model, as required, by the second version of the completeness theorem. %$\square$%

Here is an application of compactness.

• Theorem. (The Upward Löwenheim-Skolem theorem.) Let %$T$% be a theory that has an infinite model of cardinality %$\kappa$% and let %$\lambda$% be an infinite cardinal that is larger than %$\kappa$%. (There is such a %$\lambda$% by Cantor's theorem.) Then there is a model of %$T$% with at least %$\lambda$% elements in its domain, and, hence the theory %$T$% has at least two distinct (that is, nonisomorphic) models.

To avoid using cardinals, which may be unfamiliar, I shall just prove a special case of the theorem, the corollary immediately below. The proof of the general theorem is "exactly the same."

• Corollary. Let %$N$% be the set of all sentences true of the natural numbers, that is, more precisely, true in the structure %$(\mathbb{N},0.S,+,\times )$%. Then %$N$% has a model in which there are at least as many elements in the domain as there are real numbers (or, if you prefer, sets of natural numbers).

Proof. For each real number %$r$%, let %$c_r$% be a constant symbol, and assume that if %$r$% and %$s$% are distinct real numbers, then %$c_r$% and %$c_s$% are distinct symbols. Let %$T$% be the set of all sentence of the form %$c_r\ne c_s$%, for all distinct real numbers %$r$% and %$s$%.

Every finite subset of %$N\cup T$% has a model: A finite subset of %$N\cup T$% consists of a finite subset %$N_0$% of %$N$% and a finite subset %$T_0$% of %$T$%. Suppose that %$n$% of the new constants, say, %$c_{r_1},\ldots ,c_{r_n}$% occur in %$T_0$%. Then %$(\mathbb{N},0.S,+,\times ,\genfrac{}{}{0pt}{}{c_{r_1}}{1},\ldots ,\genfrac{}{}{0pt}{}{c_{r_n}}{n})$% is a model of %$N_{0}\cup T_{0}$%, as required, where the model is just the usual one of the natural numbers with the constant symbol %$c_{r_1}$% taken to stand for the number 1, and so forth. The structure is obviously a model of %$N_0$%, since it is a model of all of %$N$%, and it is obviously a model of %$T_0$%, since distinct constant symbols stand for distinct numbers, and that is the most that %$T_0$% requires.

Since every finite subset of %$N\cup T$% has a model, by compactness, %$N\cup T$% has a model. The domain of the model has at least as many elements as there are real numbers, since, because the model is a model of %$T$%, it has a member for each %$c_r$%, that is, a member for each %$r$%, with distinct members for distinct real numbers, since %$T$% says that %$c_{r}$% is distinct from %$c_{s}$% for distinct real numbers %$r$% and %$s$%.

That almost completes the proof except for a minor detail: the model just constructed not only has a large domain, it also has all the new constant symbols %$c_r$% in its language, and those symbols are not part of the language of the theory %$N$% with which the theorem is concerned. So take the model and remove the part that specifies the interpretations of the new constant symbols. That removes names of elements of the domain but it does not remove the elements themselves. They are still there; they just no longer have the names. That "stripped down" model is as required: it still has a large domain, since the domain hasn't changed, but it is now in the original language, the language %$\{0,S,+,\times\}$% of %$N$%. %$\square$%

-- ShaughanLavine - 06 Nov 2006

• #Set DENSITY = 232