Exam comments (1)

Well, so far the news is not so great. I might as well have not asked my questions 5.(d) about BL1 and 5.(e) about BL2. Only one or at most two people out of 46 did a good job with either of those problems. I think no one did a good job with both. BL1 was the same as our system BL except that it had some unknown wff A as a twelfth axiom. Otherwise the same axioms and two primary inference rules as our system BL. I asked about soundness and completeness of BL1. I gave 0 marks for just circling the label of the right answer. People had to give GOOD explanations for the right answer to get marks. I asked for a one-sentence explanation. I'll give more than one sentence as explanation here, first, to make sure that people understand. BL1 is still complete, but not necessarily sound. Reason: Let B be a tautology. Then there is a proof of B within BL, since BL is complete. But a strict annotated Hilbert proof within BL is precisely a strict annotated Hilbert proof within BL1 that never mentions A as an axiom, in an annotation. (I assume that A is not one of the 11 axioms already present in BL. It would be pretty weird to list an axiom TWICE. But if we did, then BL1 and BL would be THE SAME system, in which case BL1 is sound and complete because BL is.) So there is a proof of B within BL1. BL1 would be sound if A were a BL-theorem (i.e., a tautology). Clearly BL1 is not sound if A is not a tautology, since then A is provable from the empty set in BL1 but is not a tautology. OK. One-sentence explanation of why BL1 is complete but not necessarily sound: We may assume that A is not already an axiom of BL; then a proof in BL is just a proof within BL1 which never mentions A as an axiom, so anything provable in BL is provable in BL1, so all tautologies are provable in BL1; if A is not a tautology then BL1 is not sound. BL2 was our system with one of our eleven axioms removed. BL2 is sound. (I asked whether it is sound.) Reason: Suppose B is a BL2-theorem; then there is a proof of B from the ten axioms of BL2 using the two primary inference rules. But that proof is then automatically also a proof of B in BL. So by soundness of BL, B is a tautology; so, BL2 is sound. Next piece of bad news. Problem 6: I asked for a bullet proof that |-- (ex. x)(A \/ B) == (ex. x)A \/ (ex. x) B. I thought we had done enough such proofs of duals of theorems about (\forall ) that people would be happy and just zip right through this. The easy proof rewrites the first existential in terms of universals, then 2.4.17' on the body and WL, then 6.1.7 to split the universal into a conjunction of universals, then 2.4.18' and definition of (exists ) again. But no. While some people are giving this intended, very easy proof, many are using 6.1.6, 6.5.3, etc. Even 6.5.6.... Those metatheorems do not say that one wff is syntactically equivalent to another. They are provability statements. You cannot just toss away quantifications or introduce them in a string of biconditionals and give provability statements as your reason. Look at this: C \/ D <==> < 6.5.3 > (ex. x)C \/ (ex. x)D. That is nonsense. 6.5.3 says that each of the existentials above is PROVABLE FROM the corresponding wff in the first line. It doesn't say that they are syntactically equivalent to them. That, in fact, is FALSE. It is true that |-- C --> (ex. x)C -- one way to see this is to use 6.5.3 and D.T. But --> is very different from ==. ... People who jumped right in and used 6.1.6 (same comments about 6.1.6, by the way) and 6.5.3 ... and even 6.5.6... got very few marks on Problem 6. Look at those metatheorems. They don't have a single biconditional symbol triple-bar appearing anywhere in them. So how do you justify a <==> with them?? What is true using 6.1.6 and 6.5.3 and D.T. twice is this: (ex. x)(A \/ B) is not(forall x) not(A \/ B) <== < contrapositive of "6.1.6 plus D.T." > not not(A \/ B) <==> < 2.4.4 > A \/ B ==> < 6.5.3 plus D.T. plus a somewhat long argument about disjunctions in conditionals > (ex. x)A \/ (ex. x)B. So the middle of this chain "syntactically implies" both the beginning wff and end wff. But that is a loooong way from saying that the first and last wff in the above stack are syntactically equivalent.... That's like saying that "a less than or equal to b" and "b greater than or equal to c" imply that a = c. Hogwash. You folks surprised me with this. If there is a free occurrence of x in a wff C, then C is syntactically equivalent, in general, to NEITHER of (forall x) C, (exists x) C. And 6.1.6, 6.5.3 do not say anything about syntactic equivalence. Third piece of bad news: The last problem, finding an interpretation under which a 2-place predicate satisfying a given wff interprets as true. As usual, interpret the predicate as a binary relation, in the sense of 1019 or 1190, on the domain D. The wff interpreted as saying that (1) everybody in D points to somebody in D, (2) if a points to b and b points to c then a points to c, and (3) nobody points to himself. One person got 6 marks out of 6 on this. One got 2 out of 6. The other 44 people got 0. Here goes: D is nonempty because all universes of discourse are, so has one element a1 in it. a1 has to point to someone, and the someone cannot be a1. Let a1 point to a2. a2 must point to someone, and the someone is not a2. And the someone also is not a1, because if a2 pointed to a1 then by (2) a1 would point to itself. So a2 must point to a third guy, a3. So, by (2), a1 also points to a3. a3 must point to someone other than a3. But it cannot point to a1 or a2 because then, by (2), a1 or a2 would point to itself. So a3 points to a fourth guy a4. By (2), a1 and a2 also point to a4. Here goes a sketch of an induction: Let n be a positive integer, and suppose that we have already found elements a1, ..., an in D, n of them, such that each ai points to each aj with i < j. an must point to someone in D. The someone cannot be an itself, and cannot be any of the guys we already listed because then by (2) the guy listed would also point to itself. So an must point to an (n+1)st guy a_(n+1) in D. And then all of the guys we just listed also point to the new one, by (2). OK. So a domain D in which the predicate interprets as true must be infinite. And there is an obvious candidate for D, given the above discussion: + Let D be ZZ , the set of positive integers, and let a point to b iff a < b. Then 1 points to everyone else, 2 points to everyone except 1 and 2, etc. This interpretation "works", because every positive integer is less than itself plus 1, no pos. integer is less than itself, and "less than" is transitive. In some sense, this is the "smallest" interpretation in which the given wff interprets as true, as one sees easily by the above induction. Not difficult. Just think. And persist. 44 zeroes. Fourth piece of bad news: Very few of you got 4 out of 4 on the simple "substitutions" problem. The first substitution was undefined, the second and third produced no change in the wffs in which the substitutions were made, and the fourth double substitution yielded (w = w). Very easy. You folks don't know the substitution rules. Many scores of 0, 1 or 2 out of 4. Maybe six or so people out of 44 got perfect 4 scores.