# Mathematical Proofs and Definitions

Classified in Mathematics

Written at on English with a size of 6.43 KB.

## 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.