Mathematical Proofs

Front 1

Set

Back 1

A set is a collection of objects.

Front 2

Elements

Back 2

The objects that make up a set are called its elements (or members). If a is an element of the set A, then we write a ∈ A; if a does not belong to A, then we write a ∉ A.

Front 3

Empty, Null, or Void Set

Back 3

There is only one set that contains no elements, and it is called the empty set (or sometimes the null set or void set). The empty set is denoted by ∅. We also write ∅ = { }.

Front 4

Natural Numbers

Back 4

We use N to denote the set of all positive integers (or natural numbers); that is, N = {1, 2, 3, . . .}.

Front 5

Integers Numbers

Back 5

The set of all integers (positive, negative, and zero) is denoted by Z. So Z = {. . . ,−2,−1,0, 1, 2, . . .}.

Front 6

Real Numbers

Back 6

The set of real numbers is denoted by R, and the set of positive real numbers is denoted by R+.

Front 7

Rational Numbers

Back 7

Is a real number that can be expressed in the form of m/n for m,n ∈ Z and n ≠ 0 which is denoted as Q.

Front 8

Irrational Numbers

Back 8

Is a real number that is not a rational number which is denoted as I.

Front 9

Cardinal Number of Cardinality

Back 9

For a set S, we write |S| to denote the number of elements in S.

Examples:

- A = {1,2,{4,6}}; |A| = 3

- B = {1,3,∅,8}; |B| = 4

- |∅| = 0

Front 10

Complex Numbers

Back 10

A complex number is a number of the form a + bi where a,b ∈ R and i = √-1 which is denoted as C.

Front 11

Subset

Back 11

A set A is called a subset of a set B if every element of A also belongs to B. If A is a subset of B, then we write A ⊆ B. If A, B and C are sets such that A ⊆ B and B ⊆ C,then A ⊆ C.

Front 12

Proper Subset

Back 12

A set A is a proper subset of a set B if A ⊆ B but A ≠ B. If A is a proper subset of B, then we write A ⊂ B. For example, if S = {4, 5, 7} and T = {3, 4, 5, 6, 7}, then S ⊂ T . (Although we write A ⊂ B to indicate that A is a proper subset of B, it should be mentioned that some prefer to write A ⊆ / B to indicate that A is a proper subset of B. Indeed, there are some who write A ⊂ B, rather than A ⊆ B, to indicate that A is a subset of B. We will follow the notation introduced above, however.)

Front 13

Union

Back 13

The union of two sets A and B, denoted by A ∪ B, is the set of all elements belonging to A or B, that is:A ∪ B = {x : x ∈ A or x ∈ B}.

Front 14

Difference between two sets

Back 14

The difference A − B of two sets A and B (also written as A \ B by some mathematicians) is defined as A − B = {x : x ∈ A and x ∉ B},

Front 15

Intersection

Back 15

The intersection of two sets A and B is the set of all elements belonging to both A and B. The intersection of A and B is denoted by A ∩ B. In symbols, A ∩ B = {x : x ∈ A and x ∈ B}.

Front 16

Disjoint

Back 16

If two sets A and B have no elements in common, then A ∩ B = ∅ and A and B are said to be disjoint. The sets Q and I are also disjoint.

Front 17

Complement

Back 17

Suppose that we are considering a certain universal set U, that is, all sets being discussed are subsets of U. For a set A, its complement is A (Bar) = U − A = {x : x ∈ U and x ∉ A}.

Front 18

Collection of Unions

Back 18

Front 19

Collection of Intersections

Back 19

Front 20

Index Set

Back 20

Front 21

Pairwise Disjoint

Back 21

A collection S of subsets of a set A is called pairwise disjoint if every two distinct subsets that belong to S are disjoint. For example, let A = {1, 2, . . . , 7}, B = {1, 6}, C = {2, 5}, D = {4, 7} and S = {B, C, D}. Then S is a pairwise disjoint collection of subsets of A since B ∩ C =B ∩ D = C ∩ D = ∅.

On the other hand, let A = {1, 2, 3}, B = {1, 2}, C = {1, 3},D = {2, 3} and S = {B , C , D }. Although S is a collection of subsets of A and B ∩ C ∩ D = ∅, the set S is not a pairwise disjoint collection of sets since B ∩ C = ∅,for example. Indeed, B ∩ D and C ∩ D are also nonempty.

Front 22

Cartesian Product

Back 22

Front 23

Negation

Back 23

The negation of a statement P is the statement not P and is denoted by ∼P. Although ∼P could always be expressed as:

- It is not the case that P.

Front 24

Disjunction

Back 24

The disjunction of the statements P and Q is the statement P or Q and is denoted by P ∨ Q. The disjunction P ∨ Q is true if at least one of P and Q is true; otherwise, P ∨ Q is false. Therefore, P ∨ Q is true if exactly one of P and Q is true or if both P and Q are true.

Front 25

Conjunction

Back 25

The conjunction of the statements P and Q is the statement: P and Q and is denoted by P ∧ Q. The conjunction P ∧ Q is true only when both P and Q are true; otherwise, P ∧ Q is false.

Front 26

Implication

Back 26

A statement formed from two given statements in which we will be most interested is the implication (also called the conditional). For statements P and Q, the implication(or conditional) is the statement "If P, then Q" and is denoted by P ⇒ Q. In addition to the wording “If P, then Q,” we also express P ⇒ Q in words as P implies Q.

The implication can be also written as: P ⇒ Q ≡ (∼ P) ∨ Q.

Front 27

Biconditional

Back 27

For statements (or open sentences) P and Q, the conjunction(P ⇒ Q) ∧ (Q ⇒ P)of the implication P ⇒ Q and its converse is called the biconditional of P and Q and is denoted by P ⇔ Q. The biconditional P ⇔ Q is often stated as P is equivalent to Q.

Front 28

Logical Connectives

Back 28

The symbols ∼, ∨, ∧, ⇒ and ⇔ are sometimes referred to as logical connectives. From given statements, we can use these logical connectives to form more intricate statements.For example, the statement (P ∨ Q) ∧ (P ∨ R) is a statement formed from the given statements P, Q and R and the logical connectives ∨ and ∧.

Front 29

Compound Statement

Back 29

A compound statement is a statement composed of one or more given statements (called component statements in this context) and at least one logical connective. For example, for a given component statement P, its negation ∼P is a compound statement.

Front 30

Logically Equivalent

Back 30

Let R and S be two compound statements involving the same component statements. Then R and S are called logically equivalent if R and S have the same truth values for all combinations of truth values of their component statements. If R and S are logically equivalent, then this is denoted by R ≡ S. Hence P ⇒ Q and (∼ P) ∨ Q are logically equivalent and so P ⇒ Q ≡ (∼ P) ∨ Q.

Front 31

Logical Equivalence: Commutative Laws

Back 31

(a) P ∨ Q ≡ Q ∨ P

(b) P ∧ Q ≡ Q ∧ P

Front 32

Logical Equivalence: Associative Laws

Back 32

(a) P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R
(b) P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R

Front 33

Logical Equivalence: Distributive Laws

Back 33

(a) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
(b) P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

Front 34

Logical Equivalence: DeMorgan's Laws

Back 34

(a) ∼ (P ∨ Q) ≡ (∼P) ∧ (∼Q)

(b) ∼ (P ∧ Q) ≡ (∼P) ∨ (∼Q)

Front 35

Quantification

Back 35

Quantification is a method for converting open sentences into statement. For example, let P(x) be an open sentence over a domain S. Adding the phrase “For every x ∈ S” to P(x) produces a statement called a quantified statement.

Front 36

Universal Quantifier

Back 36

The phrase “for every” is referred to as the universal quantifier and is denoted by the symbol ∀. Other ways to express the universal quantifier are “for each”and “for all.” This quantified statement is expressed in symbols by ∀x ∈ S, P(x) and is expressed in words by "For every x ∈ S, P(x)".

Front 37

Existential Quantifier

Back 37

Each of the phrases there exists, there is, for some and for at least one is referred to as an existential quantifier and is denoted by the symbol ∃. The quantified statement ∃x ∈ S, P(x)can be expressed in words by "There exists x ∈ S such that P(x)".

Front 38

Characterization

Back 38

Suppose that some concept (or object) is expressed in an open sentence P(x) over a domain S and Q(x) is another open sentence over the domain S concerning this concept. We say that this concept is characterized by Q(x) if ∀x ∈ S, P(x) ⇔ Q(x) is a true statement. The statement ∀x ∈ S, P(x) ⇔ Q(x) is then called a characterization of this concept. For example, irrational numbers are defined as real numbers that are not rational and are characterized as real numbers whose decimal expansions are nonrepeating. This provides a characterization of irrational numbers: A real number r is irrational if and only if r has a nonrepeating decimal expansion.

Front 39

Axiom

Back 39

A true mathematical statement whose truth is accepted without proof.

Front 40

Theorem

Back 40

A true mathematical statement whose truth can be verified is often referred to as a theorem, although many mathematicians reserve the word theorem for such statements that are especially significant or interesting.

Front 41

Corollary

Back 41

Is a mathematical result that can be deduced from, and is thereby a consequence of, some earlier result.

Front 42

Lemma

Back 42

Is a mathematical result that is useful in establishing the truth of some other result. Some people like to think of a lemma as a “helping result.”

Front 43

Trivial Proof

Back 43

Is a proof in which the conclusion of an implication is shown to be true without using the hypothesis.

Front 44

Vacuous Proof

Back 44

Let P(x) and Q(x) be open sentences over a domain S. Then ∀x ∈ S, P(x) ⇒ Q(x) is a true statement if it can be shown that P(x) is false for all x ∈ S (regardless of the truth value of Q(x)), according to the truth table for implication. Such a proof is called a vacuous proof of ∀x ∈ S, P(x) ⇒ Q(x).

In other words, the hypothesis of an implication is shown to be false.

Front 45

Direct Proof

Back 45

In a direct proof of P(x) ⇒ Q(x) for all x ∈ S, we consider an arbitrary element x ∈ S for which P(x) is true and show that Q(x) is true for this element x. To summarize then, to give a direct P(x) is true for an arbitrary element x ∈ S and show that Q(x) must be true as well for this element x.

Front 46

Contrapositive Proof

Back 46

For statements P and Q, the contrapositive of the implication P ⇒ Q is the implication (∼Q) ⇒ (∼P). For example, for P: 3 is odd and Q: 57 is prime, the contrapositive of the implication P ⇒ Q: "If 3 is odd, then 57 is prime" is the implication (∼P) ⇒ (∼Q): "If 57 is not prime, then 3 is even."

Front 47

Proof by Cases

Back 47

While attempting to give a proof of a mathematical statement concerning an element x in some set S, it is sometimes useful to observe that x possesses one of two or more properties. A common property which x may possess is that of belonging to a particular subset of S. If we can verify the truth of the statement for each property that x may have,then we have a proof of the statement. Such a proof is then divided into parts called cases, one case for each property that x may possess or for each subset to which x maybe long. This method is called proof by cases. Indeed, it may be useful in a proof by cases to further divide a case into other cases, called subcases.

Front 48

Negation of ∀ x ∈ S, P(x)

Back 48

~(∀ x ∈ S, P(x)) ≡ ∃ x ∈ S, ~P(x)

There exist x such that not P(X).

Front 49

Negation of ∃ x ∈ S, P(x)

Back 49

~(∃ x ∈ S, P(x)) ≡ ∀ x ∈ S, ~P(x)

For every x, not A(x)

Front 50

Negation of P(x) ⇒ Q(x)

Back 50

~(P(x) ⇒ Q(x)) ≡ P(x) ∧ ~Q(x)

P(x) and not Q(x)

Front 51

Proof by Contradiction

Back 51

In a proof by contradiction we assume, along with the hypotheses, the logical negation of the result we wish to prove, and then reach some kind of contradiction. That is, if we want to prove "If P, Then Q", we assume P and Not Q. The contradiction we arrive at could be some conclusion contradicting one of our assumptions, or something obviously untrue like 1 = 0.

This results in: P(x) ⇒ Q(x) ≡ P(x) ∧ ~Q(x) ⇒ Some Contradiction

Front 52

Relationship

Back 52

Let A and B be two sets. By a relation R from A to B we mean a subset of A × B. That is, R is a set of ordered pairs, where the first coordinate of the pair belongs to A and the second coordinate belongs to B. If (a, b) ∈ R, then we say that a is related to b by R and write a R b. If (a, b) ∉ R, then a is not related to b by R.

For the sets A = {x, y, z} and B = {1, 2}, the set R = {(x, 2), (y, 1), (y, 2) is a subset of A × B and is therefore a relation from A to B.

Front 53

Reflexive

Back 53

A relation R defined on a set A is called reflexive if x R x for every x ∈ A. That is, R is reflexive if (x, x) ∈ R for every x ∈ A.

Let S = {a, b, c} and consider the following six relations defined on S:

R1 = {(a, b), (b, a), (c, a)}

R2 = {(a, b), (b, b), (b, c), (c, b), (c, c)}

R3 = {(a, a), (a, c), (b, b), (c, a), (c, c)}

R4 = {(a, a), (a, b), (b, b), (b, c), (a, c)}

R5 = {(a, a), (a, b)}

R6 = {(a, b), (a, c)}.

The relation R1 is not reflexive since (a, a) ∉ R1, for example. Since (a, a) ∉ R2, itfollows that R2 is not reflexive either. Because (a, a), (b, b), (c, c) ∈ R3, the relation R3is reflexive. None of the relations R4, R5, R6 are reflexive.

Front 54

Symmetric

Back 54

A relation R defined on a set A is called symmetric if whenever x R y, then y R x for all x, y ∈ A. Hence for a relation R on A to be “not symmetric,” there must be some ordered pair (w, z) in R for which (z, w) ∉ R. Certainly, if such an ordered pair (w, z) exists, then w = z.

Front 55

Transitive

Back 55

A relation R defined on a set A is called transitive if whenever x R y and y R z, then x R z for all x, y, z ∈ A. Notice that in this definition, it is not required that x, y and z be distinct. Hence for a relation R on A to be “not transitive,” there must exist two ordered pairs (u, v) and (v, w) in R such that (u, w) ∉ R. If this should occur, then necessarily u = v and v = w (although perhaps u = w).

Front 56

Equivalence Relation

Back 56

A relation R on a set A is called an equivalence relation if R is reflexive, symmetric and transitive. Of course then, the equals relation R defined on Z by a R b if a = b is an equivalence relation on Z.

Front 57

Equivalence Class

Back 57

For an equivalence relation R defined on a set A and for a ∈ A, the set [a] = {x ∈ A : x R a} consisting of all elements in A that are related to a, is called an equivalence class, in fact, the equivalence class containing a since a ∈ [a] (because R is reflexive). Loosely speaking, then, [a] consists of the “relatives” of a.

Front 58

Function

Back 58

Let A and B be nonempty sets. By a function f from A to B, written f: A → B, we mean a relation from A to B with the property that every element a in A is the first coordinate of exactly one ordered pair in f.

Front 59

Domain of a Function

Back 59

Let A and B be nonempty sets. For the function f: A → B, the set A in this case is the domain of f, denoted by dom(f).

Front 60

Codomain of a Function

Back 60

Let A and B be nonempty sets. For the function f: A → B, the set B is called the codomain of f.

Front 61

Image (Mapping) of a Function

Back 61

If (a, b) ∈ f, then we write b = f(a) and refer to b as the image of a. Sometimes f is said to map a into b. Indeed, f itself is sometimes called a mapping.

For a function f : A → B and a subset C of A, the image f (C) of C is defined as f (C) = {f (x) : x ∈ C}.

Front 62

Range of a Function

Back 62

The set range(f) = {b ∈ B : b is an image under f of some element of A} = {f(x) : x ∈ A} is the range of f and consists of the second coordinates of the elements of f.

Front 63

The Set of All Functions from A to B

Back 63

Front 64

One-to-one Function

Back 64

We now consider two important properties that a function may possess. A function f from a set A to a set B is called one-to-one or injective if every two distinct elements of A have distinct images in B. In symbols, a function f : A → B is one-to-one if whenever x, y ∈ A and x ≠ y, then f(x) ≠ f(y). Thus, if a function f: A → B is not one-to-one, then there exist distinct elements w and z in A such that f (w) = f (z).

Front 65

Injective Function

Back 65

Injective functions are functions that are one-to-one.

Front 66

Onto Function

Back 66

A function f : A → B is called onto or surjective if every element of the codomain B is the image of some element of A. Equivalently, f is onto if f(A) = B.

Front 67

Bijective Function

Back 67

A function f: A → B is called bijective or a one-to-one correspondence if it is both one-to-one and onto. From what we mentioned earlier, if a function f: A → B is bijective and A and B are finite sets, then |A| = |B|. Perhaps it is also clear that if A and B are finite sets with |A| = |B|, then there exists a bijective function f: A → B. A bijective function from a set A to a set B creates a pairing of the elements of A with the elements of B.

Front 68

Strong Principle of Mathematical Induction

Back 68

Front 69

Mathematical Induction

Back 69

Front 70

Set Properties: Commutative Laws

Back 70

(a) A ∪ B = B ∪ A

(b) A ∩ B = B ∩ A

Front 71

Set Properties: Associative Laws

Back 71

(a) A ∪ (B ∪ C) = (A ∪ B) ∪ C

(b) A ∩ (B ∩ C) = (A ∩ B) ∩ C

Front 72

Set Properties:Distributive Laws

Back 72

(a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

(b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Front 73

Set Properties: DeMorgan's Laws

Back 73