P310 Valid Reasoning II

Professor: Craig DeLancey

Office: Marano 212A

Email: craig.delancey@oswego.edu

Current Assignments

27 AprilLet's play with S to get a feel for it. Using just the axioms of S (page 150 in the latest edition of our book) prove thatWe allow free substition of identicals throughout your proofs, so you can always replace a term with an identical term. What that means is that you can have proofs like the following proof, given as a simplistic example, that 1+0=0+1:

- 2+2 = 4 (In the object language, this means you'll prove that 0''+0''=0''''. (To be even more accurate, something like Af
_{1}f_{2}f_{2}0f_{2}f_{2}0f_{2}f_{2}f_{2}f_{2}0, where A is an arity two predicate meaning identity, f_{2}is the arity one successor function, and f_{1}is the arity two addition function. But ignore all that; I mention it only to show our parentheses are irrelevant and there only for our convenience. That is: the parenthesis that surround a function disappear when we replace the function with its referent, so don't be confused by this.) (Hint: look at S5 and S6.)- 2 x 2 = 2 + 2 (Hint: look at S8; the dot is multiply.)
1. 0' + 0 = 0' ....... Axiom S5Let's introduce the following principle: we won't care about the order of the elements in the function + or *. That's a bit of a cheat, but we know it's true that they give the same answer either way, so let's make our lives easier. Thus, we'll say x+0 can be freely substituted for 0+x, and so on.

2. 0 + 0' = (0 + 0)' ...... Axiom S6

3. 0 + 0 = 0 ...... Axiom S5

4. 0 + 0' = 0' ...... substitution of identicals, 2, 3

5. 0' + 0 = 0 + 0' ...... substitution of identicals, 1, 4

Chris asked the following question: wouldn't it be great to have an axiom that let's you show x * 1 = x? The answer is that you can derive this quickly, for any case. Consider x * 1 = (x * 0) + x, according to axiom S8. But then we can quickly use axiom S7 and S5, and our principle above of not caring about order for the functions + and *, to get to x * 1 = x. Combine that insight with a look at S8, and you're almost there to show 2 * 2 = 4. Also, note that you'll have already shown 2 + 2 = 4, so that also will be helpful.29 AprilRead section 4.1 of chapter 4 of Mendelson. Here are our goals for our overview of the set theory:

- explore how to create the set theory out of axioms;
- learn some of the basic concepts, like power set, equinumerosity, and ordering;
- peek at how you can make the numbers out of sets;
- discuss two of the controversies (constructivism to avoid the Set Theory Antinomy; and also the issue of the axiom of choice).

Tentative assignments

1 MayProve the following, using NBG and our definitions. Your proof will be written out as a paragraph explanation (donâ€™t bother to try to do a proof in the object language with numbered steps). Use any rules from the natural deduction system. For example, for problem 9, just show (describe) each direction for the arbitrary cases. Use the definitions of intersection and union.

- Problem 4.7b from the book; that is, prove that ∀x∀y({x}={y} ↔ x=y)
- Problem 4.10c; that is, prove that X⊂Y ↔ X∩Y = X
- Problem 4.10d; that is, prove that X⊂Y ↔ X∪Y = Y
- Problem 4.10i; that is, prove that X∩∅ = ∅