Marys Medicine

Second order logic and set theory Both second order logic and set theory can be used as a foundation for mathematics, that is, as a formal language in which propositions ofmathematics can be expressed and proved. We take it upon ourselvesin this paper to compare the two approaches, second order logic on onehand and set theory on the other hand, evaluating their merits andweaknesses. We argue that we should think of first order set theoryas a very high order logic.
Towards the end of the 19th century mathematics had become so evolvedthat questions about its foundations emerged. These questions were mainlyabout calculus and the use of set theory. Richard Dedekind had already in1858 sensed that something was lacking: As professor in the Polytechnic School in Z¨ urich I found myself for the first time obliged to lecture upon the elements of thedifferential calculus and felt more keenly than ever before the lackof a really scientific foundation for arithmetic. In discussing thenotion of the approach of a variable magnitude to a fixed limitingvalue, and especially in proving the theorem that every magnitudewhich grows continually, but not beyond all limits, must certainlyapproach a limiting value, I had recourse to geometric evidences.
. that this form of introduction into the differential calculus canmake no claim to being scientific, no one will deny. For myselfthis feeling of dissatisfaction was so overpowering that I madethe fixed resolve to keep meditating on the question till I should find a purely arithmetic and perfectly rigorous foundation for theprinciples of infinitesimal analysis.
. It then only remained to discover its true origin in the elementsof arithmetic and thus at the same time to secure a real definitionof the essence of continuity.1 [4, page 9].
This was the impetus that led Dedekind in 1888 to introduce his famous axiomatisation of number theory [5] and other concepts such as the contin-uum using what is now known as the method of Dedekind cuts, anothertypically second order concept.
Dedekind's was not an axiomatisation of number theory in the modern sense, but rather a structural analysis of natural numbers. It was Peanowho in 1889 formulated axioms of number theory in the modern sense. Beit Dedekind's analysis or Peano's axiomatisation, the main non-trivial axiom(or principle) is the Induction Axiom: ∀X([X(0) ∧ ∀y(X(y) → X(y + 1))] → ∀yX(y)), which is still today the paradigmatic example of a second order sentence. Itis called a second order sentence because the quantifier ∀X quantifies oversets X of numbers rather than over individuals i.e. numbers.
Another typical second order axiom is the Completeness Axiom for linear ∀X([∃yX(y) ∧ ∃z∀y(X(y) → y ≤ z)] → ∃z∀y(∃u(X(u) ∧ y ≤ u) ∨ z ≤ y)), which says that every non-empty set of elements of the linear order whichhas an upper bound has a least upper bound. This is second order because ithas the bound variable X which ranges over all subsets of the domain of thelinear order, rather than just over the individuals that are linearly ordered.
Second order logic was quite dominating in early axiomatisations of math- ematical concepts, although they were not called "second order" at the time.
Hilbert's 1898 axiomatisation of geometry [10] was second order, as was Hunt-ington's 1902 axiomatisation of the continuum as an ordered set [13]. Finally,Zermelo's axiomatisation of set theory [24] was also second order, althoughthe later Zermelo-Fraenkel axiomatization of set theory is first order.
1English translation [6] The early users of second order logic, such as Hilbert, Ackermann, Bernays,Huntington and Veblen, paid substantial attention to a concept that had alasting effect on our understanding of second order logic, namely categoricity.
An axiom system Γ is said to be categorical if it has, up to isomorphism, atmost one model2, i.e.
∀M, M0((M = Γ ∧ M0 = Γ) → M ∼ Logicians went to pains to show, usually successfully, that their (second or-der) axiom systems were categorical. In particular, the ordered structureof the natural numbers, the complete separable Archimedian field of realsnumbers, the complex field, as well as practically all commonly occurringmathematical structures have a categorical second order axiomatisation.
A nice property of a categorical axiom system is (semantical) complete- ness: Any sentence φ in the language in which the axiom system is writtenis decided by Γ in the following sense. Either every model of Γ satisfies φor every model of Γ satisfies ¬φ. In other words, either φ or ¬φ is a (se-mantical) logical consequence of Γ. The reason is very simple: Γ has, up toisomorphism, only one model M . Since isomorphism preserves truth in sec-ond order logic, φ or ¬φ is a (semantical) logical consequence of Γ accordingto whether φ is true in M or false in M .
If φ is a second order sentence we define Mod(φ) = {M : M = φ} If φ characterises M up to isomorphism, then, up to isomorphism, Mod(φ) = {M}.
A kind of "formalist" view of second order logic would insist that it is only φ that exists in any meaningful sense, while M itself, the structure thatwe are really interested in, cannot (according to this view) be meaningfullyclaimed to exist, as it is infinite. The reason why Mod(φ) seems to have a 2A vocabulary consists of a set of constant, relation and function symbols, each with their own arity. A first order structure (or model) for a vocabulary L is a non-empty setendowed with interpretations of the constant, relation and function symbols of L. We useM, N, etc to denote first order structures. The truth of a sentence φ of first order logic,or any other logic, in a model M is denoted M = φ.
stronger claim to "existence" than M itself is that it, unlike M, is completelydetermined by the finite string of symbols φ. One may even take the nextstep and declare that the "existence" of M means simply the existence of φcombined with the fact that φ is categorical. What is problematic with thisline of thinking is that to check whether φ is categorical one has to appealto the the infinity of infinite models of φ.
The project of axiomatising mathematical structures with second order sentences was so successful in the first quarter of the 20th century that Car-nap even proposed that every mathematical structure is determined, up toisomorphism, by its second order theory. There are trivial cardinality reasonswhy this could not possibly hold for models of size 2ω and bigger. There aresimply not enough second order theories in comparison with the number ofnon-isomorphic models. However, the proposal of Carnap is trivially truefor finite models, and not entirely unreasonable for countable models. Infact Ajtai [1] showed that it is consistent with ZFC, provided ZFC itself isconsistent, that any two countable structures in a finite vocabulary that sat-isfy the same second order sentences are isomorphic. Ajtai also showed thatit is consistent with ZFC, provided ZFC itself is consistent, that there aretwo countable structures in a finite vocabulary that satisfy the same secondorder sentences without being isomorphic. Thus Carnap's conjecture (forcountable models) is independent of ZFC.
odel proved his Completeness and Incompleteness Theorems for first order logic, a puzzling situation existed for a while concerning second orderlogic: Let θ be the second order axiomatisation of the natural numbers, using(1). The sentence θ is categorical hence complete, that is, for every sentenceφ of the language of number theory θ = φ or θ = ¬φ.
On the other hand, G¨ odel's First Incompleteness Theorem says that if an effective deductive system is given for (first or) second order logic, then thereare sentences φ that θ 0 φ and θ 0 ¬φ.
The puzzling situation arose when this was contrasted with G¨ pleteness Theorem which states that for the Hilbert-Ackermann [11] notion of derivability for first order logic θ φ iff θ = φ.
The conditions (5), (6) and (7) seem to be in utter contradiction with eachother. Moreover, G¨ odel's theorem seemed to be quite general, especially the Incompleteness Theorem, so it was not clear which one of (5)-(7) is the onethat fails, for one has to fail. What failed turned out to be (7): for the kind ofsemantics that (5) is based on there cannot be an effective deductive systemwhich would satisfy (7). The condition (6) is not a problem as it only talksabout derivability. By changing the semantics to so-called Henkin semanticswe obtain (7) but then we lose (5), or we can keep our semantics and therebymaintain (5), but then we have to give up on (7). Let us first focus on thelatter choice, i.e. emphasising (5), having (6) and abandoning (7). This isthe topic of the next section.
Proof theory of second order logic The deductive system of second order logic, presented first explicitly inHilbert-Ackermann [11], is based on the obvious extension of axioms andrules of first order logic added with the Comprehension Axioms, definedas follows: Suppose φ(x1, . . , xn) is a second order formula with x1, . . , xnamong its free individual variables and the second order variable R is notfree in φ. Then the following formula is a Comprehension Axiom: ∃R∀x1 . . xn(φ(x1, . . , xn) ↔ R(x1, . . , xn)).
A priori (8) might appear very strong as it stipulates the existence of arelation. However, such an R exists simply because it is definable: R = {(a1 . . an) ∈ M n : M = φ(a1, . . , an)}.
Hilbert-Ackermann [11] add to the proof system of second order logic also two different Axioms of Choice. The first is AC : ∀x1 . . xm∃xm+1R(x1, . . , xm+1) → ∃F ∀x1 . . ∀xmR(x1, . . , xm, F (x1 . . xm)) and the second is AC0 : ∀x1 . . xm∃F ϕ → ∃F 0∀x1 . . xmϕ0, where the formula ϕ0 is obtained from the formula ϕ by replacing everywhereF (t1, . . , tk) by F 0(t1 . . tk, x1, . . , xm).
The first Axiom of Choice AC says intuitively that if a set {an+1 ∈ M : M = R(a1, . . , an, an+1)} is non-empty, we have a function which picks an element an+1 from the set,using the parameters a1, . . , an as arguments. The second Axiom of ChoiceAC0 is a kind of second order choice: We have for all a1, . . , an a functionF with the property φ, so in fact F depends on a1, . . , an and should bedenoted Fa . What AC0 says now is that we can collect the functions together to form just one function F 0 of higher arity such that F 0(a1, . . , an+1) = Fa Although F 0 appears to be definable, this is not the case, as the mapping (a1, . . , an) 7→ may be highly undefinable.
Both AC and AC0 are non-trivial axioms, just as Axiom of Choice of set theory is. The power of these axioms in second order logic is weaker than thepower of Axiom of Choice in set theory, because second order logic is limitedto the domain of the model. Often in set theory one applies the Axiom ofChoice to an auxiliary larger set obtained by means of the Power Set Axiom,or even a combination of the Power Set Axiom and the Replacement Axiom.
Nothing like that works in second order logic. Still AC and AC0 are essentialtools of second order logic.
The given axiom system of second order logic is designed so that it is sound, i.e. preserves truth. But it does not satisfy the Completeness The-orem, for as we already observed in Section 3, with the method of G¨ Incompleteness Theorem we can easily construct a second order number the-oretic sentence φ, a "G¨ odel sentence", such that (6) holds for the second order characterization θ of natural numbers. We can use stronger theories such asZFC to prove the statement φ, so its truth-value is not a puzzle. However,we can write in the vocabulary of the reals also a second order sentence ψ which is true of the reals if and only if the Continuum Hypothesis (CH) holds.
Nobody knows at present whether CH is true or not and in particular, theaxioms of second order logic are not able to decide CH. According to theclassical point of view the reals satisfy CH or its negation, we just do notknow which. We only know that the current axioms of second order logic arenot sufficiently strong to decide it. The same is true of Souslin's Hypothesisand many other set-theoretic statements.
The incompleteness of the axioms of second order logic with respect to the semantics M = φ is somewhat similar to the incompleteness of the Zermelo-Fraenkel axioms of set theory, ZFC. There are many mathematically mean-ingful statements that cannot be decided either by ZFC or by means of thegiven axioms of second order logic, as we will see below when we investigateHenkin models. In both cases the proof of the impossibility uses Cohen'smethod of forcing. In addition there is the consequence of G¨ pleteness Theorem: some number theoretic statements cannot be decided.
This is true both in set theory with respect to ZFC, and in second orderlogic with respect to any sentence characterising the natural numbers.
There is a quick technical way to derive the failure of completeness: The odel numbers of second order sentences that are (semantic) logical consequences of the categorical characterisation of the natural numbers, i.e.
are true in the natural numbers, is non-arithmetical by Tarski's Undefinabil-ity of Truth Theorem, while the set of theorems of any effective axiom systemis recursively enumerable. So these two sets cannot be the same.
We now turn to the alternative of changing the semantics to so-called Henkin semantics in order to obtain (7) even if we lose (5).
The problem of the incompleteness of the Hilbert-Ackermann deductive sys-tem for second order logic was solved by Henkin [9] in a decisive and boldway which has become a standard technique in other logics too. He modifiedthe concept of a structure by allowing the second order variables to rangeover a limited set of possibilities, rather than over all possibilities. This issomewhat analogous to the situation in set theory, where we cannot (yet)decide the truth value of the CH but we can study models of set theory inwhich the set variables range over a limited collection of sets rather than overall sets. Technically speaking these models are transitive sets that satisfy the ZFC-axioms. Some of them satisfy the CH, some don't.
A Henkin model is a pair (M, G), where M is a usual first order structure and G is a set of subsets, relations and functions on M . Note that we do notlimit the subsets to be unary, and we allow relations as well as functions. Inmonadic second order logic G is assumed to contain unary predicates only.
We can readily define the concept for second order φ by induction on φ by stipulating (M, G) = ∃Rφ(R) (M, G) = φ(S) for some interpretation S ∈ G of R.
The intended meaning of "∃R" is that there is a relation R on the domainof the model, and any relation can serve as R, even the most complicatedand abstract R, even an R which is by no means definable. Naturally thisintended meaning of "∃R" can in some cases go deeply into set-theoreticalquestions about existence of this or that kind of a relation on a given set.
The situation with (M, G) = ∃Rφ(R) is different. We only ask whether thereis a relation R in G. Of course, G may be complicated itself, such as P(M ),but it can also consist of just the kind of relations we are interested in andthat we can deal with. Truth in a full model is not absolute in the sense ofset theory, but truth in a given Henkin model can easily seen to be absolute.
3 There is an additional assumption on Henkin models: We assume that every Henkin model satisfies the Axioms of Comprehension, and the Axiomsof Choice. As a consequence of the Axioms of Comprehension, in everyHenkin model (M, G) we have M ∈ G and also all the distinguished constants,relations and functions of M, i.e. the interpretations of the symbols in thevocabulary of M, are in G.
We take the convention that if G is any set whatsoever, however big or small, we define (M, G) to be (M, G  M ), where G  M is defined as follows: 3A formula φ(x1, . . , xn) of set theory is absolute if for any two models M and M0 of ZFC, M 0 an end-extension of M (e.g. both transitive and M ⊆ M 0), if a1, . . , an ∈ M ,then M = φ(a1, . . , an) if and only if M 0 = φ(a1, . . , an).
{A ∩ M n : A ∈ G an n-ary relation}∪{f  Mn : f ∈ G an n-ary function}, provided that then (M, G) satisfies the Comprehesnion Axioms, i.e. is aHenkin model. So if G is a set such that (M, G) is a Henkin model, then Mand all the structural elements of M are in G. We write whenever this happens, in order to indicate that everything that M is builtup from is in G.
There is a canonical family of Henkin models, namely the full Henkin models (M, G), where G is the set P∗(M ) of all subsets, relations and func-tions on M . Since P∗(M ) is uniquely determined by M we denote (M, P∗(M ))simply by M. So a non-Henkin model M can be thought of as a Henkin modelby identifying it with (M, P∗(M )). We call semantics based on Henkin mod-els the Henkin semantics, and the original semantics based on full modelsthe full semantics.
The point of Henkin models is that they satisfy the Completeness Theo- Theorem 1 ([9]) The following are equivalent for all second order sentencesθ and φ: 2. Every Henkin model of θ is a Henkin model of φ.
Henkin's original proof was for type theory. A modern proof can be writ- ten along the lines of a "Henkin-style" proof of the Completeness Theorem offirst order logic. Respectively, we get the Compactness Theorem4as well asthe downward and the upward versions of the L¨ The way to think about Henkin models is that they fill the gaps left by full models, as irrational numbers fill the gaps left by rational numbers.
4Every set of second order sentences, every finite subset of which has a Henkin model, has itself a Henkin model.
5If a second order sentence has a Henkin model (M, G) with M infinite, it has Henkin models (M, G) with M any infinite cardinal.
They are needed in order to get a smooth theory of second order logic. Theymanifest "paradoxical" phenomena that we do not see among full models. Forexample we get non-standard models of number theory, countable models ofthe axioms of real numbers, etc. The categorical sentences characterisingmathematical structures among full models now suddenly have also other"models", namely Henkin models, and they come in all infinite cardinalities.
If φ is a second order sentence we define M odH(φ) = {(M, G) : (M, G) = φ} Obviously, Mod(φ) ⊆ M odH(φ). If φ characterises M up to isomorphism,then M ∈ Mod(φ) ⊆ M odH(φ).
In fact, in all non-trivial cases6 M odH(φ) 6= {M}. It is instructive to think ofM odH(φ) as a "cloud" around M, because the Henkin models in M odH(φ)in a sense "blur" our image of M. One of them is the "real" M but bymeans of deductions in second order logic we cannot tell which. Because ofthe inherent weakness of formal systems, going back to Skolem and G¨ infinite structures are shrouded by Henkin models and cannot be gottenperfectly into focus by means of deductions.
Categoricity is lost in the passage from full models to Henkin models.
No infinite Henkin model is characterisable in second order logic, i.e. for no(M, G) with infinite M is there second order θ such that (M, G) = θ and ∀(M0, G0)((M0, G0) = θ → M0 ∼ Respectively, no second order sentence θ with an infinite Henkin model iscategorical even in the weak sense that ∀(M, G), (M0, G0)(((M, G) = θ ∧ (M0, G0) = θ) → M ∼ Both facts are consequences of the upward L¨ However, in the next section we introduce a form of categoricity which holds also for Henkin models in interesting ways.
6By the upward L¨owenheim-Skolem Theorem, if M is infinite, M odH(φ) has Henkin models of all infinite cardinalities.
7By the upward L¨owenheim-Skolem Theorem any second order sentence with an infinite Henkin model has Henkin models in all infinite cardinalities.
It is important to bear in mind that Henkin models (M, G) are not in themselves interesting mathematical structures. Apart from the full model,none of them have any claim to fame. Their importance is in their auxiliaryrole in explaining what can be proved and what cannot. This is in har-mony with the fact that second order sentences are not categorical in Henkinsemantics.
It is true that some are more interesting than others, for example, if N is a transitive model (set or class) of set theory and N = "(M, G) is a full Henkin model", then (M, G) is a Henkin model8, albeit not necessarily a full one. Let us thensay that (M, G) is N -full. Certainly the L-full models are quite interesting,where L is G¨ odel's universe of constructible sets. Indeed, the N -full models for various N give rise to a wealth of interesting and useful Henkin models.
Note that in order to build a Henkin model for second order logic we herebuild a model for the entire set theory. This is emblematic of the situationthat the best way to understand second order logic is to understand settheory.
As was said earlier, the axioms of second order logic are not able to decide CH. Let us see how this can be seen in the light of classical independenceproofs in set theory. We know that CH is true in the universe L of con-structible sets. Let (M, G) be the L-full model of the second order axiomsθ of the real-numbers as a completely ordered separable Archimedian field.
Thus, (M, G) ∈ L and L = "(M, G) is the unique model of θ".
Since L satisfies CH, the second order sentence φ expressing this on the realssatisfies L = "(M, G) = φ".
By the absoluteness of second order truth in a Henkin model, (M, G) = φ.
As a consequence the axioms of second order logic cannot prove θ → ¬φ.
8First of all, G is clearly a set of relations and functions on M . To prove that (M, G) sat- isfies the Comprehension Axioms, suppose φ(x1, . . , xn) is a second order formula in whichthe second order variable R does not occur free. The second order formula φ(x1, . . , xn)over M can be written in the first order language of set theory as φ∗(x1, . . , xn, M ). By theSeparation Axiom of ZFC, the set of tuples of elements of M satisfying φ∗(x1, . . , xn, M )is an element of N .
Next we show that the axioms of second order logic cannot prove θ → φ. Bythe famous result of Paul Cohen, as further developed by Robert Solovay andDana Scott, there is a complete Boolean algebra B such that the truth valueof ¬CH in the B-valued universe of sets9 V B is one. As a consequence10 thereis a B-valued Henkin model for ¬CH. As the Boolean valued Henkin modelssatisfy the Comprehension axioms and the Axioms of Choice, we concludethat θ → φ cannot be proved.
Set theorists study transitive models of ZFC even though they are re- ally interested in the "full" models11 Vα, where "normal" mathematics takesplace. Second order logicians study Henkin models even though they arereally interested in the full models, i.e. the structures "normal" mathematicsis based on.
Internal categoricity We have reached the following situation in our analysis of second order logic: 1. Important mathematical structures such as natural numbers, real num- bers, complex numbers, etc can be characterized up to isomorphism inthe full semantics, but truth in full models cannot be effectively axiom-atized.
2. Truth in all Henkin structures can be effectively axiomatised, but no infinite Henkin model can be characterized up to isomorphism.
We now introduce a form of categoricity which holds for Henkin structures in important cases and agrees with the usual concept of categoricity in thecase of full Henkin models.
We say that a second order sentence θ is internally categorical [22] if ∀(M, G), M0 ∈ G, M1 ∈ G(((M0, G) = θ ∧ (M1, G) = θ) → ∃f ∈ G(f : M ∼ This is called "internal" categoricity because the models M0 and M1 areinternal to (M, G), i.e. elements of G, and furthermore the isomorphism fcan be found "internally" i.e. from G itself.
9See e.g. [2].
10See [15] for details.
11V0 = ∅, Vα+1 = P(Vα), Vν = S β , for ν limit.
It is important to notice that internal categoricity is stronger than usual categoricity, because if M0 and M1 are two models of an internally categoricalθ, then we need only choose a transitive model N of (a suitable finite partof) ZFC such that all subsets, relations and functions on M0 ∪ M1 are in Nand then apply (12) to the N -full model (N, G). Note that here we treat Nas a model of the empty vocabulary, which is all we need.
In fact, internal categoricity is a kind of provable categoricity, because if the vocabulary of θ is just {R}, for simplicity, then (12) is equivalent to ∀M0, R0∀M1, R1((θ(R0)(M0) ∧ θ(R1)(M0)) → ∃F φiso(F, M0, R0, M1, R1)), where θ(Ri)(Mi) denotes the relativisation of θ(Ri) to Mi, and the formulaφiso(F, M0, R0, M1, R1) is the second order formula which says that F is anisomorphism between (M0, R0) and (M1, R1).
To verify the categoricity of a second order sentence one has to go through infinite structures in a way which essentially calls for set theory. The situ-ation with internal categoricity is totally different. To verify the internalcategoricity of a second order sentence one just has to produce a proof whichmeans essentially going through natural numbers. So there is a dramaticdifference. And still internal categoricity is stronger than categoricity. So itwould be foolish to establish categoricity if one could establish even internalcategoricity.
The main observation about internal categoricity is that the classical examples of categorical sentences are all internally categorical: Theorem 2 ([23]) The received second order sentences characterising thestructures (N, <) and (R, <, +, ·, 0, 1) are internally categorical.
The concept of internal categoricity provides a bridge between full se- mantics and Henkin semantics. It works in the same way in both cases andshows that the full semantics is a limit case of Henkin semantics but doesnot have a monopoly when it comes to categoricity.
The approach of set theory to mathematics differs from that of second or-der logic in one fundamental aspect. While second order logic focuses onone mathematical structure at a time, set theory builds up directly one so powerful a hierarchy that all necessary mathematical structures can be seenas parts of it. In principle this hierarchy starts from some individuals, orurelements, but experience has shown that the urelements are unnecessary.
A possible way to compare second order logic and set theory might be the following: Start with a structure M. We have second order logic for thisstructure by considering the power-set of the underlying domain. Likewise,we have third, fourth, fifth, etc order logics for this structure by iteratingtaking power-sets. Let us continue to the transfinite. What results is akind of transfinite theory of types. Now throw away the distinction betweenvariables of different orders and let variables assume their order from thecontext. Then observe that there are so many sets around that the originalM is not needed any more. The whole construction can be started from theempty set and still all the structures needed in ordinary mathematics wouldbe there.
odel presents the relationship between the theory of types and set theory very much in this vain: It may seem as if another solution were afforded by the systemof axioms for the theory of aggregates, as presented by Zermelo,Fraenkel and von Neumann, but it turns out that this system ofaxioms is nothing else but a natural generalisation of the theoryof types, or rather, it is what becomes of the theory of types ifcertain superfluous restrictions are removed. [8, 1933o] When mathematics is developed in set theory, everything is constructed by means of the membership relation ∈ only. One first defines the concept ofan ordinal: a transitive set of transitive sets. The set N of natural numbersis defined as the smallest non-zero limit ordinal, i.e. the smallest non-zeroordinal which is not of the form x ∪ {x}. Thus there is a simple formulaφ0(x) of set theory, with just ∈, such that ∀x(x = N ⇐⇒ φ0(x)).
The quantifier ∀x of this equivalence, as well as all the quantifiers inside φ0(x)are supposed to range over all sets. The universe of set theory is assumed tobe closed under such basic constructions as Cartesian products and power-sets. Thus we can construct the integers Z as pairs of natural numbers, andthe rationals Q as pairs of integers. Then we have φ1(x) and φ2(x) such that ∀x(x = Z ⇐⇒ φ1(x)) and ∀x(x = Q ⇐⇒ φ2(x)).
After this we follow Dedekind and construct the reals R as Dedekind cuts ofrationals, and again we have a formula φ3(x) such that ∀x(x = R ⇐⇒ φ3(x)).
In set theory we do not define central mathematical structures, such as N,Z, Q and R, up to isomorphism, as in second order logic, but up to identity.
Second order logic is perhaps correct to defining these structures up to isomorphism only, for mathematicians do not want to know what objectsthe numbers are. It is their structure that matters. If too much is known,it may complicate matters unnecessarily. So set theory seems to go astrayhere. But the point of set theory is not to insist that the numbers in N, Z, Qand R really are what the formulas φ0(x), . . , φ3(x) say, only that this is oneconvenient way, and there are numerous isomorphic ways. The advantage ofdefining the number systems N, Z, Q and R the way we have done is thatevery object in set theory becomes built up by means of membership ∈ only,and then we can prove things about all sets by transfinite induction on ∈.
So the advantage of set theory is that everything is built up in a uniform way, and can be handled uniformly. It is actually a problem in second orderlogic that we can work in one structure and then work in another structure,but how to bring these two things together. It is possible to transfer struc-tures with isomorphisms so that they become substructures of each other,but after doing this for a while, one asks, why not assume that everythingwe need is part of one big structure, and then use second order logic on thatbig structure. Well, that is the idea of set theory. The universe of sets is theone big structure and every set that we may ever need is an element of it.
Hierarchies based on quantifier structure are a useful method to compare de-finability of concepts in different systems. Second order logic has an obvious Existential second order quantifiers followed by a first order formula Universal second order quantifiers followed by a first order formula existential second order quantifiers followed by a Π1 -formula universal second order quantifiers followed by a Σ1 -formula We use the above concepts always up to logical equivalence. The logical equivalences we usually use are all provable from the Hilbert-Ackermannaxioms.
For example, (1) and (2) are Π1-formulas.
These classes of formulas have some obvious closure properties, up to logical equivalence: They are all closed, up to logical equivalence, under ∧,∨, and first order quantifiers. The hierarchy is proper: This was first proved by Kuratowski in early descriptive set theory by meansof the following trick: By suitable coding one can construct in number theorya universal Σ1 formula Φ -formula φ(y) there is n(x, y), that is, for every Σ1 a ∈ N such that (N, +, ·, 0, 1)) = ∀y(φ(y) ↔ Φn(a, y)).
Suppose now ¬Φn(x, x) were logically equivalent to a Σ1 formula. Then there would be a ∈ N such that (N, +, ·, 0, 1)) = ∀y(¬Φn(y, y) ↔ Φn(a, y)).
Letting y = a leads to a contradiction. Since ¬Φn(x, x) is Π1 up to logical equivalence, we get the result Π1 . Analogously, Σ1 consequence, it makes sense to define ∆1 = Σ1 ∩ Π1 , and then ∆1 is closed under ∧, ∨, ¬ and first order quantifiers. Craig's Interpolation Theorem can be formulated in an equivalent form as follows: If φ and ψ are Σ1 -sentences with no models in common, then there is a first order sentence θ such that φ = θ and moreover θand ψ have no models in common.
As a consequence ∆1 is just first order logic. However, there is a sense in which Π1, or equivalently Σ1, already has the full power of second order logic, although the above hierarchy result shows that this cannot be literally true.
We present the details of this construction (due to [18] and [12]) in somedetail for completeness: To avoid cumbersome notation, we treat only unary second order logic in a vocabulary containing one binary predicate symbol S. Let A, B and E besome fixed new predicate symbols, the first two unary and the third binary.
Suppose ¯ φ(z1, . . , zn, E) is obtained from φ(R1, . . , Rn), where R1, . . , Rn are unary second order variables, by replacing every occurrence of Ri(y) byyEzi, where z1, . . , zn are new individual variables. Define a translationφ 7→ φ∗ from unary second order logic to first order logic as follows: • φ∗ = φ if φ is first order • (φ ∧ ψ)∗ = φ∗ ∧ ψ∗, (φ ∨ ψ)∗ = φ∗ ∨ ψ∗, (¬φ)∗ = ¬φ∗ • (∃xφ)∗ = ∃x(A(x) ∧ φ∗), (∀xφ)∗ = ∀x(A(x) → φ∗) • (∃Riφ)∗ = ∃zi(B(zi) ∧ ¯ φ∗), (∀Riφ)∗ = ∀zi(B(zi) → ¯ The idea is that the predicate A is reserved for individuals and the predicateB for subsets of A. The membership-relation is represented by E. Let θ bethe Π1-sentence ∀X(∀y(X(y) → A(y)) → ∃z(B(z) ∧ ∀y(yEz ↔ X(y)))) ∧∀x∀y((B(x) ∧ B(y) ∧ ∀z(zEx ↔ zEy)) → x = y).
This sentence says that for every subset X of A there is an element z of Bsuch that, if E were the membership-relation, then z would be exactly X.
Lemma 1 Suppose φ is a second order sentence, S ⊆ M × M and (M, S) =φ. Then (M ∪ P(M ), P(M ), M, ∈, S) = θ ∧ φ∗.
Conversely, if (M, B, A, E, S) = θ ∧ φ∗, then there is (A0, S0) ∼ that 2 A0 = M and (A0, S0) = φ.
Theorem 3 The following are equivalent for any second order φ and its firstorder translation φ∗: 1. φ has a model (of cardinality κ).
2. θ ∧ φ∗ has a model (of cardinality 2κ).
As a consequence, checking the validity of a second order sentence φ can be recursively reduced to checking the validity of the Σ1-sentence θ → ¬φ∗. Likewise checking whether a second order sentence φ has a model ofcardinality κ can be reduced to asking whether the Π1-sentence θ ∧ φ∗ has a model of cardinality 2κ. This means that the L¨ owenheim number12 and the Hanf number13 of the entire second order logic are the same as those of thefragment Π1.
Summing up, upon first inspection the levels Σ1 ∪ Π1 of the hierarchy of second order formulas grow strictly in expressive power as n increases, buta more careful analysis reveals that already the first level Σ1 ∪ Π1 has the power of all the levels Σ1 ∪ Π1 even if the power is somewhat hidden and needs to be brought to light.
In set theory there is the Levy-hierarchy Σn ∪ Πn of formulas [17]. This is a strict hierarchy roughly for the same reason why the hierarchy Σ1 ∪ Π1 of second order formulas is strict. But there is no known method to reduce thetruth of an arbitrary formula to the truth of a formula on the Σ1 ∪Π1 level. Infact, if the decision problem, L¨ owenheim-Skolem number and Hanf number are suitable defined for Σn ∪ Πn-formulas of set theory, the decision problemgets more and more complicated, and the numbers get bigger and bigger asn increases [20]. Recall that in the case of second order logic, these conceptsattained there maximal complexity already on the first level Σ1 ∪ Π1.
Let us finally compare the two hierarchies, the hierarchy Σ1 ∪ Π1 inside second order logic and the hierarchy Σn ∪ Πn in set theory.
Theorem 4 ([20, 21]) 1. The set of G¨ odel numbers of valid second order sentences is the complete Π2-set of natural numbers.
owenheim-Skolem number of second order logic is the supremum of all Π2-definable ordinals.
12The smallest cardinal κ such that if a second order sentence has a model at all, it has a model of cardinality ≤ κ.
13The smallest cardinal κ such that if a second order sentence has a model of cardinality ≥ κ, it has arbitrarily large models.
3. The Hanf number of second order logic is the supremum of all Σ2- definable ordinals.
4. Every model class which is definable in second order logic is ∆2-definable in set theory.
In the light of the above theorem second order logic sits firmly on the Σ2 ∪ Π2-level of set theoretic definability. This is a reason to consider secondorder logic weaker than set theory.
Foundations of mathematics Let us first discuss what do I mean when I say that I consider second orderlogic as a foundation of mathematics. I have in mind the following: Whatevermathematical structures mathematicians have need for can be characterisedin second order logic. Then truths about these structures can be identifiedwith logical consequences of those characterisations.
If a mathematician doubts the truth of a statement, he or she needs only to figure out what isthe structure that the claim is concerned with and then check whether thecharacterisation of the structure logically implies the claim14.
There are several points in this scenario which need clarification. First of all, in mathematical practice one sometimes needs to appeal to third orderlogic, that is, second order is not enough; but I consider this an irrelevantpoint15. Secondly, is it really true that whatever mathematical structuresmathematicians have need of can indeed be characterised in second orderlogic up to isomorphism? After all, there are only countably many possiblesentences in second order logic to use for such characterisations. In fact, it isalmost impossible to pinpoint a mathematical structure that is (provably inZFC) not second order characterisable, without resorting to cardinality-typearguments16.
Finally there is the question what logical consequence means in second order logic. Let us say that φ is a weak logical consequence of ψ if everymodel of ψ is a model of φ. We noted in Theorem 4 that this relation is 14I disregard here statements of the type "Every ordered set has a completion" as they can in principle be restricted, at the cost of losing some elegance, to a suitable universaldomain.
15My approach can be adapted to include third, fourth, etc order logic.
16See [14] for a careful analysis of this situation.
highly complex, which raises the question, is it actually possible to verifylogical consequence in this way? There is a clear alternative: φ is a stronglogical consequence of ψ if every Henkin model of ψ is a Henkin model of φ,or equivalently, if there is a finite proof of φ from ψ and the ComprehensionAxioms and the Axioms of Choice.
Strong logical consequence is, of course, much stronger than weak logical consequence. A famous example is the Continuum Hypothesis CH. If θ is a second order characterisation of the continuum17, then either CH or ¬CH is aweak logical consequence18 of θ , but neither is a strong logical consequence19.
The good news is that the CH is really exceptional20 and virtually any logicalconsequence appearing in mathematics (outside set theory) turns out to be astrong one. Thus the appeal to strong logical consequence, even when weaklogical consequence may seem more appealing, solves the otherwise seriouscomplexity problem.
Next I should explain what I mean when I say that I consider set theory as a foundation of mathematics. This is easier because nowadays set theoryis a much more popular foundation than second order logic. The scenario isas follows: mathematical objects are thought of as sets, whether they looklike sets or not. Properties of sets are derived from the axioms of set theory.
Thus these axioms (ZFC) are thought to be true in the universe of all sets. Inanalogy with second order logic there are statements (CH) about sets whichare true or false but we do no know which, while we do know that thesestatements cannot be derived from the ZFC-axioms. In a sense, truth in theuniverse of sets ("weak" truth) corresponds in second order logic to what wecall weak logical consequence, and derivability from ZFC ("strong" truth)corresponds to what we call strong logical consequence.
It should be noted that ("weak") truth in the universe of sets is not a set-theoretical concept21 but we can usually limit ourselves to some high levelof the cumulative hierarchy and then truth is definable. This is in analogywith the situation in second order logic where sentences such as "Every linearorder has a completion" cannot be given meaning without restricting themto some universal domain.
17First presented as a second order sentence in [13].
18As pointed out by Kreisel [16].
19By results of G¨odel [7] and Cohen [3].
20However, the independence results in set theory provide numerous examples which behave as CH. The most famous is the Souslin Hypothesis.
21By Tarski's Undefinability of Truth argument [19].
Weak logical consequence, and thereby truth in a second order charac- terisable structure, is a Π2-concept in set theory. In the Levy-hierarchy offormulas of set theory truth of a lower level is always definable in the nextlevel. Thus there is a Σ3-formula which defines the truth of Π2-formulas.
Moreover, truth of formulas on any fixed level is reflected by a closed un-bounded class of levels Vα of the cumulative hierarchy of sets. The problemwith (weak) truth of arbitrary formulas in the entire universe of sets is thatwe cannot limit the formulas to any fixed level Σn of the Levy-hierarchy andwe cannot limit truth to any fixed level Vα of the cumulative hierarchy.
In summary, truth in set theory goes beyond set theory and truth in second order logic goes beyond second order logic, but truth in second orderlogic can be defined in set theory because it is limited to the Π2-level of theLevy-hierarchy. This is what it means that second order logic is a fragmentof set theory.
I have argued that second order logic is really best understood as a frag- ment of set theory. The apparent problem that second order logic has secondorder quantifiers while set theory is presented in a first order language, is re-ally only an apparent problem. The underlying first order logic of set theoryis first order only if looked upon from outside. But there is no outside positionin foundations of mathematics. We are always inside. It is more instructiveto think of the first order logic of set theory as a very high order logic. Af-ter all, it allows quantification over subsets, sets of subsets, sets of sets ofsubsets, etc of given parameters.
I claim that when second order logic and set theory are construed as foundations there is essentially no difference in their ability to capture math-ematical concepts up to isomorphism. The huge difference between secondorder logic and first order logic disappears. The matter is different if theselogics are used as tools in mathematical logic. Then we can observe suchbig differences as one is compact, the other is not, one is absolute, the otheris not, one has Downward L¨ owenheim-Skolem Theorem, the other does not, etc. But this is mathematical logic, not foundations of mathematics.
[1] M. Ajtai. Isomorphism and higher order equivalence. Ann. Math. Logic, [2] J. L. Bell. Boolean-valued models and independence proofs in set the- ory, volume 12 of Oxford Logic Guides. The Clarendon Press, OxfordUniversity Press, New York, second edition, 1985. With a foreword byDana Scott.
[3] Paul Cohen. The independence of the continuum hypothesis. Proc. Nat.
Acad. Sci. U.S.A., 50:1143–1148, 1963.
[4] R. Dedekind. Stetigkeit und irrationale Zahlen. Braunschweig. Vieweg [5] R. Dedekind. Was sind und was sollen die Zahlen? Vieweg Sohn, 1888.
[6] R. Dedekind. Essays on the theory of numbers. I. Continuity and ir- rational numbers. II. The nature and meaning of numbers. Authorizedtranslation by W. W. Beman. Chicago: The Open Court PublishingCo. London: Kegan Paul and Co. 116 S. [Nature 64, 374.] (1901)., 1901.
odel. The consistency of the axiom of choice and of the gener- alized continuum- hypothesis. Proc. Natl. Acad. Sci. USA, 24:556–557,1938.
odel. Collected works. Vol. III. The Clarendon Press, Oxford University Press, New York, 1995. Unpublished essays and lectures,With a preface by Solomon Feferman, Edited by Feferman, John W.
Dawson, Jr., Warren Goldfarb, Charles Parsons and Robert M. Solovay.
[9] Leon Henkin. Completeness in the theory of types. J. Symbolic Logic, 15:81–91, 1950.
[10] D. Hilbert. Grundlagen der Geometrie. Leipzig: B. G. Teubner., 1899.
[11] D. Hilbert and W. Ackermann. Grundz¨ uge der theoretischen Logik.
J. Springer (Die Grundlehren der mathematischen Wis- senschaften Bd. 27). VIII, 120 S. (1928)., 1928.
[12] K. Jaakko J. Hintikka. Reductions in the theory of types. Acta Philos.
Fenn., 8:57–115, 1955.
[13] E. V. Huntington. A complete set of postulates for the theory of of absolute continuous magnitude.
[14] Tapani Hyttinen, Kaisa Kangas, and Jouko V¨ anen. On second-order characterizability. Log. J. IGPL, 21(5):767–787, 2013.
[15] Daisuke Ikegami and Jouko V¨ anen. Boolean valued second order logic. Notre Dame Journal of Formal Logic, 56(1), 2015.
[16] G. Kreisel. Informal rigour and completeness proofs. In Proceedings of the International Colloquium in the Philosophy of Science, London,1965, Vol. 1. Edited by Imre Lakatos, pages 138–157. North-HollandPublishing Co., Amsterdam, 1967.
evy. A hierarchy of formulas in set theory. Mem. Amer. Math.
Soc. No., 57:76, 1965.
[18] Richard Montague. Reduction of higher-order logic. In Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), pages 251–264. North-Holland,Amsterdam, 1965.
[19] Alfred Tarski. Der Wahrheitsbegriff in den Sprachen der deduktiven Disziplinen. Anzeiger Wien, 69:23–25, 1932.
anen. Abstract logic and set theory. I. Definability. Logic colloquium '78, Proc., Mons/Belgium 1978, Stud. Logic Found. Math.
Vol. 97, 391-421 (1979)., 1979.
anen. Second-order logic and foundations of mathematics.
Bull. Symbolic Logic, 7(4):504–520, 2001.
anen. Second order logic or set theory? Logic, 18(1):91–121, 2012.
anen and Tong Wang. Internal categoricity in arithmetic and set theory. Notre Dame Journal of Formal Logic, 56(1), 2015.
[24] E. Zermelo. Untersuchungen ¨ uber die Grundlagen der Mengenlehre. I.
Math. Ann., 65:261–281, 1908.
Department of Mathematics and StatisticsUniversity of HelsinkiFinland Institute of Logic, Language and ComputationUniversity of AmsterdamThe Netherlands


The effect of subclinical ketosis in early lactation on reproductive performance of postpartum dairy cows

J. Dairy Sci. 90:2788–2796doi:10.3168/jds.2006-560© American Dairy Science Association, 2007. The Effect of Subclinical Ketosis in Early Lactation on ReproductivePerformance of Postpartum Dairy Cows R. B. Walsh,*1 J. S. Walton,† D. F. Kelton,* S. J. LeBlanc,* K. E. Leslie,* and T. F. Duffield**Department of Population Medicine, and†Department of Animal and Poultry Science, University of Guelph, Ontario, Canada, N1G 2W1

An integrated pharmacokinetics ontology and corpus for text mining Hengyi Wu1,† Email: Shreyas Karnik1,† Email: Abhinita Subhadarshini1,† Email: Zhiping Wang1,2,† Email: Santosh Philips3 Email: Xu Han1,3,4 Email: Chienwei Chiang1 Email: