Thursday, May 18, 2006

One little sign error

It's funny how one little sign error can make the difference between a satellite fall into orbit or back onto the earth, between a finely balanced solution and an explosive mess, or in this case, between a brilliant formal answer to a troublesome paradox, and a stupidly evident and useless answer.

The liar paradox is simply "This sentence is false" so that if it is true, it is false and thus not true, and if it is false, then it is not the case that it is false so it is true and not false. Either way, it's a paradox.

I came across this earlier today, and wondered if it was solvable in predicate logic. Using a rather idiosyncratic (but efficient) method which is (I think) used by the PROLOG interpreter, internally, I got the following proof:

Click here to expand formula.

Tx: x is true
Fx: x is false
{x} is a class comprising one individual proposition a: This sentence is false.
Logic states P1 ≡ ∀x [ Fx → ~Tx ]
So x entails P2 ≡ ∀x [ Tx → Fx ]
C is the conclusion of the sentence "This sentence is false" in conjunction with the entailed complex propositions P1 and P2. I'm going to cut short and use the resolution method I learnt with Prof Denis Vernant because I'm more comfortable with it, so the following may seem a little idiosyncratic, but hopefully not too unclear.

∀x [ (Fx & (Fx → ~Tx) & (Tx → Fx)) → C ]
x is a one member class, so because of the ∀ quantifier I can substitute x for a (see above).

(Fa & (Fa → ~Ta) & (Ta → Fa)) → C (1)

Let's make the following assumption. The conclusion C is that the truth status of the proposition a is defined. In other words, Ta v Fa.

Now I apply resolution method to this statement. Basically I negate the whole statement, reduce it to conjunctions and disjunctions, and resolve along the following lines: p & (q v ~p) gives us p & q.
So ~{ (Fa & (Fa → ~Ta) & (Ta → Fa)) → (Ta v Fa) }
Fa & (Fa → ~Ta) & (Ta → Fa) & ~(Ta v Fa)
Fa & (~Fa v ~Ta) & (~Ta v Fa) & ~Ta & ~Fa

We cancel the disjunctions out and obtain Fa & ~Ta & ~Fa which is a contradiction, which means with C ≡ (Ta v Fa) we obtain a logically non-valid expression.

Can we thus conclude C ≡ ~(Ta v Fa)? We can put this to the test:
The negation of (1) with this new C gives
~{ (Fa & (Fa → ~Ta) & (Ta → Fa)) → ~(Ta v Fa) }
which is
Fa & (Fa → ~Ta) & (Ta → Fa) & (Ta v Fa)
which is
Fa & (~Fa v ~Ta) & (~Ta v Fa) & (Ta v Fa)
Which simplifies to
Fa & ~Ta which is not a contradiction (and is not a conclusion either, just to dispel possible confusion) so that (1) with C ≡ ~(Ta v Fa) is a logically valid statement.

Thus, if I haven't made a mistake, and am not making any unreasonable assumption, the sentence "This sentence is false" is compatible with the conclusion "It is not the case that this sentence is true or false", or basically "It is nor true, nor false".

Now as you can imagine, I was fairly excited. If you don't understand the above, I basically proved it logically (or did I...). So thus, very pleased with my discovery, I sent a copy of this proof to my lecturer.

Twenty minutes later, I re-read it, and the reality check came in the mail (after all, a bit silly to assume that such a straightforward proof had been missed by generations and generations of talented logicians). I had in fact gotten the signs wrong -not in the application- but in the derivation of the conclusion, so that in fact the first case being a contradiction actually confirms the logical validity of the statement (since its negation is a contradiction), while the second is inconsistent. Thus rather than solving the problem, I've just made a pretty evident confirmation of its existence. Do note however that the second case raises an interesting point: does this logical state of non-validity support the definiteness of a truth value for the proposition being studied? I doubt it, but it's something to think about, if that tickles your fancy.

Moral of the story: live cocky, breathe confident, but by all means... check your signs.

No comments: