Mathematical Proof/Print version

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

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 , 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

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 $a\in A$ to mean that the element $a$ belongs to the set $A$. If $a$ does not belong to $A$, we write $a\notin A$.

Example.

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

Ways of describing a set

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, $\{1,2\}$ and $\{2,1\}$ 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, $\{1,1,2,2,2\}$ and $\{1,2\}$ 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 $\varnothing$. This kind of set is called an empty set.

Another way to describe a set is using words. For example, consider the set $S$ of prime numbers less than 10. If we use the listing method instead, the set $S$ is represented by $\{2,3,5,7\}$.

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: $$\underbrace {\{} _{\text{The set of}}\underbrace {x} _{{\text{all elements }}x}\underbrace {:} _{\text{such that}}\underbrace {P(x)} _{{\text{the property }}P(x){\text{ is satisfied}}}\}$$

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

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

Example.

• $\{x:3x+2=0\}=\{-2/3\}$.
• $\{y:y{\text{ is a positive odd number}}\}=\{1,3,5,\ldots \}$.
• $\{z:z{\text{ is an English letter}}\}=\{a,b,c,\ldots ,z,A,B,\ldots ,Z\}$.

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

1

The set ${\big \{}\{\}{\big \}}$ contains no elements.

	True.
	False.

2

$\{\}=\varnothing .$

	True.
	False.

3

$\{1,1,2,3\}$ is a set.

	True.
	False.

4

$\{x:0<x<2{\text{ and }}x^{2}=4\}=\{2\}$.

	True.
	False.

5

$\{a,b,b\}\in \{\{a,b\},a,b,b\}$.

	True.
	False.

6

$\{\{a\},\{a\}\}\in \{\varnothing ,\{a\},\{b\},\{a,b\}\}$.

	True.
	False.

Set cardinality

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 $S$, its cardinality is denoted by $|S|$.

Example.

• Let $A=\{{\text{red}},{\text{yellow}},{\text{blue}}\}$. Then, $|A|=3$.
• Let $B=\{\varnothing ,\{\varnothing \},\varnothing \}$. Then, $|B|=2$ (not 3 since the element $\varnothing$ is listed repeatedly).
• Let $C=\{x:x^{2}<0\}$. Then, $|C|=0$ since there is no solution for $x^{2}<0$ (for real number $x$), and thus $C$ is an empty set.
• Let $D=\{y:y^{2}-4y+4=0\}$. Solving $y^{2}-4y+4=0\Leftrightarrow (y-2)^{2}=0$, we have $y=2$. Hence, $D=\{2\}$ and thus $|D|=1$ .

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

• $\mathbb {N}$ is the set of all natural numbers (0 is not regarded as a natural number in this book).
• $\mathbb {Z}$ is the set of all integers.
• $\mathbb {Q}$ is the set of all rational numbers.
• (nonstandard notation) $\mathbb {I}$ is the set of all irrational numbers.
• $\mathbb {R}$ is the set of all real numbers.
• $\mathbb {C}$ is the set of all complex numbers.

In particular, we can use set-builder notation to express $\mathbb {Q}$, as follows: $\mathbb {Q} =\{p/q:p,q\in \mathbb {Z} {\text{ and }}q\neq 0\}$.

Example.

• ${\sqrt {2}},{\sqrt {3}}\notin \mathbb {Q}$
• ${\sqrt {5}},\pi ,e\in \mathbb {I}$

Exercise. Use set-builder notation to express $\mathbb {C}$ without using "$\mathbb {C}$" in the expression.

Solution

We can express like this: $\mathbb {C} =\{x:x=a+bi{\text{ and }}a,b\in \mathbb {R} \}$ ($i={\sqrt {-1}}$).

Subsets

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

Remark.

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

Example.

• $\mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C}$.
• $\mathbb {Z} \not \subseteq \mathbb {I}$ (e.g. $1\in \mathbb {Z}$ but $1\notin \mathbb {I}$)
• $\mathbb {C} \not \subseteq \mathbb {R}$ (e.g. $i\in \mathbb {C}$ but $i\notin \mathbb {R}$)
• For each set $S$, $S\subseteq S$, i.e. each set is a subset of itself.

• This is because each element of set $S$ is an element of $S$.

• For each set $S$, $\varnothing \subseteq S$.

• If we want to prove this directly, there are some difficulties since $\varnothing$ does not contain any element. So, what is meant by "each element of $\varnothing$"?
• 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 $\varnothing \not \subseteq S$. By the negation of the definition, there is at least one element of $\varnothing$ that is not an element of $S$, which is false. This yields a contradiction, and thus the hypothesis is false (explanation will be provided later), i.e. $\varnothing \not \subseteq S$ is false.

Definition. (Proper subset) A set $A$ is a proper subset of a set $B$ (denoted by $A\subsetneq B$) if $A$ is a subset of $B$ and $A\neq B$.

Remark.

• Similarly, if $A$ is not a proper subset of $B$, we write $A\not \subsetneq B$.

Example.

• For each nonempty set $S$, $\varnothing \subsetneq S$ since $\varnothing \subseteq S$ (shown previously) and $\varnothing \neq S$ if $S$ is a nonempty set.
• $\mathbb {N} \subsetneq \mathbb {Z} \subsetneq \mathbb {Q} \subsetneq \mathbb {R} \subsetneq \mathbb {C}$.
• $\{1,2\}\subsetneq \{1,2,3\}$.
• $\{1,2\}\not \subsetneq \{\{1,2\},2,3\}$ and $\{1,2\}\not \subseteq \{\{1,2\},2,3\}$.

Exercise. Let $A=\{1\}$.

1

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

	$\{1\}$
	$\{\}$
	$\{\{1\}\}$
	$\{1,\{1\}\}$

2

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

	$\{1\}$
	$\{\}$
	$\{\{1\}\}$
	$\{1,\{1\}\}$

3

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

	$\{1\}$
	$\{\}$
	$\{\{1\}\}$
	$\{1,\{1\}\}$

We call some commonly encountered subsets of $\mathbb {R}$ intervals. For each real number $a,b$ such that $a<b$,

• $(a,b){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a<x<b\}$ (open intervals)
• $(a,b]{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a<x\leq b\}$ (half-open (or half-closed) intervals)
• $[a,b){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\leq x<b\}$ (half-open (or half-closed) intervals)
• $[a,b]{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\leq x\leq b\}$ (closed intervals)

There are also some infinite intervals:

• $(-\infty ,a){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :x<a\}$
• $(-\infty ,a]{\overset {\text{ def }}{=}}\{x\in \mathbb {R} :x\leq a\}$
• $(a,\infty ){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a<x\}$
• $[a,\infty ){\overset {\text{ def }}{=}}\{x\in \mathbb {R} :a\leq x\}$
• $(-\infty ,\infty ){\overset {\text{ def }}{=}}\mathbb {R}$

Note: $\{x\in S:P(x)\}$ is a shorthand of $\{x:x\in S{\text{ and }}P(x)\}$ ($S$ is a set).

Example.

• $(0,1)\subseteq [0,1)\subseteq [0,1]$.
• ${\sqrt {2}},e,\pi \in (1,4)$.
• $(0,1]\not \subseteq [0,1)$ since the element "1" of the set on LHS does not belong to the set on RHS.
• $(0,1)\subseteq (0,\infty )$.

Example.

• The set of (real) solutions of $x^{2}-9\leq 0$ is $[-3,3]$.
• The set of (real) solutions of $x^{2}\leq 0$ is $\{0\}$. (Note: we cannot express this set as $[0,0]$ since it is required that $a<b$ for an interval $[a,b]$.)
• The set of (real) solutions of $x^{2}<0$ is $\varnothing$.

Exercise.

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

	$(0,0)$
	$(0,0.000001)$
	$(-2,-3)$
	$[-1,\infty ]$

Universal set and Venn diagram

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

Example.

• If we are studying real numbers, the universal set is $\mathbb {R}$.

Definition. (Complement) The complement of a set $A$ that is a subset of the universal set $U$, denoted by $A^{c}$, is the set $\{x\in U:x\notin A\}$.

Example.

• Let $A=\{1\}$ and $U=\{0,1,1,2\}$. Then, $A^{c}=\{0,2\}$. (Note: $U=\{0,1,2\}$ also.)
• For each universal set $U$, $\varnothing ^{c}=U$ (since each element of $U$ does not belong to $\varnothing$) and $U^{c}=\varnothing$ (since there are no elements of $U$ that does not belong to $U$).
• Let $B=\{1,3,5\}$ and $U=\{2,4,6\}$. Then, $B^{c}=\{2,4,6\}=U$ since each element of $U$ does not belong to $B$.

Exercise. Let the universal set be $\mathbb {R}$.

1

What is $(-\infty ,1]^{c}$?

	$[1,\infty )$
	$(1,\infty )$
	$(-\infty ,1)$
	$(-\infty ,1]$

2

What is $(-\infty ,1)^{c}$?

	$[1,\infty )$
	$(1,\infty )$
	$(-\infty ,1)$
	$(-\infty ,1]$

3

If the universal set is $U$ instead, $(-\infty ,1)^{c}=(1,3)$. Which of the following can be $U$ (there may be more than one answer)?

	$[1,3]$
	$(1,3)$
	$(1,\infty )$
	$(3,\infty )$
	$(-\infty ,3)$

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 $A$ and the region enclosed by the rectangle represents the universal set, then the red region is the set $A^{c}$.

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

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

Definition. (Union of sets)

A Venn diagram for union of two sets.

The union of a set $A$ and a set $B$, denoted by $A\cup B$, is the set $\{x:x\in A{\text{ or }}x\in B\}$.

Remark.

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

Example.

• $\{1,3,5\}\cup \{2,4,6\}=\{1,2,3,4,5,6\}$.
• $\{1,3,5\}\cup \{1,4,6\}=\{1,3,4,5,6\}$.
• $\{1,3,5\}\cup \{1,3,5\}=\{1,3,5\}$.
• $\mathbb {Q} \cup \mathbb {I} =\mathbb {R}$.

Proposition. Let $A,B$ and $C$ be sets. Then,

• $A\cup A=A$
• $A\cup B=B\cup A$ (commutative law)
• $A\cup (B\cup C)=(A\cup B)\cup C$ (associative law)
• $A\subseteq A\cup B$ and $B\subseteq A\cup B$
• $A\cup \varnothing =A$

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

$\Box$

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

Definition. (Intersection of sets)

A Venn diagram for intersection of two sets.

The intersection of a set $A$ and a set $B$, denoted by $A\cap B$, is the set $\{x:x\in A{\text{ and }}x\in B\}$.

Remark.

• If $A\cap B=\varnothing$, we say that $A$ and $B$ are disjoint.

Proposition. Let $A,B$ and $C$ be sets. Then,

• $A\cap A=A$
• $A\cap B=B\cap A$ (commutative law)
• $A\cap (B\cap C)=(A\cap B)\cap C$ (associative law)
• $A\cap B\subseteq A$ and $A\cap B\subseteq B$
• $A\cap \varnothing =\varnothing$

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

$\Box$

Proposition. (Distributive laws) Let $A,B$ and $C$ be sets. Then,

• $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ (the "$A\cap$" is "distributed" to $B$ and $C$ respectively)
• $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

Relative complement

Definition. (Relative complement)

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

The relative complement of a set $A$ in a set $B$, denoted by $B\setminus A$, is the set $\{x:x\in B{\text{ and }}x\notin A\}$.

Remark.

• $A^{c}=U\setminus A$ if $U$ is the universal set. So, the complement of a set $A$ is also the relative complement of $A$ in $U$.
• The notation $B\setminus A$ is read "B with A taken away".
• We can see from the definition that $B\setminus A=B\cap A^{c}$

Example.

• $\{a,b,c\}\setminus \{b,c,d\}=\{a\}$.
• $\{a,b,c\}\setminus \{a,b,c,d\}=\varnothing$.
• $\{a,b,c\}\setminus \{1,2,3\}=\{a,b,c\}$.
• $\mathbb {R} \setminus \mathbb {Q} =\mathbb {I}$.
• $\mathbb {Z} \setminus \mathbb {N} =\{0,-1,-2,\ldots \}$.

Exercise.

1

What is $\mathbb {R} \setminus \mathbb {C}$?

	$\{x:x=a+bi,a,b\in \mathbb {R} {\text{ and }}b\neq 0\}$
	$\{x:x=bi,b\in \mathbb {R} \}$
	$\varnothing$
	$\mathbb {C}$
	$\mathbb {R}$

2

What is $[1,10]\setminus (3,5)$?

	$[1,3]\cup [5,10]$
	$[1,3)\cup (5,10]$
	$(1,3)\cup (5,10)$
	$(1,3]\cup [5,10)$

3

What is $\mathbb {R} \setminus \{0\}$?

	$(-\infty ,0)\cup (0,\infty )$
	$(-\infty ,0]\cup [0,\infty )$
	$(-\infty ,0)\cap (0,\infty )$
	$(-\infty ,0]\cap [0,\infty )$

4

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

	$\mathbb {R} \setminus (-\infty ,0)$
	$\mathbb {R} \setminus (-\infty ,0]$
	$(0,\infty )$
	$[0,\infty )$
	$\mathbb {R} \cup (0,\infty )$
	$\mathbb {R} \cap (0,\infty )$

5

What is $\varnothing \setminus \varnothing$?

	$\varnothing$
	The universal set.
	$\{\varnothing \}$

Proposition. Let $A$ and $B$ be sets. Then,

• $A\setminus A=\varnothing$.
• $A\setminus \varnothing =A$.
• $\varnothing \setminus A=\varnothing$.
• $A\setminus B=\varnothing$ if and only if $A\subseteq B$.
• $(A\setminus B)\cap (B\setminus A)=\varnothing$.
• $A\cap (B\setminus A)=\varnothing$.

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

$\Box$

Theorem. (De Morgan's Laws) Let $A$ and $B$ be sets. Then, $$(A\cup B)^{c}=A^{c}\cap B^{c}{\text{ and }}(A\cap B)^{c}=A^{c}\cup B^{c}.$$

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

$\Box$

Example. Suppose the universal set is $\{1,2,3,4,5,6,7\}$, $A=\{1,2,3\}$ and $B=\{1,3,5\}$. Since $A\cup B=\{1,2,3,5\}$, $(A\cup B)^{c}=\{4,6,7\}$. On the other hand, since $A^{c}=\{4,5,6,7\}$ and $B^{c}=\{2,4,6,7\}$, $A^{c}\cap B^{c}=\{4,6,7\}=(A\cup B)^{c}$.

Exercise.

What is $(A\cap B)^{c}$?

	$\{4,6,7\}$
	$\{4,5,6,7\}$
	$\{2,4,6,7\}$
	$\{2,4,5,6,7\}$

Symmetric difference

Definition. (Symmetric difference)

A Venn diagram illustrating symmetric difference.

The symmetric difference of sets $A$ and $B$, denoted by $A\triangle B$, is the set $(A\setminus B)\cup (B\setminus A)$.

Example.

• $\{0,1,2\}\triangle \{1,2,3\}=\{0\}\cup \{3\}=\{0,3\}$.
• $\{x,y\}\triangle \{y\}=\{x\}\cup \varnothing =\{x\}$
• $\{x\}\triangle \{y\}=\{x\}\cup \{y\}=\{x,y\}$

Proposition. Let $A,B$ and $C$ be sets. Then,

• $A\triangle A=\varnothing$
• $A\triangle \varnothing =A$
• $A\triangle B=(A\cup B)\setminus (A\cap B)$
• $A\triangle (B\triangle C)=(A\triangle B)\triangle C$ (associative law)
• $A\triangle B=B\triangle A$ (commutative law)

Exercise.

1

What is $\varnothing \triangle \varnothing$?

	$\varnothing$
	$\{\varnothing \}$
	$\{\varnothing ,\{\varnothing \}\}$
	$\{\{\varnothing \}\}$

2

What is $A\triangle (B\setminus A)$?

	$A\cup B$
	$A\cap B$
	$A\setminus B$
	$A\triangle B$
	$B\setminus A$
	$A$
	$B$

3

Does $A\triangle B\triangle C=(A\cup B\cup C)\setminus (A\cap B\cap C)$? (Try to determine it using Venn diagrams. No mathematical proof is required at the moment.)

	Yes.
	No.

Power set

Definition. (Power set) The power set of a set $A$, denoted by ${\mathcal {P}}(A)$, is the set of all subsets of $A$. In set-builder notation, ${\mathcal {P}}(A)=\{S:S\subseteq A\}$.

Remark.

• Since $\varnothing \subseteq A$ for each set $A$, $\varnothing$ is an element of each power set.
• Also, since $A\subseteq A$ for each set $A$, $A$ is an element of the power set ${\mathcal {P}}(A)$.

Example.

• ${\mathcal {P}}(\varnothing )=\{\varnothing \}$. Its cardinality is 1.
• If $A=\{1\}$, then ${\mathcal {P}}(A)=\{\varnothing ,A\}=\{\varnothing ,\{1\}\}$. Its cardinality is 2.
• If $B=\{1,\{1\}\}$, then ${\mathcal {P}}(B)=\{\varnothing ,\{1\},\{\{1\}\},B\}$. Its cardinality is 4.
• ${\mathcal {P}}(\{1,2,3\})=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}$. Its cardinality is 8.

Theorem. (Cardinality of power set of a finite set) Let $A$ be a finite set with cardinality $n$. Then, $|{\mathcal {P}}(A)|=2^{n}$.

Proof. Assume $A$ is a finite set with cardinality $n$. Since each element of the power set ${\mathcal {P}}(A)$ is a subset of $A$, it suffices to prove that there are $2^{n}$ subsets of $A$. In the following, we consider subsets of $A$ 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 $C_{1}^{n}$ subsets.
• For the subsets with two elements, there are $C_{2}^{n}$ subsets.
• ...
• For the subsets with $n-1$ elements, there are $C_{n-1}^{n}$ subsets.
• For the subset with $n$ elements, it is the set $A$, and thus there is only one such subset.

So, the total number of subsets of $A$ is $1+C_{1}^{n}+C_{2}^{n}+\dotsb +C_{n-1}^{n}+1=(1+1)^{n}=2^{n}$ by binomial theorem.

$\Box$

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.

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

1

$\{\varnothing \}$

	${\big \{}\varnothing ,\{\{\varnothing \}\}{\big \}}$
	${\big \{}\{\varnothing \},\{\{\varnothing \}\}{\big \}}$
	${\big \{}\varnothing ,\{\varnothing \}{\big \}}$
	${\big \{}\varnothing ,\{\varnothing \},\{\{\varnothing \}\}{\big \}}$

2

${\mathcal {P}}(\{\varnothing \})$

	${\big \{}\varnothing ,\{\varnothing \},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}{\big \}}$
	${\big \{}\varnothing ,\{\varnothing ,\{\varnothing \}\},\{\{\varnothing \}\},\{\varnothing ,\{\varnothing \}\}{\big \}}$
	$\left\{\varnothing ,\{\{\varnothing \}\},\{\{\{\varnothing \}\}\},{\big \{}\{\varnothing \},\{\{\varnothing \}\}{\big \}}\right\}$
	$\left\{\varnothing ,\{\varnothing \},\{\{\varnothing \}\},{\big \{}\{\varnothing \},\{\{\varnothing \}\}{\big \}}\right\}$

3

$\{a,\{a\}\}$

	$\{\varnothing ,\{a\},\{\{a\}\},\{a,\{a\}\}\}$
	$\{\varnothing ,a,\{a\},\{a,\{a\}\}\}$
	$\{\varnothing ,a,\{\{a\}\},\{a,\{a\}\}\}$
	$\{\varnothing ,a,\{a\},\{\{a\}\}\}$

4

$S=\{1,3\}\triangle \{3,5\}$

	$\{\varnothing ,\{1\},\{3\},\{5\},\{1,3\},\{3,5\},\{1,5\},S\}$
	$\{\varnothing ,\{1\},\{3\},\{5\},S\}$
	$\{\varnothing ,S\}$
	$\{\varnothing ,\{1\},\{5\},\{1,5\},S\}$

It is given that $|A|=2$. In each of the following questions, choose the cardinality of the set given in the question.

1

${\mathcal {P}}({\mathcal {P}}(A))$

	4
	8
	16
	32

2

${\mathcal {P}}({\mathcal {P}}(\varnothing ))$

	0
	1
	2
	4

3

$\{{\mathcal {P}}(A)\}$

	1
	2
	4
	8

4

${\mathcal {P}}(\{A\})$

	1
	2
	4
	8

5

${\mathcal {P}}(\varnothing \cap {\mathcal {P}}(A))$

	1
	2
	4
	8

Cartesian product

Definition. (Cartesian product) The Cartesian product of sets $A$ and $B$, denoted by $A\times B$, is $A\times B=\{(a,b):a\in A{\text{ and }}b\in B\}$.

Remark.

• $(a,b)$ 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 $(a,b)\neq (b,a)$ if $a\neq b$.
• (notation) We use $A^{2}$ to denote $A\times A$ for each set $A$.
• We can observe that $|A\times B|=|A|\times |B|$.

Example. Let $A=\{0,1\}$ and $B=\{a,b,c\}$. Then,

• $A\times B=\{(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)\}$.
• $B\times A=\{(a,0),(b,0),(c,0),(a,1),(b,1),(c,1)\}$.

Remark.

• We can see from the above example that the Cartesian product is not commutative, i.e. it is not necessary for $A\times B=B\times A$.

Exercise. Let $A=\{1,2,3\}$.

1

What is $A\times \varnothing$ (there may be more than one answer)?

	$\{(1,0),(2,0),(3,0)\}$
	$\{(1,\varnothing ),(2,\varnothing ),(3,\varnothing )\}$
	$\varnothing$
	$\varnothing \times A$
	$\varnothing ^{2}$

2

What is $A^{2}$?

	$\{(1,1),(2,2),(3,3)\}$
	$\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$
	$A$
	$\{(1,A),(2,A),(3,A)\}$

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

Definition. (Cartesian product of three or more sets) Let $n$ be an integer greater than 2. The Cartesian product of $n$ sets $A_{1},A_{2},\dotsc ,A_{n}$ is $A_{1}\times A_{2}\times \dotsb \times A_{n}=\{(a_{1},a_{2},\dotsc ,a_{n}):a_{1}\in A_{1},a_{2}\in A_{2},\dotsc ,{\text{ and }}a_{n}\in A_{n}\}$.

Remark.

• (notation) We use $A^{n}$ to denote $\underbrace {A\times A\times \dotsb \times A} _{n{\text{ times}}}$, where $n\in \mathbb {N}$.

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

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 $T$) or false (denoted by $F$).

Example. Consider the following sentences:

1. The number 9 is even.
2. $1<2$.
3. Mathematics is easy.
4. How to solve $x^{2}+2x-3=0$?
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.

Exercise.

Is the sentence "The 123th digit in the decimal expansion of $\pi$ 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 $P(x):x=2$ ($:$ is read "such that").

• This sentence is true when $x=2$, 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 $P$ and $Q$, the truth table for them is as follows: $${\begin{array}{|c|c|}P&Q\\\hline T&T\\T&F\\F&T\\F&F\\\end{array}}$$ and there are four possible combinations of truth values of $P$ and $Q$.

Example. (Truth table for three statements) For three statements $P$, $Q$ and $R$, the truth table for them is as follows: $${\begin{array}{|c|c|c|}P&Q&R\\\hline T&T&T\\T&T&F\\T&F&T\\T&F&F\\F&T&T\\F&T&F\\F&F&T\\F&F&F\\\end{array}}$$ and there are eight possible combinations of truth values of $P$, $Q$ and $R$.

Remark.

• In general, there are $\underbrace {2\times \dotsb \times 2} _{n{\text{ times}}}=2^{n}$ possible combinations of truth values of $n$ 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 $P$, write four $T$'s and then four $F$'s, from top to bottom;
• for $Q$, write in this pattern from top to bottom: $TTFFTTFF$;
• for $R$, write in this pattern from top to bottom: $TFTFTFTF$.

Conjunction, disjunction and negation

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

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

Remark.

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

Example. (Truth table for $P\land Q$) The truth table for $P\land Q$ (in terms of possible combinations of truth values of $P$ and $Q$ ) is $${\begin{array}{|c|c|c|}P&Q&P\land Q\\\hline T&T&T\\T&F&F\\F&T&F\\F&F&F\\\end{array}}$$

• We can see that $P\land Q$ is true only when both $P$ and $Q$ are true, and false otherwise.

Disjunctions

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

Remark.

• That is, $P\lor Q$ is true when at least one of $P$ and $Q$ is true, and false otherwise.
• $P\lor Q$ is read "P or Q", and the disjunction of the statements $P$ and $Q$ can also be expressed by "$P$ or $Q$" 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. $P$ or $Q$ means $P$ or $Q$ or both. However, as an English word, "or" may be used exclusively, i.e. $P$ or $Q$ means $P$ or $Q$ 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 $P\lor Q$) The truth table for $P\lor Q$ is $${\begin{array}{|c|c|c|}P&Q&P\lor Q\\\hline T&T&T\\T&F&T\\F&T&T\\F&F&F\\\end{array}}$$

• We can see that $P\lor Q$ is false only when both $P$ and $Q$ are false, and true otherwise.

Negations

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

Remark.

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

Example. (Truth table for $\sim P$) The truth table for $\sim P$ is $${\begin{array}{|c|c|}P&\sim P\\\hline T&F\\F&T\\\end{array}}$$

• We can see that $\sim P$ always has the opposite truth value to that of $P$.

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

Exercise. Complete the following truth table: $${\begin{array}{|c|c|c|c|c|c|}P&Q&\sim P&\sim Q&P\lor Q&(\sim P)\lor (\sim Q)&\sim (P\lor Q)\\\hline T&T\\T&F\\F&T\\F&F\\\end{array}}$$

Answer

$${\begin{array}{|c|c|c|c|c|c|}P&Q&\sim P&\sim Q&P\lor Q&(\sim P)\lor (\sim Q)&\sim (P\lor Q)\\\hline T&T&{\color {red}F}&{\color {red}F}&{\color {red}T}&{\color {red}F}&{\color {red}F}\\T&F&{\color {red}F}&{\color {red}T}&{\color {red}T}&{\color {red}T}&{\color {red}F}\\F&T&{\color {red}T}&{\color {red}F}&{\color {red}T}&{\color {red}T}&{\color {red}F}\\F&F&{\color {red}T}&{\color {red}T}&{\color {red}F}&{\color {red}T}&{\color {red}T}\\\end{array}}$$

• We can observe that in some combinations of truth values of $P$ and $Q$, the truth values of $(\sim P)\lor (\sim Q)$ and $\sim (P\lor Q)$ are different.

Exercise. Let $P$ be the statement "The number 3 is even.", and $Q$ be the statement "The number ${\sqrt {2}}$ is irrational."

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

Answer

• The negation of $P$ can be "The number 3 is odd.".
• The negation of $Q$ can be "The number ${\sqrt {2}}$ is rational."

Exercise. Let $P$ be the statement $3>5.$ and $Q$ be the statement $3<2.$.

(a) Is the statement $\sim (P\land Q)$ true or false?

(b) Is the statement $\sim (P\lor Q)$ true or false?

(c) Is the statement $(\sim P)\land (\sim Q)$ true or false?

(d) Is the statement $(\sim P)\lor (\sim Q)$ true or false?

Answer

• First, we can see that both $P$ and $Q$ are false.

(a) Since $P\land Q$ is false, the answer is true.

(b) Since $P\lor Q$ is false, the answer is true.

(c),(d) Since $\sim P$ and $\sim Q$ are both true, the answer for (c) and (d) are both true.

Conditionals

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 $P$ and $Q$ is the statement "If $P$ then $Q$.", denoted by $P\to Q$. $P$ and $Q$ are called the hypothesis and consequent of the conditional respectively. The conditional $P\to Q$ is false when $P$ is true and $Q$ is false, and true otherwise.

Example. (Truth table for $P\to Q$) The truth table for $P\to Q$ is $${\begin{array}{|c|c|c|}P&Q&P\to Q\\\hline T&T&T\\T&F&F\\F&T&T\\F&F&T\\\end{array}}$$

• We can observe that, in particular, even if the hypothesis $P$ is false, the conditional $P\to Q$ is true, by definition .
• 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 $P$ be the statement "Bob fails the final examination of MATH1001.", and $Q$ be the statement "Bob fails MATH1001". Then, the statement made by the course instructor is "$P\to Q$".

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 .

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 ($P$ is true and $Q$ is false) (this shows that the instructor is lying!).

Converse and biconditionals

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

In mathematics, given that the conditional $P\to Q$ is true, we are often interested in knowing whether its converse $Q\to P$ is true as well .

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 $P$ and $Q$, denoted by $P\leftrightarrow Q$, is $(P\to Q)\land (Q\to P)$, that is, "If $P$ then $Q$." and "If $Q$ then $P$.".

Remark.

• We also write $P$ if and only if $Q$ in this case.

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

Example. (Truth table for $P\leftrightarrow Q$) The truth table for $P\leftrightarrow Q$ is $${\begin{array}{|c|c|c|}P&Q&P\to Q&Q\to P&P\leftrightarrow Q\\\hline T&T&T&T&T\\T&F&F&T&F\\F&T&T&F&F\\F&F&T&T&T\\\end{array}}$$

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

Implication and logical equivalence

When the conditional $P\to Q$ is true, we can say "$P$ implies $Q$", denoted by $P\Rightarrow Q$. On the other hand, when $P$ does not imply $Q$, i.e. $P\to Q$ is false, we denote this by $P\nRightarrow Q$.

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

• $P$ is a sufficient condition for $Q$ (or $P$ is sufficient for $Q$ in short)

• We call $P$ to be sufficient for $Q$ since when $P$ implies $Q$, then "$P$ is true" is sufficient to deduce "$Q$ is true".

• $Q$ is a necessary condition for $P$ (or $Q$ is necessary for $P$ in short)

• We call $Q$ to be necessary for $P$ since when $P$ implies $Q$, the hypothesis cannot be possibly true when the consequent $Q$ is false (or else the conditional $P\to Q$ will be false). This explains the necessity of "$Q$ is true".

When $P\Rightarrow Q$, we are often interested knowing whether the converse of $P\to Q$ is true or not, i.e. whether we have $Q\Rightarrow P$ or not .

In the case where $P\Rightarrow Q$ but $Q\nRightarrow P$, we have multiple equivalent ways to express this:

• $P$ is sufficient but not necessary for $Q$.

• From the previous interpretation, when we say $P$ is necessary for $Q$, we mean $Q\Rightarrow P$. Hence, when $P$ is sufficient but not necessary for $Q$, we mean ${\color {blue}P\Rightarrow Q}$ and ${\color {red}Q\nRightarrow P}$.

• $P$ is a stronger condition than $Q$ (or $P$ is stronger than $Q$ in short).

In the case where $P\Rightarrow Q$ and $Q\Rightarrow P$ as well, the biconditional $P\leftrightarrow Q$ is also true, and we denote this by $P\Leftrightarrow Q$. There are also multiple equivalent ways to express this:

• $P$ is logically equivalent to $Q$.

• We say they are logically equivalent since they always have the same truth values (because $P\leftrightarrow Q$ is true), which is related to logic.

• "$P$ if and only if $Q$" (is true).

• Recall that we also use "$P$ if and only if $Q$" to express the biconditional $P\leftrightarrow Q$. Thus, technically, we should write "$P$ if and only if $Q$" is true in the case where $P\Leftrightarrow Q$. 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 "$P$ if and only if $Q$" in this context, we mean that the biconditional is true without saying it explicitly.
• Usually, when we just write "$P$ if and only if $Q$", we have the meaning of the logical equivalence $P\Leftrightarrow Q$, rather than the statement $P\leftrightarrow Q$. If we really want to have the latter meaning, we should specify that "$P$ if and only if $Q$" refers to a statement.

• $P$ is necessary and sufficient for $Q$.

• Following the previous interpretation, $P$ is necessary and sufficient for $Q$ means ${\color {blue}Q\Rightarrow P}$ and ${\color {red}P\Rightarrow Q}$.

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

• ${\big (}\sim (\sim P){\big )}\Leftrightarrow P$ (double negation)
• $P\land Q\Leftrightarrow Q\land P$ (commutative law of conjunction)
• $P\lor Q\Leftrightarrow Q\lor P$ (commutative law of disjunction)
• $P\land (Q\land R)\Leftrightarrow (P\land Q)\land R$ (associative law of conjunction)
• $P\lor (Q\lor R)\Leftrightarrow (P\lor Q)\lor R$ (associative law of conjunction)
• $P\lor (Q\land R)\Leftrightarrow (P\lor Q)\land (P\lor R)$ (distributive law)
• $P\land (Q\lor R)\Leftrightarrow (P\land Q)\lor (P\land R)$ (distributive law)
• ${\big (}\sim (P\land Q){\big )}\Leftrightarrow (\sim P)\lor (\sim Q)$ (De Morgan's law)
• ${\big (}\sim (P\lor Q){\big )}\Leftrightarrow (\sim P)\land (\sim Q)$ (De Morgan's law)

Proof. They can be shown using truth tables.

$\Box$

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 $P\to Q$ and $(\sim P)\lor Q$ are logically equivalent.

Proof. It can be shown using the following truth table: $${\begin{array}{|c|c|c|c|c|}P&Q&\sim P&P\to Q&(\sim P)\lor Q\\\hline T&T&F&T&T\\T&F&F&F&F\\F&T&T&T&T\\F&F&T&T&T\\\end{array}}$$

$\Box$

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

Proof. Using the bridge between conditional and disjunction and some other laws, it can be shown as follows: $$P\to Q\Leftrightarrow (\sim P)\lor Q\Leftrightarrow Q\lor (\sim P)\Leftrightarrow {\big (}\sim (\sim Q){\big )}\lor (\sim P)\Leftrightarrow (\sim Q)\to (\sim P).$$

$\Box$

Remark.

• It may seem "surprising" when we "suddenly" negate $Q$ 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 $P\to Q\Leftrightarrow (\sim P)\lor Q$ and $(\sim Q)\to (\sim P)\Leftrightarrow {\big (}\sim (\sim Q){\big )}\lor (\sim P)$. 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

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 $\sim ,\lor ,\land ,\to$ and $\leftrightarrow$. 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 $P,Q,R$ etc.) and at least one logical connective, are called compound statements.

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

Remark.

• We use $\mathbf {T}$ to denote a tautology and $\mathbf {F}$ to denote a contradiction.
• When a statement $S$ is a tautology, we can also write $S\Leftrightarrow \mathbf {T}$, since it means $S$ and $\mathbf {T}$ always have the same truth value, and because the truth value of $\mathbf {T}$ is always true, the truth value of $S$ is also always true, i.e. $S$ is a tautology.

• Because of this, when we want to prove that a statement $S$ is always true, one way is to show that $S\Leftrightarrow \mathbf {T}$. For example, if we want to prove that $P\to Q$ and $(\sim Q)\to (\sim P)$ are logically equivalent, we may show that $\left[{\big (}P\to Q{\big )}\leftrightarrow {\big (}(\sim Q)\to (\sim P){\big )}\right]\Leftrightarrow \mathbf {T}$.

Example. Let $P$ be an arbitrary statement. Then,

• $P\lor (\sim P)$ is a tautology.
• $P\land (\sim P)$ is a contradiction.

This is because the truth table for $P\lor (\sim P)$ is $${\begin{array}{|c|c|c|}P&\sim P&P\lor (\sim P)\\\hline T&F&T\\F&T&T\\\end{array}}$$ and the truth table for $P\land (\sim P)$ is $${\begin{array}{|c|c|c|}P&\sim P&P\land (\sim P)\\\hline T&F&F\\F&T&F\\\end{array}}.$$

Example. Let $P$ and $Q$ be arbitrary statements. Then, $(P\land Q)\to (P\lor Q)$ is a tautology, since its truth table is $${\begin{array}{|c|c|c|c|c|}P&Q&P\land Q&P\lor Q&(P\land Q)\to (P\lor Q)\\\hline T&T&T&T&T\\T&F&F&T&T\\F&T&F&T&T\\F&F&F&F&T\\\end{array}}.$$

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

1

Is the converse of the statement in the example, $(P\lor Q)\to (P\land Q)$, a tautology, contradiction, or neither?

	Tautology.
	Contradiction.
	Neither.

2

Is the negation of the statement in the example, $\sim {\big (}(P\land Q)\to (P\lor Q){\big )}$, a tautology, contradiction, or neither?

	Tautology.
	Contradiction.
	Neither.

3

Is the contrapositive of the statement in the example, ${\big (}\sim (P\lor Q){\big )}\to {\big (}\sim (P\land Q){\big )}$, a tautology, contradiction, or neither?

	Tautology.
	Contradiction.
	Neither.

Prove that $(P\land Q)\to (P\lor Q)$ is a tautology without using truth tables.

Answer

Since $$(P\land Q)\to (P\lor Q)\Leftrightarrow {\big (}\sim (P\land Q){\big )}\lor (P\lor Q)\Leftrightarrow {\big (}(\sim P)\lor (\sim Q){\big )}\lor (P\lor Q)\Leftrightarrow {\big (}(\sim P)\lor P{\big )}\lor {\big (}(\sim Q)\lor Q{\big )}\Leftrightarrow \mathbf {T} \lor \mathbf {T} \Leftrightarrow \mathbf {T} ,$$ the given conditional is a tautology.

A student claims that $(P\lor Q)\to (P\land Q)$ is a contradiction with the following argument:

Since $(P\lor Q)\to (P\land Q)\Leftrightarrow {\big (}\sim (P\lor Q){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land (\sim Q)){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land P){\big )}\lor {\big (}(\sim Q)\land Q{\big )}\Leftrightarrow \mathbf {F} \lor \mathbf {F} \Leftrightarrow \mathbf {F}$, the conditional is a contradiction.

Comment on his claim.

Answer

• The claim is wrong.
• The step ${\big (}(\sim P)\land (\sim Q)){\big )}\lor (P\land Q)\Leftrightarrow {\big (}(\sim P)\land P){\big )}\lor {\big (}(\sim Q)\land Q{\big )}$ 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 $(P\lor Q)\to (P\land Q)$ is neither tautology nor contradiction.

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

• $P\lor \mathbf {T} \Leftrightarrow \mathbf {T}$.
• $P\land \mathbf {T} \Leftrightarrow P$.
• $P\lor \mathbf {F} \Leftrightarrow P$.
• $P\land \mathbf {F} \Leftrightarrow F$.
• $(\sim \mathbf {T} )\Leftrightarrow \mathbf {F}$.
• $(\sim \mathbf {F} )\Leftrightarrow \mathbf {T}$.

Proof. They can be shown using truth tables.

$\Box$

Quantifiers

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 $x$, $x^{2}\geq 0$." We can let $P(x)$ be the open statement "$x^{2}\geq 0$". Then, it can be further rephrased as "For each real number $x$, $P(x)$." In this case, we can observe how an open statement ($P(x)$) is converted to a statement (For each real number $x$, $P(x)$), 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 $\forall$ (an inverted "A"). After introducing this notation, the statement we mention can be further rephrased as "$\forall x\in \mathbb {R} ,x^{2}\geq 0$" (we also use some set notations here).

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

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" , "for at least one" is referred to as an existential quantifier, and is denoted by $\exists$ (an inverted "E"). For example, we can rewrite the statement "The square of some real number is negative." as "$\exists x\in \mathbb {R} ,x^{2}<0.$" (which is false).

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

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 $\exists !$. For example, we can rewrite the statement "There exists a unique real number $x$ such that $2x=0$." as "$\exists !x\in \mathbb {R} ,2x=0$." We can express the unique existential quantifier in terms of existential and universal quantifiers, by defining "$\exists !x\in S,P(x)$" as $$\left(\exists x\in S,P(x)\right)\land \left(\forall x_{1},x_{2}\in S,P(x_{1})\land P(x_{2})\to x_{1}=x_{2}\right)$$ where the left bracket is the existence part, and the right bracket is the uniqueness part. In words, the expression means

There exists $x\in S$ such that $P(x)$, AND for every $x_{1},x_{2}\in S$, if $P(x_{1})$ and $P(x_{2})$, then $x_{1}=x_{2}$ (i.e., $x_{1}$ and $x_{2}$ are actually referring to the same thing, so there is exactly one $x$ such that $P(x)$).

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

Negation of quantified statements

Example. The statement "$\exists A\subseteq U,A=U$" can be expressed in words (partially) as "There exists a set $A\subseteq U$ such that $A=U$."

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

Answer

• For the hint, the negation of "$n\geq 1$ ($n$ is a nonnegative integer)." is "$n=0$", and the negation of "There is at least one $x\in S$ such that $P(x)$." is hence "There is no $x\in S$ such that $P(x)$". It can also be expressed equivalently as "For each $x\in S$, $P(x)$ is not satisfied.", or $\forall x\in S,\sim P(x)$.
• Inspired from the hint, the negation of this statement can be written as "For each set $A\subseteq U$, $A\neq U$."

From this example, we can see that the negation of the statement "$\exists x\in S,P(x)$" is logically equivalent to "$\forall x\in S,\sim P(x)$". Now, it is natural for us to want to know also the negation of the statement "$\forall x\in S,P(x)$. Consider this: when it is not the case that $P(x)$ is true for each $x\in S$, it means that $P(x)$ is false for at least one $x\in S$. In other words, $\exists x\in S,\sim P(x)$. Hence, we know that the negation of the statement "$\forall x\in S,P(x)$" is logically equivalent to $\exists x\in S,\sim P(x)$.

Quantified statements with more than one quantifier

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 $x$ and for each real number $y$, $xy$ is a real number." It can be written as "$\forall x\in \mathbb {R} ,\forall y\in \mathbb {R} ,xy\in \mathbb {R}$". When we interchange "$\forall x\in \mathbb {R}$" and "$\forall y\in \mathbb {R}$", 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 "$\forall x,y\in \mathbb {R} ,xy\in \mathbb {R}$" without any ambiguity.

For an example that involve two existential quantifiers, consider the statement "There exists an real number $x$ and an real number $y$ such that $xy$ is a real number." It can be written as "$\exists x\in \mathbb {R} ,\exists y\in \mathbb {R} ,xy\in \mathbb {R}$." Similarly, interchanging "$\exists x\in \mathbb {R}$" and "$\exists y\in \mathbb {R}$" does not affect the meaning of the statement (the statement still means "For at least one pair of real numbers $x$ and $y$, $xy$ is a real number.") Because of this, we can simply write the statement as "$\exists x,y\in \mathbb {R} ,xy\in \mathbb {R}$" 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 $x$, there exists an integer $y$ such that $y<x$." This can also be written as "$\forall x\in \mathbb {Z} ,\exists y\in \mathbb {Z} ,y<x$". 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 $x=13$, I can choose $y=-99,0$ or $12$. Indeed, for the integer $x$ chosen by you, I can always choose my $y$ as $x-1$ so that $y<x$.

Let's see what happen if we interchange "$\forall x\in \mathbb {Z}$" and "$\exists y\in \mathbb {Z}$". The statement becomes $\exists y\in \mathbb {Z} ,\forall x\in \mathbb {Z} ,y<x$, meaning that there exists an integer $y$ such that it is (strictly) smaller than every integer $x$! 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 $\exists$, 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 $\forall x\in \mathbb {Z} ,\exists y\in \mathbb {Z} ,y<x.$. Then, since the variable $x$ appears earlier than the variable $y$ which associated to $\exists$, $y$ may depend on $x$ (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 $x=13$, and I choose $y=12$. Then, $y<x$. However, if you change your choice to $x=9$, then my $y=12$ does not work, and I need to change my $y$ to, say, 8 so that $y<x$. Then, we can see that $y$ depends on $x$ in this case. In the second case, we have $\exists y\in \mathbb {Z} ,\forall x\in Z,y<x$. In this case, the variable $x$ appears later than the variable $y$. Hence, the variable $y$ must be independent from $x$. That is, when such $y$ is determined, it needs to satisfy $y<x$ for each $x$ chosen, and the $y$ cannot change depend on what $x$ is. Indeed, $y$ cannot possibly depend on $x$, since $y$ is supposed to be determined when $x$ is not even introduced!

Exercises

In the following questions, $P,Q,R,S$ are statements.

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

1. $\sim P\to Q$
2. $P\to (\sim Q)$
3. $(P\lor Q)\to R$
4. $(P\land Q)\to (R\lor S)$
5. $(R\to S)\to (P\to Q)$

B. Negate the following statements:

1. $P\land Q$
2. $(P\lor Q)\land (R\land S)$
3. $(P\land \sim Q)\lor (\sim R\lor S)$

Methods of Proof

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

Introduction

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

Many mathematical theorems can be expressed in the form of "$\forall x\in S,P(x)\implies Q(x)$, in which $P(x)$ and $Q(x)$ are open statements about elements $x$ in a set $S$ . This expression means "If $P(x)$ then $Q(x)$" is true for every $x\in S$. However, in practice, we rarely include the phrase "is true", and usually just write the theorem in the form of "For every $x\in S$, if $P(x)$, then $Q(x)$." Sometimes, we write instead "Let $x\in S$. If $P(x)$, then $Q(x)$.", 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 $x\in \mathbb {Z}$, $x$ is even $\implies$ $x^{2}$ is even.", or "For every $x\in \mathbb {Z}$, if $x$ is even, then $x^{2}$ is even.", or "Let $x\in \mathbb {Z}$. If $x$ is even, then $x^{2}$ 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 "$\forall x\in S,P(x)\to Q(x)$". We would like to prove that it is true. Suppose $P(x_{0})$ is false for some $x_{0}\in S$. Then, the conditional $P(x_{0})\to Q(x_{0})$ must be true for this $x_{0}$ by definition, regardless of the truth value of $Q(x_{0})$. Hence, in the proof, we do not need to consider those $x\in S$ for which the hypothesis $P(x)$ is false.

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

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

Example. Prove that for every $n\in \mathbb {Z}$, if $n$ is odd, then $3n+1$ is even.

Proof. Assume $n$ is odd. Then, by definition we have $n=2k+1$ for some $k\in \mathbb {Z}$. Thus, $$3n+1=3(2k+1)+1=6k+4=2(3k+2)=2k',$$ where $k'=3k+2\in \mathbb {Z}$ (this follows from the definition of integers). This means $3n+1$ can be written as $2k'$ for some $k'\in \mathbb {Z}$, and hence $3n+1$ is even.

$\Box$

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

• an integer $n$ is even if $n=2k$ for some integer $k$.
• an integer $n$ is odd if $n=2k+1$ for some integer $k$.

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

Proof. $${\begin{aligned}&&&n{\text{ is odd}}\\&\Rightarrow &&n=2k+1{\text{ for some }}k\in \mathbb {Z} \\&\Rightarrow &&3n+1=2(3k+2)&(3k+2\in \mathbb {Z} )\\&\Rightarrow &&3n+1{\text{ is even.}}\end{aligned}}$$

$\Box$

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 "$n$" in the proof, it is implicitly assumed it follows the same meaning as in the given statement, i.e., $n$ is an integer. We can also let $n$ 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.

Exercise. Consider the statement "For every $a,b\in \mathbb {Z}$, if $a$ is odd and $b$ is even, then $4a+5b$ is even.". A student provides the following proof to the statement:

Proof. Assume $a$ is odd and $b$ is even. That is, $a=2k+1$ and $b=2k$ for some $k\in \mathbb {Z}$. It follows that $4a+5b=8k+4+10k=2(9k+2)$, and thus $4a+5b$ is even.

$\Box$

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 $k$ for both $a$ and $b$, since using the same $k$ implies that $a=b+1$, which is not necessarily the case from the assumptions. The following proof is a correct one:

Proof. Assume $a$ is odd and $b$ is even. That is, $a=2{\color {blue}k_{1}}+1$ and $b=2{\color {blue}k_{2}}$ for some $k_{1},k_{2}\in \mathbb {Z}$. It follows that $4a+5b=8k_{1}+4+10k_{2}=2(4k_{1}+5k_{2}+2)$, and thus $4a+5b$ is even.

$\Box$

Exercise. Prove that for every $n\in \mathbb {Z}$, if $n$ is even, then $n^{2}+n+1$ is odd.

Proof

Proof. Assume $n$ is even. Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $$n^{2}+n+1=4k^{2}+2k+1=2(2k^{2}+k)+1.$$ Since $k^{2}+k\in \mathbb {Z}$, $n^{2}+n+1$ is odd.

$\Box$

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 "$\forall x,y\in S,P(x,y)\implies Q(x,y)$" first.)

Solution

(a) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ and $y$ are even, then $x+y$ is even."

Proof. Assume $x$ and $y$ are even. Then, $x=2k_{1}$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$ (notice that we should not use the same $k$ for both $x$ and $y$, since $x$ may be different from $y$.). Thus, $x+y=2(k_{1}+k_{2})$, and hence $x+y$ is even since $k_{1}+k_{2}\in \mathbb {Z}$.

$\Box$

(b) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ and $y$ are odd, then $x+y$ is even."

Proof. Assume $x$ and $y$ are odd. Then, $x=2k_{1}+1$ and $y=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $x+y=2(k_{1}+k_{2}+1)$, and hence $x+y$ is even since $k_{1}+k_{2}+1\in \mathbb {Z}$.

$\Box$

(c) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is odd and $y$ is even, then $x+y$ is odd."

Proof. Assume $x$ is odd and $y$ is even. Then, $x=2k_{1}+1$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $x+y=2(k_{1}+k_{2})+1$, and hence $x+y$ is odd since $k_{1}+k_{2}\in \mathbb {Z}$.

$\Box$

(d) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is even and $y$ is even, then $xy$ is even."

Proof. Assume $x$ and $y$ are even. Then, $x=2k_{1}$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $xy=2(2k_{1}k_{2})$, and hence $xy$ is even since $2k_{1}k_{2}\in \mathbb {Z}$.

$\Box$

(e) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is odd and $y$ is odd, then $xy$ is odd."

Proof. Assume $x$ and $y$ are odd. Then, $x=2k_{1}+1$ and $y=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $xy=(2k_{1}+1)(2k_{2}+1)=4k_{1}k_{2}+2k_{1}+2k_{2}+1=2(2k_{1}k_{2}+k_{1}+k_{2})+1$, and hence $xy$ is odd since $2k_{1}k_{2}+k_{1}+k_{2}\in \mathbb {Z}$.

$\Box$

(f) First, rewrite the statement as "For every $x,y\in \mathbb {Z}$, if $x$ is odd and $y$ is even, then $xy$ is even."

Proof. Assume $x$ is odd and $y$ is even. Then, $x=2k_{1}+1$ and $y=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $xy=(2k_{1}+1)(2k_{2})=4k_{1}k_{2}+2k_{2}=2(2k_{1}k_{2}+k_{2})$, and hence $xy$ is even since $2k_{1}k_{2}+k_{2}\in \mathbb {Z}$.

$\Box$

Exercise. A real number $x$ is defined to be rational if there exist integers $p,q$ with $q\neq 0$ such that $x={\frac {p}{q}}$. 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 $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$, then $x+y\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$. Then, $x={\frac {p_{1}}{q_{1}}}$ and $y={\frac {p_{2}}{q_{2}}}$ for some $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $q_{1}\neq 0$ and $q_{2}\neq 0$. Thus, $$x+y={\frac {p_{1}}{q_{1}}}+{\frac {p_{2}}{q_{2}}}={\frac {p_{1}q_{2}+p_{2}q_{1}}{q_{1}q_{2}}}.$$ Since $p_{1}q_{2}+p_{2}q_{1},q_{1}q_{2}\in \mathbb {Z}$ with $q_{1}q_{2}\neq 0$, $x+y\in \mathbb {Q}$.

$\Box$

(b) First, rewrite the statement as "For every $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$, then $x-y\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$. Then, $y={\frac {p}{q}}$ for some $p,q\in \mathbb {Z}$ with $q\neq 0$. So, $-q={\frac {-p}{q}}$ is rational since $-p,q\in \mathbb {Z}$ and $q\neq 0$. Thus, by (a), we have $x-y=x+(-y)\in \mathbb {Q}$.

$\Box$

(c) First, rewrite the statement as "For every $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$, then $xy\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$. Then, $x={\frac {p_{1}}{q_{1}}}$ and $y={\frac {p_{2}}{q_{2}}}$ for some $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $q_{1}\neq 0$ and $q_{2}\neq 0$. Thus, $$xy={\frac {p_{1}p_{2}}{q_{1}q_{2}}}.$$ Since $p_{1}p_{2},q_{1}q_{2}\in \mathbb {Z}$ with $q_{1}q_{2}\neq 0$, $xy\in \mathbb {Q}$.

$\Box$

(d) First, rewrite the statement as "For every $x,y\in \mathbb {R}$, if $x,y\in \mathbb {Q}$ and $y\neq 0$ then ${\frac {x}{y}}\in \mathbb {Q}$.

Proof. Assume $x,y\in \mathbb {Q}$ and $y\neq 0$. Then, $x={\frac {p_{1}}{q_{1}}}$ and $y={\frac {p_{2}}{q_{2}}}$ for some $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $p_{2}\neq 0$, $q_{1}\neq 0$, and $q_{2}\neq 0$. Thus, $${\frac {x}{y}}={\frac {p_{1}q_{2}}{p_{2}q_{1}}}.$$ Since $p_{1}q_{2},p_{2}q_{1}\in \mathbb {Z}$ with $p_{2}q_{1}\neq 0$, ${\frac {x}{y}}\in \mathbb {Q}$.

$\Box$

Example. Prove that for every $x\in \mathbb {R}$, if $x^{2}-2x+1<0$, then $(x-2)^{3}\geq 8$.

Proof. For every $x\in \mathbb {R}$, $x^{2}-2x+1=(x-1)^{2}\geq 0$. Thus, the hypothesis is false, and hence the statement must be true.

$\Box$

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 $x\in \mathbb {R}$, if $0<x<1$, then $x^{2}-x-2<-2$.

Proof. Assume $0<x<1$. Then, $$x^{2}-x=x(x-1).$$ Since $x$ is positive and $x-1$ is negative by assumption, we have $x^{2}-x<0$, and thus $$x^{2}-x-2<0-2=-2.$$

$\Box$

Remark.

• Graphically, the function $f(x)=x^{2}-x-2$ (we will discuss the concept of function in later chapter) looks like:

Exercise. Prove that for every $x\in \mathbb {R}$, if $x^{2}-x-2<-2$, then $0<x<1$ (this statement is the converse of the statement in above example). (Hint: The following property may be useful: for every $a,b\in \mathbb {R}$, if $ab<0$, then either ($a<0$ and $b>0$) or ($a>0$ and $b<0$).) (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 $x^{2}-x-2<-2$. Then, $x^{2}-x<0\implies x(x-1)<0$ ("$\implies$" is read "which implies" in this context). It follows that we have either

• $x<0$ and $x-1>0$, or
• $x>0$ and $x-1<0$.

Since no real number $x$ satisfies the first one, we must have the second one, which gives $0<x<1$.

$\Box$

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

For every $x\in \mathbb {R}$, we have $x^{2}-x-2<-2$ if and only if $0<x<1$.

In other words, using set language, $$\{x\in \mathbb {R} :0<x<1\}=\{x\in \mathbb {R} :(x-1)^{2}<1\}.$$ (Both sets represent the curve (strictly) under the horizontal line $y=-2$ in the above graph.)

Letting $P(x)$ and $Q(x)$ be the open statement "$x^{2}-x-2<-2$" and "$0<x<1$" respectively, we can express the above result symbolically: $$\forall x\in \mathbb {R} ,P(x)\iff Q(x).$$ Recall that "$P(x)\iff Q(x)$" means "$P(x)\implies Q(x)$" and "$Q(x)\implies P(x)$". So, to give a direct proof to the statement in the form of "$\forall x\in S,P(x)\iff Q(x)$", a usual way is to break the proof into two parts:

1. proving that $\forall x\in S,P(x)\implies Q(x)$ (known as the "only if" part, or "$\Rightarrow$" direction)
2. proving that $\forall x\in S,Q(x)\implies P(x)$ (known as the "if" part, or "$\Leftarrow$" direction)

Example. Prove that for every $n\in \mathbb {N}$, $n+{\frac {1}{n}}\geq 2$. (Hint: this inequality is equivalent to the inequality $n^{2}+1\geq 2n$, obtained by multiplying both side by $n$, which is a positive integer.)

Proof. Using the hint, it suffices to prove that for every $n\in \mathbb {N}$, $n^{2}+1\geq 2n$. But it follows from the fact that $n^{2}-2n+1=(n-1)^{2}\geq 0$.

$\Box$

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 $\mathbb {N}$ to a larger set. Determine which of the following (may be more than one) can be the larger set.

	$\mathbb {Z}$
	$\mathbb {Q}$
	$\mathbb {R}$
	None of the above.

A student provides the following proof to the above statement:

Proof. Since $n$ is a positive integer, multiplying $n$ to both sides of the inequality yields $n^{2}+1\geq 2n$. After rearranging, we get $n^{2}-2n+1=(n-1)^{2}\geq 0$, which is always true.

$\Box$

Point out the mistake in the proof.

Solution

The mistake is that the student implicitly assumes $n+{\frac {1}{n}}\geq 2$, 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 $n+{\frac {1}{n}}\geq 2$. Instead, we start from the fact that $(n-1)^{2}\geq 0$.)

Example. Let $S=\{3,5,7,9,11\}$. Prove that for every $n\in S$, if $n$ is prime, then $n$ is odd.

Proof. Assume $n$ is prime. Since the only primes in the set $S$ are 3,5,7 and 11, this means $n=3,5,7{\text{ or }}11$. Hence, $n$ is odd.

$\Box$

Exercise. Prove that for every $n\in S$, if $n$ is even, then $n$ is prime.

Proof

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

$\Box$

Example. (A special case of AM-GM inequality) Prove that for every $x,y\in \mathbb {R}$, if $x$ and $y$ are positive, then $${\sqrt {xy}}\leq {\frac {x+y}{2}}.$$

Proof. Assume $x$ and $y$ are positive. Then, $$(x-y)^{2}\geq 0\implies (x+y)^{2}-4xy\geq 0\implies {\sqrt {(x+y)^{2}}}\geq {\sqrt {4xy}}\implies x+y\geq 2{\sqrt {xy}}\implies {\sqrt {xy}}\leq {\frac {x+y}{2}}.$$

$\Box$

Exercise. Suggest a condition where the equality holds, i.e., ${\sqrt {xy}}={\frac {x+y}{2}}$.

Solution

The condition is $x=y$.

Proofs related to congruence of integers

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 $x$ is either even or odd, i.e., can be expressed as $2k$ or $2k+1$ for some integer $k$, according to whether the remainder is 0 or 1 when $x$ is divided by 2. Thus, if two integers $x$ and $y$ have the same remainder when divided by 2 (i.e., have the same parity), then the difference $x-y$ 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 $3k,3k+1$ or $3k+2$ for some integer $k$, according to whether remainder is 0, 1 or 2 when $x$ is divided by 3. Hence, if two integers $x$ and $y$ have the same remainder when divided by 3, then the difference $x-y$ 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 $k$" is equivalent to "their difference is a multiple of $k$". This leads us to the following definition.

Definition. (Congruence of integers) Let $a,b\in \mathbb {Z}$ and $n\in \mathbb {N}$ with $n\geq 2$. Then, the integer $a$ is congruent to $b$ modulo $n$, denoted by $a\equiv b{\pmod {n}}$, if $a-b$ is a multiple of $n$, i.e., $a-b=nk$ for some $k\in \mathbb {Z}$.

Remark.

• Instead of "$a-b$ is a multiple of $n$", we can also say $a-b$ is divisible by $n$, or $n$ divides $a-b$, denoted by $n|(a-b)$ (in general, the notation $x|y$ means "$x$ divides $y$" (and $x\nmid y$ means "$x$ does not divide $y$").

Example. We have $13\equiv 1{\pmod {12}}$ since $12|(13-1)$, and $-23\equiv -13{\pmod {12}}$ since $12|(-23-13)$. But, $5\not \equiv 10{\pmod {4}}$ since $4\nmid (5-10)$.

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 $8+5=13$. But $13>12$. 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 "$a$ modulo $n$" is $a{\text{ mod }}n$, which gives the remainder when $a$ is divided by $n$ ($a$ and $n$ are positive integers).

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

Theorem. For every $a,b,c,d,k\in \mathbb {Z}$ and for every $n\in \mathbb {N}$ with $n\geq 2$, if $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$, then

• (compatibility with addition) $a+c\equiv b+d{\pmod {n}}$.
• (compatibility with translation) $a+k\equiv b+k{\pmod {n}}$.
• (compatibility with scaling) $ka\equiv kb{\pmod {n}}$.
• (compatibility with multiplication) $ac\equiv bd{\pmod {n}}$.

(For the compatibility with translation and scaling, the assumption that $c\equiv d{\pmod {n}}$ 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 $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$. Then, $a-b=nk_{1}$ and $c-d=nk_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $$(a+c)-(b+d)=(a-b)+(c-d)=nk_{1}+nk_{2}=n(k_{1}+k_{2}).$$ Since $k_{1}+k_{2}\in \mathbb {Z}$, we have $a+c\equiv b+d{\pmod {n}}$.

Compatibility with multiplication: Assume that $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$. Then, $a-b=nk_{1}$ and $c-d=nk_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $$ac-bd=ac{\color {darkgreen}-bc+bc}-bd=c(a-b)+b(c-d)=cnk_{1}+bnk_{2}=n(ck_{1}+bk_{2}).$$ Since $ck_{1}+bk_{2}\in \mathbb {Z}$, we have $ac\equiv bd{\pmod {n}}$.

$\Box$

Remark.

• We have applied the trick $ac-bd=ac{\color {darkgreen}-bc+bc}-bd$ in the proof of compatibility with multiplication. One can also prove it without using this trick. The details are left to the following exercise.

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

Proof

Assume that $a\equiv b{\pmod {n}}$ and $c\equiv d{\pmod {n}}$. Then, $a-b=nk_{1}$ and $c-d=nk_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. That is, $a=b+nk_{1}$ and $c=d+nk_{2}$. Hence, $$ac-bd=(b+nk_{1})(d+nk_{2})-bd=bd+bnk_{2}+dnk_{1}+n^{2}k_{1}k_{2}-bd=n(bk_{2}+dk_{1}+nk_{1}k_{2}).$$ Since $bk_{2}+dk_{1}+nk_{1}k_{2}\in \mathbb {Z}$, we have $ac\equiv bd{\pmod {n}}$.

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 $a\equiv b{\pmod {n}}$. Since $k-k=0(n)$, we have $k\equiv k{\pmod {n}}$. Hence, by the compatibility with addition, we have $a+k\equiv b+k{\pmod {n}}$. Also, by the compatibility with multiplication, we have $ka\equiv kb{\pmod {n}}$.

$\Box$

In the above result, everything is with the same "modulo $n$". 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 $a$ and $b$ are relatively prime if and only if there exist integers $x$ and $y$ such that $ax+by=1$.

Proof. Omitted.

$\Box$

Using this result, we can deduce the following result:

Theorem. For every $a,b,m,n\in \mathbb {Z}$ with $m,n\geq 2$, if $a\equiv b{\pmod {m}}$, $a\equiv b{\pmod {n}}$ and $m,n$ are relatively prime, then $a\equiv b{\pmod {mn}}$.

Proof. Assume $a\equiv b{\pmod {m}}$, $a\equiv b{\pmod {n}}$, and $m,n$ are relatively prime. Then, we have $a-b=k_{1}m$ and $a-b=k_{2}n$ for some $k_{1},k_{2}\in \mathbb {Z}$. This means $k_{1}m=k_{2}n$. Also, $mx+ny=1$ for some $x,y\in \mathbb {Z}$. Multiplying both sides by the integer $k_{1}$, we get $$xmk_{1}+ynk_{1}=k_{1}.$$ Putting $m={\frac {k_{2}n}{k_{1}}}$, we get $$xk_{2}n+ynk_{1}=k_{1}\implies n(xk_{2}+yk_{1})=k_{1}.$$ Putting this into $a-b=k_{1}m$, we get $$a-b=mn(xk_{2}+yk_{1}).$$ Since $xk_{2}+yk_{1}\in \mathbb {Z}$, we have $a\equiv b{\pmod {mn}}$.

$\Box$

Remark.

• This theorem says in particular if an integer is a multiple of $m$, and also a multiple of $n$, and $n$ and $n$ are relatively prime, then the integer is a multiple of $mn$.
• 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.

Exercise. Give an example of integers $a,b,m,n$ such that $a\equiv b{\pmod {m}}$, $a\equiv b{\pmod {n}}$, $m$ and $n$ are not relatively prime, and $a\not \equiv b{\pmod {mn}}$.

Solution

Take $a=4,b=8,m=2,n=4$. Then, $4\equiv 8{\pmod {2}}$ and $4\equiv 8{\pmod {4}}$. However, $4\not \equiv 8{\pmod {8}}$.

Example. (Reflexivity, symmetry, and transitivity of the congruence of integers) Prove that for every $n\in \mathbb {N}$ with $n\geq 2$,

• (reflexivity) for every $a\in \mathbb {Z}$, $a\equiv a{\pmod {n}}$.
• (symmetry) for every $a,b\in \mathbb {Z}$, if $a\equiv b{\pmod {n}}$, then $b\equiv a{\pmod {n}}$.
• (transitivity) for every $a,b,c\in \mathbb {Z}$, if $a\equiv b{\pmod {n}}$ and $b\equiv c{\pmod {n}}$, then $a\equiv c{\pmod {n}}$.

(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 $a-a=0(n)$, we have $a\equiv a{\pmod {n}}$.

Symmetry:

Assume $a\equiv b{\pmod {n}}$. Then, $a-b=kn$ for some $k\in \mathbb {Z}$. Thus, $b-a=-kn$, and hence $b\equiv a{\pmod {n}}$ since $-k\in \mathbb {Z}$.

Transitivity:

Assume $a\equiv b{\pmod {n}}$ and $b\equiv c{\pmod {n}}$. Then, $a-b=k_{1}n$ and $b-c=k_{2}n$ for some $k_{1},k_{2}\in \mathbb {Z}$. Hence, $a-c=(a-b)-(b-c)=(k_{1}-k_{2})n$. Thus, $a\equiv c{\pmod {n}}$ since $k_{1}-k-2\in \mathbb {Z}$.

$\Box$

Remark.

• Notice that not all relations satisfy all these three properties. For instance, "$\neq$" 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 $a$ be an integer, $m$ be a nonnegative integer, and $n\in \mathbb {N}$ with $n\geq 2$. If $a\equiv 1{\pmod {n}}$, then $a^{m}\equiv 1{\pmod {n}}$.

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

Proof. Assume $a\equiv 1{\pmod {n}}$. First, $a^{0}=1\equiv 1{\pmod {n}}$. Second, we have $a\cdot a\equiv 1\cdot 1{\pmod {n}}\implies a^{2}\equiv 1{\pmod {n}}$. Applying this argument again, we get $a^{2}\cdot a\equiv 1\cdot 1{\pmod {n}}\implies a^{3}\equiv 1{\pmod {n}}$. Thus, we have $a^{m}\equiv 1{\pmod {n}}$ for every nonnegative integer $m$ by applying the argument "again and again".

$\Box$

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

Example.

(a) Consider the remainder of $3^{n}$ when divided by 4 (i.e., $3^{n}{\text{ mod }}4$) for $n=0,1,2,3,4,5$. Do you observe any pattern? Hence, suggest a conjecture.

(b) Prove the conjecture.

Solution.

(a) We have $${\begin{array}{c|cccccc}n&0&1&2&3&4&5\\\hline 3^{n}{\text{ mod }}4&1&3&1&3&1&3\\\end{array}}$$ Notice that the remainder is 1 for $n=0,2,4$, and 3 for $n=1,3,5$. It is thus natural to expect that the same pattern continue for all other larger integers. Thus, a conjecture is

Let $n$ be a nonnegative integer. If $n$ is even, then $3^{n}\equiv 1{\pmod {4}}$. Also, if $n$ is odd, then $3^{n}\equiv 3{\pmod {4}}$.

(b) We will just prove "If $n$ is even, then $3^{n}\equiv 1{\pmod {4}}$.". The proof of the second part is left to the following exercise.

Proof. Assume $n$ is even. Then, $n=2k$ for some nonnegative integer $k$ ($n$ is a nonnegative integer). It follows that $3^{n}=3^{2k}=9^{k}$. Since $9\equiv 1{\pmod {4}}$, it follows that $9^{k}\equiv 1{\pmod {4}}$ by the result in previous example. Hence, $3^{n}\equiv 1{\pmod {4}}$.

$\Box$

Exercise. Prove the second part in the above conjecture.

Proof

Proof. Assume $n$ is odd. Then, $n=2k+1$ for some nonnegative integer $k$. It follows that $3^{n}=3^{2k+1}=3\cdot 9^{k}$. From the prove above, we have $9^{k}\equiv 1{\pmod {4}}$. Thus, we get $3\cdot 9^{k}\equiv 3\cdot 1{\pmod {4}}\implies 3^{n}\equiv 3{\pmod {4}}$.

$\Box$

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

Lemma. (Euclid's division lemma) For every integer $a$ and $b$ with $b\neq 0$, there exists a unique pair of integers $q$ and $r$ such that $$a=bq+r{\text{ and }}0\leq r<|b|.$$

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

Existence part:

Case 1: $b<0$.

Then, we set $b'=-b>0$ and $q'=-q$. After that, the equation $a=bq+r$ can be rewritten equivalently as $a=b'q'+r$, and also the inequality $0\leq r\leq |b'|$ can be rewritten equivalently as $0\leq r\leq |b'|$. Through this, we transform this case to case 2.

Case 2: $b>0$.

Subcase 1: $a<0$ and $b>0$.

Then, we set $a'=-a$, $q'=-q-1$, and $r'=b-r$. After that, the equation $a=bq+r$ can be rewritten equivalently as $a'=bq'+r'$ (this is equivalent to $-a=-bq-r$). Also, the inequality $0\leq r\leq |b'|$ can be rewritten equivalently as $0\leq r'<|b|$. Through this, we transform this case to the subcase 2.

Subcase 2: $a\geq 0$ and $b>0$.

Set $q_{1}=0$ and $r_{1}=a\geq 0$. Then, we have $a=bq_{1}+r_{1}$.

Subsubcase 1: $r_{1}<b=|b|$. Take $q=q_{1}$ and $r=r_{1}$. Then, we have $$a=bq+r{\text{ and }}0\leq r<|b|,$$ and we are done.

Subsubcase 2: $r_{1}\geq b$.

Set $q_{2}=q_{1}+1$ and $0\leq r_{2}=r_{1}-b<r_{1}$. Then, we have $a=bq_{2}+r_{2}$ with $0\leq r_{2}<r_{1}$. Since there are exactly $r_{1}$ nonnegative integers less than $r_{1}$, we need to repeat this process at most $r_{1}$ times ($b\geq 1$, so $r_{2}$ is at most the preceding integer of $r_{1}$) to get a $r_{k}$ such that $0\leq r_{k}<|b|$ (and also a $q_{k}$).

So, we take $q=q_{k}$ and $r=r_{k}$. Then, we have $$a=bq+r{\text{ and }}0\leq r<|b|,$$ and we are done.

Uniqueness part:

Assume there exists another pair of integers $q^{*}$ and $r^{*}$ (in addition to the pair of integers $q$ and $r$) such that $$a=bq^{*}+r^{*}{\text{ and }}0\leq r^{*}<|b|.$$ Since we have also $$a=bq+r{\text{ and }}0\leq r<|b|,$$ we get, by subtracting the two equations, $$0=b(q-q^{*})+r-r^{*}\implies b(q-q^{*})=r^{*}-r.$$

Also, by considering the above two inequalities, we get $${\begin{aligned}&&0\leq &|r^{*}-r|<|b|\\&\Rightarrow &0\leq &|b(q-q^{*})|<|b|\\&\Rightarrow &0\leq &|b||q-q^{*}|<|b|\\&\Rightarrow &0\leq &|q-q^{*}|<1&(b\neq 0)\\&\Rightarrow &&|q-q^{*}|=0\\&\Rightarrow &&q=q^{*}.\\\end{aligned}}$$ Putting it in the above equation, we get $0=r^{*}-r\implies r=r^{*}$.

Thus, we have $q=q^{*}$ and $r=r^{*}$.

$\Box$

Remark.

• This lemma is the basis of Euclidean division, as known as division with remainder.
• $a$ is called the dividend, $b$ is called the divisor, $q$ is called the quotient, and $r$ 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 $n-1$ (from the inequality $0\leq r<|n|$) when divided by an integer $n$ with $n\geq 2$. In other words, for every integer $x$, we have either $x\equiv 0{\pmod {n}}$ or $x\equiv 1{\pmod {n}}$ or ... or $x\equiv n-1{\pmod {n}}$. For brevity, we can also write $x\equiv 0{\text{ or }}1{\text{ or }}\cdots {\text{ or }}n-1{\pmod {n}}$.

Example. Prove that for every integer $n$, $n^{2}\equiv 0{\text{ or }}1{\pmod {4}}$.

Proof. By Euclid's division lemma, we have $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\pmod {4}}$. Thus, we have $n^{2}\equiv 0{\text{ or }}1{\text{ or }}4{\text{ or }}9{\pmod {4}}$. But $4\equiv 0{\pmod {4}}$ and $9\equiv 1{\pmod {4}}$. So, the result follows by the transitivity of the congruence of integers.

$\Box$

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

Solution

Proposition: For every integer $n$, $n^{2}\equiv 0{\text{ or }}1{\text{ or }}4{\pmod {5}}$.

Proof. By Euclid's division lemma, we have $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\text{ or }}4{\pmod {5}}$. Thus, we have $n^{2}\equiv 0{\text{ or }}1{\text{ or }}4{\text{ or }}9{\text{ or }}16{\pmod {5}}$. But $9\equiv 4{\pmod {5}}$ and $16\equiv 1{\pmod {5}}$. So, the result follows.

$\Box$

Proofs related to sets

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 $X$ is a subset of another set $Y$ if for every element $x$, if $x\in X$, then $x\in Y$.

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 $X$ equals another set $Y$ if and only if $X\subseteq Y$ and $Y\subseteq X$.

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

Example. (Transitivity of "$\subseteq$") Prove that for every set $A,B$ and $C$, if $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

Proof. Assume $A\subseteq B$ and $B\subseteq C$. Then, for every $x$, $$x\in A{\overset {A\subseteq B}{\implies }}x\in B{\overset {B\subseteq C}{\implies }}x\in C,$$ and hence $A\subseteq C$.

$\Box$

Example. (Associative law) Prove that for every set $A,B$ and $C$, $A\cup (B\cup C)=(A\cup B)\cup C$.

Proof. First, we prove that $A\cup (B\cup C)\subseteq (A\cup B)\cup C$. For every $x$, $${\begin{aligned}x\in A\cup (B\cup C)&\implies (x\in A){\text{ or }}(x\in B{\text{ or }}x\in C)\\&\implies (x\in A{\text{ or }}x\in B){\text{ or }}x\in C&({\text{Associative law of disjunction}})\\&\implies x\in (A\cup B)\cup C.\end{aligned}}$$ Thus, we have $A\cup (B\cup C)\subseteq (A\cup B)\cup C$.

Now, we prove the reverse subset inclusion, i.e., $(A\cup B)\cup C\subseteq A\cup (B\cup C)$. For every $x$, $${\begin{aligned}x\in (A\cup B)\cup C&\implies (x\in A{\text{ or }}x\in B){\text{ or }}x\in C\\&\implies x\in A{\text{ or }}(x\in B{\text{ or }}x\in C)&({\text{Associative law of disjunction}})\\&\implies x\in A\cup (B\cup C).\end{aligned}}$$ Thus, we have $(A\cup B)\cup C\subseteq A\cup (B\cup C)$.

$\Box$

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 $x$, $${\begin{aligned}x\in A\cup (B\cup C)&\iff (x\in A){\text{ or }}(x\in B{\text{ or }}x\in C)\\&\iff (x\in A{\text{ or }}x\in B){\text{ or }}x\in C&({\text{associative law of disjunction}})\\&\iff x\in (A\cup B)\cup C.\end{aligned}}$$ Thus, we have $A\cup (B\cup C)=(A\cup B)\cup C$.

$\Box$

Using this proof, we can prove the set equality directly (set $A$ equals set $B$ if for every $x$, $x\in A\iff x\in B$). (However, we should be careful about whether we really have "$\iff$".) 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.

Exercise. (De Morgan's law) Let $A$ and $B$ subsets of a universal set $U$. Prove that $(A\cup B)^{c}=A^{c}\cap B^{c}$.

Proof

Proof. For every $x$, $${\begin{aligned}x\in (A\cup B)^{c}&\iff x\in U{\text{ and }}(x\notin A\cup B)\\&\iff x\in U{\text{ and }}{\big (}\sim (x\in A{\text{ or }}x\in B){\big )}\\&\iff x\in U{\text{ and }}{\big (}\sim (x\in A){\text{ and }}\sim (x\in B){\big )}&({\text{De Morgan's law in logic}})\\&\iff x\in U{\text{ and }}{\big (}x\notin A{\text{ and }}x\notin B{\big )}\\&\iff {\big (}x\in U{\text{ and }}{\big (}x\notin A{\big )}{\text{ and }}{\big (}x\in U{\text{ and }}x\notin B{\big )}\\&\iff x\in A^{c}{\text{ and }}x\in B^{c}\\&\iff x\in A^{c}\cap B^{c}.\end{aligned}}$$

$\Box$

Example. Let $A$ and $B$ be subsets of a universal set $U$. Prove that $A\setminus B=A\cap B^{c}$.

Proof. For every $x$, $$x\in A\setminus B\iff (x\in A{\text{ and }}x\notin B)\iff (x\in A{\text{ and }}x\in B^{c})\iff x\in A\cap B^{c}.$$

$\Box$

Exercise. Using this result, prove that $(A\cup B)\setminus (A\cap B)=(A\setminus B)\cup (B\setminus A)$. (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: $${\begin{aligned}(A\cup B)\setminus (A\cap B)&=(A\cup B)\cap (A\cap B)^{c}\\&=(A\cup B)\cap (A^{c}\cup B^{c})&({\text{De Morgan's law}})\\&={\big (}(A\cup B)\cap A^{c}{\big )}\cup {\big (}(A\cup B)\cap B^{c}{\big )}&({\text{Distributive law}})\\&={\big (}(A\cap A^{c})\cup (B\cap A^{c}){\big )}\cup {\big (}(A\cap B^{c})\cup (B\cap B^{c}){\big )}&({\text{Distributive law}})\\&={\big (}\varnothing \cup (B\cap A^{c}){\big )}\cup {\big (}(A\cap B^{c})\cup \varnothing {\big )}\\&=(B\cap A^{c})\cup (A\cup B^{c})\\&=(B\setminus A)\cup (A\setminus B).&({\text{above result}})\end{aligned}}$$

Example. Prove that for every set $A$ and $B$, $A\subseteq A\cup B$ and $A\cap B\subseteq A$.

Proof. For the first one, for every $x$, $$x\in A\implies x\in A{\text{ or }}x\in B\implies x\in A\cup B.$$ (no matter $x\in B$ is true or false, we always have the first implication.)

For the second one, for every $x$, $$x\in A\cap B\implies x\in A{\text{ and }}x\in B\implies x\in A.$$

$\Box$

Exercise.

(a) Propose an assumption on the sets $A$ and $B$ such that we have both reverse subset inclusions, i.e., $A\cup B\subseteq A$ and $A\subseteq A\cap B$. Prove them under this assumption.

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

(c) Propose an assumption on the sets $A$ and $B$ such that we have $A\subseteq A\cap B$ (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: $A=B$.

Proof. Assume $A=B$. For the first one, for every $x$, $$x\in A\cup B\implies x\in A{\text{ or }}x\in B\implies x\in A{\text{ or }}x\in A\implies x\in A.$$ For the second one, for every $x$, $$x\in A\implies x\in A{\text{ and }}x\in A\implies x\in A{\text{ and }}x\in B\implies x\in A\cap B.$$

$\Box$

(One can also use the some results in set theory (e.g. $A\cup A=A$, $A\cap A=A$, etc.) in the proof.)

(b) Assumption: $B\subseteq A$.

Proof. Assume $B\subseteq A$. Then, for every $x$, $$x\in A\cup B\implies x\in A{\text{ or }}x\in B\implies x\in A{\text{ or }}x\in A\implies x\in A.$$

$\Box$

(c) Assumption: $A\subseteq B$.

Proof. Assume $A\subseteq B$. Then, for every $x$, $$x\in A\implies x\in A{\text{ and }}x\in B\implies x\in A\cap B.$$ (We have the first implication, since if $x\in A$, then we have $x\in A$, and also $x\in B$ since $A\subseteq B$)

$\Box$

Exercise. Consider the statement: for every set $A,B$ and $C$, $(A\setminus B)\setminus C=(A\setminus C)\setminus (B\setminus C)$. A student gives the following proof:

Proof. For every $x$, $${\begin{aligned}x\in (A\setminus B)\setminus C&\iff x\in A\setminus B{\text{ and }}x\notin C\\&\iff x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C\\&\iff (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\\&\iff (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C&(B\setminus C\subseteq B,{\text{ and consider contrapositive}})\\&\iff x\in A\setminus C{\text{ and }}x\notin B\setminus C\\&\iff x\in (A\setminus C)\setminus (B\setminus C).\\\end{aligned}}$$

$\Box$

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

Solution

The mistake is in this step: $$(x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\iff (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C\quad (B\setminus C\subseteq B,{\text{ and consider contrapositive}}).$$ We have "$\Longrightarrow$", but do not necessarily have "$\Longleftarrow$", since we generally do not have $B\subseteq B\setminus C$, and thus we cannot show "$\Longleftarrow$" by contrapositive.

The following is a correct proof:

Proof. For every $x$, $${\begin{aligned}x\in (A\setminus B)\setminus C&\implies x\in A\setminus B{\text{ and }}x\notin C\\&\implies x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C&(B\setminus C\subseteq B,{\text{ and consider contrapositive}})\\&\implies x\in A\setminus C{\text{ and }}x\notin B\setminus C\\&\implies x\in (A\setminus C)\setminus (B\setminus C).\\\end{aligned}}$$ On the other hand, for every $x$, $${\begin{aligned}x\in (A\setminus C)\setminus (B\setminus C)&\implies x\in A\setminus C{\text{ and }}x\notin B\setminus C\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B\setminus C\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}(x\notin B{\text{ or }}x\in C)&({\text{De Morgan's law}})\\&\implies (x\in A{\text{ and }}x\notin C){\text{ and }}x\notin B){\text{ or }}(x\in A{\text{ and }}x\notin C{\text{ and }}x\in C)&({\text{Distributive law}})\\&\implies (x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C){\text{ or }}\mathbf {F} \\&\implies x\in A{\text{ and }}x\notin B{\text{ and }}x\notin C\\&\implies x\in A\setminus B{\text{ and }}x\notin C\\&\implies x\in (A\setminus B)\setminus C.\end{aligned}}$$

$\Box$

Example. Prove that for every set $A,B,C$ and $D$, if $A\subseteq C$ and $B\subseteq D$, then $A\times B\subseteq C\times D$.

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times B&\implies x\in A{\text{ and }}y\in B\\&\implies x\in C{\text{ and }}y\in D&(A\subseteq C{\text{ and }}B\subseteq D)\\&\implies (x,y)\in C\times D.\end{aligned}}$$

$\Box$

Example. Prove that for every set $A,B$ and $C$, $A\times (B\cup C)=(A\times B)\cup (A\times C)$.

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times (B\cup C)&\iff x\in A{\text{ and }}y\in B\cup C\\&\iff x\in A{\text{ and }}(y\in B{\text{ or }}y\in C)\\&\iff (x\in A{\text{ and }}y\in B){\text{ or }}(x\in A{\text{ and }}y\in C)&({\text{Distributive law}})\\&\iff (x,y)\in A\times B{\text{ or }}(x,y)\in A\times C\\&\iff (x,y)\in (A\times B)\cup (A\times C).\end{aligned}}$$

$\Box$

Exercise. Prove that for every set $A,B$ and $C$,

(a) $A\times (B\setminus C)=(A\times B)\setminus (A\times C)$.

(b) $A\times (B\cap C)=(A\times B)\cap (A\times C)$.

Solution

(a)

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times (B\setminus C)&\implies x\in A{\text{ and }}y\in B\setminus C\\&\implies x\in A{\text{ and }}y\in B{\text{ and }}y\notin C\\&\implies (x,y)\in A\times B{\text{ and }}(x,y)\notin A\times C&(y\notin C)\\&\implies (x,y)\in (A\times B)\setminus (A\times C).\end{aligned}}$$ (Notice that for the third "$\implies$", we cannot change it to "$\iff$" since $(x,y)\notin A\times C\not \implies y\notin C$.)

On the other hand, for every $(x,y)$, $${\begin{aligned}(x,y)\in (A\times B)\setminus (A\times C)&\implies (x\in A{\text{ and }}y\in B){\text{ and }}(x\notin A{\text{ or }}y\notin C)&({\text{De Morgan's law}})\\&\implies (x\in A{\text{ and }}y\in B{\text{ and }}x\notin A){\text{ or }}(x\in A{\text{ and }}y\in B{\text{ and }}y\notin C)&({\text{Distributive law}})\\&\implies \mathbf {F} {\text{ or }}(x\in A{\text{ and }}y\in B\setminus C)\\&\implies (x,y)\in A\times (B\setminus C).\end{aligned}}$$

$\Box$

(b)

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in A\times (B\cap C)&\iff x\in A{\text{ and }}y\in B\cap C\\&\iff x\in A{\text{ and }}y\in B{\text{ and }}y\in C\\&\iff (x\in A{\text{ and }}y\in B){\text{ and }}(x\in A{\text{ and }}y\in C)\\&\iff (x,y)\in A\times B{\text{ and }}(x,y)\in A\times C\\&\iff (x,y)\in (A\times B)\cap (A\times C).\end{aligned}}$$

$\Box$

Exercise. Consider the statement:

For every set $A,B$ and $C$, if $A\times C=B\times C$ and $C\neq \varnothing$, then $A=B$.

A student provides the following proof:

Proof. Assume $A\times C=B\times C$ and $C\neq \varnothing$. For every $a$, $${\begin{aligned}a\in A&\iff (a,c)\in A\times C&(C\neq \varnothing ,{\text{ so we can pick }}c\in C)\\&\iff (a,c)\in B\times C&(A\times C=B\times C)\\&\iff a\in B.\end{aligned}}$$

$\Box$

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

Solution

The proof is correct.

Example. Prove that $(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)$ for every set $A,B,C$ and $D$.

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in (A\times B)\cap (C\times D)&\iff (x,y)\in A\times B{\text{ and }}(x,y)\in C\times D\\&\iff (x\in A{\text{ and }}y\in B){\text{ and }}(x\in C{\text{ and }}y\in D)\\&\iff (x\in A{\text{ and }}x\in C){\text{ and }}(y\in B{\text{ and }}y\in D)\\&\iff x\in A\cap C{\text{ and }}y\in B\cap D\\&\iff (x,y)\in (A\cap C)\times (B\cap D).\\\end{aligned}}$$

$\Box$

Exercise. Prove that $(A\times B)\cup (C\times D)\subseteq (A\cup C)\times (B\cup D)$ for every set $A,B,C$ and $D$. (Hint: you may find the property $P{\text{ or }}Q\implies P$ useful.)

Proof

Proof. For every $(x,y)$, $${\begin{aligned}(x,y)\in (A\times B)\cup (C\times D)&\implies (x,y)\in A\times B{\text{ or }}(x,y)\in C\times D\\&\implies (x,y)\in A\times B\\&\implies x\in A{\text{ and }}y\in B\\&\implies x\in A\cup C{\text{ and }}y\in B\cup D\\&\implies (x,y)\in (A\cup C)\times (B\cup D).\end{aligned}}$$

$\Box$

Remark.

• The reverse subset inclusion does not hold. For instance, take $A=\{1\},B=\{2\},C=\{3\}$ and $D=\{4\}$. Then, $(A\times B)\cup (C\times D)=\{(1,2),(3,4)\}$ and $(A\cup C)\times (B\cup D)=\{1,3\}\times \{2,4\}=\{(1,2),(1,4),(3,2),(3,4)\}$. We can see that there is not reverse subset inclusion in this case.

Example. Let $A$ and $B$ be sets. Prove that $A\subseteq B$ if and only if ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$.

Proof. "$\Rightarrow$" direction: Assume $A\subseteq B$. Then, for every set $X$, $${\begin{aligned}X\in {\mathcal {P}}(A)&\implies X\subseteq A\\&\implies X\subseteq B&(A\subseteq B,{\text{ and transitivity of }}\subseteq )\\&\implies X\in {\mathcal {P}}(B).\end{aligned}}$$ Thus, we have ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$.

"$\Leftarrow$" direction: Assume ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$. Then, for every $x$, $${\begin{aligned}x\in A&\implies \{x\}\subseteq A&({\text{trick}})\\&\implies \{x\}\in {\mathcal {P}}(A)\\&\implies \{x\}\in {\mathcal {P}}(B)&({\mathcal {P}}(A)\subseteq {\mathcal {P}}(B))\\&\implies \{x\}\subseteq B\\&\implies x\in B.\end{aligned}}$$ Thus, $A\subseteq B$.

$\Box$

We can also prove the "$\Leftarrow$" direction more simply:

Assume ${\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$. Since for every set $X$, $X\subseteq X$, and thus $X\in {\mathcal {P}}(X)$, we have $${\begin{aligned}A\in {\mathcal {P}}(A)&\implies A\in {\mathcal {P}}(B)&({\mathcal {P}}(A)\subseteq {\mathcal {P}}(B))\\&\implies A\subseteq B.&({\text{transitivity of }}\subseteq )\end{aligned}}$$

Exercise. Let $A$ and $B$ be sets.

(a) Prove that ${\mathcal {P}}(A)\cap {\mathcal {P}}(B)={\mathcal {P}}(A\cap B)$.

(b) Give an example of $A$ and $B$ such that ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)\neq {\mathcal {P}}(A\cup B)$.

(c) We will have ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)={\mathcal {P}}(A\cup B)$ 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: $X\subseteq A{\text{ and }}X\subseteq B\iff X\subseteq A\cap B$.

Proof. "$\Rightarrow$" direction: Assume $X\subseteq A{\text{ and }}X\subseteq B$. Then, for every $x$, $x\in X\implies x\in A{\text{ and }}x\in B\implies x\in A\cap B$. So, $X\subseteq A\cap B$.

"$\Leftarrow$" direction: Assume $X\subseteq A\cap B$. Then, for every $x$, $x\in X\implies x\in A\cap B\implies x\in A$. Also, $x\in X\implies x\in A\cap B\implies x\in B$. Hence, $X\subseteq A$ and $X\subseteq B$.

$\Box$

For every set $X$, $${\begin{aligned}X\in {\mathcal {P}}(A)\cap {\mathcal {P}}(B)&\iff X\in {\mathcal {P}}(A){\text{ and }}X\in {\mathcal {P}}(B)\\&\iff X\subseteq A{\text{ and }}X\subseteq B\\&\iff X\subseteq A\cap B\\&\iff X\in {\mathcal {P}}(A\cap B).\\\end{aligned}}$$

$\Box$

(b) Take $A=\{1\}$ and $B=\{2\}$. Then, ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)=\{\varnothing ,\{1\},\{2\}\}$, while ${\mathcal {P}}(A\cup B)={\mathcal {P}}(\{1,2\})=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$.

(c) An assumption is "$A\subseteq B$ or $B\subseteq A$".

Proof. Assume $A\subseteq B$ or $B\subseteq A$.

Case 1: $A\subseteq B$.

Then, $A\cup B=B$. Hence, ${\mathcal {P}}(A\cup B)={\color {blue}{\mathcal {P}}(B)}$. On the other hand, by the above example, we have $A\subseteq B\implies {\mathcal {P}}(A)\subseteq {\mathcal {P}}(B)$, and thus ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)={\color {blue}{\mathcal {P}}(B)}$. Therefore, ${\mathcal {P}}(A)\cup {\mathcal {P}}(B)={\mathcal {P}}(A\cup B)$.

Case 2: $B\subseteq A$.

The proof is similar (just interchange "$A$" and "$B$").

$\Box$

Proof by contrapositive

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

A proof by contrapositive of the statement $\forall x\in S,P(x)\implies Q(x)$ is a direct proof of $\forall x\in S,\sim Q(x)\implies \sim P(x)$. That is, we first assume that $\sim Q(x)$ is true, and proceed to show that $\sim P(x)$ is true. In other words, we first assume that $Q(x)$ is false, and proceed to show that $P(x)$ is false.

Generally, when we encounter a statement $\forall x\in S,P(x)\implies Q(x)$, and observe that the consequent $Q(x)$ is "simpler" than the hypothesis $P(x)$, using proof by contrapositive is usually more preferable.

Example. Prove that for every $n\in \mathbb {Z}$, if $3n+1$ is even, then $n$ is odd.

Proof. Here, we use proof by contrapositive, that is we will prove that "for every $n\in \mathbb {Z}$, if $n$ is even, then $3n+1$ is odd."

Assume $n$ is even. Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $3n+1=6k+1=2(3k)+1$, and hence $3n+1$ is odd since $3k\in \mathbb {Z}$.

$\Box$

Remark.

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

Example. Prove that for every $n\in \mathbb {Z}$, $n$ is even if and only if $n^{2}$ is even.

Proof. "$\Rightarrow$" direction (or "only if" part):

Assume $n$ is even. Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $n^{2}=4k^{2}=2(2k^{2})$. Hence, $n^{2}$ is even since $k^{2}\in \mathbb {Z}$.

"$\Leftarrow$" direction (or "if" part):

We use proof by contrapositive, i.e., we will prove that "for every $n\in \mathbb {Z}$, if $n$ is odd, then $n^{2}$ is odd." Now, assume $n$ is odd. Then, $n=2k'+1$ for some $k'\in \mathbb {Z}$. Hence, $n^{2}=4k'^{2}+4k'+1=2(2k'^{2}+2k')+1$, and so $n^{2}$ is odd since $2k'^{2}+2k'\in \mathbb {Z}$.

$\Box$

Remark.

• Using proof by contrapositive for the "$\Leftarrow$" direction allows us to work with $n$, instead of $n^{2}$, initially.
• The statement is logically equivalent to "for every $n\in \mathbb {Z}$, $n$ is odd if and only if $n^{2}$ is odd." (since $P\leftrightarrow Q\iff \sim P\leftrightarrow \;\sim Q$).

Example. Prove that for every $n\in \mathbb {Z}$, $n^{2}\equiv 0{\pmod {4}}$ if and only if $n\equiv 0{\text{ or }}2{\pmod {4}}$.

Proof.

"$\Rightarrow$" direction:

We use proof by contrapositive. First, assume $n\not \equiv 0{\pmod {4}}{\text{ and }}n\not \equiv 2{\pmod {4}}$. Since $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\pmod {4}}$ by Euclid's division lemma, we have $n\equiv 1{\text{ or }}3{\pmod {4}}$. Hence, $n^{2}\equiv 1{\text{ or }}9{\pmod {4}}$. But $9\equiv 1{\pmod {4}}$. It follows that $n^{2}\equiv 1{\pmod {4}}$, and hence $n^{2}\not \equiv 0{\pmod {4}}$.

"$\Leftarrow$" direction:

Assume $n\equiv 0{\text{ or }}2{\pmod {4}}$. Then, we have $n^{2}\equiv 0{\text{ or }}4{\pmod {4}}$. But $4\equiv 0{\pmod {4}}$. So, we have $n^{2}\equiv 0{\pmod {4}}$.

$\Box$

Exercise. Prove that $n^{2}\equiv 1{\pmod {4}}$ if and only if $n\equiv 1{\text{ or }}3{\pmod {4}}$.

Proof

Proof.

"$\Rightarrow$" direction:

We use proof by contrapositive. First, assume $n\not \equiv 1{\pmod {4}}{\text{ and }}n\not \equiv 3{\pmod {4}}$. Since $n\equiv 0{\text{ or }}1{\text{ or }}2{\text{ or }}3{\pmod {4}}$ by Euclid's division lemma, we have $n\equiv 0{\text{ or }}2{\pmod {4}}$. Hence, $n^{2}\equiv 0{\text{ or }}4{\pmod {4}}$. But $4\equiv 0{\pmod {4}}$. It follows that $n^{2}\equiv 0{\pmod {4}}$, and hence $n^{2}\not \equiv 1{\pmod {4}}$.

"$\Leftarrow$" direction:

Assume $n\equiv 1{\text{ or }}3{\pmod {4}}$. Then, we have $n^{2}\equiv 1{\text{ or }}9{\pmod {4}}$. But $9\equiv 1{\pmod {4}}$. So, we have $n^{2}\equiv 1{\pmod {4}}$.

$\Box$

Notice that we can also apply the fact that $n^{2}\equiv 0{\text{ or }}1{\pmod {4}}$ (proved before) to conclude that $n^{2}\not \equiv 1{\pmod {4}}\iff n^{2}\equiv 0{\pmod {4}}$. Then, we can see that this statement is just logically equivalent to the above statement (since $P\leftrightarrow Q\iff \sim P\leftrightarrow \;\sim Q$).

Example. Let $A$ and $B$ be sets. Prove that $A\cup B=B$ if and only if $A\subseteq B$.

Proof.

"$\Rightarrow$" direction:

We use proof by contrapositive. Assume $A\not \subseteq B$, i.e., there exists an element $a\in A$ such that $a\notin B$. Since $a\in A$, it follows that $a\in A\cup B$. But $a\notin B$. So, $A\cup B\neq B$.

"$\Leftarrow$" direction:

Assume $A\subseteq B$. Since $B\subseteq A\cup B$ holds for every set $A$ and $B$, it suffices to show that $A\cup B\subseteq B$:

For every $x$, $${\begin{aligned}x\in A\cup B&\implies x\in A{\text{ or }}x\in B\\&\implies x\in B{\text{ or }}x\in B.&(A\subseteq B)\\&\implies x\in B.\end{aligned}}$$ So, $A\cup B\subseteq B$.

$\Box$

Exercise. Prove that for every set $A$ and $B$, if $(A\times B)\cap (B\times A)=\varnothing$, then $A\cap B=\varnothing$. (Hint: $A\cap B\neq \varnothing$ means that there exists an element $x$ such that $x\in A$ and $x\in B$.)

Proof

Proof. "$\Rightarrow$" direction:

We use proof by contrapositive. Assume $A\cap B\neq \varnothing$. Then, there exists an element $x$ such that $x\in A$ and $x\in B$. So, we have $(x,x)\in A\times B$ and $(x,x)\in B\times A$. This means $(x,x)\in (A\times B)\cap (B\times A)$. Thus, $(A\times B)\cap (B\times A)\neq \varnothing$.

"$\Leftarrow$" direction:

We use proof by contrapositive. Assume $(A\times B)\cap (B\times A)\neq \varnothing$. Then, there exists $(x,y)$ such that $(x,y)\in A\times B$ and $(x,y)\in B\times A$. It follows that $x\in A$ and $x\in B$, meaning that $x\in A\cap B$, and hence $A\cap B\neq \varnothing$.

$\Box$

Example. Prove that for every nonnegative real number $a$, if $a<x$ for every positive real number $x$, then $a=0$.

Proof. We use proof by contrapositive, i.e., we will prove that "if $a\neq 0$, then $a\geq x$ for some positive real number $x$."

Assume $a\neq 0$. This means $a>0$ since $a$ is nonnegative. Then, we pick $x=a$ which is a positive real number, and we have $a\geq x$.

$\Box$

Exercise. Prove that for every $x,y\in \mathbb {R}$, if $xy\leq 9$, then $x\leq 3$ or $y\leq 3$.

Proof

Proof. We use proof by contrapositive. Assume $x>3$ and $y>3$. Then, we have $xy>9$ (by the property of "$>$").

$\Box$

Exercise. An integer $n$ is defined to be a perfect square if $n=k^{2}$ for some $k\in \mathbb {Z}$. Prove that for every $a,b\in \mathbb {Z}$, if $a^{2}+b^{2}$ is a perfect square, then $a$ is even or $b$ is even. (Hint: consider a previous result about congruence of integers, that is related to perfect square.)

Proof

We use proof by contrapositive. Assume $a$ is odd and $b$ is odd. Then, $a=2k_{1}+1$ and $b=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Hence, $$a^{2}+b^{2}=4k_{1}^{2}+4k_{1}+1+4k_{2}^{2}+4k_{2}+1=4(k_{1}^{2}+k_{2}^{2}+k_{1}+k_{2})+2.$$ This means $a^{2}+b^{2}\equiv 2{\pmod {4}}$ since $k_{1}^{2}+k_{2}^{2}+k_{1}+k_{2}\in \mathbb {Z}$. However, no perfect square is congruent to 2 modulo 4 (recall that we have proved that for every integer $m$, $m^{2}\equiv 0{\text{ or }}1{\pmod {4}}$). Thus, $a^{2}+b^{2}$ is not a perfect square.

Proof by cases

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 $x$ and $y$, either $xy>0$ or $xy<0$.

• For every of the cases, it can be divided into two subcases:

1. $xy>0$: ($x>0$ and $y>0$) or ($x<0$ and $y<0$)
2. $xy<0$: ($x>0$ and $y<0$) or ($x<0$ and $y>0$)

But, we should be aware that when we use proof by cases to prove that "$\forall x\in S,\dotsc$", the cases should cover all possibilities, i.e., all $x\in S$.

Example. Prove that for every $n\in \mathbb {Z}$, $n^{2}+3n+4$ is even.

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

Case 1: $n$ is even.

Then, $n=2k$ for some $k\in \mathbb {Z}$. Thus, $$n^{2}+3n+4=4k^{2}+6k+4=2(2k^{2}+3k+2).$$ Since $2k^{2}+3k+2\in \mathbb {Z}$, $n^{2}+3n+4$ is even.

Case 2: $n$ is odd. Then, $n=2k'+1$ for some $k'\in \mathbb {Z}$. Thus, $$n^{2}+3n+4=4k'^{2}+4k'+1+6k'+3+4=2(2k'^{2}+5k'+4).$$ Since $2k'^{2}+5k'+4\in \mathbb {Z}$, $n^{2}+3n+4$ is even.

It follows that $n^{2}+3n+4$ is even for every $n\in \mathbb {Z}$.

$\Box$

Example. (Comparing parity) Prove that for every $m,n\in \mathbb {Z}$, $m$ and $n$ are of the same parity (i.e., both even or both odd) if and only if $m+n$ is even.

Proof. "$\Rightarrow$" direction: Assume $m$ and $n$ are of the same parity.

Case 1: $m$ and $n$ are both even.

Then, $m=2k_{1}$ and $n=2k_{2}$ for some $k_{1},k_{2}\in \mathbb {Z}$. Thus, $m+n=2(k_{1}+k_{2})$, and hence $m+n$ is even since $k_{1}+k_{2}\in \mathbb {Z}$.

Case 2: $m$ and $n$ are both odd.

Then, $m=2k_{3}+1$ and $n=2k_{4}+1$ for some $k_{3},k_{4}\in \mathbb {Z}$. Thus, $m+n=2(k_{3}+k_{4}+1)$, and hence $m+n$ is even since $k_{3}+k_{4}+1\in \mathbb {Z}$.

"$\Leftarrow$" direction: We use proof by contrapositive. Assume $m$ and $n$ are of different parity.

Case 1: $m$ is odd and $n$ is even.

Then, $m=2k_{5}+1$ and $n=2k_{6}$ for some $k_{5},k_{6}\in \mathbb {Z}$. Thus, $m+n=2k_{5}+1+2k_{6}=2(k_{5}+k_{6})+1$. Hence, $m+n$ is odd since $k_{5}+k_{6}\in \mathbb {Z}$.

Case 2: $m$ is even and $n$ is odd.

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

$\Box$

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 "$\Leftarrow$" direction in the above proof, we may write "Assume $m$ and $n$ are of different parity. WLOG, assume $m$ is odd and $n$ is even. ...".

Exercise. Let $a$ and $b$ be integers. Prove that $ab$ is even if and only if $a$ is even or $b$ is even.

Proof

Proof. "$\Rightarrow$" direction: We use proof by contrapositive. Assume $a$ is odd and $b$ is odd. Then, $a=2k_{1}+1$ and $b=2k_{2}+1$ for some $k_{1},k_{2}\in \mathbb {Z}$. Hence, $$ab=4k_{1}k_{2}+2k_{1}+2k_{1}+1=2(2k_{1}k_{2}+k_{1}+k_{2})+1,$$ and so $ab$ is odd since $2k_{1}k_{2}+k_{1}+k_{2}\in \mathbb {Z}$.

"$\Leftarrow$" direction: Assume $a$ is even or $b$ is even. WLOG, assume $a$ is even. Then, $a=2k$ for some $k\in \mathbb {Z}$. Thus, $ab=2kb=2(kb)$. Since $kb\in \mathbb {Z}$, $ab$ is even.

$\Box$

The following inequality is quite important in mathematics.

Theorem. (Triangle inequality) For every $x,y\in \mathbb {R}$, $|x+y|\leq |x|+|y|$.

Proof.

Case 1: $x\geq 0$ and $y\geq 0$.

Then, $x+y\geq 0$, and so $$|x+y|=x+y=|x|+|y|.$$

Case 2: $x<0$ and $y<0$.

Then, $x+y<0$, and so $$|x+y|=(-x)+(-y)=|x|+|y|.$$

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

WLOG, assume $x\geq 0$ and $y<0$.

Subcase 1: $x+y\geq 0$.

Then, $${\begin{aligned}|x+y|&=x+y\\&<x+(-y)&(y<0<-y)\\&=|x|+|y|.\end{aligned}}$$

Subcase 2: $x+y<0$.

Then, $${\begin{aligned}|x+y|&=-(x+y)\\&=(-x)+(-y)\\&\leq x+(-y)&(-x\leq 0\leq x)\\&=|x|+|y|.\end{aligned}}$$

So, we have the desired inequality for every $x,y\in \mathbb {R}$.

$\Box$

Proof by contradiction

Another important method of proof is proof by contradiction.

Let $P$ be a statement. Now, suppose we want to prove that $P$ is true. If we can show that the conditional $\sim S\to \mathbf {F}$ is true (i.e., $\sim S\implies \mathbf {F}$), then the truth table for conditional tells us that $\sim S$ must be false, and hence $S$ must be true, as desired.

The truth table: $${\begin{array}{c|c|c|c}S&\sim S&\mathbf {F} &\sim S\to \mathbf {F} \\\hline T&F&F&T\\F&T&F&F\\\end{array}}$$ 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 $n$ that can be written as a sum of two odd numbers $x$ and $y$. Then, we have $x=2k+1$ and $y=2k'+1$ for some $k,k'\in \mathbb {Z}$. Hence, we have $$n=x+y=2(k+k'+1),$$ which means $n$ is even since $k+k'+1\in \mathbb {Z}$. But this contradicts to our assumption that $n$ is odd. So, the result follows.

$\Box$

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

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

$\Box$

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 $x$. Now, consider the number $2x$. Since $x>0$, it follows that $2x>0$. Also, we have $2x>x$. Hence $2x$ is a positive real number that is greater than $x$, contradicting to our assumption that $x$ is the greatest positive real number.

$\Box$

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 $x$ and an arbitrary irrational number $y$ is a rational number $z$. So, we have $x+y=z$ where $x={\frac {p_{1}}{q_{1}}}$ and $z={\frac {p_{2}}{q_{2}}}$ where $p_{1},p_{2},q_{1},q_{2}\in \mathbb {Z}$ with $q_{1}\neq 0$ and $q_{2}\neq 0$. But we can then rewrite the equation as $$y=z-x={\frac {p_{2}}{q_{2}}}-{\frac {p_{1}}{q_{1}}}={\frac {p_{2}q_{1}-p_{1}q_{2}}{q_{1}q_{2}}}.$$ Since $p_{2}q_{1}-p_{1}q_{2},q_{1}q_{2}\in \mathbb {Z}$ and $q_{1}q_{2}\neq 0$, this means $y$ is rational, contradicting to our assumption that $y$ is irrational.

$\Box$

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

Example. Prove that the number ${\sqrt {2}}$ is irrational.

Proof. Assume to the contrary that ${\sqrt {2}}$ is rational. Then, ${\sqrt {2}}={\frac {p}{q}}$ for some $p,q\in \mathbb {Z}$ with $q\neq 0$. By dividing $p$ and $q$ by some common factor that is at least 2, if necessary, we can further assume that $p$ and $q$ have no common factor greater than or equal to 2, i.e., $p/q$ has been expressed in (or reduced to) the lowest terms.

Taking square for the both sides of the equation ${\sqrt {2}}={\frac {p}{q}}$, we get $2={\frac {p^{2}}{q^{2}}}\implies p^{2}=2q^{2}$. Since $q^{2}\in \mathbb {Z}$, this means $p^{2}$ is even. By a previous result, this implies that $p$ is even. Hence, we have $p=2k$ for some $k\in \mathbb {Z}$.

Now substituting it into the equation $p^{2}=2q^{2}$, we get $4k^{2}=2q^{2}\implies q^{2}=2k^{2}$, which means $q^{2}$ is also even since $k^{2}\in \mathbb {Z}$. By a previous result again, this implies that $q$ is even.

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

$\Box$

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 $n\geq 2$ can be expressed as a product of one or more (not necessarily distinct) primes uniquely. That is, $n=p_{1}p_{2}\dotsc p_{r}$ for some prime numbers $p_{1},p_{2},\dotsc ,p_{k}$, uniquely.

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

$\Box$

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 $n$ prime numbers. We first list them in ascending order: $p_{1}<p_{2}<\dotsb <p_{n}$. Now, consider the number $$q=p_{1}p_{2}\dotsb p_{n}+1.$$ Since the smallest prime number is 2, we have $p_{1}p_{2}\dotsb p_{n}\geq 1$ , and hence $q\geq 2$. Applying the fundamental theorem of arithmetic, there is a unique prime factorization for $q$, and thus there is a prime number dividing $q$.

Since $p_{1},\dotsc ,p_{n}$ are all the primes by our assumption, it follows that one of them, say $p_{i}$, divides $q$, i.e., $q=kp_{i}$ for some $k\in \mathbb {Z}$. In addition, we know that $p_{i}$ divides $p_{1}p_{2}\dotsb p_{n}$, i.e., $p_{1}p_{2}\dotsb p_{n}=k'p_{i}$ for some $k'\in \mathbb {Z}$.

Therefore, we have $1=q-p_{1}p_{2}\dotsb p_{n}=(k-k')p_{i}$. This means $p_{i}$ divides 1, which is impossible (notice that 2 is the smallest prime, and only 1 divides itself). So, we are arriving at a contradiction.

$\Box$

Remark.

• This proof is first suggested by Euclid.

We can also use proof by contradiction to prove that a statement "$\forall x\in S,P(x)\to Q(x)$" is true. We first assume that the negation of the statement, i.e., "$\exists x\in S,P(x)\land (\sim Q(x))$" is true, and proceed to arrive at a contradiction. (Recall that $P\to Q\iff (\sim P)\lor Q$. So, $\sim (P\to Q)\iff P\land (\sim Q)$.) Thus, to prove that $\forall x\in S,P(x)\implies Q(x)$ by contradiction, we assume that there exists $x\in S$ such that $P(x)$ is true and $Q(x)$ is false, and then deduce a contradiction.

Example. Prove by contradiction that for every $n\in \mathbb {Z}$, if $n$ is odd, then $3n+1$ is even.

Proof. Assume to the contrary that there exists $n\in \mathbb {Z}$ such that $n$ is odd and $3n+1$ is odd. Since $n$ is odd, we have $n=2k+1$ for some $k\in \mathbb {Z}$. Then, $$3n+1=3(2k+1)+1=6k+4=2(3k+2).$$ This means $3n+1$ is even since $3k+2\in \mathbb {Z}$, contradicting to our assumption that $3n+1$ is odd.

$\Box$

Exercise. Prove by contradiction that for every nonnegative real number $a$, if $a<x$ for every positive real number $x$, then $a=0$.

Proof

Proof. Assume to the contrary that $a<x$ for every positive real number $x$ and $a\neq 0$. Since $a$ is nonnegative, this means $a>0$. Now, consider the number $x=a>0$. By assumption, we have $a<x=a$, which implies that $1<1$, arriving at a contradiction.

$\Box$

Example. Prove that $x=\log _{10}3$ is irrational.

Proof. Assume to the contrary that $x$ is rational, i.e., $x={\frac {p}{q}}$ for some $p,q\in \mathbb {Z} \setminus \{0\}$ ($x\neq 0$). Notice that $x>0$. So, we only have the following cases:

Case 1: $p,q\in \mathbb {N}$.

Now, we have $${\begin{aligned}&&10^{x}&=1\\&\Rightarrow &10^{p/q}&=3\\&\Rightarrow &10^{p}&=3^{q}.\end{aligned}}$$ But $10^{p}$ is even, while $3^{q}$ is odd (product of even (odd) numbers is even (odd)).

Case 2: $p$ and $q$ are both negative integers.

Then, we write $x={\frac {-p}{-q}}$. Now, we have $${\begin{aligned}&&10^{x}&=3\\&\Rightarrow &10^{-p/-q}&=3\\&\Rightarrow &10^{-p}&=3^{-q}.\\\end{aligned}}$$ But $10^{-p}$ is even, while $3^{-q}$ is odd ($-p$ and $-q$ are positive integers).

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

$\Box$

Exercise. A student provides the following proof to the claim "$x=\log _{10}1$ is irrational.":

Proof. Assume to the contrary that $x$ is rational, i.e., $x={\frac {p}{q}}$ for some $p,q\in \mathbb {Z} \setminus \{0\}$ ($x\neq 0$). Notice that $x>0$. So, we only have the following cases:

Case 1: $p,q\in \mathbb {N}$.

Now, we have $${\begin{aligned}&&10^{x}&=1\\&\Rightarrow &10^{p/q}&=1\\&\Rightarrow &10^{p}&=1.\end{aligned}}$$ But $10^{p}$ is even, while $1$ is odd.

Case 2: $p$ and $q$ are both negative integers.

Then, we write $x={\frac {-p}{-q}}$. Now, we have $${\begin{aligned}&&10^{x}&=1\\&\Rightarrow &10^{-p/-q}&=1\\&\Rightarrow &10^{-p}&=1.\\\end{aligned}}$$ But $10^{-p}$ is even, while $1$ is odd.

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

$\Box$

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

Solution

The proof is incorrect. Indeed, $\log _{10}1=0$ is rational. The mistake is that the student states that $x\neq 0$ and also $x>0$ in the proof, which are not true.

Exercise. Prove that for every $x,y\in \mathbb {R}$, if $x+y$ is rational, then both $x$ and $y$ are rational, or both $x$ and $y$ are irrational.

Proof

Proof. Assume to the contrary that there exists $x,y\in \mathbb {R}$ such that $x+y\in \mathbb {Q}$ and exactly one of $x$ and $y$ is rational, and the other irrational. WLOG, assume $x\in \mathbb {Q}$ and $y\in \mathbb {I}$. Then, since $y=(x+y)-x$, and $x+y\in \mathbb {Q}$ and $x\in \mathbb {Q}$, we have $y\in \mathbb {Q}$, contradicting to our assumption that $y\in \mathbb {I}$.

$\Box$

Example. (Sum and product of a rational and an irrational number) Prove that for every $x,y\in \mathbb {R}$, (a) if $x\in \mathbb {Q}$ and $y\in \mathbb {I}$, then $x+y\in \mathbb {I}$;

(b) if $x\in \mathbb {Q} \setminus \{0\}$ and $y\in \mathbb {I}$, then $xy\in \mathbb {I}$.

Solution.

(a)

Proof. Assume to the contrary that there exist $x,y\in \mathbb {R}$ such that $x\in \mathbb {Q}$ and $y\in \mathbb {I}$ and $x+y\in \mathbb {Q}$. Then, $y=(x+y)-x\in \mathbb {Q}$, contradicting to our assumption that $y\in \mathbb {I}$.

$\Box$

(b)

Proof. Assume to the contrary that there exist $x\in \mathbb {Q} \setminus \{0\}$ and $y\in \mathbb {I}$ and $xy\in \mathbb {Q}$. Then, $y={\frac {xy}{x}}\in \mathbb {Q}$ ($x\neq 0$), contradicting to our assumption that $y\in \mathbb {I}$.

$\Box$

Sometimes we can prove a statement using multiple methods:

Example. Prove that for every positive real number $x$ and $y$, if $x\leq y$, then $x^{2}\leq y^{2}$.

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

(i)

Proof. Assume $x\leq y$. Then multiplying both sides by $x$ gives $x^{2}\leq xy$. Also, multiplying both sides by $y$ gives $xy\leq y^{2}$. Combining these two inequalities, we get $x^{2}\leq y^{2}$.

$\Box$

(ii)

Proof. Assume $x^{2}>y^{2}$. Rearranging the inequality gives $x^{2}-y^{2}>0\implies (x-y)(x+y)>0$. Now dividing both sides by the positive number $x+y$ preserves the direction of inequality, and thus gives $x-y>0\implies x>y$.

$\Box$

(iii)

Proof. Assume to the contrary that $x\leq y$ and $x^{2}>y^{2}$. Then, we have $x\leq y\implies x-y\leq 0$. Also, since $x$ and $y$ are positive, $x+y>0$. So we have $(x-y)(x+y)\leq 0\implies x^{2}-y^{2}\leq 0\implies x^{2}\leq y^{2}$, contradicting to our assumption that $x^{2}>y^{2}$.

$\Box$

Exercise. Let $x$ be a positive real number. Prove that if $x-{\frac {3}{x}}>2$, then $x>3$ by (i) direct proof; (ii) proof by contrapositive; (iii) proof by contradiction.

Solution

(i)

Proof. Assume $x-{\frac {3}{x}}>2$. Multiplying both side by $x$ gives $x^{2}-3>2x\implies x^{2}-2x-3>0\implies (x+1)(x-3)>0$. Then, dividing both sides by the positive number $x+1$ gives $x-3>0\implies x>3$.

$\Box$

(ii)

Proof. Assume $x\leq 3$. Then, $x-3\leq 0$. Also, $x+1>0$ ($x$ is positive). Thus, $(x-3)(x+1)\leq 0$. This implies $$x^{2}-2x-3\leq 0\implies x-{\frac {3}{x}}\leq 2.$$

$\Box$

(iii)

Proof. Assume to the contrary that $x-{\frac {3}{x}}>2$ and $x\leq 3$. Then, $x-3\leq 0$. Also, $x+1>0$. So, $(x-3)(x+1)\leq 0$, and hence $x-{\frac {3}{x}}\leq 2$. This contradicts to our assumption that $x-{\frac {3}{x}}>2$.

$\Box$

We can see that when proving a statement "$\forall x\in S,P(x)\implies Q(x)$", 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 "$\forall x\in S,P(x)\implies Q(x)$."

	Proof by contrapositive	Proof by contradiction
Assumption	$\sim Q(x)$	$P(x)\land \sim Q(x)$
Goal	$\sim P(x)$	$\mathbf {F}$

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 $P(x)$ (when we assume $P(x)\land \sim Q(x)$, we can use both $\sim Q(x)$ and $P(x)$.) However, in terms of goal, the proof by contrapositive is more advantageous since the goal is more clear ($\sim P(x)$), 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 "${\sqrt {2}}$ is irrational" vs. that of "there are infinitely many primes").

Existence proof

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

Example. Prove that there exists positive integers $a,b,c$ such that $a^{2}+b^{2}=c^{2}$ (such integers $a,b,c$ are known as a Pythagorean triple).

Proof. Take $a=3$, $b=4$ and $c=5$ (which are integers). Then, $a^{2}+b^{2}=3^{2}+4^{2}=5^{2}=c^{2}$.

$\Box$

Remark.

• The choice of $a,b,c$ is not unique. For instance, one can also take $a=5,b=12$ and $c=13$. But, giving one example of $a,b$ and $c$ that satisfies the requirement is enough.

Example. Prove that there exists an integer $x$ such that $x^{3}=x$.

Proof. Take $x=1$. Then, we have $x^{3}=1^{3}=1=x$.

$\Box$

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

Example. Prove that there exist irrational numbers $a$ and $b$ such that $a^{b}$ is rational.

Proof. We have proved that ${\sqrt {2}}$ is irrational. So, we can make use of this fact in this proof.

Consider the real number ${\sqrt {2}}^{\sqrt {2}}$. This number is either rational or irrational. Now we consider the following cases:

Case 1: ${\sqrt {2}}^{\sqrt {2}}$ is rational. Then, we can take $a=b={\sqrt {2}}\in \mathbb {I}$, and then $a^{b}$ is rational.

Case 2: ${\sqrt {2}}^{\sqrt {2}}$ is irrational. Then, we can take $a={\sqrt {2}}^{\sqrt {2}}\in \mathbb {I}$ and $b={\sqrt {2}}\in \mathbb {I}$. Then, $a^{b}=\left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}=({\sqrt {2}})^{{\sqrt {2}}\cdot {\sqrt {2}}}=({\sqrt {2}})^{2}=2,$ which is rational.

Thus, in either case, we can find two irrational numbers $a$ and $b$ such that $a^{b}$ is rational.

$\Box$

Remark.

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

Exercise.

(a) Prove that there exist distinct irrational numbers $a$ and $b$ such that $a^{b}$ is rational. (You may use the fact that ${\sqrt {3}}$ is irrational.)

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

(c) Prove that there exist a rational number $a$ and an irrational number $b$ such that $a^{b}$ is irrational. (You may use the fact that ${\frac {1}{2{\sqrt {2}}}}$ is irrational.)

(d) Prove that there exist rational numbers $a$ and $b$ such that $a^{b}$ is irrational.

Solution

(a)

Proof. Consider the real number ${\sqrt {3}}^{\sqrt {2}}$. It is either rational or irrational. Now, we consider the following cases:

Case 1: ${\sqrt {3}}^{\sqrt {2}}$ is rational. Then, we can take $a={\sqrt {3}}\in \mathbb {I}$ and $b={\sqrt {2}}\in \mathbb {I}$, and $a^{b}$ is rational.

Case 2: ${\sqrt {3}}^{\sqrt {2}}$ is irrational. Then, we can take $a={\sqrt {3}}^{\sqrt {2}}\in \mathbb {I}$ and $b={\sqrt {2}}\in \mathbb {I}$. Then, $a^{b}=\left({\sqrt {3}}^{\sqrt {2}}\right)^{\sqrt {2}}=({\sqrt {3}})^{2}=3$, which is rational.

$\Box$

(b)

Proof. Take $a=10$ and $b=\log _{10}3$. Recall that we have proved that $b=\log _{10}3$ is irrational. Then, we have $a^{b}=10^{\log _{10}3}=3$, which is rational.

$\Box$

(c)

Proof. Consider the real number $2^{1/(2{\sqrt {2}})}$. Now, consider the following cases:

Case 1: $2^{1/(2{\sqrt {2}})}$ is irrational. Then, take $a=2$ and $b={\frac {1}{2{\sqrt {2}}}}\in \mathbb {I}$, and $a^{b}$ is irrational.

Case 2: $2^{1/(2{\sqrt {2}})}$ is rational. Then, take $a=2^{1/(2{\sqrt {2}})}\in \mathbb {Q}$ and $b={\sqrt {2}}\in \mathbb {I}$. Then, $a^{b}=\left(2^{1/(2{\sqrt {2}})}\right)^{\sqrt {2}}=2^{1/2}={\sqrt {2}}$, which is irrational.

$\Box$

(d)

Proof. Take $a=2$ and $b=1/2$. Then, $a^{b}=2^{1/2}={\sqrt {2}}$, which is irrational.

$\Box$

Disproof

Consider the statement "$\forall x\in S,P(x)$.". Suppose we somehow believe that the statement is false. Then, we want to prove that it is false, i.e., prove that "$\exists x\in S$ such that $P(x)$ is false." An element $x_{0}\in S$ for which $P(x_{0})$ 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 $x^{3}\geq 0$ for every $x\in \mathbb {R}$.

Disproof. Take $x=-1$. Then, $(-1)^{3}=-1<0$.

$\Box$

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

Disproof. To disprove this, we need to find $x,y\in \mathbb {I}$ such that $xy\in \mathbb {Q}$.

Take $x=y={\sqrt {2}}$. Then, $xy=2\in \mathbb {Q}$.

$\Box$

To disprove the statement "$\forall x\in S,P(x)\to Q(x)$, we show that there exists an element $x_{0}\in S$ such that $P(x_{0})\to Q(x_{0})$ is false, i.e., $P(x_{0})$ is true and $Q(x_{0})$ is false.

Example. Disprove that for every $x\in \mathbb {Z}$, if $x^{2}\equiv 1{\pmod {4}}$, then $x\equiv 1{\pmod {4}}$.

Disproof. Take $x=3$. Then $x^{2}=9\equiv 1{\pmod {4}}$ but $3\not \equiv 1{\pmod {4}}$.

$\Box$

To disprove the statement "$\exists x\in S,P(x)$", we need to show that there is no such $x$. That is, we need to show that "$\forall x\in S,\sim P(x)$" (the negation of statement) is true. In this case, we are not just constructing counterexamples. We have to prove that ${\color {darkgreen}\forall }x\in S,\sim P(x)$, instead of $\exists x\in S,\sim P(x)$.

Example. Disprove that there exists $n\in \mathbb {Z}$ such that $n^{2}+3n+4$ is odd.

Disproof. To disprove this, we need to prove that for every $n\in \mathbb {Z}$, $n^{2}+3n+4$ is even. But this has been proved previously (in the section about proof by cases).

$\Box$

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 "$\forall \dotsb$")/example (for proving "$\exists \dotsb$") 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 $x$ satisfying the equation $x^{6}+9x^{2}+3=0$.

(b) Let $A,B$ and $C$ be sets. If $A\times C=B\times C$, then $A=B$.

(c) For every real number $x$, ${\frac {x^{2}+x}{x^{2}-x}}={\frac {x+1}{x-1}}$.

(d) There exists a real number $x$ such that $x^{3}<x<x^{2}$.

Solution.

(a)

Disproof. Since $x$ is a real number, we have $x^{6}\geq 0$ and $x^{2}\geq 0$. Hence, $x^{6}+9x^{2}+3\geq 3$, and thus $x^{6}+9x^{2}+3\neq 0$ for every $x\in \mathbb {R}$.

$\Box$

(b)

Disproof. Take $A=\{1\}$, $B=\{2\}$ and $C=\varnothing$. Then, $A\times C=B\times C=\varnothing$, but $A\neq B$ .

$\Box$

(c)

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

$\Box$

(d)

Proof. Take $x=-2$. Then, $x^{3}=-8$ and $x^{2}=4$, and we have $x^{3}<x<x^{2}$.

$\Box$

Exercise. Prove or disprove every of the following statements:

(a) There exists a real number $x$ such that ${\sqrt {2}}-x$ and ${\sqrt {2}}+x$ are both rational.

(b) There exists $m,n\in \mathbb {Q}$ with $m\neq n$ such that ${\frac {1}{m}}+{\frac {1}{n}}=3$.

(c) There exist even numbers $x$ and $y$ such that $3x^{2}+y^{2}\equiv 0{\pmod {8}}$.

(d) For every $a,b,c,d\in \mathbb {R}$, if $a<b$ and $c<d$, then $ac<bd$.

(e) For every $a,b\in \mathbb {Q}$ with $a<b$, there exists $x\in \mathbb {Q}$ such that $a<x<b$.

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 $x$ such that ${\sqrt {2}}-x$ and ${\sqrt {2}}+x$ are both rational. Then, we have $({\sqrt {2}}-x)+({\sqrt {2}}+x)=2{\sqrt {2}}$ is rational, which contradicts to the fact that $2{\sqrt {2}}$ (product of a rational number and an irrational number) is irrational.

$\Box$

(b)

Proof. Take $m=1$ and $n=1/2$. Then, ${\frac {1}{m}}+{\frac {1}{n}}=1+2=3$.

$\Box$

(c)

Proof. Take $x=y=2$. Then, $3x^{2}+y^{2}=3(2)^{2}+2^{2}=12+4=16\equiv 0{\pmod {8}}$.

$\Box$

(d)

Disproof. Take $a=c=-2$ and $b=d=1$. Then, $a<b$ and $c<d$, but $ac=4>1=bd$.

$\Box$

(e)

Proof. For every $a,b\in \mathbb {Q}$, choose $x={\frac {m+n}{2}}\in \mathbb {Q}$ (sum/product of two rational numbers is rational). Since $m<n$, we have $m={\frac {m}{2}}+{\frac {m}{2}}<{\frac {m+n}{2}}<{\frac {n}{2}}+{\frac {n}{2}}=n$, as desired.

$\Box$

Proof by mathematical induction

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 $n$ greater than or equal to an integer $m$, $P(n)$ is true.". That is, it is used to prove that a sequence of statements $P(m),P(m+1),P(m+2),\dotsc$ 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 $S$ of real numbers is well-ordered if every nonempty subset of $S$ has a least element.

Example.

• The set $\{-3,1,2\}$ is well-ordered since its nonempty subsets are $\{-3\},\{1\},\{2\},\{-3,1\},\{-3,2\},\{1,2\},\{-3,1,2\}$, and every of these subsets has a least element.
• The sets $\mathbb {Z} ,\mathbb {Q} ,\mathbb {R}$ 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 $\mathbb {N}$ 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 $\mathbb {N}$ 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. "$P(m)$ is true" means the first domino can be pushed down, and "for every integer $k\geq m$, $P(k)\implies P(k+1)$" 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 $m\in \mathbb {Z}$, if $P(m),P(m+1),P(m+2),\dotsc$ are statements satisfying

(i) $P(m)$ is true; and

(ii) for every integer $k\geq m$, $P(k)\implies P(k+1)$,

then the statements $P(m),P(m+1),P(m+2),\dotsc$ are true.

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

• $P(m)$ is true (by (i)).
• Thus, $P(m+1)$ is true (by (ii)).
• Thus, $P(m+2)$ is true (by (ii)).
• Thus, $P(m+3)$ 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 $m\in \mathbb {N}$.

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 $n$ for which $P(n)$ is false. Now, let the set $$S=\{n\in \mathbb {N} :P(n){\text{ is false}}\}.$$ Since $S$ is a nonempty subset of $\mathbb {N}$, by the well-ordering principle, $S$ contains a least element. Let us assume $s$ to be the least element.

Since $P(m)$ is true by the condition (i), $m\notin S$. This means the least element $s$ cannot be $m$. Hence, $s\geq m+1$, which means $s-1\geq m$.

Since $s$ is the least element of $S$, we have $s-1\notin S$, i.e., $P(s-1)$ is a true statement. Then, by the condition (ii), $P(s)$ is true (we have $s-1\geq m$). It follows that $s\notin S$. But this contradicts to our assumption that $s$ is the least element of $S$ (in particular, $s\in S$).

$\Box$

Remark.

• This proof can be extended to the case where $m\in \mathbb {Z}$. But the proof needs to use the result that the set $\{i\in \mathbb {Z} :i\geq m\}$ is well-ordered. Once we have proven this result, we can simply change the set $S$ in the proof to $\{i\in \mathbb {Z} :i\geq m{\text{ and }}P(i){\text{ is false}}\}$, and also modify some sentences in the proof slightly for the extension.
• Notice that in the inductive hypothesis, we assume $P(k)$ is true for an arbitrary integer $k$ with $k\geq m$, but not for every integer $k\geq m$. 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 $P(k)$ is true for an arbitrary (but not every) integer $k$ with $k\geq m$, but this does not lose generality since $k$ is arbitrary.

Using the principle of mathematical induction, to prove that the statement $P(n)$ is true for every integer $n\geq m$, it suffices to prove two things:

(i) $P(m)$ is true.

(ii) For every integer $k\geq m$, $P(k)\implies P(k+1)$.

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 $P(k)$ is true for an arbitrary integer $k$ with $k\geq m$. Such assumption is often called the inductive (or induction) hypothesis.

Example. Prove that for every $n\in \mathbb {N}$, $$P(n):1+2+\dotsb +n={\frac {n(n+1)}{2}}$$ is true.

Proof. Here we use the principle of mathematical induction.

Basis Step: Since $1={\frac {1(1+1)}{2}}$, the statement $P(1)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary positive integer. Assume $P(k)$ is true. That is, assume $${\color {blue}1+2+\dotsb +k={\frac {k(k+1)}{2}}}$$ is true.

Inductive Step: Since $${\begin{aligned}{\color {blue}1+2+\dotsb +k}+(k+1)&={\color {blue}{\frac {k(k+1)}{2}}}+(k+1)&({\text{inductive hypothesis}})\\&={\frac {k^{2}+k+2k+2}{2}}\\&={\frac {(k+1)(k+2)}{2}},\end{aligned}}$$ it follows that $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every positive integer $n$.

$\Box$

Remark.

• One can also prove this statement using a trick:

First write the sum as $1+2+\dotsb +(n-1)+n$.

Now also write the same sum, but in reverse order: $n+(n-1)+\dotsb +2+1$.

After that, add the two sums together in the following way:

$${\begin{aligned}&&{\color {darkgreen}1}+{\color {blue}2}+\dotsb +{\color {darkgreen}(n-1)}+{\color {blue}n}\\&+)&{\color {darkgreen}n}+{\color {blue}(n-1)}+\dotsb +{\color {darkgreen}2}+{\color {blue}1}\\\hline &&\underbrace {{\color {darkgreen}(n+1)}+{\color {blue}(n+1)}+\dotsb +{\color {darkgreen}(n+1)}+{\color {blue}(n+1)}} _{n{\text{ times}}}\end{aligned}}$$

Now, we can see that two times the sum gives $n(n+1)$. Thus, the sum $1+2+\dotsb +(n-1)+n$ is ${\frac {n(n+1)}{2}}$.

Exercise. For every $n\in \mathbb {N}$, consider the sum $$1^{3}+2^{3}+\dotsb +n^{3}.$$ Guess a general formula for the sum and prove it. (Hint: you may compute the value of sum for some values of $n$, and see whether there are any patterns.)

Solution

When $n=1,2,3,4$, the sum is $1,9,36,100$ respectively. Notice that $1=1^{2},9=3^{2}=(1+2)^{2},36=6^{2}=(1+2+3)^{2}$ and $100=10^{2}=(1+2+3+4)^{2}$. Hence, it is natural to guess that the formula is, for every $n\in \mathbb {N}$, $$1^{3}+2^{3}+\dotsb +n^{3}=(1+2+\dotsb +n)^{2}.$$ But we have proved that $1+2+\dotsb +n={\frac {n(n+1)}{2}}$. So this formula can be alternatively expressed as $$1^{3}+2^{3}+\dotsb +n^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}.$$

Proof. Let $P(n)$ be the open statement "$1^{3}+2^{3}+\dotsb +n^{3}=\left({\frac {n(n+1)}{2}}\right)^{2}$".

Basis Step: Since $1^{3}=\left({\frac {1(1+1)}{2}}\right)^{3}$, $P(1)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary positive integer $k$. That is, assume $$1^{3}+2^{3}+\dotsb +k^{3}=\left({\frac {k(k+1)}{2}}\right)^{2}.$$

Inductive Step: Since $${\begin{aligned}1^{3}+2^{3}+\dotsb +k^{3}+(k+1)^{3}&=\left({\frac {k(k+1)}{2}}\right)^{2}+(k+1)^{3}\\&={\frac {k^{2}(k+1)^{2}+{\color {darkgreen}4}(k+1)^{3}}{2^{2}}}\\&={\frac {(k+1)^{2}(k^{2}+{\color {darkgreen}4}(k+1))}{2^{2}}}\\&={\frac {(k+1)^{2}(k+2)^{2}}{2^{2}}}\\&=\left({\frac {(k+1)(k+2)}{2}}\right)^{2},\end{aligned}}$$ $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every positive integer $n$.

$\Box$

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 $n\geq 5$, $2^{n}>n^{2}$.

Proof. Let $P(n)$ be the open statement "$2^{n}>n^{2}$".

Basis Step: Since $2^{5}=32>25=5^{2}$, $P(5)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary integer $k$ with $k\geq 5$. That is, assume $$2^{k}>k^{2}.$$ Inductive Step: Since $$2^{k+1}=2(2^{k})>2k^{2}\quad ({\text{inductive hypothesis}}),$$ it suffices to show that $2k^{2}>(k+1)^{2}$. Now, consider $2k^{2}-(k+1)^{2}$: $$2k^{2}-(k+1)^{2}=k^{2}-2k-1=(k-1)^{2}-2>0.\quad (k\geq 5)$$ Thus, $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 5$.

$\Box$

Exercise. Prove that for every integer $n\geq 4$, $n!>2^{n}$.

Proof

Let $P(n)$ be the open statement "$n!>2^{n}$".

Basis Step: Since $4!=24>16=2^{4}$, $P(4)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary integer $k\geq 4$. That is, assume $$k!>2^{k}.$$

Inductive Step: Since $$(k+1)!=(k+1)k!>{\color {darkgreen}(k+1)}2^{k}>{\color {darkgreen}2}\cdot 2^{k}=2^{k+1},$$ (we have $k+1>2$ since $k\geq 4$) $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 4$.

Example. (Sum of a geometric sequence) Prove that for every integer $n\geq 0$ and for every real number $r\neq 1$, we have $$1+r+r^{2}+\dotsb +r^{n}={\frac {1-r^{n+1}}{1-r}}.$$

Proof. Let $P(n)$ be the open statement "$1+r+r^{2}+\dotsb +r^{n}={\frac {1-r^{n+1}}{1-r}}$".

Basis Step: Since $1={\frac {1-r^{1}}{1-r}}$, $P(0)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary nonnegative integer $k$. That is, assume $$1+r+r^{2}+\dotsb +r^{k}={\frac {1-r^{k+1}}{1-r}}.$$

Inductive Step: Since $$1+r+r^{2}+r^{k}+r^{k+1}={\frac {1-r^{k+1}}{1-r}}+r^{k+1}={\frac {1-r^{k+1}+r^{k+1}-r^{k+2}}{1-r}}={\frac {1-r^{k+2}}{1-r}},$$ $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every $n\geq 0$.

$\Box$

Example. (Cardinality of power set) Prove that for every set $A$ and for every integer $n\geq 0$, if $A$ is finite with $|A|=n$, then $|{\mathcal {P}}(A)|=2^{n}$.

Proof. Let $A_{n}$ be a finite set with cardinality $n$ and $P(n)$ be the open statement $|{\mathcal {P}}(A_{n})|=2^{n}$.

Basis Step: Since $A_{0}=\varnothing$, and $|{\mathcal {P}}(\varnothing )|=|\{\varnothing \}|=1=2^{0}$, $P(0)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary nonnegative integer $k$. That is, assume $|{\mathcal {P}}(A_{k})|=2^{k}$. In other words, there are $2^{k}$ subsets of $A_{k}$.

Inductive Step: First, fix an element $a\in A_{k+1}$. Now let $B=A_{k+1}\setminus \{a\}$. Then, $B$ contains $k$ elements, and thus by inductive hypothesis, there are $2^{k}$ subsets of $B$.

Let $S$ be a subset of $B$. Since $B$ is a subset of $A_{k+1}$, it follows that $S$ is a subset of $A_{k+1}$. But, $a\notin S$ since $a\notin B$. So, $S\cup \{a\}$ is also a subset of $A_{k+1}$, that is distinct from $S$. Thus, every subset $S$ of $B$ gives rise to two subsets of $A_{k+1}$, namely $S$ and $S\cup \{a\}$. As a result, there are $2^{k}$ subsets of $A_{k+1}$ without the element $a$ and $2^{k}$ subsets with the element $a$.

So, we have $2^{k}+2^{k}=2^{k+1}$ subsets of $A_{k+1}$ altogether. Hence, $|{\mathcal {P}}(A_{k+1})|=2^{k+1}$, and thus $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 0$.

$\Box$

Exercise. (Generalization of De Morgan's law) Prove that for every subset $A_{1},A_{2},\dotsc ,A_{n}$ of a universal set $U$ and for every integer $n\geq 2$, $$(A_{1}\cap A_{2}\cap \dotsb \cap A_{n})^{c}=A_{1}^{c}\cup A_{2}^{c}\cup \dotsb \cup A_{n}^{c}.$$ (Hint: you may use the ordinary De Morgan's law, i.e., for every subset $B,C$ of a universal set $U$, $(B\cap C)^{c}=B^{c}\cup C^{c}$.)

Proof. Let $P(n)$ be the open statement "$(A_{1}\cap A_{2}\cap \dotsb \cap A_{n})^{c}=A_{1}^{c}\cup A_{2}^{c}\cup \dotsb \cup A_{n}^{c}$.".

Basis Step: By the ordinary De Morgan's law, $P(2)$ is true.

Inductive Hypothesis: Assume $P(k)$ is true for an arbitrary integer $k\geq 2$. That is, assume $$(A_{1}\cap A_{2}\cap \dotsb \cap A_{k})^{c}=A_{1}^{c}\cup A_{2}^{c}\cup \dotsb \cup A_{k}^{c}.$$ Inductive Step: Since $${\begin{aligned}({\color {blue}A_{1}\cap A_{2}\cap \dotsb \cap A_{k}}\cap A_{k+1})^{c}&=({\color {blue}A_{1}\cap A_{2}\cap \dotsb \cap A_{k}})^{c}\cup A_{k+1}^{c}&({\text{ordinary De Morgan's law}})\\&=({\color {blue}A_{1}^{c}\cup A_{2}\cup \dotsb \cup A_{k}^{c}})\cup A_{k+1}^{c}&({\text{inductive hypothesis}})\\&=A_{1}^{c}\cup A_{2}\cup \dotsb \cup A_{k}^{c}\cup A_{k+1}^{c},\end{aligned}}$$ it follows that $P(k+1)$ is true. Hence, by the principle of mathematical induction, $P(n)$ is true for every integer $n\geq 2$.

$\Box$

The strong form of induction

In this section, we will discuss a stronger form of mathematical induction. Sometimes, we need this form of mathematical induction since merely assuming "$P(k)$ is true ..." in the inductive hypothesis may not be enough to show that $P(k+1)$ 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 $k$. That is, if "$m$" is 1, then we assume $P(1),\dotsc ,P(k)$ are all true.

Since "$P(1)\land P(2)\land \dotsb \land P(k)$" is stronger than "$P(k)$", we have the name "the strong form of induction".

Theorem. (The strong form of induction) For every $m\in \mathbb {Z}$, if $P(m),P(m+1),P(m+2),\dotsc$ are statements satisfying

(i) $P(m)$ is true; and

(ii) for every integer $k\geq m$, $P(m)\land P(m+1)\land \dotsb \land P(k)\implies P(k+1)$,

then the statements $P(m),P(m+1),P(m+2),\dotsc$ are true.

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

1. $P(m)$ is true by (i).
2. Because of 1., $P(m+1)$ is true by (ii).
3. Because of 1. and 2., $P(m+2)$ is true by (ii).
4. Because of 1., 2., and 3., $P(m+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 $m\in \mathbb {N}$.

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 $n$ for which $P(n)$ is false. Now, let the set $$S=\{n\in \mathbb {N} :P(n){\text{ is false}}\}.$$ Since $S$ is a nonempty subset of $\mathbb {N}$, by the well-ordering principle, $S$ contains a least element. Let us assume $s$ to be the least element.

Since $P(m)$ is true by the condition (i), $m\notin S$. This means the least element $s$ cannot be $m$. Hence, $s\geq m+1$, which means $s-1\geq m$.

Since $s$ is the least element of $S$, we have $s-1\notin S$, i.e., $P(s-1)$ is a true statement. Also, ${\color {blue}s-2,s-3,\dotsc ,m+1\notin S}$ (they are all less than ${\color {blue}s}$). Hence, ${\color {blue}P(m),P(m+1),\dotsc ,P(s-2)}$ are also true statements. Then, by the condition (ii), $P(s)$ is true (we have $s-1\geq m$). It follows that $s\notin S$. But this contradicts to our assumption that $s$ is the least element of $S$ (in particular, $s\in S$).

$\Box$

Hence, to prove that the statement $P(n)$ is true for every $n\geq m$ by the strong form of induction, we need to prove

(i) the basis step: $P(m)$ is true; and (ii) the inductive step: for every integer $k\geq m$, if $P(m),P(m+1),\dotsc ,P(k)$ are true (the inductive hypothesis), then $P(k+1)$ is true.

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

Example. A sequence $x_{1},x_{2},\dotsc$ of numbers is defined by $x_{1}=1$, $x_{2}=3$ and $$x_{n}=2x_{n-1}-x_{n-2}{\text{ for every integer }}n\geq 3$$ (an equation in such form is called a recurrence relation). Prove that $x_{n}=2n-1$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement "$x_{n}=2n-1$". Now, we will use the strong form of induction to prove that $P(n)$ is true for every $n\in \mathbb {N}$.

Basis Step: Since $x_{1}=1=2\cdot 1-1$, $P(1)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary positive integer. Assume that $P(1),\dotsc ,P(k)$ are true. That is, assume ${\color {blue}x_{i}=2i-1}$ for every integer $i$ with ${\color {blue}1\leq i\leq k}$.

Inductive Step: We want to show that $P(k+1)$ is true, i.e., $x_{k+1}=2(k+1)-1=2k+1$. Now, using the recurrence relation, we have $${\begin{aligned}x_{k+1}&=2x_{k}-x_{k-1}&({\text{only holds when }}k+1\geq 3)\\&=2(2k-1)-(2(k-1)-1)&({\text{inductive hypothesis}})\\&=2k-1.\end{aligned}}$$ So, we have proved that $P(k+1)$ is true for the case where $k+1\geq 3$. Now, it remains to prove that $P(k+1)$ is true when $k=1$, but it is easy to prove that: $x_{2}=3=2(2)-1$, so $P(2)$ is true. Hence, by the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$

Exercise. A sequence $x_{1},x_{2},\dotsc$ of numbers is defined by $x_{1}=1$, $x_{2}=4$ and $$x_{n}=2x_{n-1}-x_{n-2}+2{\text{ for every integer }}n\geq 3.$$ Guess a formula for $x_{n}$ for every $n\in \mathbb {N}$, and prove it.

Solution

When compute $x_{n}$ for $n=3,4$ according to the recurrence relation, we get $x_{3}=9$ and $x_{4}=16$. This pattern suggests us to guess that $x_{n}=n^{2}$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement "$x_{n}=n^{2}$". Now, we will use the strong form of induction to prove that $P(n)$ is true for every $n\in \mathbb {N}$.

Basis Step: Since $x_{1}=1=1^{2}$.

Inductive Hypothesis: Let $k$ be an arbitrary positive integer. Assume that $P(1),\dotsc ,P(k)$ are true.

Inductive Step: We divide our proof into two cases:

Case 1: $k=1$. Then, $x_{k+1}=x_{2}=4=2^{2}=(k+1)^{2}$. So, $P(k+1)$ is true.

Case 2: $k\geq 2$. Using recurrence relation, we have $${\begin{aligned}x_{k+1}&=2x_{k}-x_{k-1}+2\\&=2k^{2}-(k-1)^{2}+2&({\text{inductive hypothesis}})\\&=k^{2}+2k+1\\&=(k+1)^{2}.\end{aligned}}$$ Thus, $P(k+1)$ is true.

Hence, $P(n)$ is true for every $n\in \mathbb {N}$ by the strong form of induction.

$\Box$

Example. A sequence $x_{1},x_{2},\dotsc$ of numbers is defined by $x_{1}=1,x_{2}=2,x_{3}=3$ and $$x_{n}=x_{n-1}+x_{n-2}+x_{n-3}{\text{ for every integer }}n\geq 4,$$ then $x_{n}<2^{n}$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement $x_{n}<2^{n}$.

Basis Step: Since $x_{1}=1<2^{1}=2$, $P(1)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary integer. Assume $P(1),\dotsc ,P(k)$ are true.

Inductive Step:

Case 1: $k=1$. Then, $x_{k+1}=x_{2}=2<2^{k+1}=2^{2}=4$.

Case 2: $k=2$. Then, $x_{k+1}=x_{3}=3<2^{k+1}=2^{3}=8$.

Case 3: $k\geq 3$. Then, $${\begin{aligned}x_{k+1}&=2x_{k}-x_{k-1}+2\\&<2\cdot 2^{k}-2^{k-1}+2&({\text{inductive hypothesis}})\\&=2^{k+1}+(2-2^{k-1})\\&<2^{k+1}.&(2^{k-1}>2{\text{ since }}k\geq 3)\\\end{aligned}}$$ Hence, $P(k+1)$ is true.

By the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$

Remark.

• It may appear that we consider $2-2^{k-1}$ 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 $2^{k+1}-2^{k-1}+2$, which is in the form of $2^{k+1}+{\text{something}}$, to be less than $2^{k+1}$. So, it is natural consider the "something".

Exercise. Consider the sequence $F_{1},F_{2},\dotsc$ of Fibonacci numbers, defined by $F_{1}=1,F_{2}=1$ and $$F_{n}=F_{n-1}+F_{n-2}{\text{ for every integer }}n\geq 3.$$ (a) Construct a table for comparing the value of $F_{n}$ against the value of $n^{2}$ for $n=1,2,\dotsc ,15$.

(b) Hence, make a guess in the form of "$F_{n}>n^{2}$ for every integer $n\geq \;?$.", and prove the statement.

(c) By considering the even Fibonacci numbers in the table in (a), make a guess in the form of "$F_{n}$ is even if and only if $n\equiv \;?{\pmod {?}}$, for every $n\in \mathbb {N}$.", and prove the statement. (Hint: since there is "if and only if" in the statement, in the inductive step, we need to prove both "$\Rightarrow$" direction and "$\Leftarrow$" direction. But, we can prove both directions at once in this case.

(d) Prove that $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}$ for every $n\in \mathbb {N}$, where $\varphi ={\frac {1+{\sqrt {5}}}{2}}$ (golden ratio) and $\psi ={\frac {1-{\sqrt {5}}}{2}}$ (conjugate of golden ratio). This gives a direct formula to compute $n$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 $x^{2}=x+1$ are $\varphi$ and $\psi$.)

Solution

(a) $${\begin{array}{cccccccccccccccc}n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline F_{n}&1&1&2&3&5&8&13&21&34&55&89&144&233&377&610\\n^{2}&1&4&9&16&25&36&49&64&81&100&121&144&169&196&225\\\end{array}}$$ (b) From (a), it appears that when $n\geq 13$, $F_{n}$ increases faster than $n^{2}$. So, it is natural to guess that $F_{n}>n^{2}$ for every integer $n\geq 13$.

Proof. Let $P(n)$ be the open statement $F_{n}>n^{2}$.

Basis Step: Since $F_{13}=233>13^{2}=169$, $P(13)$ is true.

Inductive Hypothesis: Let $k$ be an arbitrary integer with $k\geq 13$. Assume that $P(13),P(14),\dotsc ,P(k)$ are true.

Inductive Step: Using recurrence relation, we have $${\begin{aligned}F_{k+1}&=F_{k}+F_{k-1}\\&>k^{2}+(k-1)^{2}\\&=2k^{2}-2k+1\\&=(k^{2}+2k+1)+(k^{2}-4k)\\&>k^{2}+2k+1&(k^{2}>4k{\text{ since }}k\geq 13)\\&=(k+1)^{2}.\end{aligned}}$$ Hence, $P(k+1)$ is true, and by the strong form of induction, $P(n)$ is true for every integer $n\geq 13$.

$\Box$

(c) From the table in (a), when $n=3,6,9,12,15$ (which are all multiples of 3), $F_{n}$ is even. This suggests us to guess that $F_{n}$ is even if and only if $n\equiv 0{\pmod {3}}$ for every $n\in \mathbb {N}$.

Proof. Let $P(n)$ be the open statement $F_{n}$ is even if and only if $n\equiv 0{\pmod {3}}$.

Basis Step: Since $F_{1}$ is odd and $1\not \equiv 0{\pmod {3}}$, $P(1)$ is true ($\mathbf {F} \iff \mathbf {F}$).

Inductive Hypothesis: Let $k$ be a positive arbitrary integer. Assume that $P(1),\dotsc ,P(k)$ are true.

Inductive Step: By recurrence relation, $F_{k+1}=F_{k}+F_{k-1}$. So, $${\begin{aligned}F_{k+1}{\text{ is even}}&\iff (F_{k}{\text{ is even and }}F_{k-1}{\text{ is even}}){\text{ or }}(F_{k}{\text{ is odd and }}F_{k-1}{\text{ is odd}})\\&\iff (k\equiv 0{\pmod {3}}{\text{ and }}k-1\equiv 0{\pmod {3}}){\text{ or }}(k\not \equiv 0{\pmod {3}}{\text{ and }}k-1\not \equiv 0{\pmod {3}})&({\text{inductive hypothesis}})\\&\iff (\underbrace {k\equiv 0{\pmod {3}}{\text{ and }}k\equiv 1{\pmod {3}}} _{\mathbf {F} }){\text{ or }}(k\not \equiv 0{\pmod {3}}{\text{ and }}k\not \equiv 1{\pmod {3}})\\&\iff k\equiv 2{\pmod {3}}&({\text{Euclid's division lemma}})\\&\iff k+1\equiv 3{\pmod {3}}\\&\iff k+1\equiv 0{\pmod {3}}\\\end{aligned}}$$ (We have $k-1\not \equiv 0{\pmod {3}}\iff k\not \equiv 1{\pmod {3}}$, since by the compatibility with translation, it can be shown directly that $k-1\equiv 0{\pmod {3}}\iff k\equiv 1{\pmod {3}}$, and after showing this, we have the desired logical equivalence.)

Thus, $P(k+1)$ is true. Hence, by the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$

(d)

Proof. Let $P(n)$ be the statement $F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}$.

Basis Step: Since ${\frac {\varphi -\psi }{\sqrt {5}}}={\frac {2{\sqrt {5}}/2}{\sqrt {5}}}=1=F_{1}$, $P(1)$ is true.

Inductive Hypothesis: Let $k$ be a positive arbitrary integer. Assume $P(1),\dotsc ,P(k)$ are true.

Inductive Step:

Case 1: $k=1$. Then, ${\frac {\varphi ^{k+1}-\psi ^{k+1}}{\sqrt {5}}}={\frac {\varphi ^{2}-\psi ^{2}}{\sqrt {5}}}={\frac {(\varphi -\psi )(\varphi +\psi )}{\sqrt {5}}}={\frac {(2{\sqrt {5}}/2)(2/2)}{\sqrt {5}}}=1=F_{k+1}=F_{2}$. Hence, $P(k+1)$ is true.

Case 2: $k\geq 2$. Then, apply the recurrence relation: $${\begin{aligned}F_{k+1}&=F_{k}+F_{k-1}\\&={\frac {\varphi ^{k}-\psi ^{k}}{\sqrt {5}}}+{\frac {\varphi ^{k-1}-\psi ^{k-1}}{\sqrt {5}}}&({\text{inductive hypothesis}})\\&={\frac {\varphi ^{k}+\varphi ^{k-1}-\psi ^{k}-\psi ^{k-1}}{\sqrt {5}}}\\&={\frac {\varphi ^{k-1}(\varphi +1)-\psi ^{k-1}(\psi +1)}{\sqrt {5}}}\\&={\frac {\varphi ^{k-1}\varphi ^{2}-\psi ^{k-1}\psi ^{2}}{\sqrt {5}}}&({\text{hint}})\\&={\frac {\varphi ^{k+1}-\psi ^{k+1}}{\sqrt {5}}}.\\\end{aligned}}$$ Hence, $P(k+1)$ is true.

Thus, by the strong form of induction, $P(n)$ is true for every $n\in \mathbb {N}$.

$\Box$

Relations

Introduction

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 $(a,b)$, where $a$ is the husband, while $b$ is the wife.

Expressing it mathematically, let $M$ and $W$ be the set of all men and women respectively. Then, the Cartesian product $M\times W=\{(a,b):a\in M{\text{ and }}b\in W\}$ 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, $R$, is a subset of $M\times W$. If a man and a woman form an ordered pair in $R$, say $(m,w)$, then it means they are married. Then, it is natural to say that $m$ is related to $w$. In other words, if we find that $(m,w)\in R$, then it means that they are related by this relation $R$. Also, knowing what $R$ 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 $R$ as a relation. Let us formally define relation below.

Terminologies

Definition. (Relation) A relation $R$ from a set $A$ to a set $B$ is a subset of $A\times B$, i.e., $R\subseteq A\times B$. In particular, when $A=B$, we say that $R$ is a relation on $A$, and we have $R\subseteq A\times A$. If $(a,b)\in R$, then we say that $a$ is related to $b$ by $R$, and write $aRb$. On the other hand, if $(a,b)\notin R$, then we say that $a$ is not related to $b$ by $R$, and write $a\not Rb$.

Example. Let $A=\{a,b,c\}$, $B=\{1,2,3,4\}$, and $R=\{(a,1),(b,1),(b,2),(c,3)\}$. Since the set $R$ is a subset of $A\times B$, $R$ defines a relation from set $A$ to set $B$. Also, in this relation, $a$ is related to 1, $b$ is related to 1 and 2, $c$ is related to 3. Thus, we have $aR1,bR1,bR2$ and $cR3$. But, we have, say $a\not R2$ or $d\not R4$, since $(a,2),(d,4)\notin R$.

Exercise.

(a) Suggest a set $S$ that is not a relation from set $A$ to set $B$.

(b) Suggest a set $T$ that is a relation from set $A$ to set $R$.

Solution

(a) $S=\{(a,5)\}$ ($(a,5)\notin A\times B$, so $S$ is not a subset of $A\times B$).

(b) $T=\left\{{\big (}a,(a,1){\big )}\right\}$.

Exercise. Let $A$ and $B$ be two nonempty sets. Are $\varnothing$ and $A\times B$ relations from $A$ to $B$? Describe the relationships meant by these two sets.

Solution

Both $\varnothing$ and $A\times B$ are relations from $A$ to $B$ since both are subsets of $A\times B$.

For $\varnothing$, it means nothing is related, i.e., there is no relationship between elements in $A$ and elements in $B$.

For $A\times B$, it means everything is related, i.e., every element in $A$ is related to every element in $B$.

Example. Let $H$ be a set of all human beings. Then, $R=\{(a,b):a{\text{ is the son of }}b\}$. Then, $R$ is a subset of $H\times H$, and defines the relation for son and (father or mother).

Example. The concept of "less than" defines a relation on $\mathbb {R}$. To be more precise, the relation corresponding to this concept is $R=\{(a,b):a<b\}\subseteq \mathbb {R} \times \mathbb {R} =\mathbb {R} ^{2}$. For instance, $1R2$ but $2\not R1$.

Example. The congruence of integers defines a relation on $\mathbb {Z}$. To be more precise, the corresponding relation is $R=\{(a,b):a\equiv b{\pmod {n}}\}\subseteq \mathbb {Z} \times \mathbb {Z}$ ($n\in \mathbb {N}$ with $n\geq 2$). For example, when $n=3$, then $2R5$ but $1\not R3$.

Exercise. Consider the relation on $\mathbb {R}$, corresponding the concept of "equal to": $R=\{(x,y):x=y\}\subseteq \mathbb {R} ^{2}$.

(a) Sketch $R$ in the Cartesian coordinate system.

(b) Consider also the relations $S,T$ on $\mathbb {R}$ corresponding the concept of "less than" and "greater than" respectively. Sketch also $S$ and $T$ in the graph in (a).

Solution

(a) and (b):

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

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

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

Remark.

• The sets $R,S,T$ give a partition of $\mathbb {R}$. As we will see, there is a close relationship between the concept of relation and the concept of partition.

Example. Let $A=\{1,2\}$. Define a relation on ${\mathcal {P}}(A)$, $R=\{(S,T)\in {\mathcal {P}}(A)\times {\mathcal {P}}(A):S\subseteq T\}$. Express $R$ by listing method.

Solution. First, we have ${\mathcal {P}}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$. So, $$R=\{(\varnothing ,\varnothing ),(\varnothing ,\{1\}),(\varnothing ,\{2\}),(\varnothing ,\{1,2\}),(\{1\},\{1\}),(\{1\},\{1,2\}),(\{2\},\{2\}),(\{2\},\{1,2\}),(\{1,2\},\{1,2\})\}.$$

Exercise. Let $A=\{1,2\}$ and $B=\{3,4\}$. Consider a relation $R$ on $A\times B$ defined by $$(a,b)R(c,d){\text{ if }}a+d=b+c.$$ Express $R$ by listing method.

Solution

First, $A\times B=\{(1,3),(1,4),(2,3),(2,4)\}$. So, $$R=\{{\big (}(1,3),(1,3){\big )}{\big (}(1,3),(2,4){\big )},{\big (}(1,4),(1,4){\big )},{\big (}(2,3),(2,3){\big )},{\big (}(2,4),(1,3){\big )},{\big (}(2,4),(2,4){\big )}\}.$$

Definition. (Domain and range) Let $R$ be a relation from a set $A$ to a set $B$. The domain of $R$, denoted by $\operatorname {dom} R$ is the subset of $A$ defined by $$\operatorname {dom} R=\{a\in A:(a,b)\in R{\text{ for some }}b\in B\}.$$ The range of $R$, denoted by $\operatorname {ran} R$, is the subset of $B$ defined by $$\operatorname {ran} R=\{b\in B:(a,b)\in R{\text{ for some }}a\in A\}.$$

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 $A=\{a,b,c\}$, $B=\{1,2,3,4\}$, and $R=\{(a,1),(b,1),(b,2),(c,3)\}$. Then, $\operatorname {dom} R=\{a,b,c\}=A$ and $\operatorname {ran} R=\{1,2,3\}$.

Example. Consider the relation $R$ on $\mathbb {Z}$: $R=\{(a,b):a{\text{ and }}b{\text{ are both even}}\}$. Then, $\operatorname {dom} R$ is the set of all even numbers, and $\operatorname {ran} R$ is the set of all even numbers also.

Exercise. Consider the relation $R$ on $\mathbb {Z}$: $R=\{(a,b):a{\text{ and }}b{\text{ are of different parity}}\}$. Find $\operatorname {dom} R$ and $\operatorname {ran} R$.

Solution

$\operatorname {dom} R=\mathbb {Z}$ and $\operatorname {ran} R=\mathbb {Z}$.

Definition. (Inverse relation) Let $R$ be a relation from a set $A$ to a set $B$. The inverse relation $R^{-1}$ from $B$ to $A$ is $$R^{-1}=\{(b,a):(a,b)\in R\}\subseteq B\times A.$$

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 $R$ is empty, then the inverse relation $R^{-1}$ is also empty since there is no ordered pair in the empty set.

Example. Let $A=\{a,b,c\}$, $B=\{1,2,3,4\}$, and $R=\{(a,1),(b,1),(b,2),(c,3)\}$. Then, the inverse relation $R^{-1}$ is $\{(1,a),(1,b),(2,b),(3,c)\}$.

Exercise. Construct an example of sets $A,B$ and a nonempty relation $R$ from set $A$ to set $B$ such that $R=R^{-1}$.

Solution

Take $A=B=\{1\}$, and $R=\{(1,1)\}$. Then, $R^{-1}=\{(1,1)\}=R$.

Reflexive, symmetric and transitive relations

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 $A$ be a set and $R$ be a relation defined on $A$. Then,

• $R$ is reflexive if $xRx$ for every $x\in A$.
• $R$ is symmetric if for every $x,y\in A$, $xRy\implies yRx$.
• $R$ is transitive if for every $x,y,z\in A$, $(xR{\color {darkgreen}y}{\text{ and }}{\color {darkgreen}y}Rz)\implies xRz$.

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

Solution

(i) There exists $x\in A$ such that $x\not Rx$.

(ii) There exist $x,y\in A$ such that $xRy$ but $y\not Rx$.

(iii) There exist $x,y,z\in A$ such that $xRy$ and $yRz$, but $x\not Rz$.

Example. Let $A=\{1,2\}$, and let a relation defined on $A$ be $$R=\{(1,1),(2,2),(1,2)\}.$$ Then, $R$ is reflexive since $(1,1),(2,2)\in R$. But $R$ is not symmetric since $(1,2)\in R$ but $(2,1)\notin R$.

Exercise. Is $R$ transitive? Explain why.

Solution

$R$ is transitive since

• $1R{\color {darkgreen}1}{\text{ and }}{\color {darkgreen}1}R2\implies 1R2$;
• $1R{\color {darkgreen}1}{\text{ and }}{\color {darkgreen}1}R2\implies 1R2$.

(There are no more ordered pairs $(x,{\color {darkgreen}y})$ and $({\color {darkgreen}y},z)$ in the relation $R$, satisfying $(x,y)\in R$ and $(y,z)\in R$.)

Example. The congruence of integers $$R=\{(a,b):a\equiv b{\pmod {n}}\}$$ defines a relation on $\mathbb {Z}$ ($n\in \mathbb {N}$ with $n\geq 2$). Prove that $R$ is a reflexive, symmetric and transitive.

Proof.

Reflexive: For every $x\in \mathbb {Z}$, $x\equiv x{\pmod {n}}$. So, $xRx$ for every $x\in \mathbb {Z}$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies x\equiv y{\pmod {n}}\implies x-y=kn\implies y-x=(-k)n\implies y\equiv x{\pmod {n}}\implies yRx$ where $k$ is some integer.

Transitive: For every $x,y,z\in \mathbb {Z}$, $${\begin{aligned}xRy{\text{ and }}yRz&\implies x-y=kn{\text{ and }}y-z=k'n{\text{ for some }}k,k'\in \mathbb {Z} \\&\implies x-z=(x-y)+(y-z)=(k+k')n\\&\implies xRz.&(k+k'\in \mathbb {Z} )\end{aligned}}$$

$\Box$

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

(a) $R=\{(x,y)\in \mathbb {R} ^{2}:x\leq y\}$.

(b) $R=\{(x,y)\in \mathbb {R} ^{2}:x<y\}$.

(c) $R=\{(x,y)\in \mathbb {Z} \times \mathbb {Z} :xy>0\}$.

Solution

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

Proof.

Reflexive: For every $x\in \mathbb {R}$, $x\leq x$. So, $xRx$.

Not symmetric: Take $x=1$ and $y=2$. Then, $1\leq 2$, so $xRy$. However, $2>1$. So, $y\not Rx$.

Transitive: For every $x,y,z\in \mathbb {R}$, $xRy{\text{ and }}yRz\implies x\leq y{\text{ and }}y\leq z{\text{ and }}x\leq z\implies xRz$ (this actually follows from the property of "$\leq$").

$\Box$

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

Proof.

Reflexive: Take $x=1$. Then, 1 is not less than 1 itself. Hence, $1\not R1$.

Not symmetric: Take $x=1$ and $y=2$. Then, $1<2$, so $xRy$. However, $2>1$. So, $y\not Rx$.

Transitive: For every $x,y,z\in \mathbb {R}$, $xRy{\text{ and }}yRz\implies x<y{\text{ and }}y<z{\text{ and }}x<z\implies xRz$ (this actually follows from the property of "$<$").

$\Box$

(c) $R$ is reflexive, symmetric and not transitive.

Proof.

Reflexive: For every $x\in \mathbb {Z}$,

Case 1: $x\geq 0$. Then, $x(x)\geq 0$. So, $xRx$.

Case 2: $x<0$. Then, $x(x)>0$. So, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies xy\geq 0\implies yx=xy\geq 0\implies yRx$.

Not transitive: Take $x=1,y=0$ and $z=-1$. Then, $xy=0$ and $yz=0$. So, $xRy$ and $yRz$. However, since $xy=-1<0$, $x\not Rz$.

$\Box$

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

(a) if $R$ is reflexive, then $R^{-1}$ is reflexive;

(b) if $R$ is symmetric, then $R^{-1}$ is symmetric;

(c) if $R$ is transitive, then $R^{-1}$ is transitive.

Equivalence relations and equivalence classes

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 $A$ be a set. A relation $R$ defined on $A$ 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 $A=\{1,2\}$. Also let a relation defined on $A$ be $$R=\{(1,1),(2,2),(1,2),(2,1)\}.$$ Prove or disprove that $R$ is an equivalence relation.

Proof.

Reflexive: Since $(1,1),(2,2)\in R$, $R$ is reflexive.

Symmetric: Since $(1,1)\in R\implies (1,1)\in R$, $(2,2)\in R\implies (2,2)\in R$, $(1,2)\in R\implies (2,1)\in R$, and $(2,1)\in R\implies (1,2)\in R$, $R$ is symmetric.

Transitive: Since for every $x,y,z\in A$, $xRy{\text{ and }}yRz\implies xRz$, $R$ is transitive.

$\Box$

Exercise. Give another equivalence relation that is defined on $A$.

Solution

$R=\{(1,1),(2,2)\}$. 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 $\mathbb {Z}$.

Suppose $R$ is an equivalence relation on a set $A$. Intuitively, for elements that are related by $R$, 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 $A$ 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 $R$ be an equivalence relation defined on a set $A$. For every $a\in A$, the set $$[a]=\{x\in A:xRa\}$$ consisting of all elements in $A$ that are related to $a$, is called an (equivalence) class of $a$ by $R$.

Example. Let $A=\{1,2,3,4\}$, and let a relation defined on $A$ be $$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,1),(3,1),(2,3),(3,2)\}.$$ This relation $R$ can be shown to be an equivalence relation. The equivalence classes are given by $$[1]=\{1,2,3\},[2]=\{1,2,3\},[3]=\{1,2,3\},[4]=\{4\}.$$ Since $[1]=[2]=[3]$, there are only two distinct equivalence classes. Graphically, the situation looks like:

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

Exercise. Construct an equivalence relation $R$ on $A$ such that the equivalence classes are given by $$[1]=\{1,2\},[2]=\{1,2\},[3]=\{3,4\},[4]=\{3,4\}.$$

Solution

$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)$. Graphically, the situation looks like:

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

Example. (Integers modulo $n$) Recall that the congruence of integers defines an equivalence relation $R$ on $\mathbb {Z}$. Using this equivalence relation, we can define the equivalence class $[a]$ for every $a\in \mathbb {Z}$, as follows:

• $$[0]=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {n}}\}=\{\dotsc ,-2n,-n,0,n,2n,\dotsc \}$$
• $$[1]=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {n}}\}=\{\dotsc ,-2n+1,-n+1,1,n+1,2n+1,\dotsc \}$$
• ...
• $$[n-1]=\{x\in \mathbb {Z} :xR(n-1)\}=\{x\in \mathbb {Z} :x\equiv n-1{\pmod {n}}\}=\{\dotsc ,-2n+(n-1),-n+(n-1),n-1,n+(n-1),2n+(n-1),\dotsc \}=\{\dotsc ,-2n-1,-n-1,-1,2n-1,\dotsc \}$$
• $$[n]=\{x\in \mathbb {Z} :xRn\}=\{x\in \mathbb {Z} :x\equiv n{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {n}}\}=[0]$$
• $$[n+1]=\{x\in \mathbb {Z} :xR(n+1)\}=\{x\in \mathbb {Z} :x\equiv n+1{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {n}}\}=[1]$$

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

• $[-1]=\{x\in \mathbb {Z} :xR(-1)\}=\{x\in \mathbb {Z} :x\equiv -1{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv n-1{\pmod {n}}\}=[n-1]$
• $[-2]=\{x\in \mathbb {Z} :xR(-2)\}=\{x\in \mathbb {Z} :x\equiv -2{\pmod {n}}\}=\{x\in \mathbb {Z} :x\equiv n-2{\pmod {n}}\}=[n-2]$
• ...

They also do not give new classes.

Hence, we conclude that there are only $n$ distinct equivalence classes, namely $[0],[1],\dotsc ,[n-1]$. Usually, the set of these equivalence classes, $\{[0],[1],\dotsc ,[n-1]\}$, is denoted by $\mathbb {Z} _{n}$, and is called integers modulo $n$. Notice that $\mathbb {Z} _{n}$ 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 $\mathbb {Z}$):

*----*----*---...---*-----*
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
|-n  |-n+1|         |-2n-1|
| 0  | 1  |  ....   | n-1 |
| n  |n+1 |         |2n-1 |
| .  |    |         |  .  |
| .  |    |         |  .  |
| .  |    |         |  .  |
*----*----*---...---*-----*

• When we consider integers modulo $m$ and integers modulo $n$ ($m\neq n$) together, there may be some ambiguities for the elements. For example, $\mathbb {Z} _{2}=\{[0],[1]\}$ and $\mathbb {Z} _{3}=\{[0],[1],[2]\}$. However, for instance, the "$[0]$" in $\mathbb {Z} _{2}$ and the "$[0]$" in $\mathbb {Z} _{3}$ 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 $\mathbb {Z} _{2}=\{[0]_{2},[1]_{2}\}$ and $\mathbb {Z} _{3}=\{[0]_{3},[1]_{3},[2]_{3}\}$.

Exercise. A relation $R$ on $\mathbb {Z}$ is defined by $$aRb{\text{ if }}3a+b\equiv 0{\pmod {4}}.$$ (a) Prove that $R$ is an equivalence relation.

(b) Express each of the equivalence classes by $R$ $[0]_{R},[1]_{R},[2]_{R},[3]_{R}$ in terms of $[0]_{4},[1]_{4},[2]_{4},[3]_{4}$ (Hint: use the symmetric property of $R$).

Solution

(a)

Proof.

Reflexive: For every $x\in \mathbb {Z}$, since $3x+x=4x\equiv 0{\pmod {4}}$, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, since $xRy\implies 3x+y\equiv 0{\pmod {4}}\implies 9x+3y\equiv 0{\pmod {4}}\implies 9x-8x+3y\equiv \underbrace {-8x} _{\text{multiple of 4}}\equiv 0{\pmod {4}}\implies yRx$.

Transitive: For every $x,y,z\in \mathbb {Z}$, $${\begin{aligned}xRy{\text{ and }}yRz&\implies 3x+y\equiv 0{\pmod {4}}{\text{ and }}3y+z\equiv 0{\pmod {4}}\\&\implies (3x+y)+(3y+z)\equiv 0{\pmod {4}}\\&\implies 3x+z+4y\equiv 0{\pmod {4}}\\&\implies 3x+z\equiv -4y\equiv 0{\pmod {4}}\\&\implies xRz.\end{aligned}}$$

$\Box$

(b) $$[0]_{R}=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :0Rx\}=\{x\in \mathbb {Z} :x\equiv 0{\pmod {4}}\}=[0]_{4}.$$ (By the symmetric property of $R$, $xR0\implies 0Rx$. Also, $0Rx\implies xR0$. So, $xR0\iff 0Rx$.) $$[1]_{R}=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :1Rx\}=\{x\in \mathbb {Z} :3+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :4+x\equiv 1{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 1{\pmod {4}}\}=[1]_{4}.$$ $$[2]_{R}=\{x\in \mathbb {Z} :xR2\}=\{x\in \mathbb {Z} :2Rx\}=\{x\in \mathbb {Z} :6+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :8+x\equiv 2{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 2{\pmod {4}}\}=[2]_{4}.$$ $$[3]_{R}=\{x\in \mathbb {Z} :xR3\}=\{x\in \mathbb {Z} :3Rx\}=\{x\in \mathbb {Z} :9+x\equiv 0{\pmod {4}}\}=\{x\in \mathbb {Z} :12+x\equiv 3{\pmod {4}}\}=\{x\in \mathbb {Z} :x\equiv 3{\pmod {4}}\}=[3]_{4}.$$

Properties of equivalence classes

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 $R$ be an equivalence relation defined on a set $A$. For every $a,b\in A$, $$[a]=[b]{\text{ if and only if }}aRb.$$

Proof. "$\Rightarrow$" direction: Assume $[a]=[b]$. Since $R$ is an equivalence relation, and in particular, is reflexive, we have $aRa$. Thus, we have by definition $a\in [a]$. Then, since $[a]=[b]$ by assumption, we have $a\in [b]$.

"$\Leftarrow$" direction: Assume $aRb$. First, for every $x\in A$, $${\begin{aligned}x\in [a]&\implies xRa&({\text{definition}})\\&\implies xRb&(aRb{\text{ and }}{\text{transitivity of }}R)\\&\implies x\in [b].&({\text{definition}})\\\end{aligned}}$$ So, $[a]\subseteq [b]$.

On the other hand, first, since $aRb$ by assumption, we have $bRa$ by the symmetry of $R$. Now, For every $y\in A$, $${\begin{aligned}y\in [b]&\implies yRb&({\text{definition}})\\&\implies yRa&(bRa{\text{ and transitivity of }}R)\\&\implies y\in [a].&({\text{definition}})\\\end{aligned}}$$ So, $[b]\subseteq [a]$.

Hence, $[a]=[b]$.

$\Box$

Remark.

• From this theorem, we know that "$aRb$" is the necessary and sufficient condition for "$[a]=[b]$". Also, we have $[a]\neq [b]$ if and only if $a\not Rb$.

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

Corollary. Let $R$ be an equivalence relation defined on a nonempty set $A$. For every $a,b\in A$, $$[a]\neq [b]{\text{ if and only if }}[a]\cap [b]=\varnothing .$$

Proof. "$\Leftarrow$" direction: $${\begin{aligned}{}[a]\cap [b]=\varnothing &\implies [a]{\text{ and }}[b]{\text{ have distinct elements}}&([a]{\text{ and }}[b]{\text{ are nonempty}})\\&\implies [a]\neq [b].\end{aligned}}$$ ($[a]$ and $[b]$ are nonempty since $R$ is reflexive. So they must contain, at least, $a$ and $b$ respectively.)

"$\Rightarrow$" direction: We use proof by contrapositive. $${\begin{aligned}{}[a]\cap [b]\neq \varnothing &\implies \exists x\in [a]\cap [b]\\&\implies xRa{\text{ and }}xRb\\&\implies aRx{\text{ and }}xRb&(R{\text{ is symmetric}})\\&\implies aRb&(R{\text{ is transitive}})\\&\implies [a]=[b].&({\text{above theorem}})\\\end{aligned}}$$

$\Box$

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 $A$ is a set of nonempty subset(s) of $A$ with the property that every element of $A$ belongs to exactly one of the subset(s). In other words, $P$ is a collection of pairwise disjoint and nonempty subset(s) of $A$ whose union is $A$.

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

Exercise. Is $\{\{1,2,3\}\}$ a partition of $A$?

Solution

Yes, since every element of $A$ belongs to exactly one of the set inside the partition, namely the set $\{1,2,3\}$.

Example. Let $A=\{1,2,3,4\}$, and let a relation defined on $A$ be $$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(1,3),(2,1),(3,1),(2,3),(3,2)\}.$$ Recall that the two distinct equivalence classes are given by $$[1]=\{1,2,3\},[4]=\{4\}.$$ We can see that every element of $A$ belongs to exactly one of these equivalence classes. Hence, the set $\{[1],[4]\}=\{\{1,2,3\},\{4\}\}$ gives a partition of $A$.

Also, we can define another equivalence relation $R$ on $A$ such that the two distinct equivalence classes are given by $$[1]=\{1,2\},[3]=\{3,4\}.$$ We can also see that every element of $A$ belongs to exactly one of these equivalence classes. hence, the set $\{[1],[3]\}=\{\{1,2\},\{3,4\}\}$.

Example. Recall that the congruence of integers defines an equivalence relation $R$ on $\mathbb {Z}$. Also, there are $n$ distinct equivalence classes: $[0],[1],\dotsc ,[n-1]$. By Euclid's division lemma, every integer belongs to exactly one of these $n$ equivalence classes. Thus, the integers modulo $n$ $$\mathbb {Z} _{n}=\{[0],[1],\dotsc ,[n-1]\}$$ gives a partition on $\mathbb {Z}$.

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 $A$ can be used to give a partition of that set.

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

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

For every $x\in A$, since $R$ is reflexive, we have $x\in [x]$. From this, we can ensure that every element of $A$ belongs to at least one of the distinct classes. It now remains to show that every element of $A$ also belongs to at most one of the distinct classes.

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

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

$\Box$

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 $P$ be a partition of a nonempty set $A$. Define a relation $R$ on $A$ by $$xRy{\text{ if there exists }}S\in P{\text{ such that }}x,y\in S.$$ Then, the relation $R$ is an equivalence relation on the set $A$.

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

Reflexive: By the definition of partition, for every $x\in A$, $x$ belongs to exactly one of $S\in P$, so there exists $S\in P$ such that $x\in S$. Hence, $xRx$.

Symmetric: For every $x,y\in A$, $${\begin{aligned}xRy&\implies \exists S\in P,x,y\in S\\&\implies \exists S\in P,y,x\in S\\&\implies yRx.\end{aligned}}$$ Transitive: For every $x,y,z\in A$, assume $xRy$ and $yRz$. Then, there exist $S,T\in P$ such that $x,{\color {blue}y\in S}$ and ${\color {blue}y},z{\color {blue}\in T}$. But by the definition of partition, $y$ belongs to exactly one of the set in the partition $P$. So, we have $S=T$. Hence, there exists a set $S$ ($=T$) such that $x,z\in S$, and thus $xRz$.

$\Box$

Example. Let $R$ be a relation defined on $\mathbb {Z}$ by $$aRb{\text{ if }}|a|=|b|.$$

(a) Prove that $R$ is an equivalence relation.

(b) Determine all distinct equivalence classes by $R$ and hence give a partition on $\mathbb {Z}$.

Solution.

(a)

Proof. Reflexive: For every $x\in \mathbb {Z}$, $|x|=|x|$. So, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies |x|=|y|\implies |y|=|x|\implies yRx$.

Transitive: For every $x,y,z\in \mathbb {Z}$, $xRy{\text{ and }}yRz\implies |x|=|y|{\text{ and }}|y|=|z|\implies |x|=|z|\implies xRz$.

$\Box$

(b) First, some equivalence classes are $${\begin{aligned}{}[0]&=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :|x|=0\}=\{0\},\\{}[1]&=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :|x|=1\}=\{-1,1\},\\{}[2]&=\{x\in \mathbb {Z} :xR2\}=\{x\in \mathbb {Z} :|x|=2\}=\{-2,2\},\dotsc \\\end{aligned}}$$ So, all distinct equivalence classes are $[0],[1],[2],\dotsc$ ($-1\in [1]$, so $[-1]$ is not distinct from them, etc.). Hence, a partition on $A$ is $$\{[0],[1],[2],\dotsc \}=\{[n]:n{\text{ is a nonnegative integer}}\}$$ (that is, every integer belongs to exactly one of $[0],[1],[2],\dotsc$.)

Exercise. Let $R$ be a relation defined on $\mathbb {Z}$ by $$aRb{\text{ if }}a+b{\text{ is even}}.$$

(a) Prove that $R$ is an equivalence relation.

(b) Determine all distinct equivalence classes by $R$, and hence give a partition on $\mathbb {Z}$.

Solution

(a)

Proof. Reflexive: For every $x\in \mathbb {Z}$, since $x+x=2x$ is even, $xRx$.

Symmetric: For every $x,y\in \mathbb {Z}$, $xRy\implies x+y{\text{ is even}}\implies y+x=x+y{\text{ is even}}\implies yRx$.

Transitive: For every $x,y,z\in \mathbb {Z}$, $${\begin{aligned}xRy{\text{ and }}yRz&\implies x+y{\text{ is even}}{\text{ and }}y+z{\text{ is even}}\\&\implies (x+y)+(y+z)=x+2y+z{\text{ is even}}\\&\implies x+2y+z-2y{\text{ is even}}&(-2y{\text{ is even}})\\&\implies x+z{\text{ is even}}\\&\implies xRz.\\\end{aligned}}$$

$\Box$

(b) First, some equivalence classes are $${\begin{aligned}{}[0]_{R}&=\{x\in \mathbb {Z} :xR0\}=\{x\in \mathbb {Z} :x{\text{ is even}}\}=[0]_{2},\\{}[1]_{R}&=\{x\in \mathbb {Z} :xR1\}=\{x\in \mathbb {Z} :x+1{\text{ is even}}\}=\{x\in \mathbb {Z} :x{\text{ is odd}}\}=[1]_{2}.\\\end{aligned}}$$ Since every integer belongs to exactly one of $[0]_{2}$ and $[1]_{2}$ (i.e., all other equivalence classes are not distinct from them), it follows that $[0]_{R}$ and $[1]_{R}$ 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 $R$ can partition the integers into two "pieces": set of all odd integers and set of all even integers.

Functions

Introduction

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 $A$ to set $B$, every element of $A$ can be related to no elements of $B$, exactly one element of $B$, or multiple elements of $B$. In this chapter, we will focus on a particular type of relations from set $A$ to set $B$ where every element in $A$ is related to exactly one (or a unique) element of $B$.

You should have encountered the concept of functions before, e.g. a function defined by $f(x)=x^{2}$ gives you a value of $f(x)$ for every given value of $x$. 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 $x$ and $f(x)$ are likely to be real numbers.

But we can generalize such ideas to more general situations where $x$ and $f(x)$ 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

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

Remark.

• The notation "$(a,b)\in f$" may seem weird at the first place. However, when we think about what $f$ represents here, it becomes more natural: since $f$ is a relation from set $A$ to set $B$, it is indeed a subset of $A\times B$. So, it makes sense to say $(a,b)$ is an element of $f$.

• However, it is much more common to write $f(a)=b$ instead (and you should have seen this notation before).

• Since $f$ is a relation, we can apply the terminologies to functions: the set $A$ is the domain of function $f$, denoted by $\operatorname {dom} f$.
• We also have some more terminologies for functions: The set $B$ is called the codomain of $f$, $b=f(a)$ is the image of $a$ under $f$. Also, $a$ is referred to as the pre-image of $b$ under $f$. Furthermore, we say that $f$ maps $a$ into $b$.

• From the definition, every element $a\in A$ has a unique (or exactly one) image.

• When the set $A$ is empty, then the only function (and also the only relation) from set $A$ to $B$ is the empty set. When set $A$ is nonempty while the set $B$ is empty, since the only relation from set $A$ to $B$ is also the empty set, but such relation does not satisfy the requirements to be a function (there does not exist $b\in B$ such that $(a,b)\in f$ for every $a\in A$).

Exercise. Write down the meaning of "$f$ is not a function from $A$ to $B$", 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 "$f$ is a function from $A$ to $B$" using logical notations: $${\big (}\forall a\in A,\exists b\in B,f(a)=b{\big )}{\text{ and }}{\big (}\forall a\in A,\forall b,c\in B,{\text{if }}f(a)=b{\text{ and }}f(a)=c,{\text{ then }}b=c{\big )}.$$ Then, the meaning of "$f$ is not a function from $A$ to $B$" is: $${\big (}\exists a\in A,\forall b\in B,f(a)\neq b{\big )}{\text{ or }}{\big (}\exists a\in A,\exists b,c\in B,f(a)=b{\text{ and }}f(a)=c{\text{ and }}b\neq c{\big )}.$$ (LHS means the existential requirement is violated, and RHS means the uniqueness requirement is violated.) In other words, the meaning is "there exists some $a\in A$ with no image, OR there exists some $a\in A$ with more than one image".

Example. Let $A=\{1,2,3\}$ and $B=\{a,b\}$. Then, $$f=\{(1,a),(2,a),(3,b)\}$$ defines a function. Graphically, it looks like

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

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

Example. Let $A=\{a,b,c,d\}$ and $B=\{1,2,3,4,5,6\}$. Then, $f=\{(a,1),(a,2),(b,3),(c,4),(d,5)\}$ is not a function from $A$ to $B$ since $a$ has two images: 1 and 2. Also, $f=\{(a,1),(b,3)\}$ is not a function from $A$ to $B$ since $c$ and $d$ have no image.

Example. It is quite common to refer, say, "$f(x)=x^{2}$" 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. $f(x)$ is just an image of a real number $x$ under $f$. The function $f$ itself should be a set.

For the first question, usually the domain and codomain are taken to be $\mathbb {R}$. But for some functions, $f(x)$ becomes undefined for some values of real number $x$. In this case, it is common to set the domain as $\{x:f(x){\text{ is a real number}}\}$, which is referred to as the natural domain.

For the second question, the actual function $f$ is indeed the set $$f=\{(x,x^{2}):x\in \mathbb {R} \}.$$ This set of point in the plane is the graph of $f$ (a parabola). However, it is acceptable to have such saying for convenience.

Exercise. A commonly encountered function is the exponential function, which is defined by $g(x)=e^{x}$. Another one is the natural logarithm function defined by $h(x)=\ln x$.

(a) Find the domain and codomain of the functions $g$ and $h$.

(b) Express the functions $g$ and $h$ using sets.

Solution

(a) The domain and codomain of $g$ are both $\mathbb {R}$. The domain of $h$ is $(0,\infty )$ (when $x$ is less than or equal to zero, $\ln x$ is undefined), and the codomain of $h$ is $\mathbb {R}$.

(b) $g=\{(x,e^{x}):x\in \mathbb {R} \}$ and $h=\{(x,\ln x):x\in (0,\infty )\}$.

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 $f$, denoted by $\operatorname {ran} f$, is $$\operatorname {ran} f=\{b\in B:b=f(x){\text{ for some }}x\in A\}=\{f(x):x\in A\}\subseteq B.$$

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 $a\in A$ can be possibly mapped.
• When the range and the codomain of a function $f$ turn out to be the same, we call such function $f$ 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 $A=\{1,2\}$ and $B=\{3,4,5\}$. Define the function $f$ by $$f=\{(1,3),(2,4)\}.$$ Then, $\operatorname {ran} f=\{3,4\}.$

Exercise. Let $A$ and $B$ be sets, and $b$ be a fixed element of $B$. Then, the function $f:A\to B$ defined by $f(a)=b$ for every $a\in A$ is called the constant function from $A$ to $B$.

(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 $b$?

Solution

(a) The range is $\{b\}$.

(b) The codomain is the set $B$.

(c) Yes, if $B=\{b\}$.

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

Example. (Identity function) Let $A$ be a set. Then the function $id_{A}$ defined by $id_{A}(a)=a$ for every $a\in A$ is called the identity function of $A$. Every $a\in A$ is the image of itself. The domain, codomain, and range of $id_{A}$ are all $A$.

Remark.

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

Example. Consider the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=e^{x}$. Find the range of the function $f$, $\operatorname {ran} f$, and prove your answer.

The range of the function $f$ is $\operatorname {ran} f=(0,\infty )$.

Proof. To prove that $\operatorname {ran} f=(0,\infty )$, we will prove (i) $\operatorname {ran} f\subseteq [0,\infty )$; (ii) $[0,\infty )\subseteq \operatorname {ran} f$.

Firstly, for $\operatorname {ran} f\subseteq (0,\infty )$: for every $y$, $${\begin{aligned}y\in \operatorname {ran} f&\implies y=e^{x}{\text{ for some }}x\in \mathbb {R} \\&\implies y>0&({\text{we do not have the reverse implication for this step}})\\&\implies y\in (0,\infty ).\end{aligned}}$$ On the other hand, for $(0,\infty )\subseteq \operatorname {ran} f$: for every $y\in (0,\infty )$, we choose $x=\ln y\in \mathbb {R}$. Then, $f(x)=e^{x}=e^{\ln y}=y$. So, by definition, we have $y\in \operatorname {ran} f$.

$\Box$

Exercise. Consider the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=x^{2}$. Find $\operatorname {ran} f$, and prove your answer.

Solution

We have $\operatorname {ran} f=[0,\infty )$.

Proof. First, for every $y$, $${\begin{aligned}y\in \operatorname {ran} f&\implies y=x^{2}{\text{ for some }}x\in \mathbb {R} \\&\implies y\geq 0\\&\implies y\in [0,\infty ).\end{aligned}}$$ This shows that $\operatorname {ran} f\subseteq [0,\infty )$.

On the other hand, for every $y\in [0,\infty )$, we choose $x={\sqrt {y}}\in \mathbb {R}$. Then, $f(x)=x^{2}=\left({\sqrt {y}}\right)^{2}=y$ . So, we have $y\in \operatorname {ran} f$. This shows that $[0,\infty )\subseteq \operatorname {ran} f$, and we are done.

$\Box$

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 $A$ and $B$ be sets, and let $f:A\to B$ and $g:A\to B$ be two functions from $A$ to $B$ (notice that their domains and codomains have to be the same). Then, the functions $f$ and $g$ are said to be equal, written $f=g$, if $f(a)=g(a)$ for every $a\in A$.

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

Solution

($f$ and $g$ have different domain) or ($f$ and $g$ have different codomain) or (there exists $a\in A$ such that $f(a)\neq g(a)$).

Example. Consider the functions $f:\mathbb {R} \to \mathbb {R}$ and $g:\mathbb {R} \to (0,\infty )$ defined by $f(x)=e^{x}$ and $g(x)=e^{x}$. Although their "formulas" are the same, they are not equal since their codomains are different.

Exercise. Consider the functions $f$ and $g$ defined by $f(x)=x$ and $g(x)={\frac {x^{2}}{x}}$. Are the functions $f$ and $g$ equal? Why?

Solution

No.

Notice hat $g(x)$ is undefined when $x=0$ (and defined for every other real number $x$), while $f(x)$ is defined for every real number $x$. Thus, the domain of $f$ is $\mathbb {R}$ and the domain of $g$ is $\mathbb {R} \setminus \{0\}$. So, $f$ and $g$ are not equal.

Injective, surjective and bijective functions

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

Definition. (Injective function) A function $f:A\to B$ is injective or one-to-one if for every $x,y\in A$, $f(x)=f(y)\implies x=y$, or equivalently (contrapositive), for every $x,y\in A$, $x\neq y\implies f(x)\neq f(y)$.

Remark.

• The definition tells us that an injective function from $A$ to $B$ maps distinct elements of $A$ into distinct elements of $B$.
• To prove that a function is injective, it is common to use a direct proof: for every $x,y\in A$, assume $f(x)=f(y)$, and then proceed to prove that $x=y$.

Exercise. Write down the meaning of "a function $f:A\to B$ is not injective".

Solution

There exist $x,y\in A$ such that $f(x)=f(y)$ and $x\neq y$.

Example. A function $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=2x+5$. Prove that $f$ is injective.

Proof. For every $x,y\in \mathbb {R}$, $$f(x)=f(y)\implies 2x+5=2y+5\implies 2x=2y\implies x=y.$$ Thus, $f$ is injective.

$\Box$

Example. A function $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=x^{2}$. Prove or disprove that $f$ is injective.

Disproof. Since $f(-1)=f(1)=1$, $f$ is not injective.

$\Box$

Exercise. A function $g:[0,\infty )\to \mathbb {R}$ is defined by $g(x)=x^{2}$. Prove that $g$ is injective.

Proof

Proof. For every $x,y\in [0,\infty )$, $$g(x)=g(y)\implies x^{2}=y^{2}\implies {\sqrt {x^{2}}}={\sqrt {y^{2}}}\implies |x|=|y|\implies x=y.$$

$\Box$

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 $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=x^{2}-3x+5$. Prove or disprove that $f$ 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 $f$ is injective, and see what we get: for every $x,y\in \mathbb {R}$, $$f(x)=f(y)\implies x^{2}-3x+5=y^{2}-3y+5\implies x(x-3)=y(y-3).$$ Notice that for the last equation to imply $x=y$, we need $x\neq 3$ and $y\neq 3$. However, $x$ and $y$ can take any real values. Hence, this suggests us to consider $f(3)$ and disprove that $f$ is injective. Another observation is that when $x=3$, then $x(x-3)=0$. But to make it equal zero, we can also take $x=0$. Thus, this gives us a counterexample for disproving that $f$ is injective:

Disproof. Since $f(0)=f(3)=5$, $f$ is not injective.

$\Box$

Exercise. A function $f:[-1,1]\to [0,1]$ is defined by $f(x)={\sqrt {1-x^{2}}}$. Prove or disprove that $f$ is injective.

Solution

Disproof. Since $f(-1)=f(1)=0$, $f$ is not injective.

$\Box$

Remark.

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

Definition. (Surjective function) A function $f:A\to B$ is surjective or onto if for every $y\in B$, there exists $x\in A$ such that $f(x)=y$.

Remark.

• The definition tells us that $f$ is surjective if every element of the codomain $B$ is the image of some element of $A$. In other words, $\operatorname {ran} f=B$.

Exercise. Write down the meaning of "$f:A\to B$ is not surjective".

Solution

There exists $y\in B$ such that for every $x\in A$, $f(x)\neq y$.

In other words, some element of the codomain $B$ is not the image of every element of $A$. In other words, $\operatorname {ran} f\neq B$ (since $\operatorname {ran} f\subseteq B$ by definition, we may also write this as $\operatorname {ran} f\subset B$).

Example. A function $f:\mathbb {R} \to \mathbb {R}$ is defined by $f(x)=2x+5$. Prove that $f$ is surjective.

To prove that $f$ is surjective, we need to prove that for every $y\in \mathbb {R}$, there exists $x\in \mathbb {R}$ such that $f(x)=y$, i.e., $y=2x+5$. To show this, we can see that the choices of $x\in \mathbb {R}$ to satisfy the requirement for different values of $y$ are different. Indeed, the choice of $x$ depend on the value of $y\in \mathbb {R}$. But it is not hard to choose such $x\in \mathbb {R}$ with a given value of $y\in \mathbb {R}$: we can just rearrange the above equation to make $x$ to be the subject of the equation: $$x={\frac {y-5}{2}}\in \mathbb {R}$$

Proof. For every $y\in \mathbb {R}$, choose $x={\frac {y-5}{2}}\in \mathbb {R}$. Then, $$f(x)=f\left({\frac {y-5}{2}}\right)=2\left({\frac {y-5}{2}}\right)+5=y-5+5=y.$$

$\Box$

Example. Prove or disprove that the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=x^{2}$ is surjective.

Disproof. Take $y=-1$. Then, there is no $x\in \mathbb {R}$ such that $$x^{2}=f(x)=-1$$ since $x^{2}=-1$ has no real solution. Hence, $f$ is not surjective.

$\Box$

Exercise. Prove that the function $g:\mathbb {R} \to [0,\infty )$ defined by $g(x)=x^{2}$ is surjective.

Proof

Proof. For every $y\in [0,\infty )$, choose $x={\sqrt {y}}\in \mathbb {R}$ (it is possible to choose such real number $x$ since $y\in [0,\infty )$). Then, $$f(x)=f\left({\sqrt {y}}\right)=\left({\sqrt {y}}\right)^{2}=y$$

$\Box$

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 $f:A\to B$ 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, $f$ is bijective if for every $y\in B$, there exists a unique $x\in A$ such that $f(x)=y$ (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.

Exercise. Write down the meaning of "$f:A\to B$ is not bijective".

Solution

$f$ is not injective or $f$ is not surjective.

Example. We have proved the function $f:\mathbb {R} \to \mathbb {R}$ defined by $f(x)=2x+5$ is both injective and surjective. Hence, it is bijective.

Example. We have proved the function $g_{1}:[0,\infty )\to \mathbb {R}$ defined by $g_{1}(x)=x^{2}$ is injective and the function $g_{2}:\mathbb {R} \to [0,\infty )$ defined by $g_{2}(x)=x^{2}$ is surjective. Then, with basically the same proof, we can prove that the function $g_{3}:[0,\infty \to [0,\infty )$ defined by $g_{3}(x)=x^{2}$ is both injective or surjective, and hence bijective.

Example. Prove that the function $f:\mathbb {R} \setminus \{1\}\to \mathbb {R} \setminus \{3\}$ defined by $f(x)={\frac {3x+1}{x-1}}$ is bijective.

For proving the surjective part, we need to make $x$ as the subject for the equaton $y={\frac {3x+1}{x-1}}$: $$y={\frac {3x+1}{x-1}}\iff xy-y=3x+1\iff (y-3)x=y+1\iff x={\frac {y+1}{y-3}}.$$

Proof.

Injective: For every $x,y\in \mathbb {R} \setminus \{1\}$, $$f(x)=f(y)\implies {\frac {3x+1}{x-1}}={\frac {3y+1}{y-1}}\implies 3x+1=3y+1\implies 3x=3y\implies x=y.$$ Surjective: For every $y\in \mathbb {R} \setminus \{3\}$, choose $x={\frac {y+1}{y-3}}$. We then need to show that $x\in \mathbb {R} \setminus \{1\}$. Since $x\in \mathbb {R}$ ($y\neq 3$, so $x$ is defined), it suffices to show that $x\neq 1$. Let us prove it by contradiction:

Assume to the contrary that $x=1$. Then, ${\frac {y+1}{y-3}}=1\implies y+1=y-3\implies 1=-3$. So we arrive at a contradiction.

Then, we have $$f(x)=f\left({\frac {y+1}{y-3}}\right)={\frac {3\left({\frac {y+1}{y-3}}\right)+1}{{\frac {y+1}{y-3}}-1}}={\frac {3y+3+y-3}{y+1-y+3}}={\frac {4y}{4}}=y.$$

$\Box$

Exercise. Let $A$ be a set. Prove that the identity function $id_{A}:A\to A$ is bijective.

Proof

Proof.

Injective: For every $x,y\in A$, $id_{A}(x)=id_{A}(y)\implies x=y$.

Surjective: For every $y\in A$, choose $x=y\in A$. Then, $id_{A}(x)=id_{A}(y)=y$.

$\Box$

Exercise. A function $f:\mathbb {Z} \times \mathbb {Z} \to \mathbb {Z} \times \mathbb {Z}$ is defined by $$f(m,n)=(n,m).$$ Prove or disprove that $f$ is bijective.

Solution

Proof.

Injective: For every $(m_{1},n_{1}),(m_{2},n_{2})\in \mathbb {Z} \times \mathbb {Z}$, $$f(m_{1},n_{1})=f(m_{2},n_{2})\implies (n_{1},m_{1})=(n_{2},m_{2})\implies n_{1}=n_{2}{\text{ and }}m_{1}=m_{2}\implies (m_{1},n_{1})=(m_{2},n_{2}).$$

Surjective: For every $(x,y)\in \mathbb {Z} \times \mathbb {Z}$, choose $(y,x)\in \mathbb {Z} \times \mathbb {Z}$. Then, $$f(y,x)=(x,y).$$

$\Box$

Exercise. Consider a function $f:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ defined by $f(m,n)=m+n$, and another function $g:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ defined by $g(m,n)=mn$.

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

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

Solution

(a) (i)

Disproof. Since $f(1,2)=f(2,1)=3$, $f$ is not injective.

$\Box$

(ii)

Disproof. Take $y=1$. Then, for every $(m,n)\in \mathbb {N} \times \mathbb {N}$, $m+n\neq y=1$.

$\Box$

(b) (i)

Disproof. Since $f(1,2)=f(2,1)=2$, $f$ is not injective.

$\Box$

(ii)

Proof. For every $y\in \mathbb {N}$, choose $(m,n)=(1,y)\in \mathbb {N} \times \mathbb {N}$. Then, $f(m,n)=1(y)=y$.

$\Box$

Composition of functions

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

Definition. (Composition) Let $f:A\to B$ and $g:B\to C$ be two functions, where $A,B$ and $C$ are nonempty sets. Then, the composition of $f$ and $g$, denoted by $g\circ f$ (read "g-circle-f"), is the function from $A$ to $C$ defined by $$(g\circ f)(a)=g(f(a)){\text{ for every }}a\in A.$$

Remark.

• We can see that the composition $g\circ f$ is obtained by first applying $f$ and then applying $g$.

Example. Let $A=\{1,2,3\},B=\{a,b,c,d\}$ and $C=\{4,5\}$. Consider the functions $f:A\to B$ and $g:B\to C$ defined by $$f=\{(1,a),(2,b),(3,b)\}{\text{ and }}g=\{((a,4),(b,5),(c,5),(d,5)\}.$$ Then, we have $(g\circ f)(1)=4,(g\circ f)(2)=5$ and $(g\circ f)(3)=5$. So, the function $g\circ f:A\to C$ is given by $$g\circ f=\{(1,4),(2,5),(3,5)\}.$$ However, $f\circ g$ is undefined, since the codomain of $g$ ($C$) is different from the domain of $f$ ($A$).

Remark.

• To make both $g\circ f$ and $f\circ g$ defined, we need to have $f:A\to B$ and $g:B\to A$, that is, the domain (codomain) of $f$ must be equal to the codomain (domain) of $g$.
• In this case, $g\circ f$ is a function from $B$ to $B$, and $f\circ g$ is a function from $A$ to $A$. So, in order for them to be possibly equal, we need to further have $A=B$.

• But, even if $A=B$, it is still possible that $f\circ g\neq g\circ f$. Consider the following example.

Example. Let $A=\{1,2\}$. Consider the functions $f:A\to A$ and $g:A\to A$ defined by $$f=\{(1,2),(2,2)\}{\text{ and }}g=\{(1,1),(2,1)\}.$$ Then, $g\circ f=\{(1,1),(2,1)\}$ and $f\circ g=\{(1,2),(2,2)\}$. Since, for example, $(g\circ f)(1)=1\neq 2=(f\circ g)(1)$, it follows that $g\circ f\neq f\circ g$.

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 $A,B,C,D$, and for every function $f:A\to B,g:B\to C$ and $h:C\to D$, we have $$h\circ (g\circ f)=(h\circ g)\circ f.$$

Proof. First, since $g\circ f$ is a function from $A$ to $C$, it follows that $h\circ (g\circ f)$ is a function from $A$ to $D$. Similarly, since $h\circ g$ is a function from $B\to D$, it follows that $(h\circ g)\circ f$ is function from $A$ to $D$.

It now remains to prove that both functions map every element $a\in A$ into the same image in $D$. For every $a\in A$, $${\big (}h\circ (g\circ f){\big )}(a)=h{\big (}(g\circ f)(a){\big )}=h{\big (}g(f(a)){\big )}.$$ (a bracket for $g\circ f$ means "grouping" $g$ and $f$ first, that is, we regard $g\circ f$ as a function first. To understand this more easily, one may write $f_{1}$ instead of "$g\circ f$" above.)

Also, $${\big (}(h\circ g)(f(a)){\big )}=h{\big (}g(f(a)){\big )}.$$

$\Box$

Example. Let $A=\{1,2,3\},B=\{a,b,c,d\},C=\{4,5\}$ and $D=\{\alpha ,\beta ,\gamma \}$. Consider the functions $f:A\to B$, $g:B\to C$ and $h:C\to D$ defined by $$f=\{(1,a),(2,b),(3,b)\},g=\{((a,4),(b,5),(c,5),(d,5)\}{\text{ and }}h=\{(4,\beta ),(5,\gamma )\}.$$ Recall that we have shown that $g\circ f=\{(1,4),(2,5),(3,5)\}$. We can further show that $h\circ g=\{(a,\beta ),(b,\gamma ),(c,\gamma ),(d,\gamma )\}$. Thus, $h\circ (g\circ f):A\to D$ and $(h\circ g)\circ f:A\to D$ are given by $$h\circ (g\circ f)=(h\circ g)\circ f=\{(1,\beta ),(2,\gamma ),(3,\gamma )\}.$$

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

Proposition. For every nonempty set $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$,

(a) if $f$ and $g$ are injective, then $g\circ f$ is injective.

(b) if $f$ and $g$ are surjective, then $g\circ f$ is surjective.

Proof. For (a), assume that $f$ and $g$ are injective. Then, for every $x,y\in A$ $${\begin{aligned}g\circ f(x)=g\circ f(y)&\implies g(f(x))=g(f(y))\\&\implies f(x)=f(y)&(g{\text{ is injective}})\\&\implies x=y.&(f{\text{ is injective}})\\\end{aligned}}$$ For (b), assume that $f$ and $g$ are injective. Then, for every $c\in C$, since $g$ is surjective, there exists $b\in B$ such that $g(b)=c$. For this $b\in B$, there must also exist $a\in A$ such that $f(a)=b$ since $f$ is surjective. It follows that for every $c\in C$, there exists $a\in A$ such that $$c=g(b)=g(f(a))=(g\circ f)(a).$$

$\Box$

Corollary. For every nonempty set $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$, if $f:A\to B$ and $g:B\to C$ are bijective, then $g\circ f$ is bijective.

Proof. Assume that $f$ and $g$ are bijective, i.e., are injective and surjective. It follows by the above proposition that $g\circ f$ is injective and surjective, i.e., is bijective.

$\Box$

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 $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$,

(a) if $g\circ f$ is injective, then $f$ is injective.

(b) if $g\circ f$ is surjective, then $g$ is surjective.

Proof. For (a), assume that $g\circ f$ is injective. Then, for every $x,y\in A$, $${\begin{aligned}f(x)=f(y)&\implies g(f(x))=g(f(y))&({\text{definition of function}})\\&\implies x=y.&(g\circ f{\text{ is injective}})\\\end{aligned}}$$ For (b), assume that $g\circ f$ is surjective. Then, for every $c\in C$, there exists $a\in A$ such that $g(f(a))=c$. So, we now can show that $g$ is surjective: for every $c\in C$, we can choose $f(a)\in B$, and then we have $g(f(a))=c$.

$\Box$

Remark.

• It follows that if $g\circ f$ is bijective, then $f$ is injective and $g$ is surjective.
• For (a), with the assumption, $f$ may or may not be surjective. Also, for (b), $g$ may or may not be injective.

To summarize the results, we have the following table:

Summary

$g\circ f$ (given)	$f$	$g$
injective	injective	injective/not injective
surjective	surjective	surjective/not surjective
bijective	injective	surjective

Exercise. Disprove that for every nonempty set $A,B,C$ and for every function $f:A\to B$ and $g:B\to C$,

(a) if $g\circ f$ is injective, then $g$ is injective.

(b) if $g\circ f$ is surjective, then $f$ is surjective.

Solution

(a)

Disproof. Take $A=\{1,2\},B=\{1,2,3\},C=\{1,2\}$, and take the functions $f:A\to B$ and $g:B\to C$ defined by $f=\{(1,1),(2,2)\},g=\{(1,1),(2,2),(3,1)\}$.

Then, the function $g\circ f:A\to C$ is given by $g\circ f=\{(1,1),(2,2)\}$, which is injective, since for every $x,y\in A$, $(g\circ f)(x)=(g\circ f)(y)\implies x=y$. However, the function $g$ is not injective since $g(1)=g(3)=1$.

$\Box$

(b)

Disproof. Take $A=\{1,2\},B=\{1,2,3\},C=\{1,2\}$, and take the functions $f:A\to B$ and $g:B\to C$ defined by $f=\{(1,1),(2,2)\},g=\{(1,1),(2,2),(3,1)\}$.

Then, the function $g\circ f:A\to C$ is given by $g\circ f=\{(1,1),(2,2)\}$, which is surjective, since for every $c\in C$, there exists $a\in A$ such that $(g\circ f)(a)=c$. However, the function $f$ is not surjective, since, for example, take $c=3$. Then, for every $a\in A$, $f(a)\neq c=3$.

$\Box$

Example. Consider two arbitrary functions $f:\mathbb {R} \to \mathbb {R}$ and $g:\mathbb {R} \to \mathbb {R}$ such that the function $g\circ f:\mathbb {R} \to \mathbb {R}$ is given by $$g\circ f(x)=x^{3}.$$ What properties do the functions $f$ and $g$ possess?

Solution. First, we claim that $g\circ f$ is bijective.

Proof.

Injective: for every $x,y\in \mathbb {R}$, $(g\circ f)(x)=(g\circ f)(y)=x^{3}=y^{3}\implies x=y$.

Surjective: for every $y\in \mathbb {R}$, choose $x=y^{1/3}\in \mathbb {R}$. Then, $(g\circ f)(x)=(y^{1/3})^{3}=y$.

$\Box$

Then, we can conclude that $f$ is injective and $g$ is surjective by the above proposition.

Exercise. Consider the function $f:\mathbb {R} \to \mathbb {R}$ satisfying $(f\circ f)(x)=x$ for every $x\in \mathbb {R}$. Prove or disprove that $f$ is (i) injective; (ii) surjective.

Solution

(i) and (ii):

Proof. First, notice that $f\circ f=id_{\mathbb {R} }$, and we have proved that $id_{\mathbb {R} }$ is bijective. So, by the above proposition, $f$ is injective and surjective.

$\Box$

Inverse functions

Recall that a function $f:A\to B$ is a special relation from set $A$ to set $B$ satisfying some requirements. Also, recall that given a relation from $A$ to $B$, the inverse relation $R^{-1}$ is defined to be $$R^{-1}=\{(b,a):(a,b)\in R\}\subseteq B\times A.$$ We know that the inverse relation is always a relation itself. However, is the inverse relation of a function $f:A\to B$ always a function from $B$ to $A$ itself? The answer is, indeed, no. Consider the following example.

Example. Let $A=\{1,2,3\}$ and $B=\{a,b\}$. Consider the function $f:A\to B$ defined by $$f=\{(1,a),(2,a),(3,b)\}.$$ Then, the inverse relation (we are not calling it inverse function) of $f$, denoted by $f^{-1}$, is $$f^{-1}=\{(a,1),(a,2),(b,3)\}.$$ We can then see that this inverse relation $f^{-1}$ is not a function from $B$ to $A$, since the element $a\in B$ has two images: 1 and 2.

Of course, when the inverse relation of a function $f:A\to B$ turns out to be also a function from $B$ to $A$, it is natural to define it as the inverse function of $f$:

Definition. (Inverse function) Let $A$ and $B$ be sets, and let $f:A\to B$ be a function. The inverse function of the function $f$ is the inverse relation of $f$, denoted by $f^{-1}$, provided that $f^{-1}$ is a function from $B$ to $A$.

Remark.

• Since given a relation from $A$ to $B$, it has a unique (or exactly one) inverse relation from $B$ to $A$ (according to the definition), it follows that the inverse function of a function $f$, if exists, is unique.

We are then interested in knowing under what conditions the inverse relation $f^{-1}$ is a function from $B$ to $A$, so that the inverse function exists.

First, in order for $f^{-1}$ to be a function from $B$ to $A$, we must have $\operatorname {dom} f^{-1}=B$. So, we need to ensure that every element of $B$ is related to some elements in $A$, so that when we "reverse" the ordered pairs in $f$ to get $f^{-1}$, there is at least one image for every $b\in B$. This means $\operatorname {ran} f=B$, i.e., $f$ needs to be surjective.

Of course, we also need to ensure that there is a unique image for every $b\in B$. Under the condition that $f$ is surjective, there is at least one image for every $b\in B$ already. So, it remains to ensure that there is at most one image for every $b\in B$.

To ensure this, we need the function $f$ to be injective, since, if $f$ is injective, then every element of $B$ has at most one pre-image. So, when we "reverse" the ordered pairs in $f$ to get $f^{-1}$, every element of $B$ has at most one image.

From this discussion, we know that if $f^{-1}$ is a function from $B$ to $A$, then $f$ has to be injective and surjective, i.e. bijective. This shows that the bijectivity of $f$ is the necessary condition for the existence of the inverse function. Is it also the sufficient condition? It turns out that the bijectivity of $f$ is actually the necessary and sufficient condition for the existence of the inverse function:

Theorem. Let $f:A\to B$ be a function. Then its inverse relation $f^{-1}$ is a function from $B$ to $A$ (i.e., the inverse function of $f$ exists) if and only if the function $f$ is bijective.

Proof.

"$\Rightarrow$" direction: Assume that $f^{-1}$ is a function from $B$ to $A$. Then, we will proceed to prove that $f$ is injective and surjective:

Injective: For every $x,y\in {\color {darkgreen}A}$, first assume $z=f(x)=f(y){\color {blue}\in B}$. Then, $(x,z),(y,z)\in f$. By definition of inverse relation, we have $(z,x),(z,y)\in f^{-1}$. Since $f^{-1}$ is a function from ${\color {blue}B}$ to ${\color {darkgreen}A}$, we have by definition $x=y$.

Surjective: For every $b\in B$, since $f^{-1}$ is a function from $B$ to $A$, there exists a unique $a\in A$ such that $(b,a)\in f^{-1}$. This means by definition of inverse relation that $(a,b)\in f$, i.e., $f(a)=b$ .

"$\Leftarrow$" direction: Assume that $f$ is bijective. Then, we will proceed to prove that $f^{-1}$ is a function from $B$ to $A$. That is, we need to ensure that for every element $b\in B$, there exists a unique $a\in A$ such that $(b,a)\in f^{-1}$.

Existence: For every $b\in B$, since $f$ is surjective, there exists $a\in A$ such that $f(a)=b$, i.e. $(a,b)\in f$. Hence, $(b,a)\in f^{-1}$. This shows that for every $b\in B$, there exists $a\in A$ such that $(b,a)\in f^{-1}$.

Uniqueness: Assume $(b,a')\in f^{-1}$, in addition to $(b,a)\in f^{-1}$. So, we have $(a,b),(a',b)\in f$, i.e., $f(a)=f(a')=b$. Since $f$ is injective, we have $a=a'$.

$\Box$

Hence, from this theorem, we know that it is only meaningful to talk about inverse function of $f$ when $f$ is bijective. If $f$ 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 $f:A\to B$ is bijective, then its inverse function $f^{-1}:B\to A$ is also bijective.

Proof. Assume that $f:A\to B$ is bijective. Then, $f^{-1}$ is a function from $B$ to $A$. Then, we will show that it is injective and surjective.

Injective: For every $b,b'\in B$, first assume $a=f^{-1}(b)=f^{-1}(b')$. Then, $(b,a),(b',a)\in f^{-1}$. Thus, $(a,b),(a,b')\in f$. It follows that $b=b'$ since $f$ is a function.

Surjective: For every $a\in A$, since $f$ is a function, there exists a unique $b\in B$ such that $f(a)=b$, i.e., $(a,b)\in f$, and hence $(b,a)\in f^{-1}$, i.e., $f^{-1}(b)$.

$\Box$

Remark.

• Notice that in the proof, we do not make use of the bijectivity of $f$ to prove the injectivity and surjectivity of $f^{-1}$. Indeed, we just use the definition of function to prove them. The bijectivity of $f$ serves only one purpose: ensuring that the inverse function exists.

Another common definition of inverse function is that the inverse function of $f$, denoted by $f^{-1}$, is a function satisfying $$f^{-1}\circ f=id_{A}{\text{ and }}f\circ f^{-1}=id_{B}.$$ It turns out that these two definitions of inverse function are indeed (logically) equivalent. Consider the following theorem.

Theorem. Let $f:A\to B$ and $g:B\to A$ be two functions such that $f\circ g=id_{A}$ and $g\circ f=id_{B}$. Then, $f$ is bijective and $g$ equals the inverse function of $f$, $f^{-1}$.

Proof. Let us first prove that $f$ is bijective.

Injective: For every $x,y\in A$, $${\begin{aligned}f(x)=f(y)&\implies g(f(x))=g(f(y))&(g{\text{ is a function}})\\&\implies (g\circ f)(x)=(g\circ f)(y)\\&\implies id_{A}(x)=id_{A}(y)&({\text{assumption}})\\&\implies x=y.\end{aligned}}$$ Surjective: For every $y\in B$, choose $x=g(y)\in A$. Then, $$f(x)=f(g(y))=id_{B}(y)=y.$$

Now, let us prove that $g=f^{-1}$. Since $f$ is bijective, the inverse function $f^{-1}$ exists. Then, since the domain and codomain of the inverse function $f^{-1}$ is $B$ and $A$ respectively by definition, $g$ and $f^{-1}$ have the same domain and codomain. It now remains to show that $g(b)=f^{-1}(b)$ for every $b\in B$. Since $f$ is surjective, for every $b\in B$, there exists $a\in A$ such that $f(a)=b$. This means $a=f^{-1}(b)$. Now, we have for every $b\in B$, $$g(b)=g(f(a))=id_{A}(a)=a=f^{-1}(b).$$

$\Box$

The converse of the above theorem is also true. More precisely, if $f$ is bijective, and thus its inverse function $f^{-1}$ exists, then we have $f\circ f^{-1}=id_{A}$ and $f^{-1}\circ f=id_{B}$. (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 $g$ satisfying $f\circ g=id_{A}$ and $g\circ f=id_{B}$ is unique, since the inverse function is unique.

Exercise. Let $f:A\to B$ be a function. Prove that if $f$ is bijective, and thus its inverse function $f^{-1}$ exists, then we have $f\circ f^{-1}=id_{A}$ and $f^{-1}\circ f=id_{B}$.

Proof. First, since $f^{-1}$ is a function from $B$ to $A$, it follows that $f\circ f^{-1}$ is a function from $A$ to $A$, and $f^{-1}\circ f$ is a function from $B$ to $B$.

Then, for every $a\in A$, there exists a unique $b\in B$ such that $f(a)=b$, and hence $a=f^{-1}(b)$. So, $$(f^{-1}\circ f)(a)=f^{-1}(f(a))=f^{-1}(b)=a.$$ Also, for every $b\in B$, $$(f\circ f^{-1})(b)=f(f^{-1}(b))=f(a)=b.$$

$\Box$

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 $f:\mathbb {R} \setminus \{1\}\to \mathbb {R} \setminus \{3\}$ defined by $f(x)={\frac {3x+1}{x-1}}$ is bijective. So, its inverse function $f^{-1}$ exists. Determine the inverse function $f^{-1}$.

Solution. We have for every $x\in \mathbb {R} \setminus \{3\}$, $(f\circ f^{-1})(x)=x$. Hence, $$x=(f\circ f^{-1})(x)=f(f^{-1}(x))={\frac {3f^{-1}(x)+1}{f^{-1}(x)-1}}\implies xf^{-1}(x)-x=3f^{-1}(x)+1\implies f^{-1}(x)={\frac {x+1}{x-3}}.$$ Thus, the inverse function $f^{-1}:\mathbb {R} \setminus \{3\}\to \mathbb {R} \setminus \{1\}$ is given by $$f^{-1}(x)={\frac {x+1}{x-3}}.$$

In this approach, we use some algebraic manipulation to find the inverse function. However, such method is not always possible. For instance, the function $f:\mathbb {R} \to (0,\infty )$ defined by $f(x)=e^{x}$ is bijective, but its inverse function $f^{-1}:(0,\infty )\to \mathbb {R}$ is given by (indeed, defined to be) $f^{-1}(x)=\ln x$. In this case, such inverse function cannot be obtained by such algebraic manipulation.

Exercise. Consider the function $f:[0,1]\to [0,1]$ defined by $$f(x)={\sqrt {1-x^{2}}}.$$ (a) Prove that $f$ is bijective.

(b) Determine the formula for inverse function, $f^{-1}(x)$.

Solution

(a)

Proof.

Injective: For every $x,y\in [0,1]$, $${\begin{aligned}f(x)=f(y)&\implies {\sqrt {1-x^{2}}}={\sqrt {1-y^{2}}}\\&\implies 1-x^{2}=1-y^{2}\\&\implies x^{2}=y^{2}\\&\implies x=y.&(x,y\geq 0)\end{aligned}}$$ Surjective: For every $y\in [0,1]$, choose $x={\sqrt {1-y^{2}}}\in [0,1]$. Then, $$f(x)=f\left({\sqrt {1-y^{2}}}\right)={\sqrt {1-\left({\sqrt {1-y^{2}}}\right)^{2}}}={\sqrt {1-(1-y^{2})}}={\sqrt {y^{2}}}=|y|=y.$$

$\Box$

(b) Since $f(f^{-1}(x))=x$ for every $x\in [0,1]$, we have $$x={\sqrt {1-(f^{-1}(x))^{2}}}\implies x^{2}=1-(f^{-1}(x))^{2}\implies f^{-1}(x)=\pm {\sqrt {1-x^{2}}}.$$ But the codomain of the inverse function $f^{-1}$ is $[0,1]$. So we should choose the positive square root as the formula, i.e., $$f^{-1}(x)={\sqrt {1-x^{2}}}.$$

Remark.

• It turns out that, in this case the function $f$ is equal to its inverse function $f^{-1}$.

Image sets and preimage sets

The concepts discussed in this section are the generalizations of the concepts of image and pre-image.

Definition. (Image (set) and preimage (set)) Let $A$ and $B$ be sets, and let $f:A\to B$ be a function.

(a) Suppose $X\subseteq A$. The image (set) of $X$ is the set $$f(X)=\{y\in B:y=f(x){\text{ for some }}x\in X\}\subseteq B.$$ (b) Suppose $Y\subseteq B$. The preimage (set) of $Y$ is the set $$f^{-1}(Y)=\{x\in A:f(x)\in Y\}\subseteq A.$$

Remark.

• Notice that the "$f^{-1}$" used in the notation for the preimage set is not referring to the inverse function. The preimage set $f^{-1}(Y)$ of $Y$ still makes sense even if the function $f$ is not bijective. However, the inverse function $f^{-1}$ does not exist if the function $f$ is not bijective.
• In other words, the image set contains the image of every element $x\in X$. 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 $y\in Y$. That is, the preimage set $f^{-1}(Y)$ is the set of elements in $A$ mapped into $Y$ by $f$.
• Special case: suppose $a\in A$ and $b\in B$. Then, the image set of $\{a\}$ is the set containing image of $a$ under $f$: $\{f(a)\}$, and the preimage of set $\{b\}$ is the set containing the preimages (if any) of $b$ under $f$.

Graphically, the image set looks like:

   A              B
*------*       *------*
|      |       |      |
|  . X |       | f(X) |
|.###. |       |  .   |
|.###.--------->.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

The preimage set looks like

   A              B
*------*       *------*
|f-1(Y)|       |      |
|  .   |       |  Y   |
|.###. |       |  .   |
|.###.<---------.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

Example. Let $A=\{1,2,3,4,5,6,7\}$ and $B=\{a,b,c,d,e\}$. Consider the function $f:A\to B$ defined by $$f=\{(1,a),(2,a),(3,b),(4,b),(5,d),(6,d),(7,a)\}.$$ Then,

• $f(\{1,3\})=\{a,b\}$
• $f^{-1}(\{a,b\})=\{1,2,3,4\}$
• $f(\{1,2,3,4\})=\{a,b\}$
• $f(\{1,2,3,4,5,6,7\})=\{a,b,d\}$
• $f^{-1}(\{c\})=\varnothing$
• $f^{-1}(\{a,c,d,e\})=\{1,2,5,6,7\}$
• $f(\{1,2,5,6,7\})=\{a,d\}$

Remark.

• Notice that $f$ is not bijective, but it is still meaningful to consider the preimage sets of $f$. For instance, we have $f^{-1}(\{a\})=\{1,2\}$, but "$f^{-1}(a)$" has no meaning since $f^{-1}$ does not exist at all.
• We can observe that $f(\{1,3\})=\{a,b\}$ but $f^{-1}(\{a,b\})=\{1,2,3,4\}$. So, $f^{-1}(f(X))\neq X$ in general. Also, we can notice that after "applying" the image set and then preimage set on a set $X$, it seems that we may get some set that is larger than $X$.
• On the other hand, we can see that $f^{-1}(\{a,c,d,e\})=\{1,2,5,6,7\}$ but $f(\{1,2,5,6,7\})=\{a,d\}$. So, $f(f^{-1}(Y))\neq Y$ in general. Also, it seems that we get some set that is smaller than $X$.
• Such kind of results turns out to be true in general (see the following theorem).

Exercise. Consider a function $f:A\to B$. Find (a) $f(A)$; (b) $f^{-1}(B)$; (c) $f(\varnothing )$; (d) $f^{-1}(\varnothing )$.

Solution

(a) $f(A)=\{y\in B:y=f(x){\text{ for some }}x\in A\}=\operatorname {ran} f$.

(b) $f^{-1}(B)=\{x\in A:\underbrace {f(x)\in B} _{\text{always true}}\}=A$.

(c) $f(\varnothing )=\{y\in B:\underbrace {y=f(x){\text{ for some }}x\in \varnothing } _{\text{always false}}\}=\varnothing$.

(d)