• 7 •
“Another fact,” said Griffin: “We have proved that a kestrel K cannot be fond of an identity bird I. This means that KI ≠ I. This fact can also be generalized: Prove that there cannot be any bird x such that Kx = I.”
· · ·
“Well,” said Griffin, “I will soon tell you an extremely important fact about kestrels. But first, how about a nice cup of tea?”
“Capital idea!” said Craig.
SOME NONEGOCENTRIC BIRDS
While Craig and Griffin are taking time out for tea, let me tell you about some other nonegocentric birds. We shall assume that the forest contains the birds K and I and that K ≠ I. On this basis, we have already proved that the kestrel K cannot be egocentric; recall that by an egocentric bird is meant a bird x such that xx = x. Many other birds can also be proved nonegocentric. We shall look at a few.
• 8 •
Prove that no bird can be both a kestrel and a thrush.
• 9 •
Now prove that no thrush T can be egocentric.
• 10 •
Prove that if R is a robin, then RII ≠ I. It can also be proved, by the way, that RI ≠ I and that R ≠ I. The reader might try these as exercises.
• 11 •
Now prove that no robin R can be egocentric.
• 12 •
Prove that no cardinal C can be egocentric.
• 13 •
Prove that no vireo V can be egocentric. [Vxyz = zxy]
• 14 •
Show that for any warbler W:
a. W is not fond of I.
b. W is not egocentric.
• 15 •
Show that for any starling S:
a. SI is not fond of I. It can also be shown that S is not fond of I.
b. S is not egocentric.
• 16 •
Prove that for any bluebird B:
a. BKK ≠ KK
b. B cannot be egocentric.
• 17 •
Can a queer bird Q be egocentric?
The reader might have fun looking at some other familiar birds and seeing which ones can be shown to be nonegocentric. The reader might also find it a good exercise to show that of the birds B, C, W, S, R, and T, no pair can be identical—i.e., B ≠ C, B ≠ W,…, B ≠ T, C ≠ W,…, C ≠ T, etc.
KESTRELS AND INFINITY
“Well,” said Griffin, after they had had a delicious tea, complete with buttered crumpets, “some of the little problems I have given you about kestrels lead to a highly significant fact. Again, we consider a forest having at least two birds. Did you know that if the forest contains a kestrel K, then it must contain infinitely many birds?”
“That sounds most interesting!” exclaimed Craig.
“Some of my former students have given me fallacious proofs of this fact,” said Griffin. “I recall that when I told this to one student, he instantly replied: ‘Oh, of course! Just consider the infinite series K, KK, KKK, KKKK,…’
“You see why this proof is fallacious?”
• 18 •
Why is this proof fallacious?
• 19 •
“Of course I see why the proof is fallacious,” replied Craig. “However, suppose we instead take the series K, KK, K(KK), K(K(KK)), K(K(K(KK))),… Will that work?”
“You got it!” said Griffin.
“To tell you the truth, that was only a guess,” replied Craig. “I haven’t really verified in my mind that all these birds are really different. For example, how do I know that K(KK) isn’t really the same bird as K(K(K(K(K(KK)))))?”
“I’ll give you a hint,” replied Griffin. “To simplify the notation, let K1 be the bird K; let K2 = KK1, which is KK; let K3 = KK2, which is K(KK); let K4 = KK3, which is K(K(KK)), and so forth. Thus for each number n, Kn+1 = KKn. The problem is to show that for two different numbers n and m, it cannot be that Kn = Km. For example, K3 = K8 cannot hold; K5 = K17 cannot hold. First recall the cancellation law for kestrels: If Kx = Ky, then x = y. Then divide your proof into three steps:
Step 1: Show that for any n greater than 1, K1 ≠ Kn—that is, K1 cannot be any of the birds K2, K3, K4,…
Step 2: Show that for any numbers n and m, if Kn+1 = Km+1, then Kn = Km. For example, if K4 were equal to K7, then K3 would have to be equal to K6.
Step 3: Using Step 1 and Step 2, show that for no two distinct numbers m and n can it be the case that Kn = Km, and therefore there really are infinitely many birds in the sequence K1, K2, K3,…”
With these hints, Craig solved the problem. What is the solution?
SOLUTIONS
1 · Suppose a kestrel K is fond of an identity bird I. Then KI = I. Therefore, for any bird x, KIx = Ix, and since Ix = x, then KIx = x. Also KIx = I, since K is a kestrel. This means that KIx is equal to both x and I, hence x = I. Therefore, if K is fond of I, then every bird x is equal to I and hence I is the only bird in the forest. But we are given that there are at least two birds in the forest; hence K cannot be fond of I.
2 · This follows from the last problem. Suppose K = I. Then KI = II, hence KI = I. This means that K is fond of I, which, according to the last problem, cannot happen.
3 · Suppose SK = K. Then for any birds x and y, SKxy = Kxy. Hence SKxy = x, since Kxy = x. Also, SKxy = Ky(xy) = y. Therefore SKxy is equal to both x and y, hence x and y are equal. So, if SK = K, then any birds x and y are equal, which means that there is only one bird in the forest.
4 · Suppose S = I. Then SK = IK = K, hence SK = K. But SK ≠ K, as we showed in the last problem; therefore S ≠ I.
5 · Suppose S = K. Then SIKI = KIKI. Now, SIKI = II(KI) = I(KI) = KI, whereas KIKI = II = I. Therefore, if S = K, then KI = I. But KI ≠ I, by Problem 1; hence S ≠ K.
6 · Suppose there were a bird x such that Kx = K. Then for every bird y, it would follow that Kxy = Ky, and hence that x = Ky. Then for any birds y1 and y2, it would follow that Ky1 = Ky2, because x is equal to each of them. Then by the cancellation law—Problem 16, Chapter 9—it would follow that y1 = y2. And so the assumption that there is a bird x such that Kx = K leads to the conclusion that for any birds y1 and y2, the bird y1 is equal to y2—in other words, that there is only one bird in the forest!
7 · This is easier. Suppose there is a bird x such that Kx = I. Then KxI = II, hence x = I, since KxI = x and II = I. Then, since Kx = I and x = I, it follows that KI = I. But KI ≠ I, according to Problem 1. Therefore, there is no bird x such that Kx = I.
8 · Suppose T = K. Then TIK = KIK, hence KI = KIK = I, but KI ≠ I, according to Problem 7.
9 · For this and the next several problems, I will make the solutions more condensed. By now, the reader should have enough experience to fill in any missing steps. I will illustrate what I mean by “missing steps” in the solution to this problem.
Suppose TT = T. Then TTKI = TKI, hence KTI = IK. Missing steps: “because TTKI = KTI and TKI = IK.” Therefore T = K. Missing steps: “because KTI = T and IK = K.” But T ≠ K according to Problem 8. Therefore it cannot be that TT = T.
10 · Suppose RII = I. Then RIIK = IK, hence IKI = K by simplifying both sides of the equation, hence KI = K, contrary to Problem 7. In Problem 7 we proved that there is no bird x such that Kx = K, so in particular, KI ≠ K.
11 · Suppose RR = R. Then RRII = RII. Now, RRII = IIR = R, so R = RII, hence RII = RIIII = IIII = I. We then have RII = I, contrary to the last problem.
12 · Suppose CC = C. Then CCIKI = CIKI = IIK = K. Also, CCIKI = CKII = KII = I. We then have I = K, contrary to Problem 2.
13 · Suppose VV = V. Then VVIII = VIII = III = I. Also VVIII = IVII = VII, and so VII = I. Then VIIK = IK = K. Also VIIK = KII = I, and so we have K = I, contrary to Problem 2.
14 · a. Suppose WI = I. Then WIK = IK = K. Then IKK = K, hence KK = K, which we know is not so; no kestrel is egocentric.
b. Suppose WW = W. Then WWI = WI. Now, WWI = WII = III = I. Hence we would have WI = I, contrary to part a of the problem.
15 · a. Suppose SI were fond of I. T
hen SII = I. Then SIIK = IK, hence IK(IK) = IK, so KK = K. But KK ≠ K, so SII ≠ I.
b. Suppose SS = S. Then SSIII = SIII = II(II) = I. Also SSIII = SI(SI)I = II(SII) = SII. Hence we have SII = I, contrary to part a of the problem.
16 · a. Suppose BKK = KK. Then BKKI = KKI, hence K(KI) = K. This is again contrary to Problem 6, which states that there is no bird x such that Kx = K.
b. Suppose BB = B. Then BBIK = BIK, hence B(IK) = BIK. Therefore BK = BIK. Therefore BKK = BIKK = I(KK) = KK and we have BKK = KK, contrary to part a of the problem.
17 · Suppose QQ = Q. Then QQIKI = QIKI = K(II) = KI. Also, QQIKI = I(QK)I = QKI. Hence QKI = KI. Then QKII = KII, so I(KI) = I, hence KI = I, contrary to Problem 1. Therefore, Q, queer as it may be, is definitely not egocentric.
18 · The fallacy is that all the infinitely many of the expressions of the series name only two different birds—namely K and KK. Clearly KKK = K, hence KKKKK = KKK = K, and indeed all the expressions with an odd number of K’s boil down to K; all those with an even number of K’s boil down to KK.
19 · The series Craig named really works!
Step 1: We proved in Problem 6 that for every bird x, K ≠ Kx. Hence K cannot be any of the birds KK1, KK2, KK3,… Thus K1 is not any of the birds K2, K3, K4 …
Step 2: Suppose, for example, that K3 = K10. Then KK2 = KK9, hence by the cancellation law for kestrels, K2 = K9.
Of course the proof works for any numbers n and m: If Kn+1 = Km+1 then KKn = KKm, and so Kn = Km.
Step 3: Suppose, for example, that K4 = K10. Then by successively applying Step 2, we would have K3 = K9, K2 = K8, K1 = K7, violating Step 1.
Obviously the proof works for any two distinct numbers.
23
Logical Birds
“I am very proud of this forest,” said Professor Griffin one day. “Some of the birds here can do very clever things. For example, did you know that some of them can do propositional logic?”
“I am not sure I understand what you mean by that,” replied Griffin.
“Let me first explain some of the basics of propositional logic,” said Griffin. “To begin with, I am using Aristotelian logic, according to which every proposition p is either true or false but not both. We use the symbol t to stand for truth and f to stand for falsehood. And so the value of any proposition p is either t or f—t if p is true and f if p is false. Now, logicians have a way of constructing more complex propositions out of simpler ones. For example, given any proposition p, there is the proposition not p—symbolized ~p—which is false when p is true and true when p is false. This is simply schematized: ~t = f; ~f = t. It is usually displayed as the following table, called the truth table for negation:
“Next, given any propositions p and q, we can form their conjunction—the proposition that p and q are both true. This proposition is symbolized p & q. It is true when p and q are both true, and false otherwise. In other words, t & t = t; t & f = f; f & t = f; and f & f = f. These four conditions are tabulated by the following table—the so-called truth table for conjunction:
“Also, given propositions p and q, we can form the proposition p v q, which is read ‘p or q, or maybe both’ and is called the disjunction of p and q. This proposition is true if at least one of the propositions p and q is true; otherwise it is false. The disjunction operation has the following truth table:
“As you see, the proposition p v q is false only in the last of the four possible cases—the case when p and q both have the value f.
“Next, from propositions p and q we can form the socalled conditional proposition p → q, which is read ‘if p, then q,’ or ‘p implies q.’ The proposition p → q is taken to be true if either p is false or p and q are both true. The only case when p → q is false is when p is true or q is false. Here is the truth table for p → q:
“Since p → q is true when and only when p is false or p and q are both true, it can also be written: (~p) v (p & q). It can be written even more simply as (~p) v q, or as ~(p & ~q).
“Finally, given any propositions p and q, there is the proposition p ↔ q, which is read ‘p if and only if q,’ which asserts that p implies q and q implies p. This proposition is true just in the case that p and q both have the value t or both have the value f.
“These five symbols— ~ (not), & (and), v (or), → (if—then), ↔ (if and only if)—are called logical connectives. Using them, one can form from simple propositions propositions of any complexity. For example, we can form the proposition p & (q v r), which is true if and only if p is true and also at least one of q and r is true. Or we could form the very different proposition (p & q) v r, which is true just in case either p and q are both true, or r is true. One can easily compute their truth values, given the truth values of p, q, and r, by combining the tables for & and v. Of course, since there are now three variables involved—p, q, and r—we now have eight possibilities instead of four. Here is the truth table for (p & q) v r.
“On the other hand, here is the truth table for p & (q v r).
“You see, the two propositions have different truth tables,” said Griffin.
“I understand all this,” said Craig, “but how does it relate to the birds?”
“I am coming to that,” replied Griffin. “To begin with, I have chosen for t and f two particular birds. The first, t, represents truth, or it can be thought of as being the representative of all true propositions. The second bird, f, of course, represents falsehood, or is the representative of all false propositions. I call t the bird of truth, or the truth bird, or more briefly, just truth. I call f the falsehood bird, or the bird of falsehood, or more briefly, just falsehood.”
“What birds are they?” asked Craig.
“For t, I take the kestrel K; for f, I take the bird KI. And so, when we are discussing propositional logic, I use t synonymously with K and f synonymously with KI.”
“Why this particular choice?” asked Craig. “It seems quite arbitrary!”
“Oh, there are many other choices that would work,” replied Griffin, “but this particular one is technically convenient. I have adopted this idea from the logician Henk Barendregt. I will tell you the technical advantage in a moment.
“The birds t and f are collectively called propositional birds. Thus, there are only two propositional birds—t and f. From now on, I shall use the letters p, q, r, and s as standing for arbitrary propositional birds, rather than propositions. I call p true if p is t and false if p = f. Thus t is called true and f is called false.
“Now, the advantage of Barendregt’s scheme is this:
“For any birds x and y, whether propositional birds or not, txy = x, since Kxy = x, and fxy = y, since fxy = KIxy = Iy = y. And so for any propositional bird p, pxy is x if p is true, and pxy is y if p is false. In particular, if p, q, and r are all propositional birds, then pqr = (p & q) v (~p & r)—or what is the same thing, pqr = (p → q) & (~p → r). This can be read ‘if p then q; otherwise r.’ ”
“You still haven’t told me what you mean when you say that some of the birds here can do propositional logic,” said Craig. “Just what do you mean by this?”
“I was just coming to that!” replied Griffin. “What I mean is that for any simple or compound truth table, there is a bird here that can compute that table.”
• 1 •
“For example, there is a bird —called the negation bird—that can compute the truth table for negation. That is, if you call t to N, N will respond by naming f; if you call f to N, N will respond by naming t. Thus Nt = f and Nf = t. In other words, for any propositional bird p, Np is the bird ~p. The first problem I want you to try is to find a negation bird .”
• 2 •
“Then we have a conjunction bird c such that for any propositional birds p and q, cpq = p & q. In other words, ctt = t; ctf = f; cft = f; and cff = f. Can you find a conjunction bird c?”
• 3 •
“Now find a disjunction bird d—a bird such that for any propositional birds p and q, dpq = p v q. In other w
ords, dtt = t; dtf = t; dft = t; but dff = f. Can you find such a bird d?”
• 4 •
“Then there is the if-then bird—a bird i such that itt = t; itf = f; ift = t; and iff = t. In other words, ipq = p → q. Can you find an if-then bird i?”
• 5 •
“Now find the if-and-only-if bird e—also called an equivalence bird—such that for any propositional birds p, q, epq = (p & q). In other words, ett = t; etf = f; eft = f; and eff = t.”
SOLUTIONS
1 · Since the Master Forest is combinatorially complete, we can find a bird such that for all x, Nx = xft. Specifically, we can take N to be Vft, where V is the vireo. Then Vftx = xft. So Nt = tft = f; Nf = fft = t. Thus N is a negation bird.
2 · Consider c such that for any x and y, cxy = xyf. Note: We can take c to be Rf, where R is the robin. Then Rfxy = xyf.
1. ctt = ttf = t
2. ctf = tff = f
3. cft = ftf = f
4. cff = fff = f
Thus c is a conjunction bird.
To Mock a Mocking Bird Page 17