Jump to content

Mathematical Proof/Print version

From Wikibooks, open books for an open world


Mathematical Proof

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Mathematical_Proof

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

Cover

Venn diagram with three sets


Introduction to Set Theory

Objects known as sets are often used in mathematics, and there exists set theory which studies them. Although set theory can be discussed formally [1], it is not necessary for us to have such a formal discussion in this book, and we may not be interested in and understand the formal discussion in this stage.

Even if we do not discuss set theory formally, it is important for us to understand some basic concepts about sets, which will be covered in this chapter.

What is a set means

[edit | edit source]

A set may be viewed as a collection of well-defined, distinct objects (the objects can also be sets). Because of the vagueness of the term "well-defined", we do not regard this as the definition of set. Instead, we regard set as a primitive notion (i.e., concepts not defined in terms of previously-defined concepts). Other examples of primitive notions in mathematics include point and line.

We have mentioned that a set is a collection of well-defined, distinct objects. Objects in a set are called elements of the set. We write to mean that the element belongs to the set . If does not belong to , we write .

Example.

  • Consider the set of all even numbers . Elements of include (but are not limited to) -2, 0, and 4, i.e., .
  • The elements of the English alphabet (a set) are English letters.


Ways of describing a set

[edit | edit source]

There are multiple ways to describe a set precisely (in the sense that element(s) belonging to the set is (are) known precisely).

If a set consists of a small number of elements, then the listing method may be quite efficient. In the listing method, elements of a set are listed within a pair of braces ({}). In particular, just changing the listing order of elements does not change the set represented. For example, and are both representing the same set whose elements are 1 and 2. If the elements listed in the pair of braces are the same, the notations created by the listing method with different listing orders refer to the same set. Also, repeatedly listing a specific element in a set does not change the set represented. For example, and are both representing the same set whose elements are 1 and 2. In particular, if a set contains no elements, it can be denoted by based on the listing method or . This kind of set is called an empty set.

Another way to describe a set is using words. For example, consider the set of prime numbers less than 10. If we use the listing method instead, the set is represented by .

The third way to describe a set is advantageous when a set contains many elements. This method is called set-builder notation. There are three parts within a pair of braces in this notation. They are illustrated below with descriptions:

As one may expect, two sets are equal if and only if they contain the same elements. Equivalently, two sets and are equal if and only if each element of is also an element of and each element of is also an element of . This can be regarded as an axiom [2] or a definition. If two sets and are equal, we write . If not, we write .

In this book, when we are solving an equation, we are only considering its real solution(s) unless stated otherwise.

Example.

  • .
  • .
  • .
Clipboard

Exercise. Assume and are different elements. Is each of the following statements true or false?

1

The set contains no elements.

True.
False.

2

True.
False.

3

is a set.

True.
False.

4

.

True.
False.

5

.

True.
False.

6

.

True.
False.



Set cardinality

[edit | edit source]

If a set contains finite number of elements, it is called a finite set, and it is called an infinite set otherwise. If a set is finite, then its cardinality is its number of elements. For infinite sets, it is harder and more complicated to define their cardinalities, and so we will do this in the later chapter about set cardinalities. For each set , its cardinality is denoted by .

Example.

  • Let . Then, .
  • Let . Then, (not 3 since the element is listed repeatedly).
  • Let . Then, since there is no solution for (for real number ), and thus is an empty set.
  • Let . Solving , we have . Hence, and thus [3].

There are some special infinite sets for which notations are given, as follows:

  • is the set of all natural numbers (0 is not regarded as a natural number in this book).
  • is the set of all integers.
  • is the set of all rational numbers.
  • (nonstandard notation) is the set of all irrational numbers.
  • is the set of all real numbers.
  • is the set of all complex numbers.

In particular, we can use set-builder notation to express , as follows: .

Example.

Clipboard

Exercise. Use set-builder notation to express without using "" in the expression.

Solution

We can express like this: ().


Subsets

[edit | edit source]

Definition. (Subset) A set is a subset of a set (denoted by ) if each element of is also an element of .

Remark.

  • If is not a subset of , we denote it as .
  • Recall that two sets and are equal if and only if each element of belongs to and each element of belongs to . Using the notion of subsets, we can write if and only if and .

Example.

  • .
  • (e.g. but )
  • (e.g. but )
  • For each set , , i.e. each set is a subset of itself.
  • This is because each element of set is an element of .
  • For each set , .
  • If we want to prove this directly, there are some difficulties since does not contain any element. So, what is meant by "each element of "?
  • Under this situation, it may be better to prove by contradiction (a proof technique covered in the later chapter about methods of proof). First, we suppose on the contrary that . By the negation of the definition, there is at least one element of that is not an element of , which is false. This yields a contradiction, and thus the hypothesis is false (explanation will be provided later), i.e. is false.

Definition. (Proper subset) A set is a proper subset of a set (denoted by ) if is a subset of and .

Remark.

  • Similarly, if is not a proper subset of , we write .

Example.

  • For each nonempty set , since (shown previously) and if is a nonempty set.
  • .
  • .
  • and .
Clipboard

Exercise. Let .

1

Which of the following set(s) is a subset of ?

2

Select the set(s) of which the set is a subset.

3

Select the set(s) of which the set is an element.


We call some commonly encountered subsets of intervals. For each real number such that ,

  • (open intervals)
  • (half-open (or half-closed) intervals)
  • (half-open (or half-closed) intervals)
  • (closed intervals)

There are also some infinite intervals:

Note: is a shorthand of ( is a set).

Example.

  • .
  • .
  • since the element "1" of the set on LHS does not belong to the set on RHS.
  • .

Example.

  • The set of (real) solutions of is .
  • The set of (real) solutions of is . (Note: we cannot express this set as since it is required that for an interval .)
  • The set of (real) solutions of is .
Clipboard

Exercise.

Which of the following is (are) valid interval(s)?


Universal set and Venn diagram

[edit | edit source]

Definition. (Universal set) A universal set, denoted by , is a set containing all elements considered in a certain investigation.

Example.

  • If we are studying real numbers, the universal set is .

Definition. (Complement) The complement of a set that is a subset of the universal set , denoted by , is the set .

Example.

  • Let and . Then, . (Note: also.)
  • For each universal set , (since each element of does not belong to [4]) and (since there are no elements of that does not belong to ).
  • Let and . Then, since each element of does not belong to .
Clipboard

Exercise. Let the universal set be .

1

What is ?

2

What is ?

3

If the universal set is instead, . Which of the following can be (there may be more than one answer)?


A Venn diagram is a diagram showing all possible logical relationships between a finite number of sets. The universal set is usually represented by a region enclosed by a rectangle, while the sets are usually represents by regions enclosed by circles. The following is a Venn diagram.

In this diagram, if the white region represents set and the region enclosed by the rectangle represents the universal set, then the red region is the set .

However, the following is not a Venn diagram.

This is because there are not regions in which only the yellow and blue region intersect, and only the red and green region intersect, respectively. So, not all logical relationships between the sets are shown.

To show all logical relationships between four sets, the following Venn diagram can be used.

Set operations

[edit | edit source]

Similar to the arithmetic operations for real numbers which combine two numbers into one, the set operations combine two sets into one.

Union of sets

[edit | edit source]

Definition. (Union of sets)

A Venn diagram for union of two sets.

The union of a set and a set , denoted by , is the set .

Remark.

  • The "or" here is inclusive, i.e. if an element belongs to both and , it also belongs to .

Example.

  • .
  • .
  • .
  • .

Proposition. Let and be sets. Then,

  • (commutative law)
  • (associative law)
  • and

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

Remark.

  • Because of the associative law, we can write union of three (or more) sets without brackets. We will have similar results for intersection of sets, and so we can also write intersection of three (or more) sets without brackets.

Intersection of sets

[edit | edit source]

Definition. (Intersection of sets)

A Venn diagram for intersection of two sets.

The intersection of a set and a set , denoted by , is the set .

Remark.

  • If , we say that and are disjoint.

Proposition. Let and be sets. Then,

  • (commutative law)
  • (associative law)
  • and

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

Proposition. (Distributive laws) Let and be sets. Then,

  • (the "" is "distributed" to and respectively)

Relative complement

[edit | edit source]

Definition. (Relative complement)

A venn diagram for relative complement. If the region enclosed by the left and right circle represents and respectively, then the red region represents .

The relative complement of a set in a set , denoted by , is the set .

Remark.

  • if is the universal set. So, the complement of a set is also the relative complement of in .
  • The notation is read "B with A taken away".
  • We can see from the definition that

Example.

  • .
  • .
  • .
  • .
  • .
Clipboard

Exercise.

1

What is ?

2

What is ?

3

What is ?

4

Which of the following set(s) is (are) the set of all positive numbers?

5

What is ?

The universal set.


Proposition. Let and be sets. Then,

  • .
  • .
  • .
  • if and only if .
  • .
  • .

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

Theorem. (De Morgan's Laws) Let and be sets. Then,

Proof. (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram.

Example. Suppose the universal set is , and . Since , . On the other hand, since and , .

Clipboard

Exercise.

What is ?



Symmetric difference

[edit | edit source]

Definition. (Symmetric difference)

A Venn diagram illustrating symmetric difference.

The symmetric difference of sets and , denoted by , is the set .

Example.

  • .

Proposition. Let and be sets. Then,

  • (associative law)
  • (commutative law)
Clipboard

Exercise.

1

What is ?

2

What is ?

3

Does [5]? (Try to determine it using Venn diagrams. No mathematical proof is required at the moment.)

Yes.
No.



Power set

[edit | edit source]

Definition. (Power set) The power set of a set , denoted by , is the set of all subsets of . In set-builder notation, .

Remark.

  • Since for each set , is an element of each power set.
  • Also, since for each set , is an element of the power set .

Example.

  • . Its cardinality is 1.
  • If , then . Its cardinality is 2.
  • If , then . Its cardinality is 4.
  • . Its cardinality is 8.

Theorem. (Cardinality of power set of a finite set) Let be a finite set with cardinality . Then, .

Proof. Assume is a finite set with cardinality . Since each element of the power set is a subset of , it suffices to prove that there are subsets of . In the following, we consider subsets of with different number of elements separately, and count the number of subsets of each of the different types using combinatorics.

  • For the subset with zero element, it is the empty set, and thus there is only one such subset.
  • For the subsets with one element, there are subsets.
  • For the subsets with two elements, there are subsets.
  • ...
  • For the subsets with elements, there are subsets.
  • For the subset with elements, it is the set , and thus there is only one such subset.

So, the total number of subsets of is by binomial theorem.

Remark.

  • The proof method employed here is called direct proof, which is probably the most "natural" method, and most commonly used. We will discuss methods of proof in a later chapter.
  • There are alternative ways to prove this theorem.
Clipboard

Exercise. In each of the following questions, choose the power set of the set given in the question.

1

2

3

4


It is given that . In each of the following questions, choose the cardinality of the set given in the question.

1

4
8
16
32

2

0
1
2
4

3

1
2
4
8

4

1
2
4
8

5

1
2
4
8



Cartesian product

[edit | edit source]

Definition. (Cartesian product) The Cartesian product of sets and , denoted by , is .

Remark.

  • is the ordered pair (i.e. a pair of things for which order is important).
  • The ordered pair is used to specify points on the plane, and the ordered pair is called coordinates.
  • In particular, we have if .
  • (notation) We use to denote for each set .
  • We can observe that .

Example. Let and . Then,

  • .
  • .

Remark.

  • We can see from the above example that the Cartesian product is not commutative, i.e. it is not necessary for .
Clipboard

Exercise. Let .

1

What is (there may be more than one answer)?

2

What is ?


Similarly, we can define the Cartesian product of three or more sets.

Definition. (Cartesian product of three or more sets) Let be an integer greater than 2. The Cartesian product of sets is .

Remark.

  • (notation) We use to denote , where .


Logic

As discussed in the introduction, logical statements are different from common English. We will discuss concepts like "or," "and," "if," "only if." (Here I would like to point out that in most mathematical papers it is acceptable to use the term "we" when referring to oneself. This is considered polite by not commanding the audience to do something nor excluding them from the discussion.)

Truth and statement

[edit | edit source]

We encounter statements frequently in mathematics.

Definition. (Statement) A statement is a declarative sentence that is either true or false (but not both), and its truth value is true (denoted by ) or false (denoted by ).

Example. Consider the following sentences:

  1. The number 9 is even.
  2. .
  3. Mathematics is easy.
  4. How to solve ?
  5. Please read this book.
  • The sentence 1 and 2 above are statements (even if the sentence 1 is false).
  • The sentences 3, 4 and 5 are not statements, since they are not declarative sentences, and we cannot say whether each of them is true or false.
  • In particular, the sentence 3 is an opinion, the sentence 4 is a question, and the sentence 5 is a command. Thus, none of them are declarative.
Clipboard

Exercise.

Is the sentence "The 123th digit in the decimal expansion of is 3." a statement?

Yes.
No.


For the sentences that are not statements, there is a special type of sentences among them, namely open statement.

Definition. (Open statement) An open statement is a sentence whose truth value depends on the input of certain variable.

Remark.

  • Since the truth value may change upon input change, we cannot determine the truth value of an open statement (we cannot say it is (always) true or it is (always) false).

Example. Consider the sentence ( is read "such that").

  • This sentence is true when , and false otherwise.
  • This sentence is an open statement.

To express all possible combinations of truth values of some statements, we usually list them in a table, called a truth table.

Example. (Truth table for two statements) For two statements and , the truth table for them is as follows: and there are four possible combinations of truth values of and .

Example. (Truth table for three statements) For three statements , and , the truth table for them is as follows: and there are eight possible combinations of truth values of , and .

Remark.

  • In general, there are possible combinations of truth values of statements, since each statement has two possible truth values.
  • The truth table for three statement may seem to be complicated, and you may miss (or duplicate) some combinations in the truth table if you are not careful enough. Because of this, here is an advice for constructing such truth table:
  • for , write four 's and then four 's, from top to bottom;
  • for , write in this pattern from top to bottom: ;
  • for , write in this pattern from top to bottom: .


Conjunction, disjunction and negation

[edit | edit source]

In this section, we will discuss some ways (conjunction and disjunction) to combine two statements into one statement, which is analogous to Mathematical Proof/Introduction to Set Theory#Set operations, in which two sets are combined into one set. Also, we will discuss a way (negation) to change a statement to another one.

Conjunctions

[edit | edit source]

Definition. (Conjunction) The conjunction of statements and , denoted by , is a statement that is true when both and are true, and false otherwise.

Remark.

  • is read "P and Q", and the conjunction of the statements and can also be expressed by " and " directly.

Example. (Truth table for ) The truth table for (in terms of possible combinations of truth values of and [6]) is

  • We can see that is true only when both and are true, and false otherwise.

Disjunctions

[edit | edit source]

Definition. (Disjunction) The disjunction of statements and , denoted by , is a statement that is false when both and are false, and true otherwise.

Remark.

  • That is, is true when at least one of and is true, and false otherwise.
  • is read "P or Q", and the disjunction of the statements and can also be expressed by " or " directly.
  • The meaning of "or" in mathematics may be different from the meaning of "or" as an English word. For "or" in mathematics, it is used inclusively, i.e. or means or or both. However, as an English word, "or" may be used exclusively, i.e. or means or but not both. For example, when someone say "I will go to library or go to park this afternoon.", we interpret this as "I will either go to library, or go to park, but not both.".

Example. (Truth table for ) The truth table for is

  • We can see that is false only when both and are false, and true otherwise.

Negations

[edit | edit source]

Definition. The negation of a statement , denoted by , is a statement with truth value that is opposite to that of .

Remark.

  • is read "not P", and the negation of the statement can also be expressed by "not ", or "It is not the case that " directly.
  • Another common notation for the negation of a statement is .
  • We refer to process of expressing a negation of a statement as negating a statement.

Example. (Truth table for ) The truth table for is

  • We can see that always has the opposite truth value to that of .

To negate a statement, we usually add the word "not" into a statement, or delete it from a statement. For example, the negation of the statement "The number 4 is even." is "The number 4 is not even.", and the negation of the statement "The number 1 is not prime." is "The number 1 is not prime."

Clipboard

Exercise. Complete the following truth table:

Answer

  • We can observe that in some combinations of truth values of and , the truth values of and are different.
Clipboard

Exercise. Let be the statement "The number 3 is even.", and be the statement "The number is irrational."

Write down (in words) the negation of each of and without using the word "not".

Answer
  • The negation of can be "The number 3 is odd.".
  • The negation of can be "The number is rational."
Clipboard

Exercise. Let be the statement and be the statement .

(a) Is the statement true or false?

(b) Is the statement true or false?

(c) Is the statement true or false?

(d) Is the statement true or false?


Answer
  • First, we can see that both and are false.

(a) Since is false, the answer is true.

(b) Since is false, the answer is true.

(c),(d) Since and are both true, the answer for (c) and (d) are both true.



Conditionals

[edit | edit source]

Apart from the above ways to form a new statement, we also have another very common way, namely the "if-then combination". The statement formed using the "if-then combination" is called a conditional.

Definition. (Conditionals) The conditional of two statements and is the statement "If then .", denoted by . and are called the hypothesis and consequent of the conditional respectively. The conditional is false when is true and is false, and true otherwise.

Example. (Truth table for ) The truth table for is

  • We can observe that, in particular, even if the hypothesis is false, the conditional is true, by definition [7].
  • Another observation is that when the consequent is true, then no matter the hypothesis is true or false, the conditional must be true (see 1st and 3rd row).

To understand more intuitively why the conditional is always true when the hypothesis is false, consider the following example.

Example. Suppose Bob is taking a mathematics course, called MATH1001. The course instructor of MATH1001 warns Bob that if he fails the final examination of this course, then he will fail this course. Let be the statement "Bob fails the final examination of MATH1001.", and be the statement "Bob fails MATH1001". Then, the statement made by the course instructor is "".

For the statement made by the course instructor to be true, either Bob actually fails the final examination of MATH1001, and he actually fails the course, or Bob passes the final examination of MATH1001. In the latter case, whether Bob fails MATH1001 or not does not matter, since the course instructor does not promise anything if Bob passes the final examination of MATH1001 [8].

For the statement made by the course instructor to be false, the only situation is that Bob fails the final examination of MATH1001, but he still passes MATH1001 ( is true and is false) (this shows that the instructor is lying!).

Converse and biconditionals

[edit | edit source]

After discussing conditional of and , we will discuss biconditional of and . As suggested by its name, there are two conditionals involved. The conditional involved, in addition to , is , which is called the converse of the conditional .

In mathematics, given that the conditional is true, we are often interested in knowing whether its converse is true as well [9].

Example. The converse of the statement made by the course instructor in the previous example is "If Bob fails MATH1001, then he fails the final examination of MATH1001.".

Definition. (Biconditionals) The biconditional of two statements and , denoted by , is , that is, "If then ." and "If then .".

Remark.

  • We also write if and only if in this case.
  • To understand the phrase "if and only if" more clearly, consider the following:
  • if and only if can be interpreted as " if and only if ".
  • For " if ", it should be easy to accept that it means "If then ".
  • For " only if , it means can only be true when is true. That is, is a necessary condition for . Thus, we can deduce that when is true, must be true (or else cannot possibly be true). Hence, " only if " means "If then .".

Example. (Truth table for ) The truth table for is

  • We can see that is true when both and have the same truth values (i.e. either both and are true, or both and are false), and false otherwise.


Implication and logical equivalence

[edit | edit source]

When the conditional is true, we can say " implies ", denoted by . On the other hand, when does not imply , i.e. is false, we denote this by .

We have some other equivalently ways to say " implies ", namely

  • is a sufficient condition for (or is sufficient for in short)
  • We call to be sufficient for since when implies , then " is true" is sufficient to deduce " is true".
  • is a necessary condition for (or is necessary for in short)
  • We call to be necessary for since when implies , the hypothesis cannot be possibly true when the consequent is false (or else the conditional will be false). This explains the necessity of " is true".

When , we are often interested knowing whether the converse of is true or not, i.e. whether we have or not [10].

In the case where but , we have multiple equivalent ways to express this:

  • is sufficient but not necessary for .
  • From the previous interpretation, when we say is necessary for , we mean . Hence, when is sufficient but not necessary for , we mean and .
  • is a stronger condition than (or is stronger than in short).

In the case where and as well, the biconditional is also true, and we denote this by . There are also multiple equivalent ways to express this:

  • is logically equivalent to .
  • We say they are logically equivalent since they always have the same truth values (because is true), which is related to logic.
  • " if and only if " (is true).
  • Recall that we also use " if and only if " to express the biconditional . Thus, technically, we should write " if and only if " is true in the case where . However, we rarely write this in practice, and usually omit the phrase "is true" since it makes the expression more complicated. So, when we write " if and only if " in this context, we mean that the biconditional is true without saying it explicitly.
  • Usually, when we just write " if and only if ", we have the meaning of the logical equivalence , rather than the statement . If we really want to have the latter meaning, we should specify that " if and only if " refers to a statement.
  • is necessary and sufficient for .
  • Following the previous interpretation, is necessary and sufficient for means and .

Theorem. (Some laws about conjunction, disjunction and negation) In the following, , and are arbitrary statements.

  • (double negation)
  • (commutative law of conjunction)
  • (commutative law of disjunction)
  • (associative law of conjunction)
  • (associative law of conjunction)
  • (distributive law)
  • (distributive law)
  • (De Morgan's law)
  • (De Morgan's law)

Proof. They can be shown using truth tables.

Remark.

  • You may observe that there are also some analogous results in set theory (some even have the same name!), discussed in the chapter about set theory. This is because the results discussed in the chapter about set theory are actually proven from the corresponding results above almost directly.

Theorem. (Bridge between conditional and disjunction) The statements and are logically equivalent.

Proof. It can be shown using the following truth table:

Theorem. (Logical equivalence of a conditional and its contrapositive) The contrapositive of a conditional is defined to be another conditional , and they are logically equivalent.

Proof. Using the bridge between conditional and disjunction and some other laws, it can be shown as follows:

Remark.

  • It may seem "surprising" when we "suddenly" negate twice. Indeed, when we are thinking about how to prove the logical equivalence, we do not directly do this from nowhere. Instead, we are "motivated" to do so after observing that and . So, we sort of finish the above series of equivalence "like a sandwich" (from left to right and from right to left simultaneously). This may be useful for other similar proofs.
  • This result is very important for Proof by Contrapositive, which will be discussed later.


Tautologies and contradictions

[edit | edit source]

Before defining what tautologies and contradictions are, we need to introduce some terms first. In the previous sections, we have discussed the meaning of the symbols and . These symbols are sometimes called logical connectives, and we can use logically connectives to make some complicated statements. Such statements, which are composed of at least one given (or component) statements (usually denoted by etc.) and at least one logical connective, are called compound statements.

Definition. (Tautologies and contradictions) A compound statement is called a tautology (contradiction) if it is true (false) for each possible combination of truth values of the component statement(s) that comprise .

Remark.

  • We use to denote a tautology and to denote a contradiction.
  • When a statement is a tautology, we can also write , since it means and always have the same truth value, and because the truth value of is always true, the truth value of is also always true, i.e. is a tautology.
  • Because of this, when we want to prove that a statement is always true, one way is to show that . For example, if we want to prove that and are logically equivalent, we may show that .

Example. Let be an arbitrary statement. Then,

  • is a tautology.
  • is a contradiction.

This is because the truth table for is and the truth table for is

Example. Let and be arbitrary statements. Then, is a tautology, since its truth table is

Clipboard

Exercise. The following are some further questions on this example.

1

Is the converse of the statement in the example, , a tautology, contradiction, or neither?

Tautology.
Contradiction.
Neither.

2

Is the negation of the statement in the example, , a tautology, contradiction, or neither?

Tautology.
Contradiction.
Neither.

3

Is the contrapositive of the statement in the example, , a tautology, contradiction, or neither?

Tautology.
Contradiction.
Neither.

Prove that is a tautology without using truth tables.

Answer

Since the given conditional is a tautology.

A student claims that is a contradiction with the following argument:

Since , the conditional is a contradiction.

Comment on his claim.

Answer
  • The claim is wrong.
  • The step is incorrect, since we should use distributive law here instead, and we cannot apply associative law with two types of logical connector here.
  • Indeed, it is shown in an above question that the conditional is neither tautology nor contradiction.


Theorem. (Laws about tautologies and contradictions) Let be an arbitrary statement. Then,

  • .
  • .
  • .
  • .
  • .
  • .

Proof. They can be shown using truth tables.

Quantifiers

[edit | edit source]

Recall that an open statement is a sentence whose truth values depends on the input of certain variable. In this section, we will discuss a way to change an open statement into a statement, by "restricting the input" using quantifiers, and such statement made is called an quantified statement. For example, consider the statement "The square of each real number is nonnegative.". It can be rephrased as "For each real number , ." We can let be the open statement "". Then, it can be further rephrased as "For each real number , ." In this case, we can observe how an open statement () is converted to a statement (For each real number , ), and the phrase "for each" is a type of the universal quantifier. Other phrases that are also universal quantifiers include "for every", "for all" and "whenever". The universal quantifier is usually denoted by (an inverted "A"). After introducing this notation, the statement we mention can be further rephrased as "" (we also use some set notations here).

In general, we can use the universal quantifier to change an open statement to a statement, which is "" in which is a (universal) set (or domain) which restricts the input .

Apart from the universal quantifier, another way to convert an open statement into a statement is using an existential quantifier. Each of the phrases "there exists", "there is", "there is at least one", "for some" [11], "for at least one" is referred to as an existential quantifier, and is denoted by (an inverted "E"). For example, we can rewrite the statement "The square of some real number is negative." as "" (which is false).

In general, we can use the existential quantifier to change an open statement to a statement, which is "" in which is a (universal) set (or domain) which restricts the input .

Another quantifier that is related to existential quantifier is the unique existential quantifier. Each of the phrases "there exists a unique", "there is exactly one", "for a unique", "for exactly one" is referred to as unique existential quantifier, which is denoted by . For example, we can rewrite the statement "There exists a unique real number such that ." as "." We can express the unique existential quantifier in terms of existential and universal quantifiers, by defining "" as where the left bracket is the existence part, and the right bracket is the uniqueness part. In words, the expression means

There exists such that , AND for every , if and , then (i.e., and are actually referring to the same thing, so there is exactly one such that ).

In general, we need to separate the existence and uniqueness part as above to prove statements involving unique existential quantifier.

Negation of quantified statements

[edit | edit source]

Example. The statement "" [12] can be expressed in words (partially) as "There exists a set such that ."

Clipboard

Exercise. Write down the negation of this statement in words (partially). (Hint: What is the negation of " ( is a nonnegative integer)."? Hence, what is the negation of "There is at least one such that ."?)

Answer
  • For the hint, the negation of " ( is a nonnegative integer)." is "", and the negation of "There is at least one such that ." is hence "There is no such that ". It can also be expressed equivalently as "For each , is not satisfied.", or .
  • Inspired from the hint, the negation of this statement can be written as "For each set , ."


From this example, we can see that the negation of the statement "" is logically equivalent to "". Now, it is natural for us to want to know also the negation of the statement ". Consider this: when it is not the case that is true for each , it means that is false for at least one . In other words, . Hence, we know that the negation of the statement "" is logically equivalent to .

Quantified statements with more than one quantifier

[edit | edit source]

A quantified statement may contain more than one quantifier. When only one type of quantifier is used in such quantified statement, the situation is simpler. For example, consider the statement "For each real number and for each real number , is a real number." It can be written as "". When we interchange "" and "", the meaning of the statement is not affected (the statement still means "The product of two arbitrary real numbers is a real number.") Because of this, we can simply write the statement as "" without any ambiguity.

For an example that involve two existential quantifiers, consider the statement "There exists an real number and an real number such that is a real number." It can be written as "." Similarly, interchanging "" and "" does not affect the meaning of the statement (the statement still means "For at least one pair of real numbers and , is a real number.") Because of this, we can simply write the statement as "" without any ambiguity.

However, when both types of quantifier are used in such quantified statement, things get more complicated. For example, consider the statement "For each integer , there exists an integer such that ." This can also be written as "". It means that for each integer, we can find a (strictly) smaller one, and we can see that this is a true statement. For instance, if you choose , I can choose or . Indeed, for the integer chosen by you, I can always choose my as so that .

Let's see what happen if we interchange "" and "". The statement becomes , meaning that there exists an integer such that it is (strictly) smaller than every integer ! This is false, since, for example, there is no integer that is (strictly) smaller than itself (which is an integer). In this example, we can see that interchanging the positions of universal quantifier and existential quantifier can change the meaning of the statement. Hence, it is very important to understand clearly the meaning of a quantified statement with both universal and existential quantifiers. To ease the understanding, here is a tips for reading such statement:

For the variable associated to the quantifier , it may depend on the variable(s) introduced earlier in the statement, but must be independent from the variable(s) introduced later in the statement.

What does it mean? For example, consider the above example. In the first case, we have . Then, since the variable appears earlier than the variable which associated to , may depend on (This is similar to the case in English. In a sentence, a thing may depend on other things mentioned earlier.). For instance, when you choose , and I choose . Then, . However, if you change your choice to , then my does not work, and I need to change my to, say, 8 so that . Then, we can see that depends on in this case. In the second case, we have . In this case, the variable appears later than the variable . Hence, the variable must be independent from . That is, when such is determined, it needs to satisfy for each chosen, and the cannot change depend on what is. Indeed, cannot possibly depend on , since is supposed to be determined when is not even introduced!

Exercises

[edit | edit source]

In the following questions, are statements.

A. Construct the truth tables for each the following statements, and also give its converse and contrapositive:

B. Negate the following statements:


Methods of Proof

There are many different ways to prove things in mathematics. This chapter will introduce some of those methods.

Introduction

[edit | edit source]

In this chapter, for every method of proof introduced, we will discuss it in this manner:

  1. Explaining why the method works, by considering its underlying logic.
  2. Introducing how to use the method.
  3. Giving examples of using the method (and possibly also some previous method introduced) to prove some results.

Before introducing the first proof method, let us go through the meanings of some frequently used terms in mathematics books (some are already used in previous chapters actually), which are used more frequently starting from this chapter.

  • Definition: an explanation of meaning of a term.
  • Theorem: an important and interesting true mathematical statement.
  • Proposition: a (relatively) less important theorem.
  • Lemma: a true mathematical statement that is useful in establishing the truth of other true statements, and is less important than a theorem.
  • Corollary: a true mathematical statement that can be deduced from a theorem (or proposition) simply.
  • Proof: an explanation of why a statement is true.
  • Axiom: a true mathematical statement whose truth is accepted without proof.
  • Conjecture: a statement that is believed to be true, but is not proven to be true.

Direct proof

[edit | edit source]

Many mathematical theorems can be expressed in the form of ", in which and are open statements about elements in a set [13]. This expression means "If then " is true for every . However, in practice, we rarely include the phrase "is true", and usually just write the theorem in the form of "For every , if , then ." Sometimes, we write instead "Let . If , then .", which has the same meaning.

In some situations, the statement is not stated in such a form directly, but can be expressed in such a form. For example, the statement "The square of an even integer is even." can be expressed as "For every , is even is even.", or "For every , if is even, then is even.", or "Let . If is even, then is even.", etc.

Now, we will introduce the first proof method to prove statements in such a form, which is known as direct proof. As suggested by its name, this method is quite "direct", and is probably the simplest method among all methods discussed in this chapter.

Consider the statement "". We would like to prove that it is true. Suppose is false for some . Then, the conditional must be true for this by definition, regardless of the truth value of . Hence, in the proof, we do not need to consider those for which the hypothesis is false.

Because of this, to give a direct proof of "", we first assume is true (So, we are considering every for which is true.), and then proceed to show that is true for every such (or else the conditional will be false).

This shows that is true for those for which is true, and this is enough to prove is true for every (for which may or may not be true), since we have mentioned that the conditional must be true for those for which is false.

Example. Prove that for every , if is odd, then is even.

Proof. Assume is odd. Then, by definition we have for some . Thus, where (this follows from the definition of integers). This means can be written as for some , and hence is even.

In the previous proof, we have used the definitions of odd and even integers:

  • an integer is even if for some integer .
  • an integer is odd if for some integer .

We can write the proof more concisely using logical notations, as follows:

Proof.

Both styles of proofs are acceptable, but for beginners, it is recommended to use the first type. Also, the first type can let the readers understand the proof easier.

Remark.

  • The property of an integer of whether it is even or odd is called parity.
  • When we use "" in the proof, it is implicitly assumed it follows the same meaning as in the given statement, i.e., is an integer. We can also let to be an integer explicitly in the proof to be more clear.
  • In some other places, the first line "Assume ..." is simply omitted for convenience, but the assumptions are still used in the proof.
Clipboard

Exercise. Consider the statement "For every , if is odd and is even, then is even.". A student provides the following proof to the statement:

Proof. Assume is odd and is even. That is, and for some . It follows that , and thus is even.

Is the proof correct? If not, point out the mistake, and write a correct proof.

Solution

The proof is incorrect. The mistake is that one should not use the same for both and , since using the same implies that , which is not necessarily the case from the assumptions. The following proof is a correct one:

Proof. Assume is odd and is even. That is, and for some . It follows that , and thus is even.


Clipboard

Exercise. Prove that for every , if is even, then is odd.

Proof

Proof. Assume is even. Then, for some . Thus, Since , is odd.


Clipboard

Exercise. Prove every of the following statements.

(a) The sum of two arbitrary even integers is even.

(b) The sum of two arbitrary odd integers is even.

(c) The sum of an arbitrary even integer and an arbitrary odd integer is odd.

(d) The product of two arbitrary even integers is even.

(e) The product of two arbitrary odd integers is odd.

(f) The product of an arbitrary even integer and an arbitrary odd integer is even.

(Hint: rewrite the statements in the form of "" first.)


Solution

(a) First, rewrite the statement as "For every , if and are even, then is even."

Proof. Assume and are even. Then, and for some (notice that we should not use the same for both and , since may be different from .). Thus, , and hence is even since .

(b) First, rewrite the statement as "For every , if and are odd, then is even."

Proof. Assume and are odd. Then, and for some . Thus, , and hence is even since .

(c) First, rewrite the statement as "For every , if is odd and is even, then is odd."

Proof. Assume is odd and is even. Then, and for some . Thus, , and hence is odd since .

(d) First, rewrite the statement as "For every , if is even and is even, then is even."

Proof. Assume and are even. Then, and for some . Thus, , and hence is even since .

(e) First, rewrite the statement as "For every , if is odd and is odd, then is odd."

Proof. Assume and are odd. Then, and for some . Thus, , and hence is odd since .

(f) First, rewrite the statement as "For every , if is odd and is even, then is even."

Proof. Assume is odd and is even. Then, and for some . Thus, , and hence is even since .


Clipboard

Exercise. A real number is defined to be rational if there exist integers with such that . Prove every of the following statements.

(a) The sum of two arbitrary rational numbers is rational.

(b) The difference of two arbitrary rational numbers is rational.

(c) The product of two arbitrary rational numbers is rational.

(d) The quotient of an arbitrary rational number by an arbitrary nonzero rational number is rational.

Solution

(a) First, rewrite the statement as "For every , if , then .

Proof. Assume . Then, and for some with and . Thus, Since with , .

(b) First, rewrite the statement as "For every , if , then .

Proof. Assume . Then, for some with . So, is rational since and . Thus, by (a), we have .

(c) First, rewrite the statement as "For every , if , then .

Proof. Assume . Then, and for some with and . Thus, Since with , .

(d) First, rewrite the statement as "For every , if and then .

Proof. Assume and . Then, and for some with , , and . Thus, Since with , .


Example. Prove that for every , if , then .

Proof. For every , . Thus, the hypothesis is false, and hence the statement must be true.


Remark.

  • Notice that we do not use direct proof here, since the false hypothesis makes the statement true. In this case, we call the proof as vacuous proof, and say that the result follows vacuously (the statement says nothing at all).

Example. Prove that for every , if , then .

Proof. Assume . Then, Since is positive and is negative by assumption, we have , and thus


Remark.

  • Graphically, the function (we will discuss the concept of function in later chapter) looks like:

Clipboard

Exercise. Prove that for every , if , then (this statement is the converse of the statement in above example). (Hint: The following property may be useful: for every , if , then either ( and ) or ( and ).) (This statement seems to be true by inspecting the above graph, but inspecting graph is not a valid way of proving this statement.)

Proof

Proof. Assume . Then, ("" is read "which implies" in this context). It follows that we have either

  • and , or
  • and .

Since no real number satisfies the first one, we must have the second one, which gives .


Combining the two results in the previous example and exercise, we get an "if and only if" result:

For every , we have if and only if .

In other words, using set language, (Both sets represent the curve (strictly) under the horizontal line in the above graph.)

Letting and be the open statement "" and "" respectively, we can express the above result symbolically: Recall that "" means "" and "". So, to give a direct proof to the statement in the form of "", a usual way is to break the proof into two parts:

  1. proving that (known as the "only if" part, or "" direction)
  2. proving that (known as the "if" part, or "" direction)

Example. Prove that for every , . (Hint: this inequality is equivalent to the inequality , obtained by multiplying both side by , which is a positive integer.)

Proof. Using the hint, it suffices to prove that for every , . But it follows from the fact that .

Clipboard

Exercise.

We can strengthen the statement (i.e., make the statement stronger (recall the meaning of "stronger" in previous chapter)) in the example, by changing to a larger set. Determine which of the following (may be more than one) can be the larger set.

None of the above.

A student provides the following proof to the above statement:

Proof. Since is a positive integer, multiplying to both sides of the inequality yields . After rearranging, we get , which is always true.

Point out the mistake in the proof.

Solution

The mistake is that the student implicitly assumes , which is what we want to prove, at the beginning of the proof. Thus, this proof does not prove the result. (Notice that in the proof in the example, we do not assume . Instead, we start from the fact that .)


Example. Let . Prove that for every , if is prime, then is odd.

Proof. Assume is prime. Since the only primes in the set are 3,5,7 and 11, this means . Hence, is odd.

Clipboard

Exercise. Prove that for every , if is even, then is prime.

Proof

Proof. Since the set only contains odd numbers, the hypothesis is false, and therefore the result follows vacuously.



Example. (A special case of AM-GM inequality) Prove that for every , if and are positive, then

Proof. Assume and are positive. Then,

Clipboard

Exercise. Suggest a condition where the equality holds, i.e., .

Solution

The condition is .


[edit | edit source]

After introducing the method of direct proof, let us apply this method on proving some results relating to congruence of integers. Before this, let us introduce the concept of congruence of integers. We begin by a motivation for the definition of congruence of integers.

We know that an integer is either even or odd, i.e., can be expressed as or for some integer , according to whether the remainder is 0 or 1 when is divided by 2. Thus, if two integers and have the same remainder when divided by 2 (i.e., have the same parity), then the difference can be proved to be a multiple of 2 (it can be proved that the converse is also true). Similarly, an integer can be expressed as or for some integer , according to whether remainder is 0, 1 or 2 when is divided by 3. Hence, if two integers and have the same remainder when divided by 3, then the difference can be proved to be a multiple of 3 (the converse is also true).

Hence, "two integers have the same remainder when divided by some integer " is equivalent to "their difference is a multiple of ". This leads us to the following definition.

Definition. (Congruence of integers) Let and with . Then, the integer is congruent to modulo , denoted by , if is a multiple of , i.e., for some .

Remark.

  • Instead of " is a multiple of ", we can also say is divisible by , or divides , denoted by (in general, the notation means " divides " (and means " does not divide ").

Example. We have since , and since . But, since .

Clipboard

Exercise.

1

Choose the integers that are congruent modulo 3.

5,8
-9,7
-9,18
0,37
None of the above.

2

Choose the integers that are congruent modulo 6.

5,8
-9,7
-9,18
0,37
None of the above.

3

Choose the integers that are congruent modulo 9.

5,8
-9,7
-9,18
0,37
None of the above.


Example. (Clock arithmetic) A familiar application of the concept of congruence of integers is clock arithmetic. For instance, when we want to know adding 5 hours to 8 o'clock gives what time, we first calculate . But . So, we now think about 13 is congruent to which integer between 1 and 12. The integer is 1. Hence, the time is 1 o'clock.

In general, we can get the resulting time by performing the modulo operation, which gives the remainder when dividing the sum of the two numbers by 12 (called modulus). The notation for " modulo " is , which gives the remainder when is divided by ( and are positive integers).

Now, let us apply direct proof to prove some results related to the congruence of integers.

Theorem. For every and for every with , if and , then

  • (compatibility with addition) .
  • (compatibility with translation) .
  • (compatibility with scaling) .
  • (compatibility with multiplication) .

(For the compatibility with translation and scaling, the assumption that is not needed.)

Proof. We will only prove the compatibility with addition and multiplication. The proof of other two compatibilities is left to the following exercise.

Compatibility with addition: Assume that and . Then, and for some . Thus, Since , we have .

Compatibility with multiplication: Assume that and . Then, and for some . Thus, Since , we have .

Remark.

  • We have applied the trick in the proof of compatibility with multiplication. One can also prove it without using this trick. The details are left to the following exercise.
Clipboard

Exercise. Prove the compatibility with multiplication in the above theorem, without using the trick used in the above proof. (Hint: You may express in terms of and in terms of first.)

Proof

Assume that and . Then, and for some . That is, and . Hence, Since , we have .

Clipboard

Exercise. Prove the compatibility with translation and scaling in the above theorem.

Proof

One can of course use direct proof and the definition of congruence of integers to prove them, but we will just apply the compatibility with addition and multiplication (which are proven) to prove them (they can be regarded as corollaries of the compatibility with addition and multiplication).

Proof. Assume . Since , we have . Hence, by the compatibility with addition, we have . Also, by the compatibility with multiplication, we have .


In the above result, everything is with the same "modulo ". It is then natural to ask whether there are any results for different "modulo". The answer is yes, and to discuss a result, we need the concept of relatively prime integers.

Definition. (Relatively prime integers) Two integers are relatively prime if their greatest common divisor is 1.

Remark.

  • The integers are also called coprime or mutually prime.

Example.

  • 2 and 3 are relatively prime.
  • 4 and 12 are not relatively prime since their greatest common divisor is 4.
  • 9 and 66 are not relatively prime since their greatest common divisor is 3.

Theorem. Two integers and are relatively prime if and only if there exist integers and such that .

Proof. Omitted.

Using this result, we can deduce the following result:

Theorem. For every with , if , and are relatively prime, then .

Proof. Assume , , and are relatively prime. Then, we have and for some . This means . Also, for some . Multiplying both sides by the integer , we get Putting , we get Putting this into , we get Since , we have .

Remark.

  • This theorem says in particular if an integer is a multiple of , and also a multiple of , and and are relatively prime, then the integer is a multiple of .
  • For example, if an inteeger is a multiple of 3 and also a multiple of 7, then the integer is a multiple of 21 since 3 and 7 are relatively prime.
Clipboard

Exercise. Give an example of integers such that , , and are not relatively prime, and .

Solution

Take . Then, and . However, .

Example. (Reflexivity, symmetry, and transitivity of the congruence of integers) Prove that for every with ,

  • (reflexivity) for every , .
  • (symmetry) for every , if , then .
  • (transitivity) for every , if and , then .

(Since the congruence of integers satisfies these three properties, it is said to be an equivalence relation. We will discuss the concept of (equivalence) relation in a later chapter.)

Proof.

Reflexivity:

Since , we have .

Symmetry:

Assume . Then, for some . Thus, , and hence since .

Transitivity:

Assume and . Then, and for some . Hence, . Thus, since .


Remark.

  • Notice that not all relations satisfy all these three properties. For instance, "" does not satisfy the reflexivity and transitivity, "" does not satisfy the reflexivity and symmetry.

Example. Applying the compatibility with multiplication in the above theorem, we can get the following result:

Let be an integer, be a nonnegative integer, and with . If , then .

We can prove it (a bit informally) as follows:

Proof. Assume . First, . Second, we have . Applying this argument again, we get . Thus, we have for every nonnegative integer by applying the argument "again and again".

To prove the result formally, we need to use proof by mathematical induction, which will be discussed later.

Example.

(a) Consider the remainder of when divided by 4 (i.e., ) for . Do you observe any pattern? Hence, suggest a conjecture.

(b) Prove the conjecture.

Solution.

(a) We have Notice that the remainder is 1 for , and 3 for . It is thus natural to expect that the same pattern continue for all other larger integers. Thus, a conjecture is

Let be a nonnegative integer. If is even, then . Also, if is odd, then .

(b) We will just prove "If is even, then .". The proof of the second part is left to the following exercise.

Proof. Assume is even. Then, for some nonnegative integer ( is a nonnegative integer). It follows that . Since , it follows that by the result in previous example. Hence, .

Clipboard

Exercise. Prove the second part in the above conjecture.

Proof

Proof. Assume is odd. Then, for some nonnegative integer . It follows that . From the prove above, we have . Thus, we get .



The following lemma is quite useful for proving results about congruence of integers.

Lemma. (Euclid's division lemma) For every integer and with , there exists a unique pair of integers and such that

Proof. We separate the proof into existence part and uniqueness part.

Existence part:

Case 1: .

Then, we set and . After that, the equation can be rewritten equivalently as , and also the inequality can be rewritten equivalently as . Through this, we transform this case to case 2.

Case 2: .

Subcase 1: and .

Then, we set , , and . After that, the equation can be rewritten equivalently as (this is equivalent to ). Also, the inequality can be rewritten equivalently as . Through this, we transform this case to the subcase 2.

Subcase 2: and .

Set and . Then, we have .

Subsubcase 1: . Take and . Then, we have and we are done.

Subsubcase 2: .

Set and . Then, we have with . Since there are exactly nonnegative integers less than , we need to repeat this process at most times (, so is at most the preceding integer of ) to get a such that [14] (and also a ).

So, we take and . Then, we have and we are done.

Uniqueness part:

Assume there exists another pair of integers and (in addition to the pair of integers and ) such that Since we have also we get, by subtracting the two equations,

Also, by considering the above two inequalities, we get Putting it in the above equation, we get .

Thus, we have and .

Remark.

  • This lemma is the basis of Euclidean division, as known as division with remainder.
  • is called the dividend, is called the divisor, is called the quotient, and is called the remainder.
  • We employ the method of proof by cases in the proof, which is not a "new" way of proof strictly speaking. We just consider different cases in the proof. However, when we use this method, we need to ensure that the cases covers all possibilities for the "for every", so that we actually prove the statement.
  • From this lemma, we know that every integer has remainder either 0 or 1 or 2 or ... or (from the inequality ) when divided by an integer with . In other words, for every integer , we have either or or ... or . For brevity, we can also write .

Example. Prove that for every integer , .

Proof. By Euclid's division lemma, we have . Thus, we have . But and . So, the result follows by the transitivity of the congruence of integers.

Clipboard

Exercise. Propose a similar result for the congruence modulo 5, and prove it.

Solution

Proposition: For every integer , .

Proof. By Euclid's division lemma, we have . Thus, we have . But and . So, the result follows.




[edit | edit source]

The proofs related to sets are often in the form of

  1. A set is a subset of another set.
  2. A set equals another set.

To prove that a set is a subset of another set, we use the definition of subset:

A set is a subset of another set if for every element , if , then .

Thus, we can employ direct proof to prove that a set is a subset of another set.

For the equality of two sets, recall that:

A set equals another set if and only if and .

Thus, to prove the equality of two sets, we often need to separate the proof into two parts: (i) proving that ; (ii) proving that .

Example. (Transitivity of "") Prove that for every set and , if and , then .

Proof. Assume and . Then, for every , and hence .


Example. (Associative law) Prove that for every set and , .

Proof. First, we prove that . For every , Thus, we have .

Now, we prove the reverse subset inclusion, i.e., . For every , Thus, we have .

Notice that the proof for reverse subset inclusion is very similar to the proof for the first part. Indeed, it is just a reverse of the proof for the first part. Hence, we can actually simplify the proof as follows:

Proof. For every , Thus, we have .

Using this proof, we can prove the set equality directly (set equals set if for every , ). (However, we should be careful about whether we really have "".) But, in many cases, the proof for reverse subset inclusion is not just simply obtained by reversing the proof for the first part, and we have to separate the proof into proofs for two subset inclusions.

We can observe that to prove different laws for the sets, we just simply use the corresponding laws in logic to prove them. Hence, the proofs for other laws, e.g., commutative law and distributive law, are similar.

Clipboard

Exercise. (De Morgan's law) Let and subsets of a universal set . Prove that .

Proof

Proof. For every ,


Example. Let and be subsets of a universal set . Prove that .

Proof. For every ,

Clipboard

Exercise. Using this result, prove that . (Hint: you may use the laws in set theory in the proof.)

Proof

Here, we just use the laws of in set theory to prove the equality of sets:


Example. Prove that for every set and , and .

Proof. For the first one, for every , (no matter is true or false, we always have the first implication.)

For the second one, for every ,

Clipboard

Exercise.

(a) Propose an assumption on the sets and such that we have both reverse subset inclusions, i.e., and . Prove them under this assumption.

(b) Propose an assumption on the sets and such that we have (the another reverse subset inclusion may or may not hold). Prove it under this assumption.

(c) Propose an assumption on the sets and such that we have (the another reverse subset inclusion may or may not hold). Prove it under this assumption.

(The assumptions proposed should be as weak (recall the meaning of weak in logic) as possible, so that the result can apply in more contexts.)

Solution

(a) Assumption: .

Proof. Assume . For the first one, for every , For the second one, for every ,

(One can also use the some results in set theory (e.g. , , etc.) in the proof.)

(b) Assumption: .

Proof. Assume . Then, for every ,

(c) Assumption: .

Proof. Assume . Then, for every , (We have the first implication, since if , then we have , and also since )



Clipboard

Exercise. Consider the statement: for every set and , . A student gives the following proof:

Proof. For every ,

Is the proof correct? If not, point out the mistake and give a correct proof.

Solution

The mistake is in this step: We have "", but do not necessarily have "", since we generally do not have , and thus we cannot show "" by contrapositive.

The following is a correct proof:

Proof. For every , On the other hand, for every ,


Example. Prove that for every set and , if and , then .

Proof. For every ,


Example. Prove that for every set and , .

Proof. For every ,

Clipboard

Exercise. Prove that for every set and ,

(a) .

(b) .

Solution
(a)

Proof. For every , (Notice that for the third "", we cannot change it to "" since .)

On the other hand, for every ,


(b)

Proof. For every ,



Clipboard

Exercise. Consider the statement:

For every set and , if and , then .

A student provides the following proof:

Proof. Assume and . For every ,

Is the proof correct? If not, point out the mistake and give a correct proof.

Solution

The proof is correct.

Example. Prove that for every set and .

Proof. For every ,

Clipboard

Exercise. Prove that for every set and . (Hint: you may find the property useful.)

Proof

Proof. For every ,


Remark.

  • The reverse subset inclusion does not hold. For instance, take and . Then, and . We can see that there is not reverse subset inclusion in this case.



Example. Let and be sets. Prove that if and only if .

Proof. "" direction: Assume . Then, for every set , Thus, we have .

"" direction: Assume . Then, for every , Thus, .

We can also prove the "" direction more simply:

Assume . Since for every set , , and thus , we have

Clipboard

Exercise. Let and be sets.

(a) Prove that .

(b) Give an example of and such that .

(c) We will have under an assumption. Propose an assumption, and prove the equality under the assumption. (Hint: construct some simple examples to observe whether there are any patterns.)


Solution
(a)

Proof. Claim: .

Proof. "" direction: Assume . Then, for every , . So, .

"" direction: Assume . Then, for every , . Also, . Hence, and .

For every set ,

(b) Take and . Then, , while .

(c) An assumption is " or ".

Proof. Assume or .

Case 1: .

Then, . Hence, . On the other hand, by the above example, we have , and thus . Therefore, .

Case 2: .

The proof is similar (just interchange "" and "").


Proof by contrapositive

[edit | edit source]

Recall that the contrapositive of a conditional is the statement , which is logically equivalent to the original conditional . Hence, if we can show that , then it follows that . This gives us another method of proof, namely proof by contrapositive.

A proof by contrapositive of the statement is a direct proof of . That is, we first assume that is true, and proceed to show that is true. In other words, we first assume that is false, and proceed to show that is false.

Generally, when we encounter a statement , and observe that the consequent is "simpler" than the hypothesis , using proof by contrapositive is usually more preferable.

Example. Prove that for every , if is even, then is odd.

Proof. Here, we use proof by contrapositive, that is we will prove that "for every , if is even, then is odd."

Assume is even. Then, for some . Thus, , and hence is odd since .

Remark.

  • Using proof by contrapositive here allows us to work with with initially, instead of the more complicated expression .


Example. Prove that for every , is even if and only if is even.

Proof. "" direction (or "only if" part):

Assume is even. Then, for some . Thus, . Hence, is even since .

"" direction (or "if" part):

We use proof by contrapositive, i.e., we will prove that "for every , if is odd, then is odd." Now, assume is odd. Then, for some . Hence, , and so is odd since .


Remark.

  • Using proof by contrapositive for the "" direction allows us to work with , instead of , initially.
  • The statement is logically equivalent to "for every , is odd if and only if is odd." (since ).

Example. Prove that for every , if and only if .

Proof.

"" direction:

We use proof by contrapositive. First, assume . Since by Euclid's division lemma, we have . Hence, . But . It follows that , and hence .

"" direction:

Assume . Then, we have . But . So, we have .

Clipboard

Exercise. Prove that if and only if .

Proof

Proof.

"" direction:

We use proof by contrapositive. First, assume . Since by Euclid's division lemma, we have . Hence, . But . It follows that , and hence .

"" direction:

Assume . Then, we have . But . So, we have .

Notice that we can also apply the fact that (proved before) to conclude that . Then, we can see that this statement is just logically equivalent to the above statement (since ).


Example. Let and be sets. Prove that if and only if .

Proof.

"" direction:

We use proof by contrapositive. Assume , i.e., there exists an element such that . Since , it follows that . But . So, .

"" direction:

Assume . Since holds for every set and , it suffices to show that :

For every , So, .


Clipboard

Exercise. Prove that for every set and , if , then . (Hint: means that there exists an element such that and .)

Proof

Proof. "" direction:

We use proof by contrapositive. Assume . Then, there exists an element such that and . So, we have and . This means . Thus, .

"" direction:

We use proof by contrapositive. Assume . Then, there exists such that and . It follows that and , meaning that , and hence .


Example. Prove that for every nonnegative real number , if for every positive real number , then .

Proof. We use proof by contrapositive, i.e., we will prove that "if , then for some positive real number ."

Assume . This means since is nonnegative. Then, we pick which is a positive real number, and we have .


Clipboard

Exercise. Prove that for every , if , then or .

Proof

Proof. We use proof by contrapositive. Assume and . Then, we have (by the property of "").


Clipboard

Exercise. An integer is defined to be a perfect square if for some . Prove that for every , if is a perfect square, then is even or is even. (Hint: consider a previous result about congruence of integers, that is related to perfect square.)

Proof

We use proof by contrapositive. Assume is odd and is odd. Then, and for some . Hence, This means since . However, no perfect square is congruent to 2 modulo 4 (recall that we have proved that for every integer , ). Thus, is not a perfect square.

Proof by cases

[edit | edit source]

In the previous sections, we have actually employed the method of proof by cases already. It is natural to use this method when we need to break down a problem into several cases, and then tackle every case individually ("divide and conquer"). Sometimes, we may even need to further divide a case into several subcases. The following are some typical cases:

  1. an integer is even or odd;
  2. a real number is less than 0, equal to 0, or greater than 0;
  3. for two nonzero real numbers and , either or .
  • For every of the cases, it can be divided into two subcases:
  1. : ( and ) or ( and )
  2. : ( and ) or ( and )

But, we should be aware that when we use proof by cases to prove that "", the cases should cover all possibilities, i.e., all .

Example. Prove that for every , is even.

Proof. We divide the proof into two cases: is even and is odd.

Case 1: is even.

Then, for some . Thus, Since , is even.

Case 2: is odd. Then, for some . Thus, Since , is even.

It follows that is even for every .


Example. (Comparing parity) Prove that for every , and are of the same parity (i.e., both even or both odd) if and only if is even.

Proof. "" direction: Assume and are of the same parity.

Case 1: and are both even.

Then, and for some . Thus, , and hence is even since .

Case 2: and are both odd.

Then, and for some . Thus, , and hence is even since .

"" direction: We use proof by contrapositive. Assume and are of different parity.

Case 1: is odd and is even.

Then, and for some . Thus, . Hence, is odd since .

Case 2: is even and is odd.

The proof is similar to case 1 (just exchange the role of and ).


Remark.

  • We sometimes use the phrase without loss of generality (WLOG) to indicate that the proofs of the two situations are similar, and thus the proof of only one of these situations is needed. For instance, for the "" direction in the above proof, we may write "Assume and are of different parity. WLOG, assume is odd and is even. ...".
Clipboard

Exercise. Let and be integers. Prove that is even if and only if is even or is even.

Proof

Proof. "" direction: We use proof by contrapositive. Assume is odd and is odd. Then, and for some . Hence, and so is odd since .

"" direction: Assume is even or is even. WLOG, assume is even. Then, for some . Thus, . Since , is even.


The following inequality is quite important in mathematics.

Theorem. (Triangle inequality) For every , .

Proof.

Case 1: and .

Then, , and so

Case 2: and .

Then, , and so

Case 3: one of and is nonnegative, and the other is negative.

WLOG, assume and .

Subcase 1: .

Then,

Subcase 2: .

Then,

So, we have the desired inequality for every .

Proof by contradiction

[edit | edit source]

Another important method of proof is proof by contradiction.

Let be a statement. Now, suppose we want to prove that is true. If we can show that the conditional is true (i.e., ), then the truth table for conditional tells us that must be false, and hence must be true, as desired.

The truth table: In words, the method of proof by contradiction is as follows: we first assume that the statement we want to prove to be true is false, and then proceed to show that this gives a contradiction, and therefore our assumption must be wrong. That is, it is impossible for the statement to be false since it leads to something "absurd". Hence, the statement is true.

The name of proof by contradiction comes from the fact that the assumption that the statement is false is later contradicted by some other fact. This is also known as reductio ad absurdum, which means reduction to absurdity.

In general, we often use the method of proof by contradiction when the statement we want to prove is negative sounding, e.g. "There is no ....", "There does not exist ...", etc.

Also, to indicate to the reader that we are using proof by contradiction, it is recommended that we write "assume to the contrary that ..." (or something similar) instead of just "assume ..." for the assumption that the statement is false.

Example. Prove that no odd number can be written as a sum of two odd numbers.

Proof. Assume to the contrary that the statement "no odd number can be written as a sum of two odd numbers" is false. That is, assume to the contrary that there is an odd number that can be written as a sum of two odd numbers and . Then, we have and for some . Hence, we have which means is even since . But this contradicts to our assumption that is odd. So, the result follows.


Example. Prove that there is no smallest positive real number.

Proof. Assume to the contrary that there is a smallest positive real number . Now, consider the number . Since , it follows that . Also, we have . Hence, is a positive real number that is less than , contradicting to our assumption that is the smallest positive real number.

Clipboard

Exercise.

Which of the following statement is/are true?

There is no smallest positive rational number.
There is no smallest positive integer.
There is no smallest nonnegative integer.

Prove that there is no greatest positive real number.

Proof

Proof. Assume to the contrary that there is a largest positive real number . Now, consider the number . Since , it follows that . Also, we have . Hence is a positive real number that is greater than , contradicting to our assumption that is the greatest positive real number.



Example. Prove that the sum of an arbitrary rational number and an arbitrary irrational number is irrational.

Although this statement appears to be not so negative sounding, "irrational" just means "not rational". In this sense, we can see that this statement is also quite negative sounding. Also, it is not easy to show that a number is irrational directly (while, on the other hand, showing that a number is rational is quite easy: just express it as a quotient of an integer by a nonzero integer).

Proof. Assume to the contrary that the sum of an arbitrary rational number and an arbitrary irrational number is a rational number . So, we have where and where with and . But we can then rewrite the equation as Since and , this means is rational, contradicting to our assumption that is irrational.


The following is a typical example in introducing proof by contradiction:

Example. Prove that the number is irrational.

Proof. Assume to the contrary that is rational. Then, for some with . By dividing and by some common factor that is at least 2, if necessary, we can further assume that and have no common factor greater than or equal to 2, i.e., has been expressed in (or reduced to) the lowest terms.

Taking square for the both sides of the equation , we get . Since , this means is even. By a previous result, this implies that is even. Hence, we have for some .

Now substituting it into the equation , we get , which means is also even since . By a previous result again, this implies that is even.

Since both and are even, they have 2 as a common factor, contradicting to our assumption that has been expressed in (or reduced to) the lowest terms.


The following example is another typical example for demonstrating proof by contradiction. But before discussing it, we need to introduce the following theorem since it is used in the proof.

Theorem. (Fundamental theorem of arithmetic) Every integer can be expressed as a product of one or more (not necessarily distinct) primes uniquely. That is, for some prime numbers , uniquely.

Proof. We will prove this theorem after introducing proof by mathematical induction.

Remark.

  • Notice that the "uniqueness" in the theorem is in the sense of the combination of prime number(s) used is unique. Simply changing the order of the multiplication is not counted as another expression.
  • This theorem is also called unique prime factorization.

Example. (Euclid's theorem) Prove that there are infinitely many prime numbers.

Proof. Assume to the contrary that there are finitely many prime numbers, say prime numbers. We first list them in ascending order: . Now, consider the number Since the smallest prime number is 2, we have [15], and hence . Applying the fundamental theorem of arithmetic, there is a unique prime factorization for , and thus there is a prime number dividing .

Since are all the primes by our assumption, it follows that one of them, say , divides , i.e., for some . In addition, we know that divides , i.e., for some .

Therefore, we have . This means divides 1, which is impossible (notice that 2 is the smallest prime, and only 1 divides itself). So, we are arriving at a contradiction.


Remark.

  • This proof is first suggested by Euclid.

We can also use proof by contradiction to prove that a statement "" is true. We first assume that the negation of the statement, i.e., "" is true, and proceed to arrive at a contradiction. (Recall that . So, .) Thus, to prove that by contradiction, we assume that there exists such that is true and is false, and then deduce a contradiction.

Example. Prove by contradiction that for every , if is odd, then is even.

Proof. Assume to the contrary that there exists such that is odd and is odd. Since is odd, we have for some . Then, This means is even since , contradicting to our assumption that is odd.


Clipboard

Exercise. Prove by contradiction that for every nonnegative real number , if for every positive real number , then .

Proof

Proof. Assume to the contrary that for every positive real number and . Since is nonnegative, this means . Now, consider the number . By assumption, we have , which implies that , arriving at a contradiction.


Example. Prove that is irrational.

Proof. Assume to the contrary that is rational, i.e., for some (). Notice that . So, we only have the following cases:

Case 1: .

Now, we have But is even, while is odd (product of even (odd) numbers is even (odd)).

Case 2: and are both negative integers.

Then, we write . Now, we have But is even, while is odd ( and are positive integers).

So, in either case, we arrive at a contradiction.

Clipboard

Exercise. A student provides the following proof to the claim " is irrational.":

Proof. Assume to the contrary that is rational, i.e., for some (). Notice that . So, we only have the following cases:

Case 1: .

Now, we have But is even, while is odd.

Case 2: and are both negative integers.

Then, we write . Now, we have But is even, while is odd.

So, in either case, we arrive at a contradiction.

Is the proof correct? If not, point out the mistake.

Solution

The proof is incorrect. Indeed, is rational. The mistake is that the student states that and also in the proof, which are not true.


Clipboard

Exercise. Prove that for every , if is rational, then both and are rational, or both and are irrational.

Proof

Proof. Assume to the contrary that there exists such that and exactly one of and is rational, and the other irrational. WLOG, assume and . Then, since , and and , we have , contradicting to our assumption that .


Example. (Sum and product of a rational and an irrational number) Prove that for every , (a) if and , then ;

(b) if and , then .

Solution.

(a)

Proof. Assume to the contrary that there exist such that and and . Then, , contradicting to our assumption that .

(b)

Proof. Assume to the contrary that there exist and and . Then, (), contradicting to our assumption that .


Sometimes we can prove a statement using multiple methods:

Example. Prove that for every positive real number and , if , then .

We can prove it using (i) direct proof; (ii) proof by contrapositive; (iii) proof by contradiction.

(i)

Proof. Assume . Then multiplying both sides by gives . Also, multiplying both sides by gives . Combining these two inequalities, we get .

(ii)

Proof. Assume . Rearranging the inequality gives . Now dividing both sides by the positive number preserves the direction of inequality, and thus gives .

(iii)

Proof. Assume to the contrary that and . Then, we have . Also, since and are positive, . So we have , contradicting to our assumption that .


Clipboard

Exercise. Let be a positive real number. Prove that if , then by (i) direct proof; (ii) proof by contrapositive; (iii) proof by contradiction.

Solution
(i)

Proof. Assume . Multiplying both side by gives . Then, dividing both sides by the positive number gives .

(ii)

Proof. Assume . Then, . Also, ( is positive). Thus, . This implies

(iii)

Proof. Assume to the contrary that and . Then, . Also, . So, , and hence . This contradicts to our assumption that .


We can see that when proving a statement "", we may be able to use both proof by contrapositive and proof by contradiction. However, the two proofs are different, and we will compare them in the following table:

Proving that "."
Proof by contrapositive Proof by contradiction
Assumption
Goal

From this table, we can see that the proof by contradiction is more advantageous in terms of assumption, since it has one more "help" from (when we assume , we can use both and .) However, in terms of goal, the proof by contrapositive is more advantageous since the goal is more clear (), while for the proof by contradiction, it is not clear that what the form of the contradiction is. There can be many "ways" for arriving at a contradiction (compare the contradiction in the proof of " is irrational" vs. that of "there are infinitely many primes").

Existence proof

[edit | edit source]

Consider the statement "". This statement is true if is true for at least one . Otherwise, it is false. Thus, to prove such kind of statement, it suffices to find one element such that is true, and this is known as an existence proof. In particular, we should verify that the choice of element is actually belonging to and is actually true for that choice.

Example. Prove that there exists positive integers such that (such integers are known as a Pythagorean triple).

Proof. Take , and (which are integers). Then, .


Remark.

  • The choice of is not unique. For instance, one can also take and . But, giving one example of and that satisfies the requirement is enough.

Example. Prove that there exists an integer such that .

Proof. Take . Then, we have .


The following example demonstrates a more advanced version of existence proof: non-constructive proof.

Example. Prove that there exist irrational numbers and such that is rational.

Proof. We have proved that is irrational. So, we can make use of this fact in this proof.

Consider the real number . This number is either rational or irrational. Now we consider the following cases:

Case 1: is rational. Then, we can take , and then is rational.

Case 2: is irrational. Then, we can take and . Then, which is rational.

Thus, in either case, we can find two irrational numbers and such that is rational.


Remark.

  • This type of proof is known as non-constructive proof since it does not actually construct an example and , and so we do not know which two irrational numbers and satisfy this requirement. However, this proof does prove the existence of such and .
Clipboard

Exercise.

(a) Prove that there exist distinct irrational numbers and such that is rational. (You may use the fact that is irrational.)

(b) Prove that there exist a rational number and an irrational number such that is rational.

(c) Prove that there exist a rational number and an irrational number such that is irrational. (You may use the fact that is irrational.)

(d) Prove that there exist rational numbers and such that is irrational.

Solution
(a)

Proof. Consider the real number . It is either rational or irrational. Now, we consider the following cases:

Case 1: is rational. Then, we can take and , and is rational.

Case 2: is irrational. Then, we can take and . Then, , which is rational.

(b)

Proof. Take and . Recall that we have proved that is irrational. Then, we have , which is rational.

(c)

Proof. Consider the real number . Now, consider the following cases:

Case 1: is irrational. Then, take and , and is irrational.

Case 2: is rational. Then, take and . Then, , which is irrational.

(d)

Proof. Take and . Then, , which is irrational.


Disproof

[edit | edit source]

Consider the statement ".". Suppose we somehow believe that the statement is false. Then, we want to prove that it is false, i.e., prove that " such that is false." An element for which is false is known as a counterexample of the statement, and a process of showing that the statement is false (in other words, disproving the statement) is called a disproof of the statement. One counterexample is enough to disprove the statement.

Example. Disprove that for every .

Disproof. Take . Then, .


Example. Disprove that the product of two arbitrary irrational numbers is irrational.

Disproof. To disprove this, we need to find such that .

Take . Then, .


To disprove the statement ", we show that there exists an element such that is false, i.e., is true and is false.

Example. Disprove that for every , if , then .

Disproof. Take . Then but .


To disprove the statement "", we need to show that there is no such . That is, we need to show that "" (the negation of statement) is true. In this case, we are not just constructing counterexamples. We have to prove that , instead of .

Example. Disprove that there exists such that is odd.

Disproof. To disprove this, we need to prove that for every , is even. But this has been proved previously (in the section about proof by cases).


Often, before proving or disproving statements, the truth of falseness of them are not known, and we need to decide whether every of them is true or false. After that, we will prove it if it is true and disprove it otherwise. Of course, our decision is not perfectly accurate, and sometimes we make mistake, which leads us to do the opposite thing, i.e., proving a wrong statement or disproving a correct statement. Clearly, when we do such thing, we cannot succeed. However, the process of performing such wrong thing may give us some insights about what the correct direction is, and how to prove/disprove the statement.

To decide whether a statement is true or false, you may follow some tips below:

  • Follow your mathematical intuition. As you have learnt more about mathematics, you may have intuition and idea about whether a statement is true or false, before proving/disproving it.
  • Construct some simple examples. Such examples constructed may be a counterexample (for disproving "")/example (for proving "") if you are lucky. Even if they are not counterexamples/examples, you may observe some kind of patterns from it, which may give you some insights about how to prove/disprove the statement.

Example. Prove or disprove every of the following statements:

(a) There exists a real number satisfying the equation .

(b) Let and be sets. If , then .

(c) For every real number , .

(d) There exists a real number such that .

Solution.

(a)

Disproof. Since is a real number, we have and . Hence, , and thus for every .

(b)

Disproof. Take , and . Then, , but .

(c)

Disproof. Take . Then the LHS is undefined (the denominator is zero), but the RHS is -1.

(d)

Proof. Take . Then, and , and we have .


Clipboard

Exercise. Prove or disprove every of the following statements:

(a) There exists a real number such that and are both rational.

(b) There exists with such that .

(c) There exist even numbers and such that .

(d) For every , if and , then .

(e) For every with , there exists such that .

Solution
(a)

Disproof. We want to prove the statement is false. We use proof by contradiction.

Assume to the contrary that the statement is true, i.e., there exists a real number such that and are both rational. Then, we have is rational, which contradicts to the fact that (product of a rational number and an irrational number) is irrational.

(b)

Proof. Take and . Then, .

(c)

Proof. Take . Then, .

(d)

Disproof. Take and . Then, and , but .

(e)

Proof. For every , choose (sum/product of two rational numbers is rational). Since , we have , as desired.


Proof by mathematical induction

[edit | edit source]

The last proof method discussed in this chapter is proof by mathematical induction. This method is used to prove a statement in the form of "For every integer greater than or equal to an integer , is true.". That is, it is used to prove that a sequence of statements is true. Of course, we can prove that every of these statements is true one by one, but the principle of mathematical induction gives an alternative and more convenient method.

To prove the principle of mathematical induction, we need the well-ordering principle. Before introducing it, we need the definition of well-ordered.

Definition. (Well-ordered set) A nonempty set of real numbers is well-ordered if every nonempty subset of has a least element.

Example.

  • The set is well-ordered since its nonempty subsets are , and every of these subsets has a least element.
  • The sets are not well-ordered since none of these sets themselves have a least element (it can be proved that there is no smallest integer/rational number/real number).

Now, one may ask that whether the set is well-ordered. It may appear that it is well-ordered. Here, we will just regard this as an axiom:

Axiom. (Well-ordering principle) The set is well-ordered.

The well-ordering principle can then be used to prove (a less general version of) the principle of mathematical induction.

Theorem. (The principle of mathematical induction)

The principle of mathematical induction can be illustrated by the sequential effect of falling dominoes. " is true" means the first domino can be pushed down, and "for every integer , " means for every domino, if it falls down, then it will push the next domino down also. With these two requirements satisfied, every domino will fall down eventually (every statement involved is true).

For every , if are statements satisfying

(i) is true; and

(ii) for every integer , ,

then the statements are true.

This theorem is quite intuitive: with the conditions satisfied, we have an "infinite chain of implications":

  • is true (by (i)).
  • Thus, is true (by (ii)).
  • Thus, is true (by (ii)).
  • Thus, is true (by (ii)) ...

But strictly speaking, this is not counted as a proof. We will give a formal (partial) proof to this theorem below:

Proof. Here we only prove the case where .

Assume to the contrary that the theorem is false. Then, the conditions (i) and (ii) are satisfied by the statements, but there exist some positive integers for which is false. Now, let the set Since is a nonempty [16] subset of , by the well-ordering principle, contains a least element. Let us assume to be the least element.

Since is true by the condition (i), . This means the least element cannot be . Hence, , which means .

Since is the least element of , we have , i.e., is a true statement. Then, by the condition (ii), is true (we have ). It follows that . But this contradicts to our assumption that is the least element of (in particular, ).

Remark.

  • This proof can be extended to the case where . But the proof needs to use the result that the set is well-ordered. Once we have proven this result, we can simply change the set in the proof to , and also modify some sentences in the proof slightly for the extension.
  • Notice that in the inductive hypothesis, we assume is true for an arbitrary integer with , but not for every integer . This is because if we assume the latter, then we are assuming what we want to prove, and so the proof is invalid. While for the former assumption, we just assume is true for an arbitrary (but not every) integer with , but this does not lose generality since is arbitrary.

Using the principle of mathematical induction, to prove that the statement is true for every integer , it suffices to prove two things:

(i) is true.

(ii) For every integer , .

Thus, proof in this form is a two-step process. We often call the proof of (i) as the basis step or base case, and the proof of (ii) is called the inductive step. In particular, when we prove (ii), we usually use the method of direct proof, and first assume is true for an arbitrary integer with . Such assumption is often called the inductive (or induction) hypothesis.

Example. Prove that for every , is true.

Proof. Here we use the principle of mathematical induction.

Basis Step: Since , the statement is true.

Inductive Hypothesis: Let be an arbitrary positive integer. Assume is true. That is, assume is true.

Inductive Step: Since it follows that is true. Hence, by the principle of mathematical induction, is true for every positive integer .


Remark.

  • One can also prove this statement using a trick:
First write the sum as .
Now also write the same sum, but in reverse order: .
After that, add the two sums together in the following way:

Now, we can see that two times the sum gives . Thus, the sum is .
Clipboard

Exercise. For every , consider the sum Guess a general formula for the sum and prove it. (Hint: you may compute the value of sum for some values of , and see whether there are any patterns.)

Solution

When , the sum is respectively. Notice that and . Hence, it is natural to guess that the formula is, for every , But we have proved that . So this formula can be alternatively expressed as

Proof. Let be the open statement "".

Basis Step: Since , is true.

Inductive Hypothesis: Assume is true for an arbitrary positive integer . That is, assume

Inductive Step: Since is true. Hence, by the principle of mathematical induction, is true for every positive integer .

Remark.

  • The following diagram illustrates this statement:


We can use the proof by mathematical induction for proving some inequalities also:

Example. Prove that for every integer , .

Proof. Let be the open statement "".

Basis Step: Since , is true.

Inductive Hypothesis: Assume is true for an arbitrary integer with . That is, assume Inductive Step: Since it suffices to show that . Now, consider : Thus, is true. Hence, by the principle of mathematical induction, is true for every integer .


Clipboard

Exercise. Prove that for every integer , .

Proof

Let be the open statement "".

Basis Step: Since , is true.

Inductive Hypothesis: Assume is true for an arbitrary integer . That is, assume

Inductive Step: Since (we have since ) is true. Hence, by the principle of mathematical induction, is true for every integer .

Example. (Sum of a geometric sequence) Prove that for every integer and for every real number , we have

Proof. Let be the open statement "".

Basis Step: Since , is true.

Inductive Hypothesis: Assume is true for an arbitrary nonnegative integer . That is, assume

Inductive Step: Since is true. Hence, by the principle of mathematical induction, is true for every .


Example. (Cardinality of power set) Prove that for every set and for every integer , if is finite with , then .

Proof. Let be a finite set with cardinality and be the open statement .

Basis Step: Since , and , is true.

Inductive Hypothesis: Assume is true for an arbitrary nonnegative integer . That is, assume . In other words, there are subsets of .

Inductive Step: First, fix an element . Now let . Then, contains elements, and thus by inductive hypothesis, there are subsets of .

Let be a subset of . Since is a subset of , it follows that is a subset of . But, since . So, is also a subset of , that is distinct from . Thus, every subset of gives rise to two subsets of , namely and . As a result, there are subsets of without the element and subsets with the element .

So, we have subsets of altogether. Hence, , and thus is true. Hence, by the principle of mathematical induction, is true for every integer .


Clipboard

Exercise. (Generalization of De Morgan's law) Prove that for every subset of a universal set and for every integer , (Hint: you may use the ordinary De Morgan's law, i.e., for every subset of a universal set , .)

Proof. Let be the open statement ".".

Basis Step: By the ordinary De Morgan's law, is true.

Inductive Hypothesis: Assume is true for an arbitrary integer . That is, assume Inductive Step: Since it follows that is true. Hence, by the principle of mathematical induction, is true for every integer .


The strong form of induction

[edit | edit source]

In this section, we will discuss a stronger form of mathematical induction. Sometimes, we need this form of mathematical induction since merely assuming " is true ..." in the inductive hypothesis may not be enough to show that is true. We may need some more helps, particularly the fact that the statement is true for all cases from the basis step to the given . That is, if "" is 1, then we assume are all true.

Since "" is stronger than "", we have the name "the strong form of induction".

Theorem. (The strong form of induction) For every , if are statements satisfying

(i) is true; and

(ii) for every integer , ,

then the statements are true.

This theorem is also quite intuitive: with the conditions satisfied, we get an "infinite chain of implications":

  1. is true by (i).
  2. Because of 1., is true by (ii).
  3. Because of 1. and 2., is true by (ii).
  4. Because of 1., 2., and 3., is true by (ii) ...

Proof. The proof for the strong form of induction is similar to that of the principle of mathematical induction. We just need to modify some parts of the proof. The blue part is the modified part.

Here we only prove the case where .

Assume to the contrary that the theorem is false. Then, the conditions (i) and (ii) are satisfied by the statements, but there exist some positive integers for which is false. Now, let the set Since is a nonempty subset of , by the well-ordering principle, contains a least element. Let us assume to be the least element.

Since is true by the condition (i), . This means the least element cannot be . Hence, , which means .

Since is the least element of , we have , i.e., is a true statement. Also, (they are all less than ). Hence, are also true statements. Then, by the condition (ii), is true (we have ). It follows that . But this contradicts to our assumption that is the least element of (in particular, ).

Hence, to prove that the statement is true for every by the strong form of induction, we need to prove

(i) the basis step: is true; and (ii) the inductive step: for every integer , if are true (the inductive hypothesis), then is true.

We usually use the strong form of induction to prove results that are related to recurrence relation.

Example. A sequence of numbers is defined by , and (an equation in such form is called a recurrence relation). Prove that for every .

Proof. Let be the open statement "". Now, we will use the strong form of induction to prove that is true for every .

Basis Step: Since , is true.

Inductive Hypothesis: Let be an arbitrary positive integer. Assume that are true. That is, assume for every integer with .

Inductive Step: We want to show that is true, i.e., . Now, using the recurrence relation, we have So, we have proved that is true for the case where . Now, it remains to prove that is true when , but it is easy to prove that: , so is true. Hence, by the strong form of induction, is true for every .


Clipboard

Exercise. A sequence of numbers is defined by , and Guess a formula for for every , and prove it.

Solution

When compute for according to the recurrence relation, we get and . This pattern suggests us to guess that for every .

Proof. Let be the open statement "". Now, we will use the strong form of induction to prove that is true for every .

Basis Step: Since .

Inductive Hypothesis: Let be an arbitrary positive integer. Assume that are true.

Inductive Step: We divide our proof into two cases:

Case 1: . Then, . So, is true.

Case 2: . Using recurrence relation, we have Thus, is true.

Hence, is true for every by the strong form of induction.


Example. A sequence of numbers is defined by and then for every .

Proof. Let be the open statement .

Basis Step: Since , is true.

Inductive Hypothesis: Let be an arbitrary integer. Assume are true.

Inductive Step:

Case 1: . Then, .

Case 2: . Then, .

Case 3: . Then, Hence, is true.

By the strong form of induction, is true for every .


Remark.

  • It may appear that we consider quite "suddenly" in the proof above. Indeed, if we "think from the bottom" for case 3, then it is natural to consider it: we want , which is in the form of , to be less than . So, it is natural consider the "something".
Clipboard

Exercise. Consider the sequence of Fibonacci numbers, defined by and (a) Construct a table for comparing the value of against the value of for .

(b) Hence, make a guess in the form of " for every integer .", and prove the statement.

(c) By considering the even Fibonacci numbers in the table in (a), make a guess in the form of " is even if and only if , for every .", and prove the statement. (Hint: since there is "if and only if" in the statement, in the inductive step, we need to prove both "" direction and "" direction. But, we can prove both directions at once in this case.

(d) Prove that for every , where (golden ratio) and (conjugate of golden ratio). This gives a direct formula to compute th Fibonacci number, which is more efficient than using the recurrence relation in the definition for the computation. (Hint: The roots of the quadratic equation are and .)

Solution

(a) (b) From (a), it appears that when , increases faster than . So, it is natural to guess that for every integer .

Proof. Let be the open statement .

Basis Step: Since , is true.

Inductive Hypothesis: Let be an arbitrary integer with . Assume that are true.

Inductive Step: Using recurrence relation, we have Hence, is true, and by the strong form of induction, is true for every integer .

(c) From the table in (a), when (which are all multiples of 3), is even. This suggests us to guess that is even if and only if for every .

Proof. Let be the open statement is even if and only if .

Basis Step: Since is odd and , is true ().

Inductive Hypothesis: Let be a positive arbitrary integer. Assume that are true.

Inductive Step: By recurrence relation, . So, (We have , since by the compatibility with translation, it can be shown directly that , and after showing this, we have the desired logical equivalence.)

Thus, is true. Hence, by the strong form of induction, is true for every .

(d)

Proof. Let be the statement .

Basis Step: Since , is true.

Inductive Hypothesis: Let be a positive arbitrary integer. Assume are true.

Inductive Step:

Case 1: . Then, . Hence, is true.

Case 2: . Then, apply the recurrence relation: Hence, is true.

Thus, by the strong form of induction, is true for every .



Relations

Introduction

[edit | edit source]

Intuitively, relation associates pairs of objects based on some rules and properties. That is, relation suggests some kinds of relationship or connection between two objects. Take marriage as an example. In the marriage registry, there is a record in which the names of husbands are associated with the names of their corresponding wives, to keep track of the marriages. The entries in the record can be interpreted as ordered pairs , where is the husband, while is the wife.

Expressing it mathematically, let and be the set of all men and women respectively. Then, the Cartesian product consists of all pairs of people (first and second coordinate is a man and woman respectively). After that, we know that the record in the marriage registry, , is a subset of . If a man and a woman form an ordered pair in , say , then it means they are married. Then, it is natural to say that is related to . In other words, if we find that , then it means that they are related by this relation . Also, knowing what exactly is (we have the record from the marriage registry) is the same as knowing all the husband and wife relationship.

Thus, it is natural to define the set as a relation. Let us formally define relation below.

Terminologies

[edit | edit source]

Definition. (Relation) A relation from a set to a set is a subset of , i.e., . In particular, when , we say that is a relation on , and we have . If , then we say that is related to by , and write . On the other hand, if , then we say that is not related to by , and write .

Example. Let , , and . Since the set is a subset of , defines a relation from set to set . Also, in this relation, is related to 1, is related to 1 and 2, is related to 3. Thus, we have and . But, we have, say or , since .

Clipboard

Exercise.

(a) Suggest a set that is not a relation from set to set .

(b) Suggest a set that is a relation from set to set .


Solution

(a) (, so is not a subset of ).

(b) .


Clipboard

Exercise. Let and be two nonempty sets. Are and relations from to ? Describe the relationships meant by these two sets.

Solution

Both and are relations from to since both are subsets of .

For , it means nothing is related, i.e., there is no relationship between elements in and elements in .

For , it means everything is related, i.e., every element in is related to every element in .

Example. Let be a set of all human beings. Then, . Then, is a subset of , and defines the relation for son and (father or mother).

Example. The concept of "less than" defines a relation on . To be more precise, the relation corresponding to this concept is . For instance, but .

Example. The congruence of integers defines a relation on . To be more precise, the corresponding relation is ( with ). For example, when , then but .

Clipboard

Exercise. Consider the relation on , corresponding the concept of "equal to": .

(a) Sketch in the Cartesian coordinate system.

(b) Consider also the relations on corresponding the concept of "less than" and "greater than" respectively. Sketch also and in the graph in (a).

Solution

(a) and (b):

        y
        |    y=x     
########|#####/%%%
########|####/%%%% 
########|###/%%%%%
########|##/%%%%%%
########|#/%%%%%%%
########|/%%%%%%%%
--------*--------- x
#######/|%%%%%%%%% 
######/%|%%%%%%%%%
#####/%%|%%%%%%%%%
####/%%%|%%%%%%%%%
###/%%%%|%%%%%%%%%

*----*
|####|
|####| : y>x (relation T)
*----*

*----*
|%%%%|
|%%%%| : y<x (relation S)
*----*

Remark.

  • The sets give a partition of . As we will see, there is a close relationship between the concept of relation and the concept of partition.


Example. Let . Define a relation on , . Express by listing method.

Solution. First, we have . So,

Clipboard

Exercise. Let and . Consider a relation on defined by Express by listing method.

Solution

First, . So,

Definition. (Domain and range) Let be a relation from a set to a set . The domain of , denoted by is the subset of defined by The range of , denoted by , is the subset of defined by

Remark.

  • You may have learnt about the domain and range for functions. Using the same terminologies for both relations and functions is indeed not a coincidence. This is because a function is actually a relation. That is, a function is indeed just a special case of relation.

Example. Let , , and . Then, and .

Example. Consider the relation on : . Then, is the set of all even numbers, and is the set of all even numbers also.

Clipboard

Exercise. Consider the relation on : . Find and .

Solution

and .

Definition. (Inverse relation) Let be a relation from a set to a set . The inverse relation from to is

Remark.

  • Again, you may have learnt a similar concept (and also a similar notation) for functions: inverse functions. Indeed, inverse functions can be defined as the inverse relation of a function, provided that the inverse relation is also a function.
  • We can see that the inverse relation is obtained by "reversing" the order of elements in every ordered pair in the original relation.
  • When is empty, then the inverse relation is also empty since there is no ordered pair in the empty set.

Example. Let , , and . Then, the inverse relation is .

Clipboard

Exercise. Construct an example of sets and a nonempty relation from set to set such that .

Solution

Take , and . Then, .

Reflexive, symmetric and transitive relations

[edit | edit source]

After introducing the terminologies related to relations, we will study three properties for a relation defined on a set.

Definition. (Reflexive, symmetric and transitive) Let be a set and be a relation defined on . Then,

  • is reflexive if for every .
  • is symmetric if for every , .
  • is transitive if for every , .
Clipboard

Exercise. Let be a set and be a relation defined on . Write down the meaning of (i) is not reflexive; (ii) is not symmetric; (iii) is not transitive.

Solution

(i) There exists such that .

(ii) There exist such that but .

(iii) There exist such that and , but .

Example. Let , and let a relation defined on be Then, is reflexive since . But is not symmetric since but .

Clipboard

Exercise. Is transitive? Explain why.

Solution

is transitive since

  • ;
  • .

(There are no more ordered pairs and in the relation , satisfying and .)


Example. The congruence of integers defines a relation on ( with ). Prove that is a reflexive, symmetric and transitive.

Proof.

Reflexive: For every , . So, for every .

Symmetric: For every , where is some integer.

Transitive: For every ,


Clipboard

Exercise. Which of the properties, reflexive, symmetric and transitive, does each of the following relations possesses? Prove your answer.

(a) .

(b) .

(c) .

Solution

(a) is reflexive, not symmetric, and transitive.

Proof.

Reflexive: For every , . So, .

Not symmetric: Take and . Then, , so . However, . So, .

Transitive: For every , (this actually follows from the property of "").

(b) is not reflexive, not symmetric, and transitive.

Proof.

Reflexive: Take . Then, 1 is not less than 1 itself. Hence, .

Not symmetric: Take and . Then, , so . However, . So, .

Transitive: For every , (this actually follows from the property of "").

(c) is reflexive, symmetric and not transitive.

Proof.

Reflexive: For every ,

Case 1: . Then, . So, .

Case 2: . Then, . So, .

Symmetric: For every , .

Not transitive: Take and . Then, and . So, and . However, since , .


Clipboard

Exercise. Let be a relation on a set . Prove or disprove that

(a) if is reflexive, then is reflexive;

(b) if is symmetric, then is symmetric;

(c) if is transitive, then is transitive.

Equivalence relations and equivalence classes

[edit | edit source]

After studying the three properties that a relation on a set can possess, let us focus on those relations that possess all three properties.

Definition. (Equivalence relation) Let be a set. A relation defined on is an equivalence relation if it is reflexive, symmetric and transitive.

Remark.

  • To show that a relation is not an equivalence relation (i.e., to disprove that the relation is an equivalence relation), it suffices to show any one of the following: (i) it is not reflexive; (ii) it is not symmetric; (iii) it is not transitive, by considering the negation of the above definition.

Example. Let . Also let a relation defined on be Prove or disprove that is an equivalence relation.

Proof.

Reflexive: Since , is reflexive.

Symmetric: Since , , , and , is symmetric.

Transitive: Since for every , , is transitive.

Clipboard

Exercise. Give another equivalence relation that is defined on .

Solution

. It can be shown to be reflexive, symmetric and transitive.


Example. Since the congruence of integers defines a reflexive, symmetric and transitive relation, it defines an equivalence relation on .

Suppose is an equivalence relation on a set . Intuitively, for elements that are related by , they are quite "closely related". Thus, when we consider the set consisting elements that are related to a given element of set A, the elements inside the set are "closely related", so the set, in some sense, forms a "group" of elements that are "relatives". It then appears that we can classify the elements of set into different such "groups", according to an equivalence relation. As we will see, this is roughly the case. Hence, such "group" is quite important. Now, let us formally define what the "group" is:

Definition. (Equivalence class)

A graph that illustrates equivalence classes. The whole circle in the set on which the relation is defined, and when there is a line connecting two dots, it means the two dots (representing elements in the set) are related by the equivalence relation.

Let be an equivalence relation defined on a set . For every , the set consisting of all elements in that are related to , is called an (equivalence) class of by .

Example. Let , and let a relation defined on be This relation can be shown to be an equivalence relation. The equivalence classes are given by Since , there are only two distinct equivalence classes. Graphically, the situation looks like:

*----------**
|  .  .   / |
| 2   3  /  |
|  .    /.  |
| 1    /  4 |
*-----*-----*
  ^        ^
  |        |
[1]=[2]    [4]
=[3]
Clipboard

Exercise. Construct an equivalence relation on such that the equivalence classes are given by

Solution

. Graphically, the situation looks like:

*---*-------*
|  .| .     |
| 2 | 3     |
|  .\    .  |
| 1  \    4 |
*-----*-----*
  ^        ^
  |        |
[1]=[2]  [3]=[4]


Example. (Integers modulo ) Recall that the congruence of integers defines an equivalence relation on . Using this equivalence relation, we can define the equivalence class for every , as follows:

  • ...

We can observe that starting from , the classes are not distinct from the previous classes. Indeed, if we consider the classes "backward":

  • ...

They also do not give new classes.

Hence, we conclude that there are only distinct equivalence classes, namely . Usually, the set of these equivalence classes, , is denoted by , and is called integers modulo . Notice that is a finite set itself, but each of its elements is an infinite set.

Remark.

  • We can illustrate the equivalence classes as follows (each column is an equivalence class, and the whole table is ):
*----*----*---...---*-----*
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
|-n  |-n+1|         |-2n-1|
| 0  | 1  |  ....   | n-1 |
| n  |n+1 |         |2n-1 |
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
*----*----*---...---*-----*
  • When we consider integers modulo and integers modulo () together, there may be some ambiguities for the elements. For example, and . However, for instance, the "" in and the "" in are different. One of them contains all even numbers, another contains all multiples of 3.
  • To avoid such ambiguities, we may add a subscript to the classes. For instance, we may write and .
Clipboard

Exercise. A relation on is defined by (a) Prove that is an equivalence relation.

(b) Express each of the equivalence classes by in terms of (Hint: use the symmetric property of ).

Solution
(a)

Proof.

Reflexive: For every , since , .

Symmetric: For every , since .

Transitive: For every ,

(b) (By the symmetric property of , . Also, . So, .)

Properties of equivalence classes

[edit | edit source]

In this section, we will discuss some properties of equivalence classes. In particular, we will address these two questions:

  1. When are two equivalence classes equal?
  2. Can two different equivalence classes contain a common element?

The answer to question 1 is given by the following theorem.

Theorem. Let be an equivalence relation defined on a set . For every ,

Proof. "" direction: Assume . Since is an equivalence relation, and in particular, is reflexive, we have . Thus, we have by definition . Then, since by assumption, we have .

"" direction: Assume . First, for every , So, .

On the other hand, first, since by assumption, we have by the symmetry of . Now, For every , So, .

Hence, .

Remark.

  • From this theorem, we know that "" is the necessary and sufficient condition for "". Also, we have if and only if .

Now, let us consider the question 2. The answer to question 2 is, indeed, "No". The following corollary justifies this answer:

Corollary. Let be an equivalence relation defined on a nonempty set . For every ,

Proof. "" direction: ( and are nonempty since is reflexive. So they must contain, at least, and respectively.)

"" direction: We use proof by contrapositive.

Remark.

  • From this result, we know that two equivalence classes are either equal or disjoint (since they are either equal or not equal). Hence, it is impossible for two different equivalence classes to contain a common element.

Now we have reached a key point in studying equivalence relations (and it is probably the major reason for studying equivalence relations at all): using equivalence relation on a set to construct a partition of that set, and vice versa. Before discussing it, let us define partition of a set:

Definition. (Partition) A partition of a nonempty set is a set of nonempty subset(s) of with the property that every element of belongs to exactly one of the subset(s). In other words, is a collection of pairwise disjoint and nonempty subset(s) of whose union is .

Example. Let . Then, a partition of is . Another one is . However, is not a partition of since and are not disjoint (or the element "2" belongs to two sets). Also, is not a partition of since the union of and is not the entire set (or the element "2" does not belong to any of the sets inside the partition).

Clipboard

Exercise. Is a partition of ?

Solution

Yes, since every element of belongs to exactly one of the set inside the partition, namely the set .


Example. Let , and let a relation defined on be Recall that the two distinct equivalence classes are given by We can see that every element of belongs to exactly one of these equivalence classes. Hence, the set gives a partition of .

Also, we can define another equivalence relation on such that the two distinct equivalence classes are given by We can also see that every element of belongs to exactly one of these equivalence classes. hence, the set .

Example. Recall that the congruence of integers defines an equivalence relation on . Also, there are distinct equivalence classes: . By Euclid's division lemma, every integer belongs to exactly one of these equivalence classes. Thus, the integers modulo gives a partition on .

We can observe from the previous examples that equivalence relation of a set can be used to give a partition of that set. The following theorem suggests that, in general, an equivalence relation on a set can be used to give a partition of that set.

Theorem. Let be an equivalence relation defined on a nonempty set . Then the set of all distinct equivalence classes by is a partition of .

Proof. It suffices to show that every element of belongs to exactly one of the distinct equivalence classes.

For every , since is reflexive, we have . From this, we can ensure that every element of belongs to at least one of the distinct classes. It now remains to show that every element of also belongs to at most one of the distinct classes.

Assume that also belongs to the class . Then, we have . Since is an equivalence relation, it means by a previous theorem. Thus, any two equivalence classes to which belongs are equal. This means every element of cannot belong to more than one of the distinct classes.

Hence, every in belongs to exactly one of the distinct classes, and thus the set of all distinct equivalence classes by gives a partition of .

The following theorem suggests the converse of the above theorem is also true. To be more precise, we can use a partition of a set to construct an equivalence relation on that set. Before introducing the theorem, let us make some intuitive guesses on how to construct the equivalence relation in this way. First, from the previous theorem, roughly speaking, using an equivalence relation on a set, we can create several "groups" of elements in different classes, in which the elements are "relatives".

Now, given a partition of a set, it means we have several "groups" of elements. Such "grouping" intuitively indicates the elements inside the group are "relatives" in some sense. So, intuitively, a relation that relates the "relatives" seems to make the relation quite "close", and hence an equivalence relation.

The following theorem formalizes this intuition:

Theorem. Let be a partition of a nonempty set . Define a relation on by Then, the relation is an equivalence relation on the set .

Proof. It suffices to prove that defined in this way is reflexive, symmetric, and transitive.

Reflexive: By the definition of partition, for every , belongs to exactly one of , so there exists such that . Hence, .

Symmetric: For every , Transitive: For every , assume and . Then, there exist such that and . But by the definition of partition, belongs to exactly one of the set in the partition . So, we have . Hence, there exists a set () such that , and thus .

Example. Let be a relation defined on by

(a) Prove that is an equivalence relation.

(b) Determine all distinct equivalence classes by and hence give a partition on .

Solution.

(a)

Proof. Reflexive: For every , . So, .

Symmetric: For every , .

Transitive: For every , .

(b) First, some equivalence classes are So, all distinct equivalence classes are (, so is not distinct from them, etc.). Hence, a partition on is (that is, every integer belongs to exactly one of .)

Clipboard

Exercise. Let be a relation defined on by

(a) Prove that is an equivalence relation.

(b) Determine all distinct equivalence classes by , and hence give a partition on .

Solution
(a)

Proof. Reflexive: For every , since is even, .

Symmetric: For every , .

Transitive: For every ,

(b) First, some equivalence classes are Since every integer belongs to exactly one of and (i.e., all other equivalence classes are not distinct from them), it follows that and are all distinct equivalence classes.

Remark.

  • Recall that the sum of two integers is even if and only if they have the same parity. So, this relation relates every pair of integers that have the same parity. So, intuitively, the relation can partition the integers into two "pieces": set of all odd integers and set of all even integers.



Functions

Introduction

[edit | edit source]

In the previous chapter, we have discussed the concept of relations. There are not much restrictions on the relations. For instance, for a relation from set to set , every element of can be related to no elements of , exactly one element of , or multiple elements of . In this chapter, we will focus on a particular type of relations from set to set where every element in is related to exactly one (or a unique) element of .

You should have encountered the concept of functions before, e.g. a function defined by gives you a value of for every given value of . The functions you have encountered are likely to be in the above form, i.e. in the form of an equation. Also, the value of and are likely to be real numbers.

But we can generalize such ideas to more general situations where and are not necessarily real numbers (e.g., they can be elements of certain sets), and the functions need not be expressed by a formula like above. As a result, the concept and definition of functions discussed here may seem foreign to you, and look quite different from what you have previously learnt about functions.

Definitions

[edit | edit source]

Definition. (Functions) Let and be sets. A function or mapping from set to set , written , is a relation from set to set such that for every element , there exists a unique such that .

Remark.

  • The notation "" may seem weird at the first place. However, when we think about what represents here, it becomes more natural: since is a relation from set to set , it is indeed a subset of . So, it makes sense to say is an element of .
  • However, it is much more common to write instead (and you should have seen this notation before).
  • Since is a relation, we can apply the terminologies to functions: the set is the domain of function , denoted by .
  • We also have some more terminologies for functions: The set is called the codomain of , is the image of under . Also, is referred to as the pre-image of under . Furthermore, we say that maps into .
  • From the definition, every element has a unique (or exactly one) image.
  • When the set is empty, then the only function (and also the only relation) from set to is the empty set. When set is nonempty while the set is empty, since the only relation from set to is also the empty set, but such relation does not satisfy the requirements to be a function (there does not exist such that for every ).
Clipboard

Exercise. Write down the meaning of " is not a function from to ", i.e., the negation of the definition above. (Hint: first split the unique existential quantifier into two the existence part and uniqueness part.)

Solution

First, we express the meaning of " is a function from to " using logical notations: Then, the meaning of " is not a function from to " is: (LHS means the existential requirement is violated, and RHS means the uniqueness requirement is violated.) In other words, the meaning is "there exists some with no image, OR there exists some with more than one image".

Example. Let and . Then, defines a function. Graphically, it looks like

  A               B
*----*          *----*
|1*  #
|    |  #       |    |
|    |       #  |    |
|    |          |#   |
|2* # # # # # #  # *a|
|    |          |    |
|3* # # # # # #  # *b|
|    |          |    |
*----*          *----*

Here, is the image of 1 and 2 under . In other words, 1 and 2 are the pre-images of . Similarly, is the image of 3 under and 3 is the pre-image of under .

Example. Let and . Then, is not a function from to since has two images: 1 and 2. Also, is not a function from to since and have no image.

Example. It is quite common to refer, say, "" to as a "function". But, when we look at the definition of function, such saying actually has some issues, strictly speaking:

  1. What are the domain and codomain?
  2. is just an image of a real number under . The function itself should be a set.

For the first question, usually the domain and codomain are taken to be . But for some functions, becomes undefined for some values of real number . In this case, it is common to set the domain as , which is referred to as the natural domain.

For the second question, the actual function is indeed the set This set of point in the plane is the graph of (a parabola). However, it is acceptable to have such saying for convenience.

Clipboard

Exercise. A commonly encountered function is the exponential function, which is defined by . Another one is the natural logarithm function defined by .

(a) Find the domain and codomain of the functions and .

(b) Express the functions and using sets.

Solution

(a) The domain and codomain of are both . The domain of is (when is less than or equal to zero, is undefined), and the codomain of is .

(b) and .

We should be aware that the codomain of a function is not necessarily the same as the range of a function. The following is the definition of the range of a function (same as the definition for a relation).

Definition. (Range of function) The range of a function , denoted by , is

Remark.

  • Comparing the definitions of range and codomain, we can notice that for the range, it includes all elements in the codomain that have at least one pre-image. On the other hand, the codomain is the set that contains everything into which every element can be possibly mapped.
  • When the range and the codomain of a function turn out to be the same, we call such function to be surjective. We will discuss more properties for a function later.
  • We can observe that we can actually manually set (or restrict) the codomain of function to be its range. So, even if a given function is not surjective, we can make it surjective by changing its codomain manually.

Example. Let and . Define the function by Then,

Clipboard

Exercise. Let and be sets, and be a fixed element of . Then, the function defined by for every is called the constant function from to .

(a) What is the range of constant function?

(b) What is the codomain of constant function?

(c) Can the range of constant function equal its codomain?

(d) What is/are the pre-image(s) of ?

Solution

(a) The range is .

(b) The codomain is the set .

(c) Yes, if .

(d) The pre-images of are all elements of .

Example. (Identity function) Let be a set. Then the function defined by for every is called the identity function of . Every is the image of itself. The domain, codomain, and range of are all .

Remark.

  • This function is quite important in the section about inverse functions.

Example. Consider the function defined by . Find the range of the function , , and prove your answer.

The range of the function is .

Proof. To prove that , we will prove (i) ; (ii) .

Firstly, for : for every , On the other hand, for : for every , we choose . Then, . So, by definition, we have .


Clipboard

Exercise. Consider the function defined by . Find , and prove your answer.

Solution

We have .

Proof. First, for every , This shows that .

On the other hand, for every , we choose . Then, . So, we have . This shows that , and we are done.


Since the domain and codomain, in addition to the "way" of the mapping, all affect the "behaviour" and properties of a function, it is natural to incorporate all these features into the definition of equality of functions:

Definition. (Equality of functions) Let and be sets, and let and be two functions from to (notice that their domains and codomains have to be the same). Then, the functions and are said to be equal, written , if for every .

Clipboard

Exercise. Write down the meaning for two functions and to be not equal.

Solution

( and have different domain) or ( and have different codomain) or (there exists such that ).

Example. Consider the functions and defined by and . Although their "formulas" are the same, they are not equal since their codomains are different.

Clipboard

Exercise. Consider the functions and defined by and . Are the functions and equal? Why?

Solution

No.

Notice hat is undefined when (and defined for every other real number ), while is defined for every real number . Thus, the domain of is and the domain of is . So, and are not equal.

Injective, surjective and bijective functions

[edit | edit source]

In this section, we will discuss some important properties that a function may possess, namely injectivity, surjectivity, and bijectivity.

Definition. (Injective function) A function is injective or one-to-one if for every , , or equivalently (contrapositive), for every , .

Remark.

  • The definition tells us that an injective function from to maps distinct elements of into distinct elements of .
  • To prove that a function is injective, it is common to use a direct proof: for every , assume , and then proceed to prove that .
Clipboard

Exercise. Write down the meaning of "a function is not injective".

Solution

There exist such that and .

Example. A function is defined by . Prove that is injective.

Proof. For every , Thus, is injective.


Example. A function is defined by . Prove or disprove that is injective.

Disproof. Since , is not injective.

Clipboard

Exercise. A function is defined by . Prove that is injective.

Proof

Proof. For every ,

Remark.

  • It suggests that the domain of a function is important when we determine whether a function is injective. We should not just look at the formula of the function.



Example. A function is defined by . Prove or disprove that is injective.

This time, it is not immediately clear that whether this function is injective or not. So, we may first try to prove that is injective, and see what we get: for every , Notice that for the last equation to imply , we need and . However, and can take any real values. Hence, this suggests us to consider and disprove that is injective. Another observation is that when , then . But to make it equal zero, we can also take . Thus, this gives us a counterexample for disproving that is injective:

Disproof. Since , is not injective.


Clipboard

Exercise. A function is defined by . Prove or disprove that is injective.

Solution

Disproof. Since , is not injective.

Remark.

  • The graph of this function is a semicircle located above the -axis.


Definition. (Surjective function) A function is surjective or onto if for every , there exists such that .

Remark.

  • The definition tells us that is surjective if every element of the codomain is the image of some element of . In other words, .
Clipboard

Exercise. Write down the meaning of " is not surjective".

Solution

There exists such that for every , .

In other words, some element of the codomain is not the image of every element of . In other words, (since by definition, we may also write this as ).

Example. A function is defined by . Prove that is surjective.

To prove that is surjective, we need to prove that for every , there exists such that , i.e., . To show this, we can see that the choices of to satisfy the requirement for different values of are different. Indeed, the choice of depend on the value of . But it is not hard to choose such with a given value of : we can just rearrange the above equation to make to be the subject of the equation:

Proof. For every , choose . Then,


Example. Prove or disprove that the function defined by is surjective.

Disproof. Take . Then, there is no such that since has no real solution. Hence, is not surjective.

Clipboard

Exercise. Prove that the function defined by is surjective.

Proof

Proof. For every , choose (it is possible to choose such real number since ). Then,

Remark.

  • It suggests that the codomain of a function is important when we determine whether a function is surjective. So, again, we should not just look at the formula of the function.



Definition. (Bijective function) A function is bijective or one-to-one correspondence if it is both injective and surjective.

Remark.

  • We should be aware that "one-to-one correspondence" (which means bijective) is different from "one-to-one" (which means injective).
  • In other words, is bijective if for every , there exists a unique such that (the existence part corresponds to the surjectivity, and the uniqueness part corresponds to the injectivity).
  • However, we usually still prove the bijectivity by proving the injectivity and surjectivity separately, similar to the case for proving "there exists a unique ..." where we prove the existence part and uniqueness part separately.
Clipboard

Exercise. Write down the meaning of " is not bijective".

Solution

is not injective or is not surjective.

Example. We have proved the function defined by is both injective and surjective. Hence, it is bijective.

Example. We have proved the function defined by is injective and the function defined by is surjective. Then, with basically the same proof, we can prove that the function defined by is both injective or surjective, and hence bijective.

Example. Prove that the function defined by is bijective.

For proving the surjective part, we need to make as the subject for the equaton :

Proof.

Injective: For every , Surjective: For every , choose . We then need to show that . Since (, so is defined), it suffices to show that . Let us prove it by contradiction:

Assume to the contrary that . Then, . So we arrive at a contradiction.

Then, we have


Clipboard

Exercise. Let be a set. Prove that the identity function is bijective.

Proof

Proof.

Injective: For every , .

Surjective: For every , choose . Then, .


Clipboard

Exercise. A function is defined by Prove or disprove that is bijective.

Solution

Proof.

Injective: For every ,

Surjective: For every , choose . Then,


Clipboard

Exercise. Consider a function defined by , and another function defined by .

(a) Prove or disprove that is (i) injective; (ii) surjective.

(b) Prove or disprove that is (i) injective; (ii) surjective.

Solution
(a) (i)

Disproof. Since , is not injective.

(ii)

Disproof. Take . Then, for every , .

(b) (i)

Disproof. Since , is not injective.

(ii)

Proof. For every , choose . Then, .


Composition of functions

[edit | edit source]

Let and be nonempty sets, and let and be two functions. In this section, we are going to discuss a way to create a new function from "combining" the two functions and , called their composition:

Definition. (Composition) Let and be two functions, where and are nonempty sets. Then, the composition of and , denoted by (read "g-circle-f"), is the function from to defined by

Remark.

  • We can see that the composition is obtained by first applying and then applying .

Example. Let and . Consider the functions and defined by Then, we have and . So, the function is given by However, is undefined, since the codomain of () is different from the domain of ().

Remark.

  • To make both and defined, we need to have and , that is, the domain (codomain) of must be equal to the codomain (domain) of .
  • In this case, is a function from to , and is a function from to . So, in order for them to be possibly equal, we need to further have .
  • But, even if , it is still possible that . Consider the following example.

Example. Let . Consider the functions and defined by Then, and . Since, for example, , it follows that .

Remark.

  • This example shows that the composition of functions is not commutative. That is, after changing the order of the composition, the result may be different.

Although the composition of functions is not commutative, it is associative.

Theorem. (Associativity of the composition of functions) For every nonempty set , and for every function and , we have

Proof. First, since is a function from to , it follows that is a function from to . Similarly, since is a function from , it follows that is function from to .

It now remains to prove that both functions map every element into the same image in . For every , (a bracket for means "grouping" and first, that is, we regard as a function first. To understand this more easily, one may write instead of "" above.)

Also,

Example. Let and . Consider the functions , and defined by Recall that we have shown that . We can further show that . Thus, and are given by

Now, let us study some results that are related to the composition, injectivity, surjectivity, and bijectivity.

Proposition. For every nonempty set and for every function and ,

(a) if and are injective, then is injective.

(b) if and are surjective, then is surjective.

Proof. For (a), assume that and are injective. Then, for every For (b), assume that and are injective. Then, for every , since is surjective, there exists such that . For this , there must also exist such that since is surjective. It follows that for every , there exists such that

Corollary. For every nonempty set and for every function and , if and are bijective, then is bijective.

Proof. Assume that and are bijective, i.e., are injective and surjective. It follows by the above proposition that is injective and surjective, i.e., is bijective.

After knowing such results, it is natural to question that whether the converse of the above proposition holds. Indeed, the converse does not hold, and we have the following results:

Proposition. For every nonempty set and for every function and ,

(a) if is injective, then is injective.

(b) if is surjective, then is surjective.

Proof. For (a), assume that is injective. Then, for every , For (b), assume that is surjective. Then, for every , there exists such that . So, we now can show that is surjective: for every , we can choose , and then we have .

Remark.

  • It follows that if is bijective, then is injective and is surjective.
  • For (a), with the assumption, may or may not be surjective. Also, for (b), may or may not be injective.

To summarize the results, we have the following table:

Summary
(given)
injective injective injective/not injective
surjective surjective surjective/not surjective
bijective injective surjective
Clipboard

Exercise. Disprove that for every nonempty set and for every function and ,

(a) if is injective, then is injective.

(b) if is surjective, then is surjective.

Solution
(a)

Disproof. Take , and take the functions and defined by .

Then, the function is given by , which is injective, since for every , . However, the function is not injective since .

(b)

Disproof. Take , and take the functions and defined by .

Then, the function is given by , which is surjective, since for every , there exists such that . However, the function is not surjective, since, for example, take . Then, for every , .


Example. Consider two arbitrary functions and such that the function is given by What properties do the functions and possess?

Solution. First, we claim that is bijective.

Proof.

Injective: for every , .

Surjective: for every , choose . Then, .

Then, we can conclude that is injective and is surjective by the above proposition.

Clipboard

Exercise. Consider the function satisfying for every . Prove or disprove that is (i) injective; (ii) surjective.

Solution

(i) and (ii):

Proof. First, notice that , and we have proved that is bijective. So, by the above proposition, is injective and surjective.


Inverse functions

[edit | edit source]

Recall that a function is a special relation from set to set satisfying some requirements. Also, recall that given a relation from to , the inverse relation is defined to be We know that the inverse relation is always a relation itself. However, is the inverse relation of a function always a function from to itself? The answer is, indeed, no. Consider the following example.

Example. Let and . Consider the function defined by Then, the inverse relation (we are not calling it inverse function) of , denoted by , is We can then see that this inverse relation is not a function from to , since the element has two images: 1 and 2.

Of course, when the inverse relation of a function turns out to be also a function from to , it is natural to define it as the inverse function of :

Definition. (Inverse function) Let and be sets, and let be a function. The inverse function of the function is the inverse relation of , denoted by , provided that is a function from to .

Remark.

  • Since given a relation from to , it has a unique (or exactly one) inverse relation from to (according to the definition), it follows that the inverse function of a function , if exists, is unique.

We are then interested in knowing under what conditions the inverse relation is a function from to , so that the inverse function exists.

First, in order for to be a function from to , we must have . So, we need to ensure that every element of is related to some elements in , so that when we "reverse" the ordered pairs in to get , there is at least one image for every . This means , i.e., needs to be surjective.

Of course, we also need to ensure that there is a unique image for every . Under the condition that is surjective, there is at least one image for every already. So, it remains to ensure that there is at most one image for every .

To ensure this, we need the function to be injective, since, if is injective, then every element of has at most one pre-image. So, when we "reverse" the ordered pairs in to get , every element of has at most one image.

From this discussion, we know that if is a function from to , then has to be injective and surjective, i.e. bijective. This shows that the bijectivity of is the necessary condition for the existence of the inverse function. Is it also the sufficient condition? It turns out that the bijectivity of is actually the necessary and sufficient condition for the existence of the inverse function:

Theorem. Let be a function. Then its inverse relation is a function from to (i.e., the inverse function of exists) if and only if the function is bijective.

Proof.

"" direction: Assume that is a function from to . Then, we will proceed to prove that is injective and surjective:

Injective: For every , first assume . Then, . By definition of inverse relation, we have . Since is a function from to , we have by definition .

Surjective: For every , since is a function from to , there exists a unique such that . This means by definition of inverse relation that , i.e., .

"" direction: Assume that is bijective. Then, we will proceed to prove that is a function from to . That is, we need to ensure that for every element , there exists a unique such that .

Existence: For every , since is surjective, there exists such that , i.e. . Hence, . This shows that for every , there exists such that .

Uniqueness: Assume , in addition to . So, we have , i.e., . Since is injective, we have .

Hence, from this theorem, we know that it is only meaningful to talk about inverse function of when is bijective. If is not bijective, then its inverse function does not exist at all, and it is meaningless to talk about it. The following theorem further suggests that the inverse function must also be bijective.

Theorem. If the function is bijective, then its inverse function is also bijective.

Proof. Assume that is bijective. Then, is a function from to . Then, we will show that it is injective and surjective.

Injective: For every , first assume . Then, . Thus, . It follows that since is a function.

Surjective: For every , since is a function, there exists a unique such that , i.e., , and hence , i.e., .

Remark.

  • Notice that in the proof, we do not make use of the bijectivity of to prove the injectivity and surjectivity of . Indeed, we just use the definition of function to prove them. The bijectivity of serves only one purpose: ensuring that the inverse function exists.

Another common definition of inverse function is that the inverse function of , denoted by , is a function satisfying It turns out that these two definitions of inverse function are indeed (logically) equivalent. Consider the following theorem.

Theorem. Let and be two functions such that and . Then, is bijective and equals the inverse function of , .

Proof. Let us first prove that is bijective.

Injective: For every , Surjective: For every , choose . Then,

Now, let us prove that . Since is bijective, the inverse function exists. Then, since the domain and codomain of the inverse function is and respectively by definition, and have the same domain and codomain. It now remains to show that for every . Since is surjective, for every , there exists such that . This means . Now, we have for every ,

The converse of the above theorem is also true. More precisely, if is bijective, and thus its inverse function exists, then we have and . (Details are left to the following exercise.) Hence, the two definitions are actually logically equivalent, in the sense that

  • by the above theorem, the conditions in the alternative definition imply the conditions in our definition.
  • by the above remark, the conditions in our definition imply the conditions in the alternative definition.

It then follows that the function satisfying and is unique, since the inverse function is unique.

Clipboard

Exercise. Let be a function. Prove that if is bijective, and thus its inverse function exists, then we have and .

Proof. First, since is a function from to , it follows that is a function from to , and is a function from to .

Then, for every , there exists a unique such that , and hence . So, Also, for every ,


Here, we will introduce an approach to find a formula for the inverse function. But this approach does not always work.

Example. Recall that we have proved that the function defined by is bijective. So, its inverse function exists. Determine the inverse function .

Solution. We have for every , . Hence, Thus, the inverse function is given by

In this approach, we use some algebraic manipulation to find the inverse function. However, such method is not always possible. For instance, the function defined by is bijective, but its inverse function is given by (indeed, defined to be) . In this case, such inverse function cannot be obtained by such algebraic manipulation.

Clipboard

Exercise. Consider the function defined by (a) Prove that is bijective.

(b) Determine the formula for inverse function, .


Solution
(a)

Proof.

Injective: For every , Surjective: For every , choose . Then,

(b) Since for every , we have But the codomain of the inverse function is . So we should choose the positive square root as the formula, i.e.,

Remark.

  • It turns out that, in this case the function is equal to its inverse function .


Image sets and preimage sets

[edit | edit source]

The concepts discussed in this section are the generalizations of the concepts of image and pre-image.

Definition. (Image (set) and preimage (set)) Let and be sets, and let be a function.

(a) Suppose . The image (set) of is the set (b) Suppose . The preimage (set) of is the set

Remark.

  • Notice that the "" used in the notation for the preimage set is not referring to the inverse function. The preimage set of still makes sense even if the function is not bijective. However, the inverse function does not exist if the function is not bijective.
  • In other words, the image set contains the image of every element . So, it is a set of images, and hence the name.
  • On the other hand, the preimage set contains the pre-images of every element . That is, the preimage set is the set of elements in mapped into by .
  • Special case: suppose and . Then, the image set of is the set containing image of under : , and the preimage of set is the set containing the preimages (if any) of under .

Graphically, the image set looks like:

   A              B
*------*       *------*
|      |       |      |
|  . X |       | f(X) |
|.###. |       |  .   |
|.###.--------->.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

The preimage set looks like

   A              B
*------*       *------*
|f-1(Y)|       |      |
|  .   |       |  Y   |
|.###. |       |  .   |
|.###.<---------.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

Example. Let and . Consider the function defined by Then,

Remark.

  • Notice that is not bijective, but it is still meaningful to consider the preimage sets of . For instance, we have , but "" has no meaning since does not exist at all.
  • We can observe that but . So, in general. Also, we can notice that after "applying" the image set and then preimage set on a set , it seems that we may get some set that is larger than .
  • On the other hand, we can see that but . So, in general. Also, it seems that we get some set that is smaller than .
  • Such kind of results turns out to be true in general (see the following theorem).
Clipboard

Exercise. Consider a function . Find (a) ; (b) ; (c) ; (d) .

Solution

(a) .

(b) .

(c) .

(d)