1.1. Sets

A set is a collection of objects, which are the elements of the set.

 

x is an element of S, $$x\in S$$

x is not an element of S, $$x\notin S$$

S have no elements, empty set : $$\emptyset$$

---

Finite, Countably infinite, uncountable

 

If \(S\) contains a finite number of elements, \(S\) is finite; $$S = \{x_1, x_2, \cdots, x_n\}.$$

 

If \(S\) contains infinitely many elements, \(S\) is countably infinite; $$S = \{x_1, x_2, \cdots\}.$$

 

The set of all \(x\) that have a certain property \(P\); \(\{x | x  \text{ satisfies }  P\}\)

 

If \(S\) takes a continuous range of values, and cannot be written down in a list, \(S\) is uncountable.

 

---

Def.

If every element of a set \(S\) is also an element of a set \(T\), \(S\) is a subset of \(T\).

\(S\subset T\) or \(T\supset S\)

 

If \(S\subset T\) and \(T\subset S\), the two sets are equal, \(S\) = \(T\).

 

A universal set, denoted by \(\Omega\), contains all objects that could conceivably be of interest in a particular context.

---

Set Operations

 

Complement, Union, Intersection

 

The complement of a set S is the set \( \{ x \in \Omega | x \notin S\} \) of all elements of \(\Omega\) that do not belong to S, and is denoted as \(S^c\).

Note. \(\Omega^c = \emptyset\).

 

The union of two sets S and T is the set of all elements that belong to S or T (or both), and is denoted by \(S \cup T\).

$$S \cup T = \{ x \ | \ x \in S \ \text{or} \ x \in T \}$$.

 

The intersection of two sets S and T is the set of all elements that belong to both S and T, and is denoted by \(S \cap T\).

$$S \cap T = \{ x \ | \ x \in S \ \text{and} \ x \in T \}$$.

---

The union or the intersection of several, even infinitely many sets;

ex) for every positive integer \(n\), we are given a set \(S_n\),

$$\bigcup^{\infty}_{n=1} S_n = S_1 \cup S_2 \cup \cdots = \{x \ | \ x \in S_n \text{ for some } n \}.$$

$$\bigcap^{\infty}_{n=1} S_n = S_1 \cap S_2 \cap \cdots = \{x \ | \ x \in S_n \text{ for all } n \}.$$

 

---

Disjoint, Partition

Several sets are said to be disjoint, if no two of them have a common element.

A collection of sets is said to be a partition of a set S, if the sets in the collection are disjoint and their union is S.

---

Exaples of Venn diagrams.

(a) The shaded region is \(S \cap T\).

(b) The shaded region is \(S \cup T\).

(c) The shaded region is \(S \cap T^c\).

(d) \(T \in S\). The shaded region is \(S^c\).

(e) The sets S, T, and U are disjoint.

(f) The sets S, T, and U form a partition of the set \(\Omega\).

 

---

The Algebra of Sets

 

Properties of set operations

• \(S \cup T = T \cup S\)
• \(S \cup (T \cup U) = (S \cup T) \cup U\)
• \(S \cap (T \cup U) = (S \cap T) \cup (S \cap U)\)
• \(S \cup (T \cap U) = (S \cup T) \cap (S \cup U)\)
• \((S^c)^c = S\)
• \(S \cap S^c = \emptyset\)
• \(S \cup \Omega = \Omega\)
• \(S \cap \Omega = S\)

De Morgan's laws:

 

$$(A \cup B)^c = A^c \cap B^c$$

$$(A \cap B)^c = A^c \cup B^c$$

De Morgan's laws

 

$$\left( \bigcup_{n} S_n \right)^c = \bigcap_n S^c_n, \text{        } \left( \bigcap_n S_n \right)^c = \bigcup_n S^c_n.$$

 

---

\(x \in (\cup_n S_n)^c\).

Then \(x \notin \cup_n S_n\), which implies that for every n, we have \( x \notin S_n\).

Thus, x belongs to the complement of every \(S_n\);  \(x \in \cap_n S_n^c\)

 

 

---

References

Bertsekas, D. P., Tsitsiklis, J. N. (2008). Introduction to Probability Second Edition. Athena Scientific.

De Morgan's laws: [이산수학]드 모르간(De-Morgan) 법칙이란? (tistory.com)