Sets
- Tags
- logic
Is an orderless collection which is defined solely by the [see page 22, objects] it contains, all of which share some property (a logical proposition).
Set theory was initially used to [see page 18, explore] and answer questions about infinities.
There are infinitely many orders of infinities.
Notationally a set is enclosed in curly brackets and has a comma separated list of values. For example: \( \{\text\{false\}, \text\{true\}\} \), \( \{3, 7, 14\} \), or \( \{\text\{red\}, \text\{blue\}, \text\{yellow\}\} \). When the values are too exhaustive we can use ellipses (\( \{1,2,3,4,5 \ldots \} \)) or the recommended [see page 24, set-builder] notation: \( \{variable: proposition involving the variable\} \).
For a set \( S \). We define the cardinality of \( S \) as the number of items in the set, denoted by \( |S| \) or \( \#S \). The fundamental relationship between a set and its objects is membership. An object is either in or not in the set. This is denoted by the \( \in \) symbol, or if not present then \( \not \in \) or \( \ni \).
Two sets are said to be [see page 27, equal] if they both contain all the same elements (note: order and repeated elements is irrelevant). To prove two sets are not equivalent you must find a witness, an element that is in one set but not the other. Its also sufficient to show the two sets have a different cardinality (proving one set has at least one element the other lacks).
| Symbol | Definition | Name |
|---|---|---|
| \( \varnothing \) | \( \{\} \) | The Empty Set |
| \( B \) | \( \{ 0, 1 \} \) | Binary Digits |
| \( N \) | \( \{ 0, 1, 2, 3, \ldots \} \) | Natural Numbers |
| \( Z \) | \( \{ \ldots, -1, 0, 1, \ldots \} \) | Integers |
| \( Q \) | \( \{ \frac{m}{n} : m, n \in Z, n \neq 0 \} \) | Rationals |
| \( R \) | \( \{ x : x \; \text{is a real number} \} \) | Reals |
A set can also be defined as a collection of other sets and a set is not the same as its elements. For example \( \varnothing \) is not the same as \( \{ \varnothing \} \), because \( |\varnothing| = 0 \) but \( |\{ \varnothing \}| = 1 \), however \( \varnothing \in \{ \varnothing \} \) is true.
Set Operations
| Rule | LHS | RHS |
|---|---|---|
| Commutativity | \( A \cup B \) | \( B \cup A \) |
| Associativity | \( A \cup (B \cup C) \) | \( (A \cup B) \cup C \) |
| \( A \cap (B \cap C) \) | \( (A \cap B) \cap C \) | |
| Idempotence | \( A \cup A \) | \(A\) |
| \( A \cap A \) | \( A \) | |
| Distributivity | \( A \cup (B \cap C) \) | \( (A \cup B) \cap (A \cup C) \) |
| \( A \cap (B \cup C) \) | \( (A \cap B) \cup (A \cap C) \) | |
| De Morgan's Law | \( \overline{(A \cup B)} \) | \( \overline{A} \cap \overline{B} \) |
| \( \overline{(A \cap B)} \) | \( \overline{A} \cup \overline{B} \) | |
| Double Complement Law | \( \overline{\overline{A}} \) | \( A \) |
| Universe Laws | \( A \cup \mathcal{U} \) | \( \mathcal{U} \) |
| \( A \cap \mathcal{U} \) | \( A \) | |
| Empty Set Laws | \( A \cup \varnothing \) | \( A \) |
| \( A \cap \varnothing \) | \( \varnothing \) | |
| Complement Laws | \( A \cup \overline{A} \) | \( \mathcal{U} \) |
| \( A \cap \overline{A} \) | \( \varnothing \) | |
| Absorption Laws | \( A \cup (A \cap B) \) | \( A \) |
| \( A \cap (A \cup B) \) | \( A \) |