Posts Tagged ‘Model theory’


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.)