Point 1: Does second-order logic have rules of inference? Second order logic is not defined by any complete set of rules of inference. It is defined semantically. But there are rules of inference which are sound for it. These include the usual first-order rules, the analogues for second-order quantifiers of the first-order rules for quantifiers and comprehension axioms. These rules do not constitute second order logic but they are valid from a second-order standpoint. Simpson objects to this because of his definition of the word "logic" as "the science of valid inference". I have noted that there are more general definitions of what "logic" is that do support the idea that second-order logic is a logic. I won't reiterate arguments about this point here. Clarification re point 1: My "second-order standpoint" properly extends a first-order standpoint; I assume availability of a partial formalization of rules of inference, including but not restricted to the axioms and rules of inference of the two-sorted first-order system commonly referred to as "second-order logic". Point 2: Does first-order ZFC support definitions of familiar mathematical structures? I claim that it does not, and if Simpson understands what I mean by this, he cannot disagree with me (the question is whether it is clear to him what I mean). I take the natural numbers as an example. We certainly can define in ZFC a structure commonly called "the natural numbers". It is the intersection of all sets containing the von Neumann ordinal 0 (the empty set) and closed under the ordinal successor operation (x -> x u {x}). I agree heartily with Simpson that first-order ZFC is a beautiful system for proving theorems about the (true!) natural numbers. If we interpret the true natural numbers as the elements of the set defined above in ZFC and the properties of natural numbers as being suitably correlated with the elements of the power set of the "natural numbers" of ZFC then every theorem of second order arithmetic whose interpretation in ZFC can be proved in ZFC is true. Moreover, the set of theorems of second order arithmetic whose interpretations are provable in ZFC is quite large; it is, for example, larger than the set of theorems provable in the first order two-sorted theory usually called "second-order arithmetic". However, I claim that we cannot justify the assertion that the true natural numbers are implemented by the set of ZFC whose definition is outlined above in terms of first-order ZFC alone. First-order ZFC, if it is consistent, has models in which the set defined above does not have the order type of the true natural numbers. This is a familiar mathematical fact. The reason that these models of ZFC have nonstandard natural numbers is that there are inductive subsets of the "set of naturals" in the model which do not correspond to any set of the model. In other words, the reason that a model of first-order ZFC may have nonstandard natural numbers is that it fails to be a model of second-order ZFC -- its "sets of natural numbers" are not all the sets of its "natural numbers". Again, there is nothing here which Simpson and I should disagree about. The conclusion which I draw from all this which Simpson evidently does not draw or simply does not understand is that the reason that we regard ZFC as providing us with a definition of the natural numbers is that we are implicitly appealing to an intended interpretation of the language of ZFC as referring to _second-order ZFC_. In second-order ZFC, all the axioms and rules of inference of first-order ZFC are valid (in fact, one obtains the axioms of Kelley-Morse set theory as well), so everything we can do formally in first-order ZFC is still available in second-order ZFC. A recent posting of Friedman (received while I was writing this posting) is making it quite clear to me what is going on (if Simpson's opinions are similar, which they might not be, of course). Friedman thinks that "to express something in first-order ZFC" means exactly what I think is meant by "to express something in second-order ZFC". I think that this is wrong-headed, and I will try to explain why below. Thus Harvey Friedman: Holmes uses an inappropriate notion of "expressed" here and throughout his postings. The appropriate way to look at this is as follows. There is the first order language of set theory. It is then trivial to express such concepts as "inductive number system" in this first order language of set theory. Since there are no axioms and rules of inference involved here, there is no issue as to "nonstandard models" and the like. And this is the normal concept of "express" that mathematicians use. Holmes replies: I think this is _really_ the crux of the matter. Friedman appears to think that the language of first-order set theory has an "intended interpretation" which requires no formal justification. I think that the meaning of the terms in any formal system is implicitly defined (as far as it can be defined) by the axioms and rules of inference of the formal system. The symbols of a formal language considered in isolation from the axioms, rules of inference, etc. have no built-in meaning. This is a standard viewpoint (though certainly not the only one) in philosophy of mathematics, ably expounded by Mayberry, for example. It is of course easy to express the notion of "the set of natural numbers" (the intersection of all inductive sets) in the first-order language of set theory, if we understand the symbols of the language "naively" (is this what Friedman is saying we should do?). If this language is understood to refer to models of second-order ZFC, the definition succeeds: the referent of our "set of natural numbers" in any such model will be an implementation of the set of natural numbers. In some models of first-order ZFC, the reference of the "set of natural numbers" thus defined will not be an implementation of the set of natural numbers. This is the precise sense in which I say that second-order ZFC allows us to express the notion "the set of natural numbers" and first-order ZFC does not. In fact, I would say that the "naive" understanding of the symbols to which I think Friedman appeals is exactly the same as the interpretation in second-order ZFC; this is the content of my conjecture that Friedman's view (or Simpson's) is founded on an equivocation between first-order and second-order ZFC. In any case, no language has semantics in the absence of a given interpretation or interpretations. If I can define "the set of natural numbers" in a language, the only way this definition can be correct or incorrect is insofar as it refers or fails to refer to the object(s) to which it is intended to refer in the interpretation(s) of the language I consider. The intended class of models is _always_ relevant (and the axioms and rules of inference (and other semantic constraInts in the case of second-order logic) implicitly determine the intenced class of models). I would like to ask Friedman how he thinks the symbols of a formal system acquire meaning? In particular, where do the meanings of the symbols of first-order ZFC, considered as a foundation for mathematics, come from? Friedman comments on a Holmes remark: >(in >this thread; I am fond of (first-order!) extensions of NFU as working >foundations). This is very bad. Holmes replies (aside -- not really relevant to this thread): It is demonstrably a matter of taste. I actually agree that ZFC foundations are better overall. Part of the reason that I think this has to do with the much better interface between ZFC and second order logic :-) (speaking loosely; I would be happy to make this more precise, but this is not relevant to the current thread). But I think that it is useful to develop foundations, however peculiar, that differ from the standard ones; comparison of foundational approaches helps us to see what foundations do for us. I do _not_ agree that NFU foundations are "very bad"; I think they do have some merit, but they also have disadvantages. Friedman responds to Holmes earlier: >One possible position (I think that this is John >Mayberry's position (?)) which would have very little effect on the >way mathematics looks in practice is to adopt second-order ZFC (and >extensions as desired) as one's working foundation, >using the proof >machinery of the first-order theory (which is of course sound for the >second-order theory). I'm not entirely comfortable with this because >the ontological commitments of second-order ZF are very strong. If I understand this correctly, it would be trivially equivalent to adopting first-order ZFC (and extensions as desired) as one's working foundation. I don't see the difference. If you do, spell out the difference. Holmes replies: I have done so above (it has to do with semantics). This statement of yours confirms my impression that the differences between our positions are largely ones of terminology. I think that some of these differences are nonetheless important. Friedman replies to Holmes: >It is >also fascinating to study the model theory of ZFC. But it doesn't do >everything that we need for a foundation of mathematics. What is missing? Of course, large cardinals and other related issues are missing. But what are you referring to? Holmes replies: I am referring to the inability to define familiar mathematical structures such as the natural numbers. You did not appear to understand what I mean by definability of a structure in a theory; this may be beginning to become clearer (I hope). Friedman replies to Holmes: >The point which is >being belabored is that the reference of mathematical language is >an important foundational issue. OK, let's talk about it more sensibly. Holmes replies: Amen! Simpson responds to Mayberry: > ZFC does not provide the foundation for mathematics. *Set theory* > provides the foundation for mathematics, and ZFC is a first order > formalisation of set theory. Yes, your distinction between set theory and its first-order formalizations may be valid at some level, at least for realists or Platonists. However, the fruitful approach that has yielded a lot of serious insight (G"odel, Cohen, ...) is to study the first-order formalizations. Experience has shown that alternative approaches via second-order logic are ultimately sterile, because they are disconnected from inference. Holmes comments: The issue of realism is obviously important here (the issue of the reference of mathematical language...) I agree that the study of the first-order formalizations is fruitful. It remains possible (and fruitful) from a second-order standpoint (which does admit partial formalizations of inference). Simpson replies to Mayberry: > The very same formal axioms and rules that are complete for Henkin > semantics are *sound* for standard semantics. No, these axioms are not necessarily sound for standard semantics. It depends on the metatheory. For example, suppose the axiom of choice fails in the metatheory. (The metatheory might reasonably be something like ZF + DC + AD, which is generally regarded as providing an interesting alternative to the axiom of choice.) Suppose also that our axioms of second-order logic include a choice scheme, as in Shapiro's system D2, for instance. Then the axioms for second-order logic will *not* be sound for the standard semantics. To say that Shapiro's choice scheme is sound for the standard semantics is easily seen to be equivalent to the axiom of choice holding in the metatheory. We know that this need not be the case, thanks to modern f.o.m. research, specifically to Cohen's important work on the axiom of choice in the context of (first-order!) f.o.m. Thus Cohen's work can save us from embarrassment and confusion, provided we take it to heart. Holmes comments: This is a very nice point. One does need to be careful about this kind of thing. I would not include a choice scheme in my second-order logic. As I noted above, I have never claimed that Cohen's work (or other modern f.o.m. research) was not applicable from (and to) a second-order standpoint (nor has Mayberry); it is you who have claimed that! Simpson replies to Mayberry: > What makes the formal theory ZFC so important for foundations is > the fact that any proof in ordinary mathematics has a formal > counterpart in ZFC. This statement of the importance of ZFC is inadequate. There's more to it than that, especially from the Platonist or realist viewpoint. Not only can ZFC formalize all mathematical proofs, but in addition, ZFC is the strongest axiomatic theory that we can write down in the language {epsilon,=} that is directly based on certain informal insights or naive intuitions about the universe of set theory (informal replacement, informal axiom of choice, etc). Thus ZFC is unique in an appropriate, relevant sense. This should be viewed as another aspect of why ZFC is so important for f.o.m. Holmes comments: The informal theory you are describing is second-order ZFC! Mayberry goes on to guess that Simpson's view is "old-fashioned formalism". I'm not sure this is the case; I'm not sure what Simpson's positions are on the substantive philosophical questions, because it has hitherto been very hard to communicate with him. I hope that this is about to improve. I would like Friedman to explain why he thinks that it is so easy to define the set of natural numbers in the language of first-order set theory. How do we see that the definition captures our pre-formal notion of what a natural number is? How do we understand what the primitives of first-order ZFC mean? I'd like to ask Simpson whether his apparent problems with understanding what I am saying are based on similar issues. And God posted an angel with a flaming sword at | Sincerely, M. Randall Holmes the gates of Cantor's paradise, that the | Boise State U. (disavows all) slow-witted and the deliberately obtuse might | holmes@math.idbsu.edu not glimpse the wonders therein. | http://math.idbsu.edu/~holmes