PHL310 Valid Reasoning II, past assignments



26 August
Let's review propositional logic for a while (before we get to reviewing quantified logic AKA predicate logic AKA First Order Logic). So that I can see what rules you learned and how you do proofs, try the following. It's OK if you can't see how to do any of them; I want to see what we've got in common.

Please do the following!
  1. Translate the following into symbolic propositional logic: If both Nemo and Jaws are fish, then neither Patrick nor Mr. Krab are.
  2. Prove the following, using a syntactic proof. Premises: (P ∧ Q), (P-->R), (Q-->S). Conclusion (R^S).
  3. Prove the following, using a syntactic proof (hint, you'll probably need indirect proof). Premises: (P → Q), (R ↔ Q), (P v R). Conclusion: Q.
  4. Prove the following, using a syntactic proof (hint: you'll probably need a conditional proof). Conclusion: ((P → Q) → (¬Q → ¬P)
Please write it up and hand it in at the beginning of class. Reviewing these will help me to see where each of us is at, what systems you learned, and so on.

We are going to be reviewing propositional logic this day. For review, you might find it helpful to read the first chapters of A Concise Introduction to Logic. Chapter 10 provides a concise 3-page summary of an entire natural deduction system propositional logic

The virtual student involvement fair is on 10-3: https://lakerlife.oswego.edu/event/6161615.
4 September
Read: "On Denoting" by Bertrand Russell. I have put it in BlackBoard so you can download it. Bring it to class so that we can review it together, if you happen to print it.

Here is a helpful question. Translate, into something like our contemporary natural deduction system quantified logic, the phrases:
1. "C(all men)" means "'If x is human, then C(x) is true' is always true."
2. "C(no men)" means "'If x is human, then C(x) is false' is always true."
3. "C(some men)" means "It is false that 'C(x) and x is human' is always false."
4 September
Here are some problems to try, if you want extra practice. My intro book is a quick read, if you want a book to review with. Each problem is in propositional logic. Translate 1-4. Try to do 5 and 6 with a direct proof; 7 and 8 with a conditional proof; and 9 and 10 with an indirect proof. Don't use theorems just yet; we'll start using those later.
  1. Tom will go to London or Paris but not both.
  2. Tom will go to London if and only if he goes to New York or Newark.
  3. Tom will go to London only if he doesn't get arrested.
  4. Tom will go to Paris provided that he doesn't get arrested.
  5. Premises: (P → Q), (S ^ ¬T), (T v P), (¬R → ¬S).
    Conclusion: (Q ^ R)
  6. Premises: (¬P v Q), (Q → S), ¬S.
    Conclusion: ¬P
  7. Premises: (¬R v T), (T → Q), ((Q ^ S) ↔ V), (V ↔ P).
    Conclusion: ((R ^ S) → P).
  8. Conclusion: ((P v Q) → (¬P → Q))
  9. Premises: (P → R), (Q → S), (¬R ^ ¬S).
    Conclusion: ¬(P v Q).
  10. Conclusion: ¬(P ^ ¬P).
  11. Extra extra credit: Conclusion: (¬(P ^ Q) ↔ (¬P v ¬Q)).
  12. Extra extra extra credit: Prove that we only need ¬ and → as connectives. To do this, identify a complex sentence equivalent to "and", "or", and "if and only if", where the sentence is composed of atomic sentences and ¬ and →.
8 September
Sorry, I'm getting a flu shot at 2:00. I'll have office hours 3:00 - 5:00 pm at https://meet.google.com/cjs-hynb-zww.
9 September
A short practice homework: translate the following using our FOL. Assume your domain of discourse is people (so ∀ means "all people" or "everyone.")
  1. Everyone likes Tom.
  2. Tom likes everyone.
  3. Someone likes Tom.
  4. No one likes Tom.
  5. Tom like no one.
  6. Tom doesn't like everyone.
  7. Someone likes someone.
  8. Someone likes everyone.
  9. Everyone likes someone.
  10. Everyone likes everyone.
11 September
A short practice homework: Prove the following.
  1. From A Concise Introduction to Logic, chapter 13, try problems 1a, 2a, and 3c.
  2. From A Concise Introduction to Logic, chapter 14, try problems 1a and 1b.
  3. Prove this theorem: (∀x∀yFxy → ∃y∃xFxy)
  4. Prove this theorem: (∀x∃y(Fx → ∃z(Gz → Hy)) → ((∃xFx ^ ∀xGx) → ∃xHx))
    Hint: this is a big conditional! Do conditional derivation. The consequent (the then side) is a big conditional; do another conditional derivation. You'll have a lot of assumptions left with which to prove ∃xHx. Remember to do EIs before your UIs. I use p, q, r... as names of indefinite objects.
14 September
Another short practice. If you need more time, I'll take it Wednesday without penalty.
  1. Using any of our tools, prove: (A ⊆ B → A ∩ B = A)
    Hint: it is sufficient to prove:
    (∀x(x ∈ A → x ∈ B) → ∀x((x ∈ A ^ x ∈ B) ↔ x ∈ A))
  2. Using any of our tools, prove: (A ⊆ B → A ∪ B = B)
    Hint: it is sufficient to prove:
    (∀x(x ∈ A → x ∈ B) → ∀x((x ∈ A v x ∈ B) ↔ x ∈ B))
  3. We can define "-" in the following way: ∀x(x ∈ A - B ↔ (x ∈ A ^ ¬ x ∈ B)).
    Using any of our tools, prove: (A ⊆ B → A - B = {})
    Hint: it is sufficient to prove:
    (∀x(x ∈ A → x ∈ B) → ¬∃x(x ∈ A ^ ¬ x ∈ B))
September 17
Office hours 9:00 - 11:00 am.
https://meet.google.com/mdf-vvpr-wqi?authuser=0 .
September 18
Some problems for our axiomatic approach.
  1. Using our three axioms and MP alone, prove: { (A → (B → C)), (A → B) } |-L (A → C). Do this one without the deduction theorem.
  2. See if using our three axioms alone, you can prove: {} |-L (B → (¬B → C)). This one is hard to do with straight axioms, but using the deduction theorem twice it is not hard; so, if you are stumped, use DT.
  3. Using our three axioms alone, prove: {} |-L ((A → B) → ((C → A) → (C → B))). Try to do this using deduction theorem at most once. (For many of these proofs, note this useful trick: if you have as a line φ, note that axiom 1 lets you say (φ → (ψ → φ)) and then with MP you get (ψ → φ). In other words, with axiom 1, if you have some sentence φ you can always in two steps get (anything → φ).)
September 21
Class synchronous online at: https://meet.google.com/kbh-fdup-ats?authuser=0 .
29 September
Office hours 2-4 pm https://meet.google.com/niy-yveh-ahs?authuser=0
30 September
Class linK: https://meet.google.com/uhb-enac-gmi?authuser=0

This year’s ORI for summer 2020 was There There by Tommy Orange. The author is going to speak to the campus community about the book at 7:00PM ET on September 30th (tomorrow) via Zoom. For more information, visit the ORI website at: https://ww1.oswego.edu/oswego-reading-initiative/.

Please note that M chapter 2 is posted on BlackBoard for your use. This covers the First Order Logic.
October 5
Here is a homework for us due at the beginning of class. It includes some concepts, some review, and then our new stuff.
  1. Suppose we have an axiom system K, and we discover that it is inconsistent (we prove some theorem φ and we also prove a theorem ¬φ). Of course we want to fix the system. What should our strategy be? What kind of action will a fix require? (Remember, this is an axiom system, like our PL.)
  2. Using system PL (that is, just axioms L1-L3 and modus ponens, and without DT) show {¬Q, (¬¬P → Q), (¬R → P) } |-- R
  3. Prove using just L1-L5, MP, and DT, and GEN: ∀x1(B(x1) → C(x1)) → (∀x1B(x1) → ∀x1C(x1))
  4. Prove using just L1-L5, MP, and DT, and GEN: ∀x1(¬C(x1) → ¬B(x1)) → ∀x1(B(x1) → C(x1))
Deduction Theorem for our AFOL:
Suppose S is a set of premises, and φ and ψ are particular sentences. If a deduction showing S ∪ {φ} |-- ψ involves no application of generalization (GEN) of which the quantified variable is free in φ, then S |-- (φ → ψ)
October 6
Today I have to hold my office hours an hour earlier: 1-3 pm. Office hours GoogleMeet link: https://meet.google.com/wki-vjgy-hgg?authuser=0
October 9
Quiz. Topics and questions will include:
  • Simple proofs in natural deduction (NDS) propositional logic, NDS FOL, and NDS set theory.
  • Basic principles of set theory.
  • Simple proofs with the three axioms of standard axiomatic propositional logic.
  • Proving the Deduction Theorem.
  • Completeness of the axiomatic propositional logic using Kalmar's Lemma.
  • Meaning of completeness and consistency.
October 12 - 23
Set theory. Some history. ZF axioms.
21 October
There is a philosophy talk this day! We have an annual talk, and unfortunately now with COVID it has to be online. The topic is "moral realism," which is the view that good and evil are real things, not just projections by human beings. The "anti-realists" are people who deny this. You're welcome to "attend" by logging on.

Here are the details (click the image for a big poster to see the details):

21 October
In class, we might practice another proof, and then we'll talk about some concepts in set theory that will be very useful for our discussion of modal logic.
October 26 - October 30
Modal propositional logic. Systems.
28 October
Numbers and Set theory homework. Please prove the following.
  1. Using our PA axioms: 2 + 2 = 2 * 2
    In the half-way-there object language, this means you'll prove that 0''+0''=0''*0''. (To be even more accurate, in the true object language this is Ff2f1f10f1f10f3f1f10f1f10, where F is an arity two predicate meaning identity, f3 is the arity two multiplication function, and f2 is the arity two addition function, and f1 is the arity one successor function. But ignore all that; I mention it only to show our parentheses around functions in the axioms are there only for our convenience. That is: the parenthesis that surround a function disappear when we replace the function with its proper statement in the object language, so don't be confused by this.
  2. Using our PA axioms: 3 * 0 = 0 + 0
  3. Given the axioms of ZF, describe why I know that there exist the set {{}, {{}}}.
    It can be cumbersome to prove this directly, so it's enough to describe carefully why we know it is so.
  4. An alternative axiomatization of ZF can use the weak axiom of pair: ∀x ∀y ∃ z (x ∈ z v y ∈ z). Prove we aren't missing anything; that is, prove this sentence using the given ZF axioms.
    HINT: there are probably tons of ways to prove this. I suspect the easiest is by indirect proof. Consider the denial of the weak axiom of pair. With some quantifier negations and de Morgan's theorem, you can show ∃x∃y∀z(¬x ∈ z ^ ¬ y ∈ z). That's the useful version of the assumption for reductio. But consider the strong axiom of pair (the axiom of pair in ZF). What if you consider an instance where your pairs are something like (p∈q ↔ (p=p v p=q))? Play around with your useful version of the assumption for reductio and you'll have a contradiction. The only issue is working with quantifier instantiations; you have to be careful to do them in order; remember EI has to be to a new indefinite variable, so you'll have to consider the order of instantiation carefully. Also, please note any time you like you can say p=p or q=q or r=r, and cite "indiscernability of identicals" as your justification.
  5. Prove in ZF with our other tools that (A = B ↔ (A ⊂ B ^ B ⊂ A)).
    This is actually rather trivial, but is a good exercise in going back and forth from our shorthand to the actual object-language meanings. I can send hints if you are stumped.
    (HINTS: remember that A ⊂ B is defined as ∀x (x ∈ A → x ∈ B) and so of course also B ⊂ A is defined as ∀x (x ∈ B → x ∈ A) and remember that the A=B is defined as ∀x(x ∈ A ↔ x ∈ B). Too many hints now!)
  6. Extra-credit. Prove in ZF there is no set of all sets. Hint: use the comprehension schema, where the property φ is ¬ x ∈ x. This will allow you to find a contradiction with the claim that there is a set of all sets. You must figure out how to say there is a set of all sets, though!
  7. Extra-credit. Prove the axiom of pair, using the other axioms and the weak axiom of pair.
In case this is helpful, here are our latest versions of the handouts (you'll just need the first two for these problems):
November 2
Homework: Prove the following, keeping as resources the propositional logic and the specified modal system.
  • In M: If {}|-- (φ → ψ) then {} |-- ([]φ → []ψ)
  • In S4: ([]φ↔[][]φ)
  • In S4: (<>φ↔<><>φ)
  • In S5: ([]φ↔<>[]φ).
For these problems and the next, you will find they are much easier if you allow yourself two rules sometimes added to natural deduction systems. These are: (1) Contraposition, which allows one to assert that (¬ψ→¬φ) given (φ → ψ); and (2) a relaxing of double negation that allows one to remove any double negation from anywhere in a formula, or insert any double negation anywhere in a formula as long as the result is well formed. Also helpful in many of these problems is the chain rule.

You may at any time replace <> with ¬[]¬, and vice versa. Your justification can be "definition" or "def." Note also that ¬<>¬ is thus ¬¬ [] ¬¬, so with DN* twice, you have [].

Our rule that lets you go from {}|- φ to {}|- []φ is called "necessitation" or "nec."

In case you need these to remember the axioms and systems, they're on page 2 of our handout with Arithmetic and modal axioms.
November 2 - November 6
Semantics of modal propositional logic. <>Completeness of some modal propositional logics. We can also discuss some interesting philosophical applications of modal logic.
November 4
Homework:
  • Show that S5 is equivalent to the combination of Brouwer and S4. You can do this by showing that from the axioms of Brouwer ((M1), (M2), and (M3)) and S4 (axiom (M4)) you can derive the additional axioms of S5 (in this case, just (M5)). Then show that from the axioms of S5 ((M1), (M2), and (M5)) you can derive the additional axioms of Brouwer and S4 (that is, (M3) and (M4)).

    I was asked for hints. If you are crying uncle, here are some hints.
November 9
In class, we'll discuss other modal logics some more, and then introduce the idea of quantified modal logic.

A little homework: Descartes says in Meditation VI that
To commence this examination accordingly, I here remark, in the first place, that there is a vast difference between mind and body, in respect that body, from its nature, is always divisible, and that mind is entirely indivisible.
How would you translate into our modal logic with quantifiers: "the body, from its nature, is always divisible" and "mind is entirely indivisible"?

Extra-credit: in case you want to try some more problems, here are three.
  1. Prove in system M that []A |-- [](B → A)
  2. Prove in system M that {} |-- (([]A ^ <>B) → <>(A ^ B)). This one can be proved directly using just axioms, but it might be faster if you use the modal instantiation methods we introduced. For that, remember, you can do possibility instantiation to an indefinite instance, and necessity instantiation to any world; we indicate worlds with an index on each proposition in a formula (such as "p" for indefinite, or "1" for world 1).
  3. Here were some of the deontic axioms we considered:
    • D1 ([]φ → <>φ)
    • D2 ([](φ ^ ψ) ↔ ([]φ ^ []ψ))
    • D3 [](φ v ¬φ)
    • D4 ([][]φ → []φ)
    • D5 []([]φ → φ)
    • D6 ([]φ → ((φ → []ψ) → []ψ))
    In this system, and any propositional logic rules (but there is no rule like necessitation), prove the following argument is valid, so that our robot programmers can know they saved the day. Shakey the robot reasons as follows:
    One ought to save Tommy. One ought not to endanger Timmy. If one is to save Tommy, one ought to guard the cliff. If one is not to endanger Timmy, one ought to hide the knives. So, one ought to both guard the cliff and hide the knives.
11 November
Read: before class read "Reference and Modality" by Quine.
13 November
We will continue our discussion of identity and essentialism.
16 November
Transworld identity.

Read: before class read "Identity through possible worlds--some questions" by Roderick Chisholm.
18 November
Some last thoughts about modal logic. Then: Review 1.
20 November
Review 2. Let me know what you'd like to review. Things we could discuss include:
  1. Definite descriptions. If I deny that The Present King of America is tall, is he then short?
  2. Using multiple quantifiers. Everyone likes someone whom no one else likes.
  3. Natural deduction theory version of set theory.
  4. Cantor's two theorems for cardinalities.
  5. Cantor's antinomy.
  6. Axioms of propositional logic.
  7. Proving the deduction theorem in propositional logic
  8. Proving consistency of propositional logic
  9. Proving Kalmar's Lemma in propositional logic
  10. Proving completeness of propositional logic
  11. Arithmetic axioms
  12. ZF axioms for set theory. (PS: how do we -- hopefully -- avoid Cantor's antinomy in ZF?)
  13. Modal system for propositional logic.
  14. Conundrums about quantified modal logic.
23 November
Final exam in class. Some things to study:
  • Any questions from the midterm are fair game.
  • Using the axioms of the propositional and quantified axiomatic logic.
  • Using the Peano axioms.
  • Proving Cantor's theorem in natural set theory.
  • Proving some simple things in set theory, both with and without ZF axioms.
  • Applying and explaining concepts like: complete, consistent, provable.
  • Proving basic sentences in various modal propositional systems.
  • Why might we need modal logic? Obviously to discuss modality, but are there any another motivations? (E.g., what's wonky about "If Ben were a turtle then Ben would be an invertebrate"? Or: what's worrisome about Aristotle's maybe-definition, "humans are rational animals"?)
  • Conceptual issues in modal logic:
    • What are some challenges to creating a model for a modal logic?
    • Why and when would one prefer a Kripke model over a Leibniz model?
    • Explain what an opaque referential context is (a la Quine). Why does it seem a problem? Reference Leibniz's Law in your explanation. How do you think we should solve it.
    • An opinion piece: do you think we should do away with modality, as Quine suggests? Do you think there are essential properties? Feel free to cast aspersions on your enemies.
26 November
Review of the final exam in class. I'll record it.
November 30 - December 4
Extra-credit online session.

Hi, team, sorry for the delay. I wanted to spend this week doing a proof of Arrow's Theorem (an important result in economics), which is fantastic because it just uses natural deduction system first order logic, but I was wrong to think I could reduce the proof to something manageable in a few hours. It'll take a couple weeks to get through all the definitions that Arrow introduces. Sorry--I had an intuition I could simplify the proof quickly but I was wrong.

Let's do this for our extra-credit. If you like, answer any question on the final exam that you did not answer. Send a pdf scan to me. I'll grade and return my comments, and you'll get extra credit. Do this before midnight on Friday! (If you can't remember which one's you answered, write me and I'll tell you.)

Here is our test in a pdf.

Thanks. I hope you're not disappointed! I did want to do something new, but I don't want to drown you and me with extra work.

I'll have office hours Friday, so that you can check in with me about any questions you may have.
December 4
Office hours at from 10:00 to 11:30 am.