Mathematical Proof/Introduction to Set Theory

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

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

What is a set?

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

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

Example.

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

Ways of describing a set

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

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

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

The third way to describe a set is advantageous when a set contains many elements. This method is called set-builder notation. There are three parts within a pair of braces in this notation. They are illustrated below with descriptions: $$\underbrace {\{} _{\text{The set of}}\underbrace {x} _{{\text{all elements }}x}\underbrace {:} _{\text{such that}}\underbrace {P(x)} _{{\text{the property }}P(x){\text{ is satisfied}}}\}$$

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

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

Example.

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

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

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

	True.
	False.

2 $\{\}=\varnothing .$

	True.
	False.

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

	True.
	False.

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

	True.
	False.

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

	True.
	False.

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

	True.
	False.

Set cardinality

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

Example.

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

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

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

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

Example.

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

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

Solution

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

Subsets

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

Remark.

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

Example.

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

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

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

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

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

Remark.

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

Example.

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

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

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

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

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

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

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

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

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

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

There are also some infinite intervals:

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

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

Example.

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

Example.

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

Exercise.

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

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

Universal set and Venn diagram

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

Example.

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

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

Example.

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

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

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

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

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

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

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

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

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

In this diagram, if the white region represents set $A$ and the region enclosed by the rectangle represents the universal set, then the red region is the set $A^{c}$.

However, the following is not a Venn diagram.

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

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

Set operations

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

Union of sets

Definition. (Union of sets)

A Venn diagram for union of two sets.

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

Remark.

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

Example.

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

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

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

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

$\Box$

Remark.

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

Intersection of sets

Definition. (Intersection of sets)

A Venn diagram for intersection of two sets.

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

Remark.

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

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

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

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

$\Box$

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

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

Relative complement

Definition. (Relative complement)

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

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

Remark.

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

Example.

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

Exercise.

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

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

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

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

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

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

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

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

5 What is $\varnothing \setminus \varnothing$?

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

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

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

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

$\Box$

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

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

$\Box$

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

Exercise.

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

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

Symmetric difference

Definition. (Symmetric difference)

A Venn diagram illustrating symmetric difference.

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

Example.

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

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

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

Exercise.

1 What is $\varnothing \triangle \varnothing$?

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

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

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

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

	Yes.
	No.

Power set

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

Remark.

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

Example.

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

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

Proof. Assume $A$ is a finite set with cardinality $n$. Since each element of the power set ${\mathcal {P}}(A)$ is a subset of $A$, it suffices to prove that there are $2^{n}$ subsets of $A$. In the following, we consider subsets of $A$ with different number of elements separately, and count the number of subsets of each of the different types using combinatorics.

• For the subset with zero element, it is the empty set, and thus there is only one such subset.
• For the subsets with one element, there are $C_{1}^{n}$ subsets.
• For the subsets with two elements, there are $C_{2}^{n}$ subsets.
• ...
• For the subsets with $n-1$ elements, there are $C_{n-1}^{n}$ subsets.
• For the subset with $n$ elements, it is the set $A$, and thus there is only one such subset.

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

$\Box$

Remark.

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

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

1 $\{\varnothing \}$

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

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

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

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

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

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

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

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

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

	4
	8
	16
	32

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

	0
	1
	2
	4

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

	1
	2
	4
	8

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

	1
	2
	4
	8

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

	1
	2
	4
	8

Cartesian product

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

Remark.

• $(a,b)$ is the ordered pair (i.e. a pair of things for which order is important).

• The ordered pair is used to specify points on the plane, and the ordered pair is called coordinates.

• In particular, we have $(a,b)\neq (b,a)$ if $a\neq b$.
• (notation) We use $A^{2}$ to denote $A\times A$ for each set $A$.
• We can observe that $|A\times B|=|A|\times |B|$.

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

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

Remark.

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

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

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

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

2 What is $A^{2}$?

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

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

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

Remark.

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