Sets #
A set is an unordered collection of members or elements. It has no other properties besides the elements it contains.
A set is written with curly braces: \(\{1, 2, 3\}\) . It has no duplicates: \(\{1, 2, 2, 3\}\) is not a valid set. It has no order: \(\{1, 2, 3\}\) is equal to \( \{3, 2, 1\}\) .
Sets can be members of other sets! \(\{\{1, 2\}, 1, 2\}\) is a valid set. The empty set is a set with no members: \(\{\}\) or \(\emptyset\) .
Cardinality is the number of elements in a set. \(|\{1, 2, 3\}| = 3\) . The cardinality of the empty set is 0: \(|\emptyset| = 0\) . Note that the cardinality of \(\{\emptyset\}\) is still 1! The empty set is still a set, after all.
The universal set is just everything. It’s the set of all sets. It’s usually written with a capital \(\mathbb{U}\) . The cardinality of the universal set is infinite.
A sequence is a collection of objects with that has an order and a length instead of cardinality. Both sets and sequences can contain anything, including other sets and sequences, and are immutable – they cannot be modified.
Comparing Sets #
- \(\in\) means “is an element of”: \(A \in B\) means \(A\) is an element of \(B\) .
- \(\subseteq\)
means “is a subset of”: \(A \subseteq B\)
means all elements of \(A\)
are in \(B\)
.
- Think of it as the \(\le\) of sets.
- \(\subset\)
means “is a proper subset of”: \(A \subset B\)
means all elements of \(A\)
are in \(B\)
and \(A\)
is not equal to \(B\)
.
- Think of it as the \(<\) of sets.
- \(\supseteq\)
means “is a superset of”: \(A \supseteq B\)
means all elements of \(B\)
are in \(A\)
.
- Think of it as the \(\ge\) of sets.
- \(\supset\)
means “is a proper superset of”: \(A \supset B\)
means all elements of \(B\)
are in \(A\)
and \(A\)
is not equal to \(B\)
.
- Think of it as the \(>\) of sets.
Set Operations #
- \(\cup\)
means “union”: \(A \cup B\)
means the set of all elements in \(A\)
or \(B\)
.
- \(A \cup \emptyset = A\)
- \(A \cup \mathbb{U} = \mathbb{U}\)
- \(A \cup A = A\)
- \(A \cup B = B \cup A\)
- \(\cap\)
means “intersection”: \(A \cap B\)
means the set of all elements in \(A\)
and \(B\)
.
- \(A \cap \mathbb{U} = A\)
- \(A \cap \emptyset = \emptyset\)
- \(A \cap A = A\)
- \(A \cap B = B \cap A\)
- \(\setminus\) means “set difference”: \(A \setminus B\) means the set of all elements in \(A\) but not in \(B\) .
- \(\bar{A}\) means “complement of \(A\) ”: it’s all the elements in the universe that don’t belong to \(A\) .
- \(A \times B\) is the Cartesian product of the two sets: it’s the set of all possible ordered pairs (sequence of two elements) where the first item in the pair is from \(A\) and the second is from \(B\) .
Set-Builder Notation #
Set-builder notation often takes this form:
\[S = \{x \in A|x > 5\}\]The first half means “the set of all \(x\) in \(A\) ”. The vertical bar means “such that”. The second half means “ \(x\) is greater than 5”. Putting it all together, we get “the set of all \(x\) in \(A\) such that \(x\) is greater than 5”.
Our formal set operators in set-builder notation are:
- \(\land\) for “and”
- \(\lor\) for “or”
- \(\neg\) for “not”
We could formally define \(S \cap T\) in set-builder notation as \(\{x \in \mathbb{U} | x \in S \land x \in T\}\) .
The power set of a set \(A\) is the set of all possible subsets of \(A\) . It’s denoted \(\mathbb{P}(A)\) . In set-builder notation, it’s expressed as \(\{x | x \subseteq A\}\) . For example, \(\mathbb{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\) .
Two sets are disjoint if their intersection is the empty set. For example, \(\{\text{New York, Washington}\}\) is disjoint with \(\{3, 4\}\) . The empty set is disjoint with every set, including itself.