Posts Tagged ‘Second order logic’


Is second order logic really first order?

November 6, 2008

Nowadays, I guess, a lot more people are sympathetic to the idea that second order logic is real logic than in Quine’s day due to the popularity of plural logic. However, this falls short of full second order logic by quite a long way due to the fact that it can’t quantify over relations. For example, you can’t state various facts about sizes or the axiom of choice.

In the first order case, the question seems to be more tractable. If we identify the logical vocabulary as those terms that are not sensitive to the particular identities of the individuals (i.e. whose extensions remain unchanged if you permute the domain) then we get the cardinality quantifiers and arbitrary unions of the cardinality quantifiers as logical terms. McGee confirms the intuition that these truly are logical by showing that the permutation invariant (first order) vocabulary are precisely those defineable from intuitively logical operations: negation, identity, arbitrary conjunctions, universal quantification with respect to an arbitrary block of variables. Admittedly, this language (L_{\infty, \infty}) is not a language that anyone can speak, but that is a deficiency on our part, and should not place constraints on logic. Thus, first order quantification seems to be ontologically innocent, even for quantifiers like ‘there are uncountably many F’s’.

Indeed, similar results hold if we allow second order quantifiers. They are also permutation invariant, and conversely, the permutation invariant second order quantifiers is precisely those that can be defined in the equivalent of L_{\infty, \infty} with arbitrary blocks of second order quantifiers too. But the difference here, it seems, is that it is not clear that second order quantification over relations is ontologically innocent. Sure, plural quantifiers are, but as soon as we leave the realm of monadic quantification there is less reason to think so (although some have suggested that you can get around it: e.g. Burgess, and Rayo and Linnebo.)

Anyway, I was wondering if it would be possible to reduce second order quantification to first order quantification in our infinitary language. If this were possible then we could happily use the second order quantifiers and safely know that the are not ontologically committing, because they are definable using first order vocabulary.

I think you can do it, but I’m not entirely sure so this might be wrong. Let \kappa be antizero – the size of everything. For each second order variable X of the language keep aside \kappa many variables: x_\alpha for \alpha \leq \kappa. Then define a translation schema as follows: [UPDATE: I reformulated it slightly so that it wasn’t quite so confusing.] For a subset of the domain, I, we define the translate of \phi with repsect to I as follows:

(Xx)^I \mapsto \bigvee_{\alpha \in I}x=x_\alpha

(\forall X \phi)^I \mapsto \forall x_1 \ldots x_\kappa(\forall y\bigvee_{\alpha \leq \kappa}x_\alpha=y \rightarrow \bigvee_{J \subseteq \kappa} (\phi)^J)

For the other connectives and quantifiers translation just commutes in the natural way. A couple of notes: this isn’t like L_{\infty, \infty} in that it must allow truly arbitrary disjunctions and quantifications (including proper class length conjunctions.) Secondly, it’s not really as simple a translation as it looks because in the first clause I left I “free”, to be later “bound” by an earlier application of the second translation clause. What this really means is that the length of the disjunction in the first clause is really determined by when it is called in the second clause. Lastly – that’s just monadic quantification, which we already had – but it seems it will extend nicely to polyadic second order quantifiers (this time we disjoin (x = x_\alpha \wedge y = y_\alpha) instead.)


Is the axiom of choice a logical truth?

October 5, 2008

I actually think there are a bunch of related statements which we might think of as expressing choice principles. The most striking contrast is probably the set theoretic statement of choice, and the choice principle as it is stated in second order logic: \forall R(\forall x \exists y Rxy \rightarrow \exists f \forall x Rxf(x)). I want to argue that the second principle is a purely logical principle, unlike the first, despite the fact that the question of whether or not the latter is a logical truth seems to depend on the (ordinary) truth of the former.

Let’s start off with the set theoretic principle. I believe this is non logical. Note, however, that this is not because of the Gödel Cohen arguments – I think set-choice is a logical consequence of the second order ZF axioms, given SOL-choice. It is rather because the ZF axioms themselves are non logical. For example consider a model with three elements such that: a \in b \in c – clearly c is a set of nonempty sets, but there isn’t a choice function for it because there aren’t any functions at all (that would require a set of set of set of sets.) Simply put: membership is not a logical constant, and so admits choice refuting interpretations. Note, I don’t mean to downplay the importance of the Gödel Cohen arguments; forcing and inner model theory are important tools in the epistemology of mathematics. Set-choice and CH may not be logically independent of the ZF axioms, but they do show us that, for all we are currently in a position to know, CH might be a logical consequence of second order ZF. It provides a method for showing epistemic independence and epistemic consistency, despite falling short of logical independence and consistency.

It might then be surprising to say that the second order choice principle is a logical truth. For following the Tarskian definition of logical truth for second order languages, i.e. truth in every set model, it follows that SOL-choice is a logical truth just in case set-choice is an ordinary truth (“true as a matter of fact”.) For example, if our metatheory was ZF+AD, SOL-choice would be neither a logical truth nor a logical falsehood!

I think this is to put the cart before the horse. Once the logical constants are a part of our metalanguage, then it is possible to do model theory in such a way that the non-logical fragment doesn’t affect the definitions of validity – indeed the non-logical component can be reserved purely for the syntax (see particularly, Rayo/Uzquiano/Williamson (RUW) style model theory.) So much the worse for Tarskian model theory.

But why think that SOL-choice is a logical truth or a logical falsehood, rather than neither? I guess I have three reasons for thinking this. Firstly, SOL-choice is stateable in almost purely logical vocabulary: Plural logic plus a pairing operation. While it is possible for it to fail under non-standard interpretations of the pairing function, it is enough to provide well orderings of many sets of interest: e.g. the plural theory of the real numbers gives us enough machinery for pairing, so well orderings under this encoding of pairs is possible. Secondly, SOL-choice is stateable in purely logical vocabulary. If you treat the binary quantifier “there are just as many F’s as G’s” as a logical quantifier, then you can state cardinal comparability in Plural logic+”there are just as many F’s as G’s” (which is certainly equivalent to choice in the ZF metatheory, I’m not sure what you need for this in the RUW setting.) I argued here that “there are just as many F’s as G’s” is a logical quantifier.

Lastly, imagine that we interpreted the second order quantifiers as ranging completely unrestrictedly over all pluralities there are. Suppose we still think that SOL-choice is not logically true or false. I.e. SOL-choice and it’s negation is logically consistent in the strong sense (not just that there are refuting Henkin models – that you can’t prove a contradiction from standard axioms.) Then there is a model in which SOL-choice is true, and a model in which it is false. But since our domain is everything, and the quantifiers in both models range over every plurality there is, the second order quantifier in the choice-satisfying model ranges over a choice function, which the second order quantifiers in the choice-refuting model must have missed. This is a contradiction, because we assumed that the quantifiers ranged over every plurality there is. Basically, choice-refuting models are missing things out. If there’s a choice interpretation and a ~choice interpretation for our unrestricted plural quantifiers, the choice model quantifiers range over more pluralities, in which case the ~choice model wasn’t really unrestricted after all. It seems then, that if SOL-choice is logically consistent, then it is logically true! (Note: this is kind of similar to the Sider argument against relativism about mereology. If there is an interpretation of our unrestricted quantifier that includes mereological fusions, and one that doesn’t, then the latter wasn’t really unrestricted after all.)


Which things occupy the set role?

September 21, 2008

Question: out of everything there is, which of those things are sets? A standard (platonist) answer would go something like the following: just those objects that are setty – those objects that have some special metaphysical property had only by sets. No doubt being setty involves being abstract, but presumably it involves something more – unless you’re a hardcore set theoretic reductionist there are non-setty abstract objects too.

I’ve been wondering about giving a more structuralist answer to this question: there is no primitive metaphysical property of being setty, rather, the sets are just whichever things happen to fill the set role. To get a rough idea, a model of set theory is just a relation R, (and by relation here I mean the things second order quantifiers range over.) Thus the set role is some third order property, F, which characterises the role the sets play. Since there will certainly be several relations satisfying the set role we have a choice: we can either ramsify or supervaluate. I prefer the supervaluational route here: it is (semantically) indeterminate whether the empty set is Julius Ceasar, but even so, it is supertrue that the empty set belongs to its singleton. More generally, a set theoretic statement \phi(\in) is supertrue iff \phi(R) is true for every R satisfying F, superfalse iff … and so on as usual, where an admissible precisification of the membership relation is just any relation R that satisfies F.

[Of course there may be no relations satisfying the set role. But presumably this will only happen if there aren’t enough things. On the ontological side, I’m just imagining there only being concrete things, and the more worldly abstract objects such as properties. I’m not assuming that there are any mathematical objects, but I am assuming there is a wealth of properties including loads of modal properties and haecceities. I’m also assuming the use of full second order logic, which we can interpret in terms of plural quantification over pairs, where pairs are constructed from 0-ary properties (e.g. <x,y> = the proposition that x is taller than y.)]

Ok, all that was me setting things up the way I like to think about it. The real question I’m concerned with is: what is the set role?

Several obvious candidates come to mind. Perhaps the most natural is that it satisfies the axiom of second order set theory F(R) = ZFC(R), i.e. R satisfies second order replacement and a couple of other constraints. One nice thing about this on the supervaluational approach, if you assume there are enough things, is that you can retrieve a version of indefinite extensibility: however long the ordinals stretch there will be a precisification on which the ordinals stretch further. In general this depends on F – depending on F there may be a maximal precisification. Whether there is a maximal precisification, when F(R)=ZFC(R), depends on how many objects there are to begin with (e.g. indefinite extensibility holds if the number of things is an accessible limit of inaccessibles.)

The problem with this view is that if the number of things is at least the second inaccessible it will be indeterminate whether the number of sets is the first inaccessible, since there will be at least two precisifications. However, it shouldn’t be indeterminate whether the number of sets is the first inaccessible, it should be superfalse – the set theoretic hierarchy is much bigger than that! Perhaps we can tag some large cardinal property onto the end of F. For example, F(R) = “ZFC(R) & Ramsey(R)”, that is, an admissible precisification of membership is one that satisfies ZFC + there is a Ramsey cardinal/there is a supercompact cardinal/whatever… But this seems just as unsatisfactory as before – why does any one LC property in particular encode the practice of set theorists? What is more, for obvious reasons there are only countably many large cardinal properties we can define is second order logic, which gives rise to the following complaints: (a) we might expect the size of the set theoretic universe to be ineffable – i.e. that it’s cardinality is not definable by any second order formula and (b) if sethood is determined by the linguistic practices of mathematicians, presumably it must meet some constraints such as definability in some finite language. Sethood must be a concept graspable by beings of finite epistemic means.

So here is the view I’m toying with: the sets must be maximal in the domain. The height of the set theoretic universe is not fixed by some static large cardinal property. Rather it inflates to be as big as possible with respect to the domain. This leads to some rather nice consequences, which I’ll come to in a second. But first let’s work out what it means to be maximal. Let R \leq S be the second order formula that says that R is isomorphic to an initial segment of S as a model of second order ZFC. Then just define

  • F(R) := ZFC(R) \wedge \forall S(R \leq S \rightarrow S \leq R).

Here are the nice things. Firstly, this is simple definable property. It also captures the intuition that the sets are ‘as big as they possibly could be’. But what is particularly interesting is that the height of the hierarchy is not some fixed cardinality – it varies depending on the size of the domain you start with. In particular, the height of the hierarchy varies from world to world. In a world where there are the first inaccessible number of things, the sets only goes up as high as the first inaccessible, but at worlds where there are more, the sets go higher. Add to this the following modal principle

  • Necessarily, however many things there are, there’s possibly more.

and it seems like we can defend a version of indefinite extensibility. That the set theoretic hierarchy could always be extended higher, can be interpreted literally as metaphysical possibility.

Two things to iron out. Firstly note that it follows from some results due to Zermelo that any two maximal models are isomorphic. Thus there is at most one maximal model of ZFC up to isomorphism, so no set theoretic statements will come out indeterminate. Secondly, we need to know if there will always be a maximal model. Obviously, if there aren’t enough objects (less than the first inaccessible) there won’t be a maximal model, as there won’t be any models. However, I’m assuming there are a lot of objects. Certainly 2^{2^{\aleph_0}} from just the regions of spacetime alone (which, by a forcing argument, is consistently enough objects for a model), but I’m also assuming there are lots of properties hanging about too.

More worryingly, however, there can fail to be a maximal model even when there are lots of objects. This was a possibility I, foolishly, hadn’t considered until I checked it. Let \kappa_\omega be the omega’th inaccessible. Obviously \kappa_\omega is not itself inaccessible because it’s not regular, and for every inaccessible less than it there is a larger one, thus for every model of ZFC there is a bigger one, and thus no maximal one.

So that’s a bit of a downer. But nonetheless, even if the size of the actual world is of an unfortunate cardinality, we can regain all the set theory by going to the modal language, where we have indefinite extensibility.