1.7 Introduction to Proofs Flashcards
Proofs
A valid argument that establishes the truth of a mathematical statement
What is used to prove a statement
Axioms
Definitions
Previously proved results
Rules of inference
Axioms
Statements that are assumed to be true
Lemma
A less important theorem that is helpful in the proof
Corollary
A theorem that can be established directly from a proven theorem
Conjecture
A statement that is being proposed to be a true statement.
When does a conjecture become a theorem
When proof of a conjecture is found
Types of proof
Direct proof
Proof by contraposition
Proof by contradiction
Proof by induction
Direct proof
p->q
1.Assume p
2.Use axioms, definitions…
3.Show q
For ∀(x)P(x) in direct proof
Let x be an arbitrary value in the domain, show P(x)
Steps to prove ∃(x)P(x) (direct proof)
Build, construct, exhibit a value in the domain, verify p(x)
Proof by contraposition (contrapositive)
~q->~p
1. Assume ~q
2. Prove ~p
3. Conclude p->q
Proof by contradiction
- Assume the result to be false
- Deduce a contradiction
Proof of equivalence
To prove p↔q, show p->q and q->p
Definition of rational numbers
Vacuous Proof
p->q can be proven when we know that p is false
Properties of odd integers
n = 2k+1
The product and division of two odd integers is odd
The addition and subtraction of two odd integers is even
Properties of even integers
n = 2k
The product, division, addition and subtraction of two even integers is even
How to prove that sqrt(2) is irrational
Use proof by contradiction
Assume it is rational. Which means sqrt2 = a/b, b does not equal zero, a&b have no common factor(meaning they are in their lowest form)
Find that a and b are both even, meaning they are divisible by 2, hence a contradiction.
