Definition (Set). A set is a well-defined (unordered) collection of distinct objects. Objects of a set are called elements or members of the set.

Remark.

1. Sets are denoted by uppercase letters such as A,B,S,U,X.


2. Elements may be denoted by lowercase letters such as a,b,c,x,y,z.


3. The notation \(a\in A\) (read as '\(a\) belongs to \(A\)') means \(a\) is an element of \(A\).

Example.

1. The collection of all positive integers is a set.


2. The collection of all smart/ beautiful people is not a set because the collection is not well-defined.

Remark. A collection \(S\) of objects is "well-defined" if for any given object \(x\), we know whether \(x\in S\) or \(x\notin S\). Further reading: Russell's paradox.

How to describe a set? For example how to describe the set \(E\) of all positive even integers less than 10?

1. Roster method: List all elements. e.g., \(E=\{2,4,6,8\}\) or \(E=\{4,8,2,6\}\).


2. Set builder notation: Characterize all elements. e.g., \(E=\{x\;|\;x \text{ is an even integer and }0 < x < 10\}\).

Some standard sets and their notation:

• \(\varnothing\) or \(\{\}\), the empty set or null set.


• \(\mathbb N \text{ or } \mathbb Z^+=\{1,2,3,\ldots\}\), the set of natural numbers.


• \(\mathbb Z=\{0,\pm1,\pm2,\pm3,\ldots\}\), the set of all integers.


• \(\mathbb Q=\{\frac{p}{q}\;|\;p,q\in \mathbb Z\text{ and }q\neq 0\}\), the set of all rational numbers.


• \(\mathbb R\), the set of all real numbers.


• \(\mathbb C\), the set of all complex numbers.

Definition (Subset). The set \(A\) is a subset of \(B\) if all the elements of \(A\) are in \(B\). We denote it by \(A\subseteq B\). The set \(A\) is a proper subset of \(B\) if \(A\subseteq B\) and \(A\neq B\). We denote it by \(A\subset B\) or \(A\subsetneqq B\).

Example.

1. \(\mathbb N\subseteq \mathbb Z\) and \(\mathbb N\subseteq \mathbb N\). \(\mathbb N\subsetneqq \mathbb Z\) and \(\mathbb Q\subsetneqq \mathbb R\).


2. For any set \(S\), we have \(S\subseteq S\) and \(\varnothing\subseteq S\).

Remark.

1. If \(A\) is not a subset of \(B\), then we write \(A\nsubseteq B\). E.g., \(\{1,2\}\nsubseteq \{2,3,4\}\).


2. Equality of sets: \(A=B\) if and only if \(A\subseteq B\) and \(B\subseteq A\).

Venn diagram (1881)
Let \(U\) be the universal set under consideration drawn as a rectangle. Subsets of \(U\) are drawn inside the rectangle as circle, rectangle etc. Elements of the subsets are denoted by points.

Definition (Size of a set). A set is finite set if it has a finite number of elements. The size or cardinality of a finite set \(S\), denoted by \(|S|\), is the number of elements of \(S\).

Example. \(|\varnothing|=0\) and \(|\{2,4,6,8\}|=4\).

Remark. The cardinality of an infinite set is very interesting! For example, \(\mathbb N\), \(\mathbb Z\), and \(\mathbb Q\) have the same cardinality (see Hilbert's hotel). But \(|\mathbb Q|\neq |\mathbb R|\).

Definition (Power set). For a set \(S\), the power set of \(S\), denoted by \(\mathcal P(S)\), is the set of all subsets of \(S\).

Example. Let \(S=\{a,b,c\}\). Then \(\mathcal P(S)=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},S\}\).

Remark. If \(|S|=n\), then \(|\mathcal P(S)|=\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n\) by the binomial expansion.

Definition (Cartesian product). The cartesian product of n sets \(A_1,A_2\ldots,A_n\), denoted by \(A_1\times A_2\times\cdots\times A_n\), is defined by \[A_1\times A_2\times\cdots\times A_n=\{(a_1,a_2,\ldots,a_n)\;|\;a_i\in A_i\text{ for }i=1,\ldots,n\}.\]
Remark.

1. \((a_1,a_2,\ldots,a_n)\) is an \(n\)-tuple. A 2-tuple is called an ordered pair. Note that \((a,b)\neq(b,a)\) unless \(a=b\).


2. We denote \(A\times A\times\cdots\times A\) by \(A^n\).


3. \(|A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot |A_2|\cdots| A_n|\). In particular \(|A\times A\times\cdots\times A|=|A|^n\).

Example. Let \(A=\{a,b,c\}\) and \(B=\{1,2\}\). Then \[A\times B=\{(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)\}\] \[B\times A=\{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}\] Note that \(A\times B\neq B\times A\). But \(|A\times B|=|B\times A|=|A|\cdot|B|=3\cdot2=6\). \(B^2=B\times B=\{(1,1),(1,2),(2,1),(2,2)\}\) and \(|B^2|=|B|^2=2^2=4\).

Set Operations

Definition (Universe). When we study a particular kind of objects, the universe or universal set, denoted by \(U\), is the set of all such objects.

Example. When we study real numbers, \(U=\mathbb R\). So any set can be a universe depending on the objects under consideration.

Definition. (Complement). The complement of a set \(A\) in a universe \(U\), denoted by \(\overline{A}\) or \(A^c\), is defined by \[\overline{A}=\{x\in U\;|\;x\notin A\}.\]

Example. The complement of \(\mathbb Q\) in \(\mathbb R\) is the set of all irrational numbers.

Definition (Union). The union of two sets \(A\) and \(B\), denoted by \(A\cup B\), is the set of all elements that belong to either \(A\) or \(B\) or both. \[A\cup B=\{x\;|\;x\in A \text{ or } x\in B\}.\]

Example. Let \(A=\{a,b,c\}\) and \(B=\{1,2\}\). Then \(A\cup B=\{a,b,c,1,2\}\).

Definition (Intersection). The intersection of two sets \(A\) and \(B\), denoted by \(A\cap B\), is the set of all elements that belong to both \(A\) and \(B\). \[A\cap B=\{x\;|\;x\in A \text{ and } x\in B\}.\]

Example. Let \(A=\{0,2,4\}\) and \(B=\{1,2\}\). Then \(A\cap B=\{2\}\).

The principle of inclusion-exclusion computes \(|A\cup B|\) by avoiding double-counting.
Theorem (The principle of inclusion-exclusion). Let \(A,B\) be two sets in a universe \(U\). Then \[|A\cup B|=|A|+|B|-|A\cap B|.\]

Example. Let \(A=\{0,2,4\}\) and \(B=\{1,2\}\). Then \(|A\cup B|=|A|+|B|-|A\cap B|=3+2-1=4\).

Definition (Difference). The difference of two sets \(A\) and \(B\), denoted by \(A\backslash B\) or \(A-B\), is the set of all elements of \(A\) that are not in \(B\). \[A\setminus B=\{x\;|\;x\in A \text{ and } x\notin B\}.\]

Example. Let \(A=\{0,2,4\}\) and \(B=\{1,2\}\). Then \(A\backslash B=\{0,4\}\) and \(B\backslash A=\{1\}\).

Theorem. Let \(A,B\) be two sets in a universe \(U\). Then \(A\backslash B=A\cap \overline{B}\).

Theorem (Set identities). Let \(A,B\), and \(C\) be three sets in a universe \(U\). Then the following are true:

1. \(A\cup U=U\), \(A\cap U=A\).


2. \(A\cup \varnothing =A\), \(A\cap \varnothing=\varnothing\).


3. \(A\cup A=A\cap A=\overline{\overline{A}}=A\).


4. \(A\cup \overline{A}=U\), \(A\cap \overline{A}=\varnothing\).


5. \(A\cup B=B\cup A\), \(A\cap B=B\cap A\).


6. \(\overline{A\cup B}=\overline{A}\cap \overline{B}\) and \(\overline{A\cap B}=\overline{A}\cup \overline{B}\) (De Morgan's laws).


7. \(A\cup(B\cap C)=(A\cup B) \cap (A\cup C)\), \(A\cap(B\cup C)=(A\cap B) \cup (A\cap C)\).


8. \(A\times (B\cup C)=(A\times B) \cup (A\times C)\), \(A\times (B\cap C)=(A\times B) \cap (A\times C)\).

Last edited