10.28 Set

Elements of set theory

Definition

Set

a collection of objects

Belonging

\(x\) is an element of A (x belongs to A)

Notation: \(x\in A\), \(x\notin A\)

Comment

Formally, the element of a set are also sets. For example, \(\N_0=\{0,1,2,3,4,...\}\)

\(0=\emptyset,1=\{0\},2=\{0,1\},3=\{0,1,2\},\ldots\)

Remark

1. Some open proposition define sets \(P(x)\rightarrow\{x:P\left(x\right)\}\)

2. Sets are determined by their objects: \(A=B\equiv\left(\forall x\right)\left(x\in A\Leftrightarrow x\in B\right)\)​

Example

1. The multiple of 3: \(\{x:\exists k\in\mathbb{Z},x=3k\}=\{3k:k\in\mathbb{Z}\}=\{\ldots,-6,-3,0,3,6,\ldots\}\)

2. \(\{x:x\in\mathbb{R}\wedge x^3=x\}=\{-1,0,1\}\)​

Subset

Given sets A,B, we say that:

• A is a subset of B, in notation \(A\subseteq B\), if \((\forall x )(x\in A\Rightarrow x\in B)\)​
• A is a proper subset of B if \(A\subset B\)​

We write \(A\nsubseteq B\equiv\neg\left(A\subseteq B\right)\equiv\left(\exists x\right)\left(x\in A\wedge x\notin B\right)\)

Theorem

1. \(A\subseteq A\)

   Proof

   Let \(x\in A\). Since \(x\in A\Rightarrow x\in A\) is true, then \(A\subseteq A\)​

2. If \(A\subseteq B\wedge B\subseteq A\) then \(A=B\)​

   Proof

   Let \(x\in A\). Since \(A\subseteq B\) and \(x\in A\), we have \(x\in B\)

   Since \(B\subseteq A\) and \(x\in B\), we have \(x\in A\)

   We have proved that \(x\in A\Leftrightarrow x\in B\) is true for any \(x\).

   Thus \(A=B\)

3. If \(A\subseteq B\wedge B\subseteq C\) then \(A\subseteq C\)​

   Proof

   Let \(x\in A\). Since \(A\subseteq B\) and \(x\in A\), we have \(x\in B\)​

   Since \(B\subseteq C\) and \(x\in B\), we have \(x\in C\)

   We have proved that \(x\in A\Rightarrow x\in C\) is true for any \(x\).

   Thus \(A\subseteq C\)​

Empty set

\(\emptyset=\{x:x\neq x\}\) is a set called the empty set

Property

• \(\empty\) has no element
• If \(A\) is another set with no element, then \(A=\empty\)

Theorem

\(\empty \subseteq A\) for any \(A\)

Proof

We have to prove that for any \(x\), \(x\in\empty\Rightarrow x\in A\) is true.

The condition of \(x\in\empty\) is false, then the proposition is always true.

Power set

Given a set \(A\), we define \(\wp(A)=\{B:B\subseteq A\}\)

This is a set called the power set of \(A\)

Example

\(A=\{\{1,2,3\},\{4,5\},6\}\)

This set has 3 elements: \(\{1,2,3\},\{4,5\},6\)

Note: \(\{4,5\}\nsubseteq A\)

Remark

• Sets of 0 elements: \(\emptyset\)​
• Subsets of 1 element: \(\{\left\lbrace1,2,3\right\rbrace\},\{\left\lbrace4,5\right\rbrace\},\{\left.6\right\rbrace\)
• Subsets of 2 element: \(\{\left\lbrace1,2,3\right\rbrace,\left\lbrace4,5\right\rbrace\},\{\left\lbrace1,2,3\right\rbrace,6\}\),\(\left\lbrace\left\lbrace4,5\right\rbrace,6\right\rbrace\)
• Subsets of 3 elements: \(\left\lbrace\left\lbrace1,2,3\right\rbrace,\left\lbrace4,5\right\rbrace,6\right\rbrace=A\)

\(P(A)=\{\emptyset,\left\lbrace\left\lbrace1,2,3\right\rbrace\right\rbrace,\{\left\lbrace4,5\right\rbrace\},\{6\},\left\lbrace\left\lbrace1,2,3\right\rbrace,\left\lbrace4,5\right\rbrace\right\rbrace,\{\left\lbrace1,2,3\right\rbrace,6\},\left\lbrace\left\lbrace4,5\right\rbrace,6\right\rbrace,\left\lbrace\left\lbrace1,2,3\right\rbrace,\left\lbrace4,5\right\rbrace,6\right\rbrace\}\) Observation: \(P(A)\) has \(8=2^3\) elements

Theorem

If \(A\) has \(n\) elements, then \(P(A)\) has \(2^n\) elements

Proof

Let \(a_1,a_2,...,a_n\) be the elements of \(A\)

To define a subset \(B\subseteq A\), we have to tell whether \(a_1\in B\) or \(a_1\notin B\) 2 possibilities

\(a_2\in B\) or \(a_2\notin B\) 2 possibilities ... \(a_n\in B\) or \(a_n\notin B\) 2 possibilities

So the number of possibilities for \(B\) is \(2\cdot 2\cdot 2\cdot...\cdot 2=2^n\)

Set operation

Let A,B be sets. We define:

• \(A\cup B=\{x:x\in A\vee x\in B\}\) union of \(A\) and \(B\)​
• \(A\cap B=\{x:x\in A\wedge x\in B\}\) intersection of \(A\) and \(B\)
• \(B-A=\{x:x\in B\wedge x\notin A\}\) difference between \(B\) and \(A\)​

Observation: \(B-A=B-(A\cap B)\)

Proof: Let \(x\in B-A\), then \(x\in B\) and \(x\notin A\). Then \(x\notin A\cap B\)

From \(x\in B\) and \(x\notin A\cap B\), we obtain \(x\in B-(A\cap B)\)

Conversely, Let \(x\in B-(A\cap B)\). Then \(x\in B\) and \(x\notin A\cap B\Rightarrow x\notin A\cup x\notin B\)

Then \(x\notin A\). From \(x\in B\) and \(x\notin A\), we get \(x\in B-A\)

Example

\(3\mathbb{Z}-2\mathbb{Z}\) (multiple of 3 - multiple of 2)\(=3\Z-(3\Z\cap 2\Z)=3\Z-6\Z=\{...,-15,-9,-3,3,9,15,...\}\)​\(=\{x:x=3+6k\text{ for some }k\in\Z\}\)

Theorem

• \(A\cup A=A\)
• \(A\cap A=A\)​
• \(A\cap \emptyset =\emptyset\)​
• \(A\cup\emptyset=A\)
• \(A-\emptyset=A\)​
• \(\emptyset -A=\empty\)​
• \(A\subseteq A\cup B\)​
• \(A\cap B\subseteq A\)​
• \(A\cup B=B\cup A\)​
• \(A\cap B=B\cap A\)​
• \(A\subseteq B\) iff \(B=A\cup B\) iff \(A=A\cup B\)​
• \(\begin{aligned} A \cap (B \cap C) = (A \cap B) \cap C \quad &\text{(associativity)} \end{aligned}\)
• \(A \cup (B \cup C) = (A \cup B) \cup C\)
• \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
• \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
• \(A \subseteq B \Rightarrow A \cup C \subseteq B \cup C\)
• \(A \subseteq B \Rightarrow A \cap C \subseteq B \cap C\)

---

Proof of \(A \subseteq B \iff B = A \cup B\).

We first prove \(A \subseteq B \Rightarrow B = A \cup B\).

Assume \(A \subseteq B\). We know \(B \subseteq A \cup B\). On the other hand, let \(x \in A \cup B\).

Then \(x \in A \vee x \in B\). If \(x \in A\), then we use \(A \subseteq B\) and get \(x \in B\).

If \(x \in B\), then \(x \in B\). Hence \(x \in B\). So \(A \cup B \subseteq B\).

Then from \(B \subseteq A \cup B\) and \(A \cup B \subseteq B\), we get \(B = A \cup B\).

We now prove \(B = A \cup B \Rightarrow A \subseteq B\). If \(B = A \cup B\), by a previous property \(A \subseteq A \cup B = B\).

and so \(A \subseteq B\).

‍

Proof of \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\).

\(x \in A \cap (B \cup C) \iff x \in A \land x \in B \cup C \iff x \in A \land (x \in B \vee x \in C)\)

\(\iff (x \in A \land x \in B) \vee (x \in A \land x \in C)\)

\(\iff x \in (A \cap B) \cup (A \cap C)\)

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

The universe set

Usually, we work with sets that are subsets of a large set called the universal set.

Given \(A \subseteq U\) (universal set),

we define \(A^c = \{ x : x \in U \land x \notin A \} = U - A\).

Risk: \(A^c\) doesn't make sense if you don't fix a universe.

Example

• \((2\mathbb{Z})^c = \{\text{odd numbers}\}\), if the universe is \(\mathbb{Z}\).
• \((2\mathbb{Z})^c = \dots \cup (-2,0) \cup (0,2) \cup (2,4) \cup (4,6) \cup \dots\), if the universe is \(\mathbb{R}\).

Properties

Fix a universe \(U\).

• \(U^c = \emptyset\) and \(\emptyset^c = U\).
• \((A^c)^c = A\).
• \(A \cap A^c = \emptyset\).
• \(A \cup A^c = U\).
• \((A \cap B)^c = A^c \cup B^c\).

• \((A \cup B)^c = A^c \cap B^c\).

• \(A \subseteq B \iff B^c \subseteq A^c\)

Proof

Let \(x\in B^{c}\Rightarrow x\in U-B\Rightarrow x\in U\wedge x\notin B\Rightarrow x\in U\wedge x\notin A\Rightarrow\ldots\Rightarrow x\in A^{c}\)​ * \(B - A = B \cap A^c\)

Cartesian Product

Definition

Ordered pair

Fix \(A, B\). Let \(a \in A\) and \(b \in B\).

Then \(\{a\}\), \(\{a, b\}\) are sets.

Define \((a, b) = \{\{a\}, \{a, b\}\}\). This is a set called an ordered pair.

Theorem

\((a, b) = (a', b') \iff a = a' \text{ and } b = b'\).

Proof

\(\Rightarrow\)) \((a,b)=\{\{a\},\{a,b\}\}=(a^{\prime},b^{\prime})=\{\{a^{\prime}\},\{a^{\prime},b^{\prime}\}\}\), then we have two cases.

1. \(\{a\}=\{a'\}\) and \(\{a,b\}=\{a^{\prime},b^{\prime}\}\)​

   Then we have \(a=a'\) and \(b=b'\)​

2. \(\{a\}=\{a^{\prime},b^{\prime}\}\) and \(\{a,b\}=\{a^{\prime}\}\)

   Impossible

\(\Leftarrow\)) If \(a=a'\), then \(\{a\}=\{a'\}\) and if \(b=b'\), then \(\{b\}=\{b^{\prime}\}\Rightarrow\{a,b\}=\{a,b^{\prime}\}\Rightarrow\{a,b\}=\{a^{\prime},b^{\prime}\}\)

Thus \((a,b)=(a^{\prime},b^{\prime})\)​

Cartesian Product

Define: \(A \times B = \{(a, b) : a \in A \text{ and } b \in B\}\)

This is called the Cartesian product of \(A\) and \(B\).

Example

Let \(A = \{-1, 0, 1\}\) and \(B = [-1, 1]\).

Then: \(A\times B=\{(-1,a):a\in[-1,1]\}\cup\{(0,a):a\in[-1,1]\}\cup\{(1,a):a\in[-1,1]\}.\)​

\((-\frac12,0)\notin A\times B\)

More definition

We can also define \(A \times B \times C = \{(a, b, c) : a \in A, b \in B, c \in C\}\).

\((a, b, c) = (a', b', c') \iff a = a', b = b', c = c'\)

Notation

• \(A \times A = A^2\).
• \(A \times A \times A = A^3\).
• \(\dots\)
• \(A \times \cdots \times A = A^n = \{(a_1, \dots, a_n) : a_i \in A\}\).

Theorem

• \(A \times (B \cup C) = (A \times B) \cup (A \times C)\).
• \(A \times (B \cap C) = (A \times B) \cap (A \times C)\).
• \(A \times \emptyset = \emptyset\).
• \((A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)\).

Working with Indexed Families of Sets

Let \(\mathcal{A}\) be a family of sets. We can define:

• \(\begin{aligned}\bigcup_{A\in\mathcal{A}}A=\{x:x\in A\text{ for some }A\in\mathcal{A}\}\end{aligned}\).
• \(\begin{aligned}\bigcap_{A\in\mathcal{A}}A=\{x:x\in A\text{ for all }A\in\mathcal{A}\}\end{aligned}\).

Sometimes, members of a family are indexed by another set. Let \(\Delta\) be a set and suppose that for \(\alpha \in \Delta\) we have a set \(A_\alpha\)

Then:
​\(\begin{aligned}\bigcup_{\alpha\in\Delta}A_{\alpha}=\{x:x\in A_{\alpha}\text{ for some }\alpha\in\Delta\}\end{aligned}\)

\(\begin{aligned}\bigcap_{\alpha\in\Delta}A_{\alpha}=\{x:x\in A_{\alpha}\text{ for all }\alpha\in\Delta\}\end{aligned}\)

Example

Let \(A_n = \left[-\frac{1}{n}, \frac{1}{n}\right]\)

Then
​\(\begin{aligned}\bigcap_{n \in \mathbb{N}} A_n = \{ x : x \in \left[-\frac{1}{n}, \frac{1}{n}\right] \, \forall n \in \mathbb{N} \} = \{0\}\end{aligned}\)
​\(\begin{aligned}\bigcup_{n \in \mathbb{N}} A_n = [-1, 1]\end{aligned}\)

We can prove the properties satisfied by the union and intersection of two sets.

Exercise

\(\begin{aligned}A \cap \left( \bigcup_{\alpha \in \Delta} B_\alpha \right) = \bigcup_{\alpha \in \Delta} (A \cap B_\alpha)\end{aligned}\)

Proof

\(\begin{aligned}A\cap\bigcup_{\alpha\in\Delta}B_{\alpha}=A\cap\{x:x\in B_{\alpha}\text{ for some }\alpha\in\Delta\}\end{aligned}\)

Then \(x\in A\text{ and }x\in B_{\alpha}\text{ for some }\alpha\in\Delta\Rightarrow x\in A\cap B_{\alpha}\text{ for some }\alpha\in\Delta\Rightarrow\bigcap_{\alpha\in\Delta}(A\cup B_{\alpha})\)​

Thus \(\begin{aligned}A \cup \left( \bigcap_{\alpha \in \Delta} B_\alpha \right) = \bigcap_{\alpha \in \Delta} (A \cup B_\alpha)\end{aligned}\)

‍