2 Sets and elements

A set is, essentally, a collection of elements. An element can be anything. In the usual notation, the name of a set is capitalized, whereas the name of an element is usually in lowercase. We can define a set of primary colors as follows:

$\rm {PrimaryColors} = \{ \rm {red}, \rm {green}, \rm {blue} \}$

The curly braces $\{\}$ are used to indicate the beginning and ending of elements in a set.

There is a special set called an ``empty set''. An empty set is, as the name implies, a set with no elements. It is denoted as $\{\}$ or $\emptyset$ .

A set can be finite (with a finite number of elements) or infinite (with an infinite number of elements). For a finite set $S$ , $\vert S\vert$ denotes the number of elements in $S$ .

You can also indicate the elements in a set using a predicate. Let $R(x)$ be a predicate (we avoid the use of $P$ in this module). Then $S = \{x \vert R(x)\}$ means that all elements in $S$ make the predicate $R(x)$ true. However, it also means that all possible values that makes $R(x)$ true are also in $S$ . In other words, $(\forall x \in S: R(x)) \wedge (\forall y: R(x) \rightarrow (x \in S))$ . There is a shorter way to describe this: $\forall x: (x \in S) \leftrightarrow R(x)$ . In English, this means that a value $x$ is in $S$ if and only if (iff) $R(x)$ is true.

For example, $\{x\vert(x \in I) \wedge (0 < i < 5)\}$ produces the set $\{1, 2, 3, 4\}$ .

Elements in a set must follow two rules. First, order is not important in a set. This means that $\{\rm {red}, \rm {green}, \rm {blue}\} = \{\rm {red}, \rm {blue}, \rm {green}\}$ . Note that elements in a set may have ordered relationship, such as $\{1, 3, 5\}$ , however, it doesn't matter how the elements are listed.

Second, elements in a set must be unique. In other words, a set cannot have two duplicate elements.

You can relate an element to a set using the ``element of'' (also known as ``in'') relationship. This relationship is represented by the $\in$ symbol. $e \in S$ means that $e$ is an element of $S$ , or simply $e$ is in $S$ . In our primary colors example, $\rm {red} \in \rm {PrimaryColors}$ is true, whereas $\rm {purple} \in \rm {PrimaryColors}$ is false.

Two sets can be related by the following relationships:

• $S \subset T$ means that $S$ is a proper subset of $T$ . This means that $(\forall x \in S: x \in T) \wedge (\exists y \in T: \neg(x \in S))$ . In English, it means that (all elements in S can be found in T) and (there exists an element in T that cannot be found in S).
• $S \supset T$ means that $S$ is a proper superset of $T$ . This relationship is equivalent to $T \subset S$ .
• $S \subseteq T$ means that $S$ is a subset (note the lack of proper) of $T$ . In symbols, this means that $\forall x \in S: x \in T$ .
• $S \supseteq T$ means $T \subseteq S$ .
• $S = T$ means that $S$ and $T$ are the same. Note that $(S = T) \equiv ((S \subseteq T) \wedge (T \subseteq S))$ .

Set $S$ and $T$ such that $S \cap T = \emptyset$ are said to be disjoint. Assuming $X_1, X_2, \ldots X_n$ are disjoint from each another, $\{X_1,\ldots X_n\}$ is called a partition of the set $\bigcup_{i=1}^{n} X_i$ . Each $X_i$ is also called a ``block''. For a given set, the number of possible partitions is called a Bell number.