## Posts Tagged ‘Gödel’

April 23, 2009

I’ve been casually reading Field’s “Saving Truth from Paradox” for some time now. I think it’s a fantastic book, and I highly recommend it to anyone interested in the philosophy of logic, truth or vagueness.

I’ve just read Ch. 21 where he discusses a paradox presented in Restall 2006. The discussion was very enlightening for me, since I had often thought this paradox to be fatal to non-classical solutions to the liar. But although Fields discussion convinced me Restall’s argument wasn’t as watertight as I thought it was, I was still left a bit uneasy. (I think there is something wrong with Restall’s argument that Field doesn’t consider, but I’ll come to that.)

Before I continue, I should state the paradox. The problem is that if one has a strong negation in the language, $\neg$, one can generate a paradoxical liar sentence which says of itself that it’s strongly not true. Strong negation has the following properties which ensures that that last sentence is inconsistent:

1. $p, \neg p \models \bot$
2. If $\Gamma , p \models \bot$ then $\Gamma \models \neg p$

Roughly, the strong negation of p is the weakest proposition inconsistent with p – the first condition guarantees that it’s inconsistent with p, the second that it’s the weakest such proposition. It’s not too hard to see why having such a connective will cause havoc.

Restall’s insight (which was originally made to motivate a “strong” conditional, but it amounts to the same thing) was that one can get such a proposition by brute force: the weakest proposition inconsistent with p is equivalent to the disjunction of all propositions inconsistent with p. Thus, introducing infinitary disjunction into the language, we may just “define” $\neg p$ to be $\bigvee \{q \mid p \wedge q \models \bot \}$. Each disjunct is inconsistent with p so the whole disjunction must be inconsistent with p, giving us the first condition. If q is inconsistent with p, then q is one of the disjuncts in $\neg p$ so q entails $\neg p$, giving us (more or less) the second condition.

An initial problem Field points out is that this definition is horribly impredicative – $\neg p$ is inconsistent with p, so $\neg p$ must be one of it’s own disjuncts. Field complains that such non-well founded sentences give rise to paradoxes even without the truth predicate, for example, the sentence that is it’s own negation. (I personally don’t find these kinds of languages too bad, but maybe that’s best left for another post.) This problem is overcome since you can run a variant of the argument by only disjoining atomic formulae so long as you have a truth predicate.

The second point, Field’s supposed rebuttal of the argument, is that to specify a disjunction by a condition, F say, on the disjuncts, you must first show F isn’t vague or indeterminate, or else you’ll end up with sentences such that it is vague/indeterminate what their components are. Allowing such sentences means they can enter into vague/indeterminate relations of validity – for example, it is vague whether a sentence such that it is vague whether it has “snow is white” as a conjunct entails “snow is white”. But the property F, in this case, is the property of entailing a contradiction if conjoined with p. Thus to assess whether F is vague/indeterminate or not, we must ask if entailment can ever be vague. But to do this we must determine whether there are sentences in the language such that it is indeterminate what their components are. Since the language contains the disjunction of the F’s, this requires us to determine whether F is vague – so we have gone in a circle.

Clearly something weird is going on. That said, I don’t quite see how this observation refutes the argument. It’s perfectly consistent with what’s been said above that entailment for the expanded language with infinitary disjunction is precise, that there is a precise disjunction of the things inconsistent with p, and that Restall’s argument goes through unproblematically. It’s also consistent that there *are* vague cases of entailment – but that the two conditions for strong negation above determinately obtain (there are some subtle issues that must be decided here, e.g., is “p and q” determinately distinct from the sentence that has p as its first conjunct, but only has q as its second conjunct indeterminately.)

Even so, I think there are a couple of problems with Restall’s argument. The first is a minor problem. To define the relevant disjunction, we must talk about the property of “entailing a contradiction if conjoined with p”. But to do this we are treating “entails” like it was a connective in the language. However, one of Fields crucial insights is that “A entails B” is not an assertion of some kind of implication holding between A and B, but rather the conditional assertion of A on B. “entails” cannot be thought of like a connective. For one thing, connectives are embeddable, whereas it doesn’t make much sense to talk of embedded conditional assertions. Secondly, a point which I don’t think Field makes explicit, is that it is crucial that “entails” doesn’t work like an embeddable connective, otherwise one could run a form of Curry’s paradox using entailment instead of the conditional.

This not supposed to be a knockdown problem. After all, so what if you can’t *define* strong negation, there is, nonetheless, this disjunction whose disjuncts are just those propositions inconistent with p. We may not be able to define it or refer to it, but God knows which one it is all the same.

The real problem, I think, is the following. How are we construing $\neg p$? Is it a new connective in the language, stipulated to mean the same as “the disjunction of those things inconsistent with p”? If it is, how do we know it is a logical connective? (If $\neg$ weren’t logical neither (1) nor (2) would hold, since there would be no logical principles governing it.) Field objects to a similar argument from Wright, because “inconsistent with p” is not logical. Inconsistency is not logical: for a start it can only be had by sentences, so it is not topic neutral.

The way of construing $\neg p$ that makes it different from Wright’s argument, and allegedy problematic, is to construe $\neg p$ as schematic for a large disjunction. The symbol $\neg$ does not actually belong to the language at all – writing $\neg p$ is just a metalinguistic shorthand for a very long disjunction, a disjunction that will change, depending in each case, on p. Treating it as such guarantees that (1) and (2) hold, since when they are expanded out, are just truths about the logic of disjunction and don’t contain $\neg$ at all.

But treating $\neg p$ as schematic for a disjunction means it doesn’t behave like an ordinary connective. For one you can’t quantify into it’s scope. What sentence would $\exists x\neg Fx$ be schematic for? What we want it to mean is that there is some object, a, such that the disjunction of things inconsistent with Fa holds. But there’s no single sentence involved here.

Another crucial shortcoming is that it’s not clear that we can “put a dot” under $\neg$. That is, define a function which takes the Gödel number of p, to the Gödel number of the disjunction of things inconsistent with p. Firstly there might not be enough Gödel numbers to do this (since we have an uncountable language now!) But secondly, how do we know we can code “inconsistent with p” in arithmetic? Fields logic isn’t recursively axiomatizable (Welch, forthcoming) so it seems like we’re not going to be able to code “inconsistent with p” or the strong negation of p – and thus it seems we’re not going to be able to run the Gödel diagonalisation argument. (I was always asleep in Gödel class so maybe someone can check I’m not missing something here.)

So you can’t get a strongly negated liar sentence through Gödel diagonalisation, but what about indexical self reference? “This sentence is strongly not true” is schematic for a sentence not including “strongly not”, but with a large disjunction instead. However, which disjunction is it? We’re in the same pickle we were in when we tried to quantify into the scope of $\neg$. In both cases, the disjunction needed to vary depending on the value of the variable “x” or in this case, the indexical “this”.

I can’t say I’ve gotten to the bottom of this, but it’s no longer clear to me how problematic Restall’s argument is for the non classical logician.

## Cardinality and the intuitive notion of size

January 1, 2009

According to mathematicians two sets have the same size iff they can be put in one-one correspondence with one another. Call this Cantor’s principle:

• CP: X and Y have the same size iff there is a bijection $\sigma:X\rightarrow Y$

Replace ‘size’ by ‘cardinality’ in the above and it looks like we have a definition: an analytic truth. As it stands, however, CP seems to be a conceptual analysis – or at the very least an extensionally equivalent charaterisation. In what follows I shall call the pretheoretic notion ‘size’ and the technical notion ‘cardinality. CP thus states that two sets have the same size iff they have the same cardinality.

Taken as a conceptual analysis of sizes of sets, as we ordinarily understand it, people often object. For example, according to this definition the natural numbers are the same size as the even numbers, and the same size as the square numbers, and many more sets even sparser than these. This is an objection to the right to left direction of CP.

I’m not inclined to give these intuitions too much weight. In fact, I think the intuitive principles behind these judgements are inconsistent. Here are two principles that seem to be at work: (i) if X is a proper subset of Y then X is smaller than Y, (ii) if by uniformly shifting X you get Y, then X and Y have the same size. For example (i) is appealed to when it’s argued that the set of evens is smaller than the set of naturals. (ii) is appealed to when people argue that the evens and the odds have the same size. Furthermore, both principles are solid when we are dealing with finite sets. However (i) and (ii) are clearly inconsistent. If the evens and the odds have the same size, so do the odds and the evens\{2}. This is just an application of (ii), but intuitively, the evens\{2} stand in exactly the same relation to the odds, as the odds to the evens. By transitivity, the evens and the evens\{2} are the same size – but this contradicts (i) since one is a proper subset of the other.

In fact Gödel gave a very convincing argument for the right to left direction: (a) changing the properties of the elements of a set does not change its size, (b) two sets which are completely indistinguishable have the same size and (c) if $\sigma:X \rightarrow Y$ , each $x \in X$ can morph its properties so that x and $\sigma(x)$ are indistinguishable.  Thus, if $\sigma$ is a bijection, X can be transformed in such a way that it is indiscernable from Y, and must have the same size. (Kenny has a good discussion of this at Antimeta.)

The direction of CP I think there is a genuine challenge to is the left to right. And without it, we cannot prove there is more than one infinite size! (That is, if we said every infinite set had the same size, that would be consistent with the right to left direction of CP alone.)

What I want to do here is justify the left to right direction of CP. The basic idea is to do with logical indiscernability. If two sets have the same size, I claim, they should be logically indiscernable in the following sense: any logical property had by one, is had by the other. Characterising the logical properties as the permutation invariant ones, we can see that if two sets have the same cardinality, then they are logically indiscernable. Since we accept the inference from having the same cardinality to having the same size, this partially confirms our claim.

But what about the full claim? If two sets have the same size, how can they be distinguished logically? There must be some logically relevant feature of the set which is distinguishing them, but has nothing to do with the size. But what could that possibly be? Surely size tells us everything we can know about a set without looking at the particular characteristics of  its elements (i.e. its non-logical properties.) If there is any natural notion of size at all, it must surely involve logical indiscernability.

The interesting thing is that if we have the principle that sameness in size entails logical indiscernability we get CP in full. The logical properties over the first layer of sets of the urelemente are just those sets invariant under all permutations of the urelemente. Logical properties of these sets are just unions of collections sets of the same size. Thus logically indiscernable sets are just sets with the same cardinality!

Ignore sets for a moment. The usual setting for permutation invariance tests is on the quantifiers. A variant of the above argument can be given. This time we assume that size quantifiers are maximally specific logical quantifiers. There are two ways of spelling this out, both of which will do:

• For every logical quantifier, Q, $Sx\phi \models Qx\phi$ or $Sx\phi \models \neg Qx\phi$
• For every logical quantifier, Q, if $Qx\phi \models Sx\phi$ then $Qx\phi \equiv Sx\phi$

The justification is exactly the same as before: the size of the $\phi$‘s tells us everything we can possibly know about the $\phi$‘s without looking at the particular characteristics of the individuals $phi$‘s – without looking at their non-logical properties. Since the cardinality quantifiers have this property too, we can show that every size quantifier is logically equivalent to some cardinality quantifier and vice versa.

I take this to be a strong reason to think that cardinality is the only natural notion of size on sets. That said, there’s still the possibility that the ordinary notion of size is simply underdetermined when it comes to infinite sets. Perhaps our linguistic practices do not determine a unique extension for expressions like ‘X is the same size as Y’ for certain X and Y. One thing to note is that the indeterminacy view seems to be motivated by our wavering intuitions about sizes. But as we saw earlier, a lot of these intuitions turn out to be inconsistent, so there won’t even exist precisifications of ‘size’ corresponding to these intuitions. On the other hand, if we are to think of the size of a set as the most specific thing we can say about that set, without appealing to the particular properties of its members, then there is a reason to think this uniquely picks out the cardinality precisification.

## XKCD on Gödel…

August 27, 2008

They eventually resolved this self-reference, but Cantor's 'everything-in-the-fetish-book-twice' parties finally sunk the idea.