Mathematical Proof/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{De Morgan's 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)&\implies x\in A{\text{ and }}y\in B\cup C\\&\implies x\in A{\text{ and }}(y\in B{\text{ or }}y\in C)\\&\implies (x\in A{\text{ and }}y\in B){\text{ or }}(x\in A{\text{ and }}y\in C)&({\text{Distributive law}})\\&\implies (x,y)\in A\times B{\text{ or }}(x,y)\in A\times C\\&\implies (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$,