Basics of Sets |
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.
Example.
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?
Some standard sets and their notation:
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.
Remark.
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.
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:
Last edited