3.1 Set theory

What is a set? By a set \(S\) we are to understand, according to Georg Cantor, “a collection into a whole, of definite, well-distinguished objects (called the ‘elements’ of \(S\)) of our perception or of our thought.”14 (Kamke 1950, 1)

A set is a collection of elements, without repetition and unordered. \(A\) is a subset of the set \(B\) if the elements of \(A\) are also elements of \(B\); \(B\) is therefore a superset of \(A\). (Iezzi and Murakami 1977, 19–A) point out that formally there is no definition for set, subset, element and membership, as these are considered primitive notions . Due to the variety of possible notations, the ISO 8000-2:2009 notation was chosen.

Let \(A\) be a set and \(a\) be an element of \(A\). \(a \in A\) symbolizes that \(a\) is an element of \(A\). If an element \(b\) is not an element of \(A\), write \(b \notin A\). A set \(A\) is a subset of the set \(B\) if all elements of \(A\) are also elements of \(B\), symbolized by \(A \subset B\) or \(B \supset A\).

Example 3.4 Consider the sets \(T\), \(M\) and \(F\) defined in Example 3.5.

Set-set Element-set
\(M \subset T\) \(a \in T\)
\(F \subset T\) \(a \in M\)
\(T \not\subset M\) \(a \notin F\)
\(T \not\subset F\) \(e \in T\)
\(F \not\subset M\) \(e \notin M\)
\(M \not\subset F\) \(e \in F\)

Definition 3.1 The cardinal of a set indicates its number of elements, denoted by \(|A|\).

Example 3.5 (Set, subset, element and cardinal) Suppose the set \(T\) formed by the students who participate in the university’s truco selection. You can note \[ T = \lbrace Aaron, Beatriz, Carlos, Denivaldo, Evelise \rbrace \equiv \lbrace a,b,c,d,e \rbrace. \] Each student player in the truco selection is a member of \(T\). The set \(T\) can be divided into two subsets, \[M = \lbrace a,c,d \rbrace \] and \[F= \lbrace b,e \rbrace. \] The boys are elements of \(M\), the girls are elements of \(F\), \(|T|=5\), \(|M|=3\) and \(|F|=2\).

3.1.1 Empty set

Empty set is a set with no elements, of zero cardinality and denoted by \(\lbrace \rbrace\) or \(\emptyset\). It usually indicates the result of an intersection operation (Section 3.1.2.2) where there are no elements in common between the considered sets.

3.1.2 Operations

The operations on sets are fundamental in Probability theory. A visual way to represent operations between sets is using the Venn diagram.

3.1.2.1 Union \(\cup\)

The union operation is represented by the symbol \(\cup\). Indicates that the new generated set must consider all elements of the sets involved in this operation. The union of a collection of sets is annotated by \[\begin{equation} \cup_{i=1}^{n} A_i = A_1 \cup A_2 \cup \cdots \cup A_n \tag{3.1} \end{equation}\]

Example 3.6 (Union) If \(A=\{1,2,3,4,5\}\) and \(B=\{2,4,6,8\}\), \[A \cup B = \{1,2,3,4,5,6,8\}\]

A <- 1:5
B <- c(2,4,6,8)
base::union(A,B)
## [1] 1 2 3 4 5 6 8
base::union(B,A) # unordered, same as union(A,B)
## [1] 2 4 6 8 1 3 5

3.1.2.2 Intersection \(\cap\)

The intersection operation is represented by the symbol \(\cap\). Indicates that the new set generated should only consider the elements that are common to the sets involved in this operation. The intersection of a collection of sets is denoted by \[\begin{equation} \cap_{i=1}^{n} A_i = A_1 \cap A_2 \cap \cdots \cap A_n = A_1 A_2 \cdots A_n \tag{3.2} \end{equation}\]

Example 3.7 (Intersection) Suppose again the sets \(A=\{1,2,3,4,5\}\) and \(B=\{2,4,6,8\}\). \[A \cap B = \{2,4\}\]

A <- 1:5
B <- c(2,4,6,8)
base::intersect(A,B)
## [1] 2 4

3.1.2.3 Complement \(A^C\)

The complement or absolute complement of the set \(A\) indicates that the new generated set should consider the elements that do not belong to \(A\). It will be represented by \(A^C=\Omega \backslash A\), where \(\Omega\) represents the set of all considered elements. It is associated with the word ‘no’ and can be formally described \[\begin{equation} A^C = \{ x \in \Omega : x \notin A \} \tag{3.3} \end{equation}\]

3.1.2.4 Difference \(B \backslash A\)

The difference or relative complement between the sets \(B\) and \(A\) is denoted by \(B \backslash A\) or \(B-A\). It can be read as ‘the elements that are in \(B\) but not in \(A\)’.

Example 3.8 (Difference) Assume again the sets \(A=\{1,2,3,4,5\}\) and \(B=\{2,4,6,8\}\). \[A \backslash B = \{1,3,5\}\] \[B \backslash A = \{6,8\}\]

A <- 1:5
B <- c(2,4,6,8)
base::setdiff(A,B)
## [1] 1 3 5
base::setdiff(B,A)
## [1] 6 8
Properties

Let \(A\) and \(B\) be two sets in a universe \(\Omega\).

\[\begin{equation} A \cup A^C = \Omega \tag{3.4} \end{equation}\]

\[\begin{equation} A \cap A^C = \emptyset \tag{3.5} \end{equation}\]

\[\begin{equation} \emptyset^C = \Omega \tag{3.6} \end{equation}\]

\[\begin{equation} \Omega^C = \emptyset \tag{3.7} \end{equation}\]

\[\begin{equation} \text{If} \;\; A \in B, \; \text{then} \;\; B^C \in A^C \tag{3.8} \end{equation}\]

\[\begin{equation} A \backslash B = A \cap B^C \tag{3.9} \end{equation}\]

\[\begin{equation} (A \backslash B)^C = A^C \cup B \tag{3.10} \end{equation}\]

\[\begin{equation} A^C \backslash B^C = B \backslash A \tag{3.11} \end{equation}\]

Involution \[\begin{equation} (A^C)^C = A \tag{3.12} \end{equation}\]

De Morgan’s Laws \[\begin{equation} (A \cup B)^C = A^C \cap B^C \tag{3.13} \end{equation}\]

\[\begin{equation} (A \cap B)^C = A^C \cup B^C \tag{3.14} \end{equation}\]

3.1.3 Power set

Power set of a set \(A\) is the set containing all subsets of \(A\), noted here by \(Po(A)\) . By definition the empty set \(\emptyset\) is a subset of \(Po(A)\). The cardinal of the set of parts is given by \(|Po(A)| = 2^{|A|}\).

Example 3.9 (Cardinal and power set) Let the set \(A = \left\lbrace -9, 0, 5 \right\rbrace\). It is known that \[ |A| = 3,\] \[ |Po(A)| = 2^{3} = 8 \] and \[ Po(A) = \left\lbrace \emptyset, \left\lbrace -9 \right\rbrace, \left\lbrace 0 \right\rbrace, \left\lbrace 5 \right\rbrace, \left\lbrace -9, 0 \right\rbrace, \left\lbrace -9, 5 \right\rbrace, \left\lbrace 0, 5 \right\rbrace, \left\lbrace -9, 0, 5 \right\rbrace \right\rbrace. \]

A <- c(-9,0,5)
length(A)
## [1] 3
(ps <- rje::powerSet(A))
## [[1]]
## numeric(0)
## 
## [[2]]
## [1] -9
## 
## [[3]]
## [1] 0
## 
## [[4]]
## [1] -9  0
## 
## [[5]]
## [1] 5
## 
## [[6]]
## [1] -9  5
## 
## [[7]]
## [1] 0 5
## 
## [[8]]
## [1] -9  0  5
length(ps)
## [1] 8

3.1.4 Disjoint sets and partition

Disjoint sets are those that have no elements in common. Equivalently, their intersection is the empty set. A partition is a grouping of the elements of a set into non-empty subsets such that each element is allocated in only one subset.

Example 3.10 (Disjoint set and partition) If people in a population (\(\Omega\)) are classified into male (\(M\)) and female (\(F\)), notated by \[\Omega = \{ M,F \} \] this division forms a possible partition of this population since \[ M \cup F = \Omega \] \[ M \cap F = \emptyset. \]

References

Cantor, Georg. 1895. “Beiträge Zur Begründung Der Transfiniten Mengenlehre.” Mathematische Annalen 46 (4): 481–512. https://link.springer.com/content/pdf/10.1007/BF02124929.pdf.
Iezzi, G., and C. Murakami. 1977. Fundamentos de Matemática Elementar 1: Conjuntos, Funções. SP Editora Atual. https://barbosadejesu.files.wordpress.com/2021/09/fundamentos-da-matematica-elementar-1-.pdf.
Kamke, Erich. 1950. Theory of Sets. Courier Corporation.

  1. Unter einer ‚Menge‘ verstehen wir jede Zusammenfassung \(M\) von bestimmten wohlunterschiedenen Objekten \(m\) unserer Anschauung oder unseres Denkens (welche die ‚Elemente‘ von \(M\) genannt werden) zu einem Ganzen.(Cantor 1895, 481)↩︎