Mathematical Proofs and Definitions

Axiom

Statement that is considered to be self evident and assumed to be true without any proof or demonstration.

Theorem

Statement that has been proved on the basis of previously established statements, such as other theorems and generally accepted statements such axioms.

Corollary

Statement that follows with little or no proof required from an already proven statement.

Lemma

Mathematical result that is useful in establishing the truth values of some other results.

Trivial proof

The statement on the proof is trivial if we can prove that Q(x) is true for all x in S, then for all x in S, p(x) => q(X) is true regardless of the truth value of p(x).

Vacuous proof

The statement on the proof is vacuous if we can prove that P(x) is true for all x in S, then for all x in S, p(x)=>q(x) regardless of the truth value of q(x).

Direct proof

In a direct proof you assume the hypothesis P and give a direct combination of established facts, existing lemmas and/or theorems to show the conclusion q holds.

Contrapositive proof

A proof by contrapositive of an implication (Let x in S , p(x) => q(x) ) is a DIRECT proof of the contrapositive statement.

Even integer

Is an integer of the form n=2k for some k in Z.

Odd integer

Is an integer of the form n=2k+1 for some k in Z.

Proof by cases

Mathematical proof in which the statement to be proved is split into a finite number of cases and each type of case is checked to see if the proposition in question holds.

Of the same parity

Two integers x and y are said to be of the same parity if x and y are both even or x and y are both odd.

Of opposite parity

Two integers x and y are said to be of opposite parity if one of them is odd and the other is even.

WOLOG

Is a term used in proofs to indicate that an assumption is being made that doesn’t introduce new restrictions to the problem.

A divides B (integers)

Given two integers a and b with a ≠ 0, we say a divides b if there is an integer c such that b = ac.

Multiple/Divisor

A divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some other integer to produce n. In this case one says also that n is a multiple of m. An integer n is divisible by another integer m if m is a divisor of n; this implies dividing n by m leaves no remainder.

Congruent modulo n

For integers a and b and n ≥ 2, we say that a is congruent to b modulo n, written a ≡ b (mod n), if n|(a-b)

Absolute value

Absolute value is defined as a(inverse) x in R, |x|={x, -x if x ≥ 0, x < 0}

Set union

Given two sets A and B, the set union of A and B is defined as : AUB = {x in U| x in A or x in B}

Set intersection

The intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.

Relative complement

The relative complement of A with respect to a set B, also termed the difference of sets A and B, written B ∖ A, is the set of elements in B but not in A.

Complement

The complement of a set A refers to elements not in A.

Cartesian product

Is defined as AxB= { (x,y) | x in A and y in B}

Counterexample

If the statement “ a x in S, R(x)” is false, then there exists some element x in S for which R(x) is false such an element x is called counterexample of the statement “a x in S, r(X)”

Proof by contradiction:

Is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition. It starts by assuming that the opposite conlusion is true, and then shows that such an assumption leads to a contradiction.

P=>Q

-(P=>Q) === P=>(-Q)

-(PóQ)

=== (P AND (-Q)) OR (Q AND (-P))

Let x ∈Z. Then x^2 is even if and only if x is even.

Proof by Contrapositive

Proof Assume that x is even. Then x =2a for some integer a. Therefore, x2 =(2a)2 =4a2 =2(2a2). Because 2a2 ∈Z, the integer x2 is even. For the converse, assume that x is odd. So x =2b+1, where b ∈Z. Then x2 =(2b+1)2 =4b2 +4b+1=2(2b2 +2b)+1. Since 2b2 +2b is an integer, x2 is odd.

(The Triangle Inequality) For every two real numbers x and y, |x + y|≤| x|+|y|.

108 Chapter 4 More on Direct Proof and Proof by Contrapositive

Proof Since|x + y|=| x|+|y|if either x or y is 0, we can assume that x and y are nonzero.We proceed by cases. Case 1.x> 0 and y > 0. Then x + y > 0 and |x + y|=x + y =| x|+|y|. Case 2.x< 0 and y < 0. Since x + y < 0, |x + y|=− (x + y)=(−x)+(−y)=| x|+|y|. Case 3. One of x and y is positive and the other is negative. Assume, without loss of generality, that x > 0 and y < 0. We consider two subcases. Subcase 3.1.x+ y ≥0. Then |x|+|y|=x +(−y)= x − y > x + y =| x + y|. Subcase 3.2.x+ y < 0. Here |x|+|y|=x +(−y)= x − y > −x − y =− (x + y)=| x + y|. Therefore,|x + y|≤| x|+|y|for every two real numbers

For sets A, B and C,

(1) Commutative Laws (a) A∪ B = B ∪ A (b) A∩ B = B ∩ A

(2) Associative Laws (a) A∪(B ∪C)=(A∪ B)∪C (b) A∩(B ∩C)=(A∩ B)∩C

(3) Distributive Laws (a) A∪(B ∩C)=(A∪ B)∩(A∪C) (b) A∩(B ∪C)=(A∩ B)∪(A∩C)

 (4) De Morgan’s Laws (a)complement( A∪ B )= complement(A)∩ comp(B) (b) A∩ B = A∪ B.

The real number√2 is irrational

Proof Assume,tothecontrary,that√2isrational.Then√2=a/b,wherea,b ∈Zandb =0. We may further assume that a/b has been expressed in (or reduced to) lowest terms.

Then 2=a2/b2; soa2 =2b2. Since b2 is an integer, a2 is even. By Theorem 3.12, a is even.Soa =2c,wherec ∈Z.  Thus,(2c)2 =2b2 andso4c2 =2b2.Therefore,b2 =2c2. Becausec2 isaninteger,b2 iseven,whichimpliesbyTheorem3.12that b is even. Since a and b are even, each has 2 as a divisor, which is a contradiction since a/b has been reduced to lowest terms.