Mathematical Proof Flashcards
Definition
A carefully reasoned arguments to convince a skeptical listener that a given statement is true.
∃
Exists
∀
For all
⇔
If and only if
Universal Statement
Certain property is true for all elements in a set (all positive number are greater than zero)
Conditional Statement
One thing is true, then the other has to be true (if 378 is divisible by 18, then 378 is divisible by 6)
Existential Statement
Given a property may or not be true, there is a least one thing for a property that is true (there is a prime number that is even).
Universal Conditional Statements
Statement that is both universal and conditional (for all animals a, if a is a dog, then a is a mammal)
Can be rewritten in ways that make it appear purely conditional or universal (if a is a dog, then a is a mammal ; all dogs are mammals).
Similar to an if statement in a for loop.
Universal Existential Statements
First part says that a certain property is true for all objects of a given type (universal), and is the second part asserts the existence for something (existential).
Every real number - universal because it applies universally.
Has an additive inverse - asserts the existence than an additive inverse exists.
Existential Universal Statements
First part asserts that a certain object exists, second part says that that the objects satisfies a certain property for all things of a certain kind.
There is a positive integer (existential because it confirm the existence of something) that is less than or equal to every positive integer (universal, all things of a certain kind).
Additive Inverse
What you add to a number to get zero.
Proving Universal Statements
Generalisation from the generic particular ; choose an example, write an equation, combine the equation with the example. If there are two numbers which have the same equation, you must create difference otherwise they will mean the same thing.
EXAMPLES ARE PARTICULAR BUT ARBITRARILY CHOSEN. (Suppose that x is a particular but arbitrarily chosen integer)
Contradiction
Use proof by contradiction to show that there is no greater integer
Suppose for a proof by contradiction that there exists a greatest number n
But n + 1 > n, n + 1 is also an integer
So n is not the greatest integer
Contraposition
If p(x) then Q(x) then not P(x) is not Q(x)
Induction
Question like this:
Prove by induction that a property holds for every natural number n.
For every natural number n: 0 + 1 + … + n = n(n+1)/ 2 (a rule, n(n+1) adds up all the numbers between 0 and n twice over whilst 2 divides it.
Base Case gives you something to define it:
Base Case: n = 0
LHS = 0 (because n is equal to 0)
RHS = 0*1/ 2=0 (because putting 0 into n(n+1) gives zero.
INDUCTIVE STEP:
Suppose that the property holds for n = m then it holds for n = m+1.
Suppose that 1 + 2 + … + m = m(m+1)/2, then we need to prove that 1 + 2 … m+(m+1)=(m+1)(m+1)+1 / 2
LHS = 1 + 2 + m + (m+1) = m(m+1) / 2 + (m+1) (because of the initial equation)
= m(m+1) + 2(m+1) / 2 = (m+1)(m+2) / 2
In other words: n can by anything
Base case = n=0
Induction Step = property holds for n = m, but what about m+1 (carries forward). M is a specific number (particular). We are adding m+1, not replacing m.
Strong Induction
Applies to all the numbers in-between.
n…m…m+1 ; between n and m+1 etc.
Strong Induction: applies to all below as well.
Every natural number n>= 2, is a prime number or a product of primes
Base Case: Take = 2. Then n is a prime number
Inductive Step: Assume property holds for n = m so every number i such that 2 <= i <= m is a prime or a product of primes. Now consider n = m + 1.
m+1 = kl such that k < m+1 and l<m+1
k > 1 and l > 1, leading to k >= 2 and l >= 2
k is a prime or product of primes and l is a prime or product of primes.
-> kl is a product of primes.
Constructive Proof
The very basic proof/ giving an example that something is correct.
Prove that two products of an even number both can be prime.
10 = 7 + 3 etc.
Exhaustion Proof
Proving with limited numbers.
Prove that two products of an even number both can be prime for all numbers less than 14.
10 = 7 + 3
12 = 7 + 5
Proof is done.
Proving even
Try to make something equate to 2(…), making sure that the last thing done is the multiplication of 2, as multiplying an integer by 2 makes it even.
Direct Proof
Using a statement to prove something.
Suppose that x is a particular but arbitrarily chosen integer.
