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

# Introduction to Set Theory

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

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

## What is a set?

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

Example.

• Consider the set of all even numbers ${\displaystyle E}$. Elements of ${\displaystyle E}$ include (but are not limited to) -2, 0, and 4, i.e., ${\displaystyle -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, ${\displaystyle \{1,2\}}$ and ${\displaystyle \{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, ${\displaystyle \{1,1,2,2,2\}}$ and ${\displaystyle \{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 ${\displaystyle \{\}}$ based on the listing method or ${\displaystyle \varnothing }$. This kind of set is called an empty set.

Another way to describe a set is using words. For example, consider the set ${\displaystyle S}$ of prime numbers less than 10. If we use the listing method instead, the set ${\displaystyle S}$ is represented by ${\displaystyle \{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:

${\displaystyle \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 ${\displaystyle A}$ and ${\displaystyle B}$ are equal if and only if each element of ${\displaystyle A}$ is also an element of ${\displaystyle B}$ and each element of ${\displaystyle B}$ is also an element of ${\displaystyle A}$. This can be regarded as an axiom [2] or a definition. If two sets ${\displaystyle A}$ and ${\displaystyle B}$ are equal, we write ${\displaystyle A=B}$. If not, we write ${\displaystyle A\neq B}$.

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

Example.

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

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

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

 True. False.

2 ${\displaystyle \{\}=\varnothing .}$

 True. False.

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

 True. False.

4 ${\displaystyle \{x:0.

 True. False.

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

 True. False.

6 ${\displaystyle \{\{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 ${\displaystyle S}$, its cardinality is denoted by ${\displaystyle |S|}$.

Example.

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

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

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

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

Example.

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

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

Solution

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

## Subsets

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

Remark.

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

Example.

• ${\displaystyle \mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C} }$.
• ${\displaystyle \mathbb {Z} \not \subseteq \mathbb {I} }$ (e.g. ${\displaystyle 1\in \mathbb {Z} }$ but ${\displaystyle 1\notin \mathbb {I} }$)
• ${\displaystyle \mathbb {C} \not \subseteq \mathbb {R} }$ (e.g. ${\displaystyle i\in \mathbb {C} }$ but ${\displaystyle i\notin \mathbb {R} }$)
• For each set ${\displaystyle S}$, ${\displaystyle S\subseteq S}$, i.e. each set is a subset of itself.
• This is because each element of set ${\displaystyle S}$ is an element of ${\displaystyle S}$.
• For each set ${\displaystyle S}$, ${\displaystyle \varnothing \subseteq S}$.
• If we want to prove this directly, there are some difficulties since ${\displaystyle \varnothing }$ does not contain any element. So, what is meant by "each element of ${\displaystyle \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 ${\displaystyle \varnothing \not \subseteq S}$. By the negation of the definition, there is at least one element of ${\displaystyle \varnothing }$ that is not an element of ${\displaystyle S}$, which is false. This yields a contradiction, and thus the hypothesis is false (explanation will be provided later), i.e. ${\displaystyle \varnothing \not \subseteq S}$ is false.

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

Remark.

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

Example.

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

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

1 Which of the following set(s) is a subset of ${\displaystyle A}$?

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

2 Select the set(s) of which the set ${\displaystyle A}$ is a subset.

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

3 Select the set(s) of which the set ${\displaystyle A}$ is an element.

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

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

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

There are also some infinite intervals:

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

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

Example.

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

Example.

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

Exercise.

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

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

## Universal set and Venn diagram

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

Example.

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

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

Example.

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

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

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

 ${\displaystyle [1,\infty )}$ ${\displaystyle (1,\infty )}$ ${\displaystyle (-\infty ,1)}$ ${\displaystyle (-\infty ,1]}$

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

 ${\displaystyle [1,\infty )}$ ${\displaystyle (1,\infty )}$ ${\displaystyle (-\infty ,1)}$ ${\displaystyle (-\infty ,1]}$

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

 ${\displaystyle [1,3]}$ ${\displaystyle (1,3)}$ ${\displaystyle (1,\infty )}$ ${\displaystyle (3,\infty )}$ ${\displaystyle (-\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 ${\displaystyle A}$ and the region enclosed by the rectangle represents the universal set, then the red region is the set ${\displaystyle 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)

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

Remark.

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

Example.

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

Proposition. Let ${\displaystyle A,B}$ and ${\displaystyle C}$ be sets. Then,

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

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

${\displaystyle \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)

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

Remark.

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

Proposition. Let ${\displaystyle A,B}$ and ${\displaystyle C}$ be sets. Then,

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

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

${\displaystyle \Box }$

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

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

### Relative complement

Definition. (Relative complement)

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

Remark.

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

Example.

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

Exercise.

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

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

2 What is ${\displaystyle [1,10]\setminus (3,5)}$?

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

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

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

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

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

5 What is ${\displaystyle \varnothing \setminus \varnothing }$?

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

Proposition. Let ${\displaystyle A}$ and ${\displaystyle B}$ be sets. Then,

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

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

${\displaystyle \Box }$

Theorem. (De Morgan's Laws) Let ${\displaystyle A}$ and ${\displaystyle B}$ be sets. Then,

${\displaystyle (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.

${\displaystyle \Box }$

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

Exercise.

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

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

### Symmetric difference

Definition. (Symmetric difference)

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

Example.

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

Proposition. Let ${\displaystyle A,B}$ and ${\displaystyle C}$ be sets. Then,

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

Exercise.

1 What is ${\displaystyle \varnothing \triangle \varnothing }$?

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

2 What is ${\displaystyle A\triangle (B\setminus A)}$?

 ${\displaystyle A\cup B}$ ${\displaystyle A\cap B}$ ${\displaystyle A\setminus B}$ ${\displaystyle A\triangle B}$ ${\displaystyle B\setminus A}$ ${\displaystyle A}$ ${\displaystyle B}$

3 Does ${\displaystyle A\triangle B\triangle C=(A\cup B\cup C)\setminus (A\cap B\cap C)}$[5]? (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 ${\displaystyle A}$, denoted by ${\displaystyle {\mathcal {P}}(A)}$, is the set of all subsets of ${\displaystyle A}$. In set-builder notation, ${\displaystyle {\mathcal {P}}(A)=\{S:S\subseteq A\}}$.

Remark.

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

Example.

• ${\displaystyle {\mathcal {P}}(\varnothing )=\{\varnothing \}}$. Its cardinality is 1.
• If ${\displaystyle A=\{1\}}$, then ${\displaystyle {\mathcal {P}}(A)=\{\varnothing ,A\}=\{\varnothing ,\{1\}\}}$. Its cardinality is 2.
• If ${\displaystyle B=\{1,\{1\}\}}$, then ${\displaystyle {\mathcal {P}}(B)=\{\varnothing ,\{1\},\{\{1\}\},B\}}$. Its cardinality is 4.
• ${\displaystyle {\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 ${\displaystyle A}$ be a finite set with cardinality ${\displaystyle n}$. Then, ${\displaystyle |{\mathcal {P}}(A)|=2^{n}}$.

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

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

${\displaystyle \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 ${\displaystyle \{\varnothing \}}$

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

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

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

3 ${\displaystyle \{a,\{a\}\}}$

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

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

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

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

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

 4 8 16 32

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

 0 1 2 4

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

 1 2 4 8

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

 1 2 4 8

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

 1 2 4 8

### Cartesian product

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

Remark.

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

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

• ${\displaystyle A\times B=\{(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)\}}$.
• ${\displaystyle 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 ${\displaystyle A\times B=B\times A}$.

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

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

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

2 What is ${\displaystyle A^{2}}$?

 ${\displaystyle \{(1,1),(2,2),(3,3)\}}$ ${\displaystyle \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}}$ ${\displaystyle A}$ ${\displaystyle \{(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 ${\displaystyle n}$ be an integer greater than 2. The Cartesian product of ${\displaystyle n}$ sets ${\displaystyle A_{1},A_{2},\dotsc ,A_{n}}$ is ${\displaystyle 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 ${\displaystyle A^{n}}$ to denote ${\displaystyle \underbrace {A\times A\times \dotsb \times A} _{n{\text{ times}}}}$, where ${\displaystyle 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 ${\displaystyle T}$) or false (denoted by ${\displaystyle F}$).

Example. Consider the following sentences:

1. The number 9 is even.
2. ${\displaystyle 1<2}$.
3. Mathematics is easy.
4. How to solve ${\displaystyle x^{2}+2x-3=0}$?
• 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 ${\displaystyle \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 ${\displaystyle P(x):x=2}$ (${\displaystyle :}$ is read "such that").

• This sentence is true when ${\displaystyle 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 ${\displaystyle P}$ and ${\displaystyle Q}$, the truth table for them is as follows:

${\displaystyle {\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 ${\displaystyle P}$ and ${\displaystyle Q}$.

Example. (Truth table for three statements) For three statements ${\displaystyle P}$, ${\displaystyle Q}$ and ${\displaystyle R}$, the truth table for them is as follows:

${\displaystyle {\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 ${\displaystyle P}$, ${\displaystyle Q}$ and ${\displaystyle R}$.

Remark.

• In general, there are ${\displaystyle \underbrace {2\times \dotsb \times 2} _{n{\text{ times}}}=2^{n}}$ possible combinations of truth values of ${\displaystyle 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 ${\displaystyle P}$, write four ${\displaystyle T}$'s and then four ${\displaystyle F}$'s, from top to bottom;
• for ${\displaystyle Q}$, write in this pattern from top to bottom: ${\displaystyle TTFFTTFF}$;
• for ${\displaystyle R}$, write in this pattern from top to bottom: ${\displaystyle 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 ${\displaystyle P}$ and ${\displaystyle Q}$, denoted by ${\displaystyle P\land Q}$, is a statement that is true when both ${\displaystyle P}$ and ${\displaystyle Q}$ are true, and false otherwise.

Remark.

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

Example. (Truth table for ${\displaystyle P\land Q}$) The truth table for ${\displaystyle P\land Q}$ (in terms of possible combinations of truth values of ${\displaystyle P}$ and ${\displaystyle Q}$ [6]) is

${\displaystyle {\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 ${\displaystyle P\land Q}$ is true only when both ${\displaystyle P}$ and ${\displaystyle Q}$ are true, and false otherwise.

### Disjunctions

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

Remark.

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

${\displaystyle {\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 ${\displaystyle P\lor Q}$ is false only when both ${\displaystyle P}$ and ${\displaystyle Q}$ are false, and true otherwise.

### Negations

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

Remark.

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

Example. (Truth table for ${\displaystyle \sim P}$) The truth table for ${\displaystyle \sim P}$ is

${\displaystyle {\begin{array}{|c|c|}P&\sim P\\\hline T&F\\F&T\\\end{array}}}$

• We can see that ${\displaystyle \sim P}$ always has the opposite truth value to that of ${\displaystyle 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:

${\displaystyle {\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}}}$

${\displaystyle {\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 ${\displaystyle P}$ and ${\displaystyle Q}$, the truth values of ${\displaystyle (\sim P)\lor (\sim Q)}$ and ${\displaystyle \sim (P\lor Q)}$ are different.

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

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

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

Exercise. Let ${\displaystyle P}$ be the statement ${\displaystyle 3>5.}$ and ${\displaystyle Q}$ be the statement ${\displaystyle 3<2.}$.

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

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

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

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

• First, we can see that both ${\displaystyle P}$ and ${\displaystyle Q}$ are false.

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

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

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

Example. (Truth table for ${\displaystyle P\to Q}$) The truth table for ${\displaystyle P\to Q}$ is

${\displaystyle {\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 ${\displaystyle P}$ is false, the conditional ${\displaystyle P\to Q}$ is true, by definition [7].
• Another observation is that when the consequent is true, then no matter the hypothesis is true or false, the conditional must be true (see 1st and 3rd row).

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

Example. Suppose Bob is taking a mathematics course, called MATH1001. The course instructor of MATH1001 warns Bob that if he fails the final examination of this course, then he will fail this course. Let ${\displaystyle P}$ be the statement "Bob fails the final examination of MATH1001.", and ${\displaystyle Q}$ be the statement "Bob fails MATH1001". Then, the statement made by the course instructor is "${\displaystyle 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 [8].

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

### Converse and biconditionals

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

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

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

Definition. (Biconditionals) The biconditional of two statements ${\displaystyle P}$ and ${\displaystyle Q}$, denoted by ${\displaystyle P\leftrightarrow Q}$, is ${\displaystyle (P\to Q)\land (Q\to P)}$, that is, "If ${\displaystyle P}$ then ${\displaystyle Q}$." and "If ${\displaystyle Q}$ then ${\displaystyle P}$.".

Remark.

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

Example. (Truth table for ${\displaystyle P\leftrightarrow Q}$) The truth table for ${\displaystyle P\leftrightarrow Q}$ is

${\displaystyle {\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 ${\displaystyle P\leftrightarrow Q}$ is true when both ${\displaystyle P}$ and ${\displaystyle Q}$ have the same truth values (i.e. either both ${\displaystyle P}$ and ${\displaystyle Q}$ are true, or both ${\displaystyle P}$ and ${\displaystyle Q}$ are false), and false otherwise.

### Implication and logical equivalence

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

We have some other equivalently ways to say "${\displaystyle P}$ implies ${\displaystyle Q}$", namely

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

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

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

• ${\displaystyle P}$ is sufficient but not necessary for ${\displaystyle Q}$.
• From the previous interpretation, when we say ${\displaystyle P}$ is necessary for ${\displaystyle Q}$, we mean ${\displaystyle Q\Rightarrow P}$. Hence, when ${\displaystyle P}$ is sufficient but not necessary for ${\displaystyle Q}$, we mean ${\displaystyle {\color {blue}P\Rightarrow Q}}$ and ${\displaystyle {\color {red}Q\nRightarrow P}}$.
• ${\displaystyle P}$ is a stronger condition than ${\displaystyle Q}$ (or ${\displaystyle P}$ is stronger than ${\displaystyle Q}$ in short).

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

• ${\displaystyle P}$ is logically equivalent to ${\displaystyle Q}$.
• We say they are logically equivalent since they always have the same truth values (because ${\displaystyle P\leftrightarrow Q}$ is true), which is related to logic.
• "${\displaystyle P}$ if and only if ${\displaystyle Q}$" (is true).
• Recall that we also use "${\displaystyle P}$ if and only if ${\displaystyle Q}$" to express the biconditional ${\displaystyle P\leftrightarrow Q}$. Thus, technically, we should write "${\displaystyle P}$ if and only if ${\displaystyle Q}$" is true in the case where ${\displaystyle 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 "${\displaystyle P}$ if and only if ${\displaystyle Q}$" in this context, we mean that the biconditional is true without saying it explicitly.
• Usually, when we just write "${\displaystyle P}$ if and only if ${\displaystyle Q}$", we have the meaning of the logical equivalence ${\displaystyle P\Leftrightarrow Q}$, rather than the statement ${\displaystyle P\leftrightarrow Q}$. If we really want to have the latter meaning, we should specify that "${\displaystyle P}$ if and only if ${\displaystyle Q}$" refers to a statement.
• ${\displaystyle P}$ is necessary and sufficient for ${\displaystyle Q}$.
• Following the previous interpretation, ${\displaystyle P}$ is necessary and sufficient for ${\displaystyle Q}$ means ${\displaystyle {\color {blue}Q\Rightarrow P}}$ and ${\displaystyle {\color {red}P\Rightarrow Q}}$.

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

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

Proof. They can be shown using truth tables.

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

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

${\displaystyle {\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}}}$

${\displaystyle \Box }$

Theorem. (Logical equivalence of a conditional and its contrapositive) The contrapositive of a conditional ${\displaystyle P\to Q}$ is defined to be another conditional ${\displaystyle (\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:

${\displaystyle 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).}$

${\displaystyle \Box }$

Remark.

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

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

Definition. (Tautologies and contradictions) A compound statement ${\displaystyle 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 ${\displaystyle S}$.

Remark.

• We use ${\displaystyle \mathbf {T} }$ to denote a tautology and ${\displaystyle \mathbf {F} }$ to denote a contradiction.
• When a statement ${\displaystyle S}$ is a tautology, we can also write ${\displaystyle S\Leftrightarrow \mathbf {T} }$, since it means ${\displaystyle S}$ and ${\displaystyle \mathbf {T} }$ always have the same truth value, and because the truth value of ${\displaystyle \mathbf {T} }$ is always true, the truth value of ${\displaystyle S}$ is also always true, i.e. ${\displaystyle S}$ is a tautology.
• Because of this, when we want to prove that a statement ${\displaystyle S}$ is always true, one way is to show that ${\displaystyle S\Leftrightarrow \mathbf {T} }$. For example, if we want to prove that ${\displaystyle P\to Q}$ and ${\displaystyle (\sim Q)\to (\sim P)}$ are logically equivalent, we may show that ${\displaystyle \left[{\big (}P\to Q{\big )}\leftrightarrow {\big (}(\sim Q)\to (\sim P){\big )}\right]\Leftrightarrow \mathbf {T} }$.

Example. Let ${\displaystyle P}$ be an arbitrary statement. Then,

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

This is because the truth table for ${\displaystyle P\lor (\sim P)}$ is

${\displaystyle {\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 ${\displaystyle P\land (\sim P)}$ is
${\displaystyle {\begin{array}{|c|c|c|}P&\sim P&P\land (\sim P)\\\hline T&F&F\\F&T&F\\\end{array}}.}$

Example. Let ${\displaystyle P}$ and ${\displaystyle Q}$ be arbitrary statements. Then, ${\displaystyle (P\land Q)\to (P\lor Q)}$ is a tautology, since its truth table is

${\displaystyle {\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, ${\displaystyle (P\lor Q)\to (P\land Q)}$, a tautology, contradiction, or neither?

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

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

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

Since

${\displaystyle (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 ${\displaystyle (P\lor Q)\to (P\land Q)}$ is a contradiction with the following argument:

Since ${\displaystyle (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.

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

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

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

Proof. They can be shown using truth tables.

${\displaystyle \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 ${\displaystyle x}$, ${\displaystyle x^{2}\geq 0}$." We can let ${\displaystyle P(x)}$ be the open statement "${\displaystyle x^{2}\geq 0}$". Then, it can be further rephrased as "For each real number ${\displaystyle x}$, ${\displaystyle P(x)}$." In this case, we can observe how an open statement (${\displaystyle P(x)}$) is converted to a statement (For each real number ${\displaystyle x}$, ${\displaystyle 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 ${\displaystyle \forall }$ (an inverted "A"). After introducing this notation, the statement we mention can be further rephrased as "${\displaystyle \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 ${\displaystyle P(x)}$ to a statement, which is "${\displaystyle \forall x\in S,P(x)}$" in which ${\displaystyle S}$ is a (universal) set (or domain) which restricts the input ${\displaystyle 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" [11], "for at least one" is referred to as an existential quantifier, and is denoted by ${\displaystyle \exists }$ (an inverted "E"). For example, we can rewrite the statement "The square of some real number is negative." as "${\displaystyle \exists x\in \mathbb {R} ,x^{2}<0.}$" (which is false).

In general, we can use the existential quantifier to change an open statement ${\displaystyle P(x)}$ to a statement, which is "${\displaystyle \exists x\in S,P(x)}$" in which ${\displaystyle S}$ is a (universal) set (or domain) which restricts the input ${\displaystyle 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 ${\displaystyle \exists !}$. For example, we can rewrite the statement "There exists a unique real number ${\displaystyle x}$ such that ${\displaystyle 2x=0}$." as "${\displaystyle \exists !x\in \mathbb {R} ,2x=0}$." We can express the unique existential quantifier in terms of existential and universal quantifiers, by defining "${\displaystyle \exists !x\in S,P(x)}$" as

${\displaystyle \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 ${\displaystyle x\in S}$ such that ${\displaystyle P(x)}$, AND for every ${\displaystyle x_{1},x_{2}\in S}$, if ${\displaystyle P(x_{1})}$ and ${\displaystyle P(x_{2})}$, then ${\displaystyle x_{1}=x_{2}}$ (i.e., ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ are actually referring to the same thing, so there is exactly one ${\displaystyle x}$ such that ${\displaystyle 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 "${\displaystyle \exists A\subseteq U,A=U}$" [12] can be expressed in words (partially) as "There exists a set ${\displaystyle A\subseteq U}$ such that ${\displaystyle A=U}$."

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

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

From this example, we can see that the negation of the statement "${\displaystyle \exists x\in S,P(x)}$" is logically equivalent to "${\displaystyle \forall x\in S,\sim P(x)}$". Now, it is natural for us to want to know also the negation of the statement "${\displaystyle \forall x\in S,P(x)}$. Consider this: when it is not the case that ${\displaystyle P(x)}$ is true for each ${\displaystyle x\in S}$, it means that ${\displaystyle P(x)}$ is false for at least one ${\displaystyle x\in S}$. In other words, ${\displaystyle \exists x\in S,\sim P(x)}$. Hence, we know that the negation of the statement "${\displaystyle \forall x\in S,P(x)}$" is logically equivalent to ${\displaystyle \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 ${\displaystyle x}$ and for each real number ${\displaystyle y}$, ${\displaystyle xy}$ is a real number." It can be written as "${\displaystyle \forall x\in \mathbb {R} ,\forall y\in \mathbb {R} ,xy\in \mathbb {R} }$". When we interchange "${\displaystyle \forall x\in \mathbb {R} }$" and "${\displaystyle \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 "${\displaystyle \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 ${\displaystyle x}$ and an real number ${\displaystyle y}$ such that ${\displaystyle xy}$ is a real number." It can be written as "${\displaystyle \exists x\in \mathbb {R} ,\exists y\in \mathbb {R} ,xy\in \mathbb {R} }$." Similarly, interchanging "${\displaystyle \exists x\in \mathbb {R} }$" and "${\displaystyle \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 ${\displaystyle x}$ and ${\displaystyle y}$, ${\displaystyle xy}$ is a real number.") Because of this, we can simply write the statement as "${\displaystyle \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 ${\displaystyle x}$, there exists an integer ${\displaystyle y}$ such that ${\displaystyle y." This can also be written as "${\displaystyle \forall x\in \mathbb {Z} ,\exists y\in \mathbb {Z} ,y". 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 ${\displaystyle x=13}$, I can choose ${\displaystyle y=-99,0}$ or ${\displaystyle 12}$. Indeed, for the integer ${\displaystyle x}$ chosen by you, I can always choose my ${\displaystyle y}$ as ${\displaystyle x-1}$ so that ${\displaystyle y.

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

## Exercises

In the following questions, ${\displaystyle P,Q,R,S}$ are statements.

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

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

B. Negate the following statements:

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