Given: (Ex)(Px & Qx) Prove: (Ex)Px & (Ex)Qx 1. Given (Ex)(Px & Qx) <== If a given begins with (Ex), maybe existential elimination might be a good thing to try. 2. Assume Pu & Qu 3. Pu & Qu (Assumption 2) 4. Pu (&E, 3) 5. Qu (&E, 3) [If we're using existential elimination, what we want to do after we assume a statement with a u in it, we want to develop an interesting statement without a u.] 6. (Ex)Px (EI,4) 7. (Ex)Qx (EI,5) 8. (Ex)Px & (Ex)Qx (&I,6,7) 9. (Ex)(Px & Qx) (Given 1) 10. (Ex)Px & (Ex)Qx (EE,9,2-8) Given: nothing Prove: (Ax)(Px<=>~Qx) => ~(Ex)(Px & Qx) 1. Assume (Ax)(Px<=>~Qx) 2. (Ax)(Px<=>~Qx) (Assumption 1) 3. Pu <=> ~Qu (AE, 2) 4. Assume (Ex)(Px & Qx) 5. (Ex)(Px & Qx) (Assumption 4) 6. Assume Pu & Qu <== begins an EE proof 7. Assume (Ex)(Px & Qx) 8. Pu & Qu (Assumption 6) 9. Pu (&E,8) <== lines 7-11 are proof by contradiction 10. Qu (&E,8) 11. ~Qu (<=>E,3,9) 12. ~(Ex)(Px & Qx) (~I,7-(10,11)) Notice that we assumed on line 7 the same thing we assued on line 4. This is a technicality in this sort of proof, assuming something we've already assumed specifically to use for a different inference rule. On line 7, we're assuming for (~I) i.e. proof by contradiction. On line 4, we're assuming it specifically for (EE). 13. ~(Ex)(Px & Qx) (EE,5,6-12) EE: If we know (Ex)S and under the assumption S(u/x) we can derive T where u does not appear free in our previous givens and assumptions or in T, we can then conclude T. Informally, if know (Ex)Px, and under the assumption of Pu, I can conclude Q, and Q doesn't have any u's in it anywhere, and there are no u's in my givens or prior assumptions still in play, then I know Q is true, even without the assumption of Pu. The idea is that (Ex)Px, means Px is true SOMEWHERE. I don't know exactly where, but I'm calling it u temporarily. Since I concluded something without any u's in it, I could have run the exact same derivation no matter what I had plugged into x. Py, Pf, Pr, it doesn't matter, I could have still done the proof the same way and still gotten Q since Q doesn't have that random u in it. Therefore, Q must be true, no matter what value works for Px. 14. ~(Ex)(Px & Qx) (~I,5,13) 15. (Ax)(Px<=>~Qx) => ~(Ex)(Px & Qx) (=>I,1-14) So, these techniques translate into broader mathematical proof techniques. Proof by contradiction. If, under an assumption, I can prove a certain statement both true and false, the assumption must be false. This technique is used ALL THE TIME. (Universal Introduction): If I can prove a certain fact about an ARBITRARY member of a set, I know the fact for every member of the set. By ARBITRARY I mean that my proof can't assume any specific detail about the member of that set other than that it's in that set. A perfect number: A number that is equal to the sum of all of its factors except itself. 6 = 1+2+3 . 28 = 1+2+4+7+14. Prove: There are no odd perfect numbers. Choose an arbitrary odd number, say, 11. The proper factors of 11 are 1. The sum is 1. 1 does not equal 11. Therefore, 11 is not perfect. Therefore, no odd number is. I am not allowed to assume anything about an arbitrary odd number except that it's an odd number. I certainly can't decide that it's going to be 11. (Existential Elimination). If I know that a statement is true about SOME member of a set. I can assume it's true for a nonspecific element of that set (because I know it's somewhere), but I can't assume any properties about that element except that it's in the set. Under this assumption, if I prove something general that makes no reference to the nonspecific element I indicated before, then that general thing is true. Given that I have a set that contains an odd number, prove...whatever... OK, the set contains an odd number. Call it x. My proof continues without using specific information about x, other than it's known to be odd. If I can prove something about the set, and the thing I prove does not reference x specifically, then that thing is true. I haven't actually said x is; it's just a place holder.