Sunday, 30 May 2010

Counterexample

The starting point in evaluating an argument for validity is the definition of a valid argument itself: an argument is valid if and only if it is impossible for the premises to be true while the conclusion is false.

Like many other definitions in logic and mathematics, the definition of a valid argument is formulated in such a way as to exclude all other options – options where, for example, both the premises and the conclusion are true but the argument is invalid nevertheless.

An effective way to show that an argument is invalid is simply to find a counterexample – a situation where we can show that even though the premises are true the conclusion cannot be guaranteed to be so. The conclusion is simply false.

A counterexample serves as a knock-down blow. It would follow that we would want to use it whenever an opportunity presents itself, to get the upper hand over our opponent. That depends. A counterexample can reduce conversation to the level of banality or sophistry. Of course, we can blame the opponent for setting up the situation in the first place, but this rarely leads to constructive answers.

Arguing by counterexample comes naturally, even though counterexamples themselves often don’t. That’s another reason not to abuse the technique. Since I can’t find a counterexample every time I would like to, I want to be cautious lest I should walk into a trap myself.

I had this in mind when I followed a debate last week between an Anglican minister, an agnostic and an atheist on Heresy, a BBC comedy show which, being a comedy and of that title too boot, often crosses freely between silliness and seriousness.

The minister (actually, a born-again Christian) related how finding God led him to enlightenment and knowledge. The agnostic countered that Christianity, and religion generally, is responsible for promoting ignorance and superstition. The Middle Ages were mentioned. To this, the minister replied, with a well-practiced air of benevolence and censoriousness typical of his profession, with a question: and who gave us schools and universities?

A pregnant pause had begun to insinuate itself but, fortunately, its force was dissipated amidst the hurly-burly of the debate and general laughter.

What the agnostic didn’t say but could have said is that England gave football to the rest of the world. Look at England now! It doesn’t follow that you should have a monopoly on something just because you started it or that you do it best.

Raising the level of the debate, one might have said: civilization originated in Mesopotamia. Yes, but that particular vine has withered and degenerated, not least because of the hold religion has on the people of this area.

Medicine, too, traces its roots to shamans, witch doctors, and priests, as do many other things. In a primitive society caught between fear and wonder the minds are susceptible of manipulation and all too eager to hand over power and resources to imposters.

So much for counterexamples. The better route to follow would have been to focus on the absurdities taught by the medieval Schoolmen: Abelard, Scotus, Aquinas and company, and conclude, with relief, that we don’t have them to thank for key hole surgery, the aircraft and the telephone. But that would have been nowhere near as effective as, say, the football counterexample.

Thursday, 27 May 2010

Symbolic Logic, Irving M. Copi, Prentice Hall, Fifth Edition, 1979, p. 150, problem 7

The argument is put as follows:
Adams and Brown were the only men at the banquet who drank. All the men at the banquet who brought liquor drank. Adams did not bring any liquor. If any man at the banquet drank, then some man at the banquet who drank must have brought liquor. All who drank became ill. Therefore, the man at the banquet who brought liquor became ill.
(a: Adams, b: Brown, Mx: was a man at the banquet, Dx: x drank, Lx: x brought liquor, Ix: x became ill). Symbolize and prove the validity.
  1. (∃x){Mx • Dx • (y)[(My • Dy) ⊃ y = x] • (x = a ∨x = b)}
  2. (x)[(Mx • Lx) ⊃Dx]
  3. ¬ La
  4. (∃x)(Mx • Dx) ⊃(∃x)(Mx • Dx • Lx)
  5. (x)(Dx ⊃Ix)
  6. ∴ (∃x){Mx • Lx • (y)[(My • Ly) ⊃y = x] • Ix}
  7. Mm • Dm • (y)[(My • Dy) ⊃ y = m] • (m = a ∨m = b) / 1EI x/m
  8. Mm • Dm / 7Simp.
  9. (∃x)(Mx • Dx) / 8EG
  10. (∃x)(Mx • Dx • Lx) / 9,4MP
  11. Mr • Dr • Lr / 10EI x/r
  12. * My • Ly / ACP
  13. * (y)[(My • Dy) ⊃ y = m] / 7Simp.
  14. * (My • Dy) ⊃ y = m / 13UI y/y
  15. * (My • Ly) ⊃Dy / 2UI y/y
  16. * Dy /12,15MP
  17. * My /12Simp.
  18. * My • Dy /16,17Conj.
  19. * y = m /18,14MP
  20. (My • Ly) ⊃y = m / 12-19CP
  21. (y)[(My • Ly) ⊃y = m] / 20UG
  22. Dm ⊃Im / 5UI x/m
  23. Dm / 8Simp.
  24. Im / 22,23MP
  25. (y)[(My • Dy) ⊃ y = m] / 7Simp.
  26. (Mr • Dr) ⊃ r = m / 25UI y/r
  27. Mr • Dr / 11Simp.
  28. r = m / 27,26MP
  29. Lr / 11Simp.
  30. Lm / 28,29Id
  31. Mm / 8Simp.
  32. Mm • Lm • (y)[(My • Ly) ⊃y = m] • Im / 31,30,25,24Conj.
  33. (∃x){Mx • Lx • (y)[(My • Ly) ⊃y = x] • Ix} / 32EG

Saturday, 22 May 2010

The ash cloud and the oil spill

The ash cloud and the oil spill have been filling the air in my house for the last few weeks, enough to lodge themselves in the recesses of my mind from where they harry Fortress Logic. The oil spill – I don’t question so much, but the ash cloud is another matter altogether. Why is it ‘the’ ash cloud?

Granted, the frequent references to it, warnings, jokes, doom scenarios peddled by the media and my own inability to get English language newspapers in Warsaw when the planes are grounded in the UK due to ‘the’ ash cloud have thrust something so incredibly distant and rarified to the forefront of my consciousness. It has become to me a presence somewhat like Russell’s teapot – I think of it as being out there somewhere, visible to those who strongly believe in it. And if everybody refers to it as ‘the’ ash cloud, I take my cue from them and do likewise.

But it can’t be ‘the’ ash cloud, can it? In terms of Aristotelian categories, it does not resemble the 2004 tsunami, the Haiti earthquake of earlier this year or even the oil spill in the Gulf of Mexico – the closest analogy. It is not a uniform cloud and, in my understanding at least, it is not connected to the source by a thin thread of ash. The volcano is like a smoker – it takes a puff on its stack, then broods, then takes another puff, and broods again, and so on.

The point is ‘the’ ash cloud is something in our minds. The real ash cloud is many clouds, just like regular clouds in the sky, whose substance rather than whose properties alone undergoes constant change. It is not the same cloud that threatened us four weeks ago that is threatening us today, is it? They soar, they drift around Europe and then they peter out, don’t they? There are clear days in between. Yet when I hear about ‘the’ ash cloud on the radio, it is like a beach ball in a fish tank, bobbing on the ripples of aerated water, scattering aquatic life into the distant corners of the tank.

The Chernobyl cloud had a better claim to the definite article ‘the’, it seems to me. There is little ‘definite’ about the ash cloud. Meteorologists give names to powerful natural phenomena, like Hurricane Katrina, or assign numbers, like the UK met office to weather fronts. Or that’s what I think they are, although I’d rather not know because knowledge would spoil the joy of listening to the shipping forecast. At any rate, we might hear something like ‘Low Viking 922 moving steadily east and losing its identity by same time.’ ‘Identity’ is the key word – if these things lose their identity at some point, they have enjoyed an identity for a while at least. The ash cloud is like Phoenix out of ashes. It loses its identity and then – we are led to believe by the ‘the’ – regains it.

What would it take for ‘the’ ash cloud to lose its identity if multiple dissipation is not enough? Perhaps Mount Etna erupting? In a universe consisting of more than one object of the same kind, identity is wiped out. The definite article truly calls for a definition, thus ‘The ash cloud over Spain has spread out,’ is logically ‘there is an ash cloud called x, it is over Spain, and if any ash cloud is identical to x, then it has spread out.’

Friday, 21 May 2010

Understanding Symbolic Logic, Virginia Klenk, Prentice Hall, 2008, Fifth edition, Unit 20, Ex.3e, p.381

Another theorem to prove. The hardest part is to realize that the same expression can be instantiated twice, each time to a different variable, the idea being to set up two identities under the second assumption below and then use the transitive property of identity to derive x = y. It would have been possible to decompose line 6 into a conjunction of two disjunctions and then simplify via disjunctive syllogism but I am too lazy to do that so I have used exportation instead.
Theorem: {(∃x)Fx • (x)(y)[(Fx • Fy) ⊃x = y]} ≡ (∃x)[Fx • (y)(Fy ⊃x = y)]
  1. * (∃x)Fx • (x)(y)[(Fx • Fy) ⊃x = y] / ACP
  2. * (∃x)Fx / 1Simp.
  3. * Fm / 2EI x/m
  4. * (x)(y)[(Fx • Fy) ⊃x = y] / 1Simp.
  5. * (y)[(Fm • Fy) ⊃m = y] / 4UI x/m
  6. * (Fm • Fy) ⊃m = y / 5UI y/y
  7. * Fm ⊃(Fy ⊃m = y) / 6Exp.
  8. * Fy ⊃m = y / 3,7MP
  9. * (y)(Fy ⊃m = y) / 8UG
  10. * Fm • (y)(Fy ⊃m = y) / 3,9Conj.
  11. * (∃x)[Fx • (y)(Fy ⊃x = y)] / 10EG
  12. {(∃x)Fx • (x)(y)[(Fx • Fy) ⊃x = y]} ⊃ (∃x)[Fx • (y)(Fy ⊃x = y)]
  13. * (∃x)[Fx • (y)(Fy ⊃x = y)] / ACP
  14. * Fa • (y)(Fy ⊃a = y) / 13EI
  15. * (y)(Fy ⊃a = y) / 14Simp.
  16. * * Fx • Fy / ACP
  17. * * Fy ⊃a = y / 15UI y/y
  18. * * Fy / 16Simp.
  19. * * a = y / 18,17MP
  20. * * Fx ⊃a = x / 15UI y/x
  21. * * Fx / 16Simp.
  22. * * a = x / 21,20MP
  23. * * x = a / 22Id
  24. * * x = y / 19,23Id
  25. * (Fx • Fy) ⊃x = y / 16-24CP
  26. * (y)[(Fx • Fy) ⊃x = y] / 25UG
  27. * (x)(y)[(Fx • Fy) ⊃x = y] / 26UG
  28. * Fa / 14Simp.
  29. * Fa • (x)(y)[(Fx • Fy) ⊃x = y] / 28,27Conj.
  30. * (∃x){Fx • (x)(y)[(Fx • Fy) ⊃x = y]} / 29EG
  31. (∃x)[Fx • (y)(Fy ⊃x = y)] ⊃(∃x){Fx • (x)(y)[(Fx • Fy) ⊃x = y]} / 13-30CP
  32. {{(∃x)Fx • (x)(y)[(Fx • Fy) ⊃x = y]} ⊃ (∃x)[Fx • (y)(Fy ⊃x = y)]} • {(∃x)[Fx • (y)(Fy ⊃x = y)] ⊃(∃x){Fx • (x)(y)[(Fx • Fy) ⊃x = y]}} / 12,31Conj.
  33. {(∃x)Fx • (x)(y)[(Fx • Fy) ⊃x = y]} ≡ (∃x)[Fx • (y)(Fy ⊃x = y)] / 32BE

Sunday, 16 May 2010

When 'some' means 'any' and when it doesn't

Lack of awareness of the difference between ‘some’ and ‘any’ as opposed to acute such awareness is what makes some people call themselves ‘humanists’, in the sense of ‘not scientifically-minded’. They shy away from anything connected with mathematics. It is a safe bet that the other lot, those who say they’ve never been good at languages, are not mathematicians either. The distinction between ‘some’ and ‘any’ is the bedrock for logical and mathematical analysis.

In the teaching of English, the problem is explained in terms of positive declarative sentences for ‘some’ and interrogative or negative sentences for ‘any’. That is wholly inadequate, although it may serve the purpose of marking the correct answers on a test paper. Consider the sentence:

(1) If someone is in, the lights are on.

Does this sentence say that there is a person, whoever they may be, such that if that person is in, the lights are on, or does it rather say that if a person, any person, happens to be in, then the lights are on? Clearly the latter. The former interpretation is possible but it makes a very weak sentence, or else it is extremely unlikely for anyone to have uttered such a sentence. It follows then that (1) says in fact that if anyone is in, the lights are on.

Another way of putting it is that if we allowed questions such as, ‘Have you eaten something?’, then we would probably mean, ‘Have you eaten anything?’ anyway. The difference is this: ‘Is there something that you have eaten? as opposed to ‘Is there anything that you have eaten?’

The word ‘some’ means ‘any’ also in a sentence like this:

(2) Someone who doesn’t tell the whole truth is a liar.

Again, I could mean to say that there exists a person who doesn’t tell the whole truth and that person is a liar, but I am more likely to extend this classification to anyone who doesn’t tell the whole truth.

Quantification is key in testing whether a mathematical formula is true or not. (x – 1)(x + 1) > 0 is true for some x, but not for any x we happen to pick in the set of real numbers. Specifically, the formula is false for an x that is greater than – 1 and less than 1.

Negations bring into sharp relief the difference between ‘some’ and ‘any’.

(3) I don’t know something.
(4) I don’t know anything.

Clearly, ‘something’ in (3) must not be interpreted in the same way as ‘someone’ in (1). In (1) the indefinite pronoun ‘someone’ has wide scope, meaning it captures anyone or everyone who happens to be in when the lights are on. In (3) on the other hand, ‘something’ takes narrow scope: it includes at least one thing, but excludes everything else besides.

What is (1) equivalent to? Answer:

(5) I don’t know everything.

Sentence (5) is the reciprocal of (3). Since the universal set U is the disjoint union of A, or the set representing ‘some’ members, and Ac, its complement, that is the set of all those members of U that are not members of A, in both sentences we are focusing on Ac. What changes is the perspective: in (3) we are indicating how much we are short of the full set, while in (5) we are saying what it is that we are a certain amount short of.

The word ‘any’, on the other hand, takes the widest scope possible, in (4) and in negations in general.

Thursday, 13 May 2010

Understanding Symbolic Logic, Virginia Klenk, 5th edition, Pearson Prentice Hall, Unit 20, Ex. 3(d)

The theorem to prove this time requires little beyond the application of the transitive property of identity.

Theorem: (x)(y)(z)(w)[(x = y • y = z • z = w) ⊃x = w]
  1. * x = y / ACP
  2. * * y = z / ACP
  3. * * * z = w / ACP
  4. * * * x = z / 1,2HS
  5. * * * x = w / 4,3HS
  6. * * z = w ⊃x = w / 3-5CP
  7. * y = z ⊃(z = w ⊃x = w) / 2-6CP
  8. x = y ⊃[y = z ⊃(z = w ⊃x = w)] / 1-7CP
  9. (x = y • y = z • z = w) ⊃x = w / 8Exp.
  10. (w)[(x = y • y = z • z = w) ⊃x = w] / 9UG
  11. (z)(w)[(x = y • y = z • z = w) ⊃x = w] / 10UG
  12. (y)(z)(w)[(x = y • y = z • z = w) ⊃x = w] / 11UG
  13. (x)(y)(z)(w)[(x = y • y = z • z = w) ⊃x = w] / 12UG

Saturday, 8 May 2010

Modality

Reasoning with may and could is no less a challenge to a student of logic than to a student of English, and both would rather banish the modality outside the sentence than wait for it to come up in a mid-position and then discover that the sentence does not say what they meant it to say.

For example, ‘Gordon may have apologized for the gaffe,’ will come out as: ‘Maybe Gordon has apologized for the gaffe,’ through the mouth of someone unsure about the force of ‘may’, or ‘It is possible that Gordon has apologized for the gaffe,’ for the purposes of deduction with modal logic.

The adverb ‘maybe’ at the beginning of a sentence may seem just the trick to avoid the uncertainty of ‘may’ inside it, but true to the theory that no exact synonyms exist in natural languages, the overall effect may be different. The sentence-initial ‘maybe’ may be begging a response from the listener, something the more matter-of-fact ‘may’ in a mid-position does not do.

Possibility can be expressed in terms of necessity, and modal logic has developed a guide, of sorts, to paraphrasing into non-modal language. In so far as the modal verb expresses possibility, the guide is reliable. Where other concepts (ability, permission, criticism, regret, etc) are thrown into the mix, this translation will not suffice.

It is necessary that P = It is not possible that not P
It is not necessary that P = It is possible that not P
It is possible that P = It is not necessary that not P
It is not possible that P = It is necessary that not P

Thus, ‘Gordon may have apologized for the gaffe,’ is ‘It is possible that he did,’ or ‘It is not necessary that he didn’t.’ And, ‘Gordon must have apologized for the gaffe,’ is ‘It is not possible that he didn’t,’ or ‘It is necessary that he did.’

For negations: ‘Gordon couldn’t have apologized for the gaffe’, comes out as ‘It is not possible that he did,’ or ‘It is necessary that he didn’t’, while ‘Gordon may not have apologized for the gaffe,’ is rendered as ‘It is possible that he didn’t,’ and ‘It is not necessary that he did.’

As can be seen, the position of the negation in our paraphrases changes the degree of possibility.
From the logical point of view, the implications of the particular statements are worked out somewhat differently. Thus, if we know that Gordon necessarily apologized for the gaffe, we can infer that he possibly apologized for the gaffe, but not the other way round. If we know that Gordon necessarily did not apologize for the gaffe, then he possibly did not do so, but not the other way round. The inference is always from more to less, or stronger to weaker.

Symbolic Logic, Dale Jacquette, Wadsworth, 2001, Chpt. 8, Ex. III, problem 12

Required: natural deduction proof for the following tautology. The number of steps could be cut down in my proof by simply instantiating the first assumption (line 2) by UI and applying DeMorgan's law straight away. Note that even though we have a free variable in our assumption on line 3, we are justified in applying UG on line 9 because we have discharged this assumption on line 6 (we are not applying UG within the scope of the innermost assumption).
  1. ├ (x)(Fx ⊃Gx) ⊃(x) ¬ (Fx • ¬ Gx)
  2. * (x)(Fx ⊃Gx) / ACP
  3. * * Fx / ACP
  4. * * Fx ⊃Gx / 2UI x/x
  5. * * Gx / 3,4MP
  6. * Fx ⊃Gx / 3-5CP
  7. * ¬ Fx ∨Gx / 6MI
  8. * ¬ (Fx • ¬ Gx) / 7DeM
  9. * (x) ¬ (Fx • ¬ Gx) / 8UG
  10. (x)(Fx ⊃Gx) ⊃(x) ¬ (Fx • ¬ Gx) / 2-9CP

Monday, 3 May 2010

Deduction, Daniel Bonevac, Blackwell Publishing, 2003, 8.3, Problem 14

As in earlier problems in this section (11, 12, 13), we show that the implication holds. The overall strategy is to show that the biconditional in the conclusion holds both ways, so we prove each implication separately and conjoin them on line 48. After making the first assumption on line 3 we might be tempted to carry on and assume Fa on line 4 in order to bring us faster to the conclusion. However, we have already introduced Fa on line 3 and repeating it would be a violation. Instead, it is better to assume the negation of (∃x)(Gx • Hx) and then show that we can obtain the negation of Fa. Since it is an implication, we swap round the sides by contraposition and arrive at the desired conclusion on line 20. Likewise, in the second set of assumptions further down, the conclusion has been negated - this time to obtain a contradiction.
  1. (∃x)(y)(y = x ≡ Gy)
  2. ∴ (∃x)[Gx • (Fa ⊃Hx)] ≡ [Fa ⊃(∃x)(Gx • Hx)]
  3. * (∃x)[Gx • (Fa ⊃Hx)] / ACP
  4. * * ¬ (∃x)(Gx • Hx) / ACP
  5. * * (x)(Gx ⊃¬ Hx) / 4QC
  6. * * Gr • (Fa ⊃Hr) / 3EI x/r
  7. * * (y)(y = m ≡ Gy) / 1EI x/m
  8. * * r = m ≡ Gr / 7UI y/r
  9. * * (r = m ⊃ Gr) • (Gr ⊃r = m) / 8BE
  10. * * Gr ⊃r = m / 9Simp.
  11. * * Gr / 6Simp.
  12. * * r = m / 11,10MP
  13. * * Gm ⊃¬ Hm / 5UI x/m
  14. * * Gm / 12,11Id
  15. * * ¬ Hm / 14,13MP
  16. * * ¬ Hr / 12,15Id
  17. * * Fa ⊃Hr / 6Simp.
  18. * * ¬ Fa / 16,17MT
  19. * ¬ (∃x)(Gx • Hx) ⊃¬ Fa / 4-18ACP
  20. * Fa ⊃(∃x)(Gx • Hx) / 19Contrap.
  21. (∃x)[Gx • (Fa ⊃Hx)] ⊃[Fa ⊃(∃x)(Gx • Hx)] / 3-20CP
  22. * Fa ⊃(∃x)(Gx • Hx) / ACP
  23. * * ¬ (∃x)[Gx • (Fa ⊃Hx)] / AIP
  24. * * (x)[Gx ⊃(Fa • ¬ Hx)] / 23QC
  25. * * (y)(y = m ≡ Gy) / 1EI x/m
  26. * * m = m ≡ Gm / 25UI y/m
  27. * * (m = m ⊃Gm) • (Gm ⊃m = m) / 26BE
  28. * * m = m ⊃Gm / 27Simp.
  29. * * m = m / Id
  30. * * Gm / 29,28MP
  31. * * Gm ⊃(Fa • ¬ Hm) / 24UI x/m
  32. * * Fa • ¬ Hm / 30,31MP
  33. * * Fa / 32Simp.
  34. * * (∃x)(Gx • Hx) / 22,33MP
  35. * * Gr • Hr / 34EI x/r
  36. * * r = m ≡ Gr / 25UI y/r
  37. * * (r = m ⊃Gr) • (Gr ⊃r = m) / 36BE
  38. * * Gr ⊃r = m / 37Simp.
  39. * * Gr / 35Simp.
  40. * * r = m / 38,39MP
  41. * * Hr / 35Simp.
  42. * * Hm / 40, 41Id
  43. * * ¬ Hm / 32Simp.
  44. * * Hm • ¬ Hm / 42,43Conj.
  45. * ¬ ¬ (∃x)[Gx • (Fa ⊃Hx)] / 23-44IP
  46. * (∃x)[Gx • (Fa ⊃Hx)] / 45DN
  47. [Fa ⊃(∃x)(Gx • Hx)] ⊃(∃x)[Gx • (Fa ⊃Hx)] / 23-46CP
  48. {(∃x)[Gx • (Fa ⊃Hx)] ⊃[Fa ⊃(∃x)(Gx • Hx)]} • {[Fa ⊃(∃x)(Gx • Hx)] ⊃(∃x)[Gx • (Fa ⊃Hx)]} / 21,47Conj.
  49. (∃x)[Gx • (Fa ⊃Hx)] ≡ [Fa ⊃(∃x)(Gx • Hx)] / 48BE