Exercise 5.4 - Answers

1	(i)	Correct. (If everything is F and everything is G, everything must be both.)
	(ii)	Correct. (If everything is both F and G, everything must be F, and everything must be G.)
	(iii)	Correct.
	(iv)	Incorrect. The following is a counterexample: Domain: Positive integers. Fx: x is odd Gx: x is even
	(v)	Incorrect. The following is a counterexample (I expect) Domain: Human beings Fx: x is female Gx: x is male
	(vi)	Correct.
	(vii)	Incorrect. The empty domain provides a counterexample – in fact, the only one.
	(viii)	Correct. (The empty domain does not provide a counterexample because we are not allowed empty names in an interpretation: names must have bearers.)
	(ix)	Incorrect. Not only does the empty domain provide a counterexample, so does any interpretation of Fx which makes Fx true of nothing. For instance: Domain: Birds Fx: x can understand predicate logic Gx: x has a beak.
	(x)	Incorrect. The empty domain does not provide an example, because we are not allowed empty names. But an interpretation which make Fxa true of nothing will do. For instance: Domain: the natural numbers a: 0 Fxy: x<y Gxy: anything you like!
	(xi)	Correct. Given that something is F, it cannot be both that everything F is G (i.e. that there is nothing which is F but not G) and that nothing F is G.
	(xii)	Incorrect. ""x$y[FyÙRxy]" says that in the case of each thing there is something which is F to which it bears R – but leaves it open whether this is the same thing in each case. "$y"x[FyÙRxy]", on the other hand, says there is a thing which is F and to which everything bears R. A counterexample would be: Domain: Natural numbers Fx: x is a number. Rxy: x=y Or: Domain: {Queen Elizabeth, Prince Philip} Fx: x is human Rxy: x is married to y.
	(xiii)	Correct. Given that there is something, or $xFx would not be true, if "x$y[FxÙGy] is true, everything must be F and something must be G. But in that case $y"x[FxÙGy] will be true too.
	(xiv)	Incorrect. Domain: Humans Fx: x is female. P: anything false. (This will make ["xFx®P] true, since "xFx is false. But "x[Fx®P] is false. (Consider the Queen.)
	(xv)	Correct. One way to see this is to notice that ["xFx®P] is equivalent to [¬"xFxÚP], which is equivalent to [$x¬FxÚP], which, together with $xFx (which implies that the domain can't be empty) entails $x[¬FxÚP], which is equivalent to $x[Fx®P]. Another way would be to notice that ["xFx®P] is equivalent to ¬["xFxÙ¬P] and to argue from there.
	(xvi)	Correct. [$xFx®P] is equivalent to ¬[$xFxÙ¬P], which is equivalent to ¬$x[FxÙ¬P], which is equivalent to "x¬[FxÙ¬P], which is equivalent to "x[Fx®P].
	(xvii)	Correct. "x[P®Fx] is equivalent to "x[¬PÚFx], which is equivalent to [¬PÚ"xFx], which is equivalent to [P®"xFx].
2	(i)	The conclusion says that everything F is G. The premise will be true if not everything is F. It will also be true if something is G. So all we need to do is to find an interpretation according to which not everything is F (or one in which something is G), and not everything that is F is G. We could think of a real life interpretation with the appropriate features. But another way of proceeding is to tell a story which has the appropriate characteristics. So suppose we have room containing just three living things: a dog, a man and a woman. Our interpretation is: Domain: living things in the room Fx: x is human Gx: x is a woman. That makes the premises true (because not everything in the domain is human); and it makes the conclusion false, because it is not true that all the humans are women. (As it happen this interpretation also makes it true that something is G.)
	(ii)	It sometimes helps to do a little relettering of variables, so as to bring out the key features. If we reletter the conclusion we get the equivalent formula [$xFx®$y"xGyx]. Now we have done that, it looks as if the key to finding a counterexample lies in the fact that in the premise the $y comes after the "x, but in the conclusion they are the other way round. So maybe we can exploit the same sort of counterexample as would do for:             "x$yGyx |= $y"xGyx. For that we could use: Domain: natural numbers Gxy: x>y All we need is to find an interpretation for Fx, which will make the premise true and will also make $xFx true. Let us add: Fx: x is a number.
	(iii)	It often helps when one is looking for a counterexample to replace some or all the formulae by equivalent formulae. Here it looks as if it may help to replace the ®s with something equivalent using Ús. Remember that [j®y] is equivalent to [¬jÚy]. So the premise is equivalent to "x[[¬FxÚGx]Ú[¬¬FxÚHx]]. But then we notice that this is bound to be true, because everything is bound to be ¬F or ¬¬F, so to speak. So all we need to do is to find an interpretation which makes the conclusion false and which assigns some meaning to Fx, and we are there. (Left to you.)
	(iv)	A strategy which often works is to try to think of whether we can make the premises true and the conclusion false by taking a very small domain. (It is worth thinking of the empty domain first – but that won't do for this sequent, because it will make the conclusion true.) It is fairly obvious that it won't do to take a domain with just one thing either. (Suppose we do. Call the thing "a". Then the conclusion amounts to saying that Faaa . But that is what both the premises say too. So if they are true, the conclusion will be.) Let us try a domain with just two things in it, which we will call "a" and "b". To make the second premise true, let us say that Faaa and Faba. We want the conclusion to be false. So let us say that it is not true that Fbab nor that Fbbb. So far so good. Now can we make the other premise true? Well it tells us that whatever x and y are $zFxyz. So we need to make $zFbaz true without making Fbab true after all. Let us say, then, that Fbaa. And we need to make $zFbbz true without making Fbbb true. Let us say that Fbba. And now we need to deal with the other values of x and y in $zFxyz, and we are there. But we already got Faaa and Faba. So all is well. Now, at this stage we haven't yet got an interpretation, but we all we need to do is (i) to think of a domain with two things, (ii) to think of something for Fxyz to mean, and (iii) to tell a (consistent) story which makes Fxyz true just when we want it to be. Here is an example: Domain: Mary, John Fxyz: x and z like y. Let's think of the a we spoke of as being Mary, and the b as being John. Then the story is that Mary (and Mary) likes Mary, as does John (and John) and (so) John and Mary like Mary and so do Mary and John. Neither, however, likes John. Or we could take a more mathematical example: Domain: {1, 2} Fxyz: <x,y,z> Î {<1,1,1>, <1,2,1>, <2,1,1>, <2,2,1>} ("<1,2,1>", e.g., means "the ordered triple consisting of 1, 2 and 1, in that order".)
	(v)	We want the conclusion to be false – so we don't want everything to be G. We want the premises to be true. Suppose we had an interpretation according to which nothing was G. That would be perfect! Remember that "x[Gx®Hx] is true if nothing is G. Why? Well, because [P®Q] is true whenever P is false. Or, if you prefer, because "x[Gx®Hx] is equivalent to "x[¬GxÚHx]. So, if nothing is G, the second premise will be true. So all we need to do is to find an interpretation which makes it true that nothing is G, and also makes the first premise true – easy, because what we choose for Fxy won't affect the truth of the second premise or the falsity of the conclusion. What if we hadn't noticed that it would do to make nothing G? Well, we could take a small domain with just two things, a and b, in it, and say that a is G but b isn't. Now, we have to make the second premise true. So [Gx®"y[Fyx«Gy]] has to be true of both a and b. Easy, in the case of b: the fact that it is not G gives us want we want. But what about a? It has to be true that [Ga®"y[Fya«Gy]] . Since Ga is true, this means that "y[Fya«Gy]. So we must have both [Faa«Ga] and [Fba«Gb]. To avoid making Gb true we want Fba to be false. And because Ga is true, Faa must be. But we still have to make the first premise true. We have a choice between "y[FayÙFya] and "y[FbyÙFyb]. The first won't do, because, although it will make Faa true, which we want, it will make Fba true too, which we don't want; and the second won't do because it also will make Fba true (and won't make Faa true). Try adding a third thing? Try it, and see. Actually it won't help. There is no counterexample which makes G true of something. (Try adding $xGx to the premises, and proving the corresponding syntactic sequent.)
	(vi)	Try a small domain. We can't have just one thing in it, or we will make the conclusion true, if we make the first premise true. So let us try two things, a and b. And let us try to make Raa false, so that the conclusion will be false. If you look at the third premise you will see that we need to avoid letting Rba be true, because then we shall have [[RbaÙRba]®Raa], which will make Raa true. But we need to make the first premise true. We could try Rab, or Rbb. Let us go for Rbb, which conveniently makes the other premises true without our having to add anything else. All that remains is to construct an interpretation with the appropriate features. Here is an example. Domain: {Mary, John} Fxy: x likes y The story is that John likes himself (but not Mary), and Mary likes no one at all.
	(vii)	The empty domain will do, because all the premises begin with """, and so are true in the empty domain, whereas the conclusion begins with "$", and so is false. (It is always worth thinking of the empty domain, because it sometimes provides an easy answer, and sometimes, indeed, the only answer. And, as it happens, this sequent has no counterexample in any other domain.)
	(viii)	Here some initial manipulation seems as if it may help. Remember that ¬"xj is equivalent to $x¬j, and that  ¬[j®y] is equivalent to [jÙ¬y]. So the first premise is equivalent to "x"y[Fxy®$z[GzÙ¬Hzy]]. But the conclusion is equivalent to "x"y[[Fxy®$z[GzÙ¬Hzy]]Ù[$z[GzÙ¬Hzy]®Fxy]], which is equivalent to ["x"y[Fxy®$z[GzÙ¬Hzy]]Ù"x"y[$z[GzÙ¬Hzy]®Fxy]], So if we make the first premise true, we will make the first part of the conclusion true. So we had better concentrate on trying to make "x"y[$z[GzÙ¬Hzy]®Fxy] false. Let's try a domain with just one thing, a, in it. Then we need Faa to be false and $z[GzÙ¬Hza] true. So we need [GaÙ¬Haa] – i.e Ga true and Haa false. We also want the second premise to be true. It is easier to see what it amounts to if we replace it by the equivalent "x"y$z[HzxÚFyx]. But if there is just one thing, a, that means that [HaaÚFaa] is true, which it can't be, because we've already got Faa false and Haa false. Let's add another thing, b, and try to keep [GaÙ¬Haa] true, so as to keep the conclusion false. We want "x"y$z[HzxÚFyx] to be true, and in particular that means that $z[HzaÚFaa] must be true. So since Faa needs to be false and Haa needs to be false, we had better have Hba true. Now the easiest way to make sure that the first premise true is to have Fxy true of nothing at all. In which case, to preserve the truth of the second premise, we need to have Hbb or Hab – it doesn't matter which. Everything else can be false. So our recipe for a counterexample is: Ga, Hba, Hab true; everything else false. The following will do.   Domain: {Mary, John} Gx: x is female Hxy: x is the brother or sister of y. Fxy: x is the father of y   The story is that Mary and John are brother and sister, and Mary is female.

Close Window