Introduction to Proofs Flashcards
the proofs of theorems designed for human
consumption are almost always
informal proofs
is a statement that can be shown to be true
theorem
Less important theorems sometimes are called
propositions
Theorems can also be referred to
as
facts or results
We demonstrate that a theorem is true
with a
proof
The statements used in a proof can include
axioms (or postulates)
axioms (or postulates), which are
statements we assume to be true
In practice, the
nal step of a proof is usually just the
conclusion of the theorem
A less important theorem that is helpful in the proof of other results is called a
lemma
(plural lemmas or lemmata)
is a theorem that can be established directly from a theorem that has been proved
corollary
is a statement that is being proposed to be a true statement, usually on the basis of some partial
evidence, a heuristic argument, or the intuition of an expert
conjecture
A ____________________ of a conditional statement p → q is constructed when the first step is the assumption that p is true; subsequent steps are constructed using rules of inference, with the final step showing that q must also be true.
direct proof
The integer n is ______ if there exists an integer k such that n = 2k, and n is _____ if there exists an integer k such that n = 2k + 1. (Note that every integer is either even or odd, and no
integer is both even and odd.)
even, odd
Two integers have the _____________ when both are even or both
are odd; they have ________________ when one is even and the other is odd.
same parity, opposite parity
An integer a is a _________________ if there is an integer b such that a = b2
perfect square
Proofs of theorems of this type that are not direct
proofs, that is, that do not start with the premises and end with the conclusion, are called
indirect proofs.
An extremely useful type of indirect proof is known as
proof by contraposition
if we can show that p is false, then we have a proof, called a
vacuous proof, of the conditional statement p → q
We can also quickly prove a conditional statement p → q if we know that the conclusion
q is true
A proof of p → q that uses the fact that q is true is called a
trivial proof
The real number r is _________if there exist integers p and q with q = 0 such that r = p/q. / suppose to be through first = sign
rational
A real number that is not rational is called
irrational
Because the statement r ∧ ¬r is a contradiction whenever r is a proposition, we can prove that p is true if we can show that ¬p → (r ∧ ¬r) is true for some proposition r. Proofs of this
type are called
proofs by contradiction
a statement of the form ∀xP (x) is false, we need only find a
counterexample
