What is an argument?
A sequence of propositions
What is a valid argument?
A sequence of statements such that each statement is either a premise or follows from previous statements by rules of inference
What is a proof?
A valid argument that establishes the truth of a statement
What is a theorem?
An important statement that can be proven
What is a lemma?
A result which is needed to prove a theorem
What is a corollary?
A result which follows directly from a theorem
What is a conjecture?
A statement that is being proposed to be true
What does ∀x,y. x>y → x^2>y^2 mean?
For all positive real numbers x and y, if x>y, then x^2>y^2
How do you start a trivial proof of p→q?
If q is true
How do you start a vacuous proof of p→q?
If p is false
What is a direct proof of p→q?
Assume p then show q
What is a proof by contraposition of p→q?
Assume ¬q and show ¬p
What is the first statement in the direct proof of “If n is an odd integer, then n^2 is odd”?
Assume n is odd
What is the first statement in the proof by contraposition of “If n is an odd integer, then n^2 is odd”?
Assume n is even, show n^2 is even
How do you prove a statement of the form p↔q?
Prove p→q and q→p are both true
How do you prove ∀x. P(x) is false by counter example?
Find an example x for which P(x) is false
How does a constructive existence proof work?
Try to find an explicit value of c, for which P(c) is true. Then ∃x.P(x) is true by existential generalisation
Give an example of a constructive existence proof
Show that there is a positive integer that can be written as the sum of cubes of
positive integers. eg. 1729 is such a number since 1729 = 10³ + 9³
How does a nonconstructive existence proof work?
Assume no c exists which makes P(c)
true and derive a contradiction
How do you show there exists irrational numbers x and y such that xʸ is rational using a nonconstructive existence proof?
Find a number (like √2) that you know is irrational then set x and y both equal to that number and write xʸ. If xʸ is then rational, you have the two irrational numbers. But you don’t know if it is rational. If it is irrational, then you can set the new number (√2^√2) equal to x and the original number (√2) equal to y, therefore by the power laws the resulting number is raitonal (2).
What is modus ponens on p→q?
p∴q
What is modus tollens on p→q?
¬q∴¬p
