Start Presentation

Thanks

Thanks for inviting me.

Comprehension Axiom

The Axiom of Comprehension (CA) states that every formula defines a class. That is, $\exists X\forall x(x\in X\leftrightarrow\phi(x)) $ for any formula $\phi $ in which $X $ does not occur free.

That seems clear enough. What I don't understand is its supposed utility.

Comprehension Axiom

The Axiom of Comprehension (CA) states that every formula defines a class. That is, $\exists X\forall x(x\in X\leftrightarrow\phi(x)) $ for any formula $\phi $ in which $X $ does not occur free.

The first remark that one usually makes about CA is that it is too strong: Substituting $x\notin x $ for $\phi $ yields Russell's paradox. (It seems that I am making the remark first too.)

Comprehension Axiom

The Axiom of Comprehension (CA) states that every formula defines a class. That is, $\exists X\forall x(x\in X\leftrightarrow\phi(x)) $ for any formula $\phi $ in which $X $ does not occur free.

The first remark that one usually makes about CA is that it is too strong: Substituting $x\notin x $ for $\phi $ yields Russell's paradox. (It seems that I am making the remark first too.)

The remark does not apply when the domain of the lower-case quantifiers does not include classes (or even when it excludes enough classes). For example, no paradox arises from CA in second-order arithmetic or even over a suitable theory of sets.

Comprehension Axiom

The Axiom of Comprehension (CA) states that every formula defines a class. That is, $\exists X\forall x(x\in X\leftrightarrow\phi(x)) $ for any formula $\phi $ in which $X $ does not occur free.

The usual response to the paradox is to conclude that CA is too strong, and to set about looking for motivated ways to weaken it. Though I certainly do not deny that some weakening is necessary, I am, for the purposes of this talk, interested in ways in which CA is too weak, and so I shall make all my remarks about the full CA, even for putative applications in which it is inconsistent, blithely ignoring the inconsistency.

Comprehension Axiom

The Axiom of Comprehension (CA) states that every formula defines a class. That is, $\exists X\forall x(x\in X\leftrightarrow\phi(x)) $ for any formula $\phi $ in which $X $ does not occur free.

It may well be that much of what I say is false or incoherent, read strictly as applying to the inconsistent cases—I'm not being too careful about that—but my intention is that my remarks will hold true for whatever weaker version of CA one might adopt, independent of the details.

Categoricity

The Axiom of Comprehension (CA) states that every formula defines a class. That is, $\exists X\forall x(x\in X\leftrightarrow\phi(x)) $ for any formula $\phi $ in which $X $ does not occur free.

For the philosopher of mathematics, perhaps the most important strength of second-order logic is the ability to prove categoricity results using it. I'll take the categoricity of the axioms of second-order arithmetic as our example, but, for my purposes today, nothing turns on special features of that choice. It is convenient because it is familiar.

Categoricity

A language for arithmetic is an arbitrary language $ { \mathcal A}= \{ 0, S, +, \cdot \} $ with a constant symbol, one-placed function symbol, and two two-placed function symbols. The basic axioms of Peano arithmetic in the language $ \mathcal A $ are
$ (\forall x)(Sx \ne 0)\land (\forall xy)(Sx=Sy\rightarrow x=y) $ Successor
$ (\forall x)(x+0=x)\land (\forall xy)(x+Sy=S(x+y)) $ Addition
$ (\forall x)(x \cdot 0=0)\land (\forall xy)(x \cdot Sy=x \cdot y+x) $ Multiplication

The only second-order axiom of second-order Peano arithmetic is the final one:

\[(\forall X)( 0\in X\land (\forall x)(x\in X\rightarrow Sx\in X)\rightarrow (\forall x)x\in X). \]

Categoricity

The categoricity result is not straightforward to state in the language of second-order arithmetic. It seems to be most naturally formulated in the language of pure second-order logic, where it must go something like this:
\[ ( \forall D_{0}, 0_{0}, S_{0}, +_{0}, \cdot _{0} , D_{1}, 0_{1}, S_{1}, +_{1}, \cdot _{1} )( \mbox{PA} (D_{0} , 0_{0} , S_{0} , +_{0} \cdot_{0} ) \land \mbox{PA} (D_{1} , 0_{1} , S_{1} , +_{1} , \cdot _{1} ) \]
\[ \quad \rightarrow ( \exists f)(f \mbox{ is an isomorphism between } \langle D_{0}, 0_{0}, S_{0}, +_{0}, \cdot_{0} \rangle\} \mbox{ and } \langle D_{1},0_{1}, S_{1}, +_{1}, \cdot_{1} \rangle ), \]
where $ f \mbox{ is an isomorphism between } \langle D_{0}, 0_{0}, S_{0}, +_{0}, \cdot_{0} \rangle \mbox{ and } \langle D_{1}, 0_{1}, S_{1}, +_{1}\cdot_{1} \rangle $ is an abbreviation for a long formula that says things like $f $ is a bijection from $ D_0 $ to $D_1 $, $ f(0_{0})=0_{1} $, and $ ( \forall xy)(xy\in D_{0}\rightarrow f(x+_{0}y)=f(x)+_{1}f(y))$

Categoricity

We usually take the theorem
\[ ( \forall D_{0}, 0_{0}, S_{0}, +_{0}, \cdot_{0} , D_{1}, 0_{1}, S_{1}, +_{1}, \cdot_{1}) ( \mbox{PA}(D_{0}, 0_{0}, S_{0}, +_{0}, \cdot_{0} ) \land\mbox{PA}(D_{1}, 0_{1}, S_{1}, +_{1}) \]
\[ \quad \rightarrow( \exists f)(f \mbox{ is an isomorphism between }\langle D_{0}, 0_{0}, S_{0}, +_{0}, \cdot_{0}\rangle \mbox{ and }\langle D_{1},0_{1}, S_{1}, +_{1}\rangle ),\]
to say that "any two models of second-order Peano arithmetic are isomorphic" and hence that the axioms characterize the natural numbers up to isomorphism.

Categoricity

We usually take the theorem to say that "any two models of second-order Peano arithmetic are isomorphic" and hence that the axioms characterize the natural numbers up to isomorphism.

If that reading were correct, then we ought to be able to take two models $ {\mathcal N}_{0} $ and $ {\mathcal N}_{1} $ of second-order arithmetic in the language $ \mathcal A $ and conclude that they are isomorphic on the basis of the theorem.

Categoricity

We usually take the theorem to say that "any two models of second-order Peano arithmetic are isomorphic" and hence that the axioms characterize the natural numbers up to isomorphism.

If that reading were correct, then we ought to be able to take two models $\mathcal N_{0} $ and $\mathcal N_{1} $ of second-order arithmetic in the language $\mathcal A $ and conclude that they are isomorphic on the basis of the theorem.

In outline, the application of the theorem would require that we take $D_{i} $ to be the domain of $\mathcal{N}_i $, $+_i $ to be the function + of $\mathcal{N}_i $, and so forth. To begin, it must certainly have to be the case that the domains of the $\mathcal{N}_i $s and the addition functions of the $\mathcal{N}_i $s must be in the domain of the quantifiers of the theorem.

Categoricity

We usually take the theorem to say that "any two models of second-order Peano arithmetic are isomorphic" and hence that the axioms characterize the natural numbers up to isomorphism.

In outline, the application of the theorem would require that we take $D_{i} $ to be the domain $N_i $ of $\mathcal{N}_i $, $+_i $ to be the function + of $\mathcal{N}_i $, and so forth. To begin, it must certainly have to be the case that the domains of the $\mathcal{N}_i $s and the addition functions of the $\mathcal{N}_i $s must be in the domain of the quantifiers of the theorem.

To start, we must show, along with many similar facts, that $(\exists X)(\forall x)(x\in X\leftrightarrow x\in N_{0}) $

Comprehension

To start, we must show, along with many similar facts, that $(\exists X)(\forall x)(x\in X\leftrightarrow x\in N_{0}) $

That is supposed to be straighforward—it is an instance of CA.

Comprehension

To start, we must show, along with many similar facts, that $(\exists X)(\forall x)(x\in X\leftrightarrow x\in N_{0}) $

That is supposed to be straighforward—it is an instance of CA. Unfortunately, it is not an instance of CA.

CA states only that $\exists X\forall x(x\in X\leftrightarrow\phi(x)) $for any formula $\phi $ in which $X $ does not occur free. $x\in N_{0} $ is not a formula: The theorem was stated and proved in pure second-order logic, which has no nonlogical symbols whatever, and in particular no symbols connected with the language $\mathcal A $ or with the structure $\mathcal{N}_0 $. We are stopped at square 1.

Comprehension

We are stopped at square 1.

Of course, we know how to patch this up: prove "the same" theorem in a sufficiently large language, so that all the instances of CA we need actually do turn out to be instances of CA.

Comprehension

We are stopped at square 1.

Of course, we know how to patch this up: prove "the same" theorem in a sufficiently large language, so that all the instances of CA we need actually do turn out to be instances of CA.

The minor change, however, is not so minor. Changing the language changes the axioms (that was, after all, the point—to bring in new axioms of comprehension). The new theorem is genuinely stronger than the old one, and so "`the same' theorem" is not the same theorem.

Comprehension

Of course, we know how to patch this up: prove "the same" theorem in a sufficiently large language, so that all the instances of CA we need actually do turn out to be instances of CA.

The minor change, however, is not minor. That is what I do not comprehend about comprehension. How is it that something can be an axiom when it is different in every application? Suppose we wanted a truly general categoricity result. How would we have to prove it?

Comprehension

Of course, we know how to patch this up: prove "the same" theorem in a sufficiently large language, so that all the instances of CA we need actually do turn out to be instances of CA.

That is what I do not comprehend about comprehension. How is it that something can be an axiom when it is different in every application? Suppose we wanted a truly general categoricity result. How would we have to prove it?

It seems that we would have to prove it by the usual proof presented, however, in a language that includes names for enough predicates, relations, and functions to ensure that any predicate, relation, or function I might need is definable in the language. There doesn't seem to be a way to present such a theory axiomatically, and it seems clear that in such a language it is the language, not CA that is doing all the work.

Comprehension

Suppose we wanted a truly general categoricity result. How would we have to prove it?

It seems that we would have to prove it by the usual proof presented, however, in a language that includes names for enough predicates, relations, and functions to ensure that any predicate, relation, or function I might need is definable in the language. There doesn't seem to be a way to present such a theory axiomatically, and it seems clear that in such a language it is the language, not CA that is doing all the work. I shall make good on that feeling next lecture by proving a categoricity result relying on strong assumptions about the inclusiveness of the background language without using anything second order (and in particular no CA) whatsoever.

Measurement

I have now shown you that CA, and hence second-order logic, is of no use in proving categoricity theorems—or at least what I mean by that claim. CA is also of no help in accounting for how mathematics gets applied to physics.

Measurement

I have now shown you that CA, and hence second-order logic, is of no use in proving categoricity theorems—or at least what I mean by that claim. CA is also of no help in accounting for how mathematics gets applied to physics.

I'll use length in Newtonian physics as an example. I believe it is possible to give examples that take account of quantum mechanical or even thermodynamical considerations, but the additional difficulties are quite subtle and not germane to my central point.

Measurement

I have now shown you that CA, and hence second-order logic, is of no use in proving categoricity theorems—or at least what I mean by that claim. CA is also of no help in accounting for how mathematics gets applied to physics.

I'll use length in Newtonian physics as an example.

It will be convenient to think of the real numbers as being formalized as Dedekind cuts. I shall identify a real number with the set of rational numbers less than it.

Measurement

To measure the length of a rod, we compare it with a unit (say meter) rod: If $n$ copies of the rod lined up form an extent greater than that of $m$ copies of the meter stick, we say that the length of the rod is greater than $\frac{m}{n}$ meters. The length of the rod in meters, a real number, is the Dedekind cut consisting of the set of all rational numbers $r$ such that the rod is greater than $r$ meters long. (I haven't handled negative rationals, but never mind.)

Measurement

I hope the point is clear---on standard formulations of the real numbers, what I have just defined will not be a Dedekind cut, because there will be no instance of Comprehension concerning the physical criterion by which I picked out the appropriate set of rationals.

It is simply does not follow from standard formulations of the real numbers, even second-order ones, that every rod has length a real number of meters.

-- ShaughanLavine - 10 Mar 2005