Sets and Tuples
Definition: Set
A set is any unordered, well-defined collection of distinct objects. A set is completely identified by its members, which are called elements of the set.
Notation: Elementhood
For any object \(x\) and set \(X\), we denote that \(x\) is an element of \(X\) by
\[x \in X\]or
\[X \ni x\](though this is more often read as “\(X\) contains \(x\)”), and we denote that \(x\) is not a member of \(X\) by
\[x \notin X\]or
\[X \not\ni x\](though, again, this is more often read as “\(X\) does not contain \(x\)”).
Roster Notation
If all elements of a set can be enumerated, that set can simply be denoted by a list, enclosed by curly braces, of all its elements, where elements are separated by commas. For example, the set of all objects my friend listed when asked to list some distinct objects could be denoted
\[\{\text{stools},\text{leggings},\text{paperclips},\text{Ford Fiestas}\}.\]Set-Builder Notation
For any statement \(P\),
\[\{x \mid P\}\]denotes the set of all objects \(x\) such that \(P\). We also write
\[\{x \in X \mid P\}\]to denote
\[\{x \mid x \in X \wedge P\},\] \[\{X \ni x \mid P\}\]to denote
\[\{X \mid X \ni x \wedge P\},\]and similarly for
\[\{x \notin X \mid P\}\]and
\[\{X \not\ni x \mid P\}.\]Notation: Quantifiers and Elementhood
For any statement \(P\),
\[\exists x \in X \colon P\]denotes
\[\exists x \mid x \in X \colon P,\] \[\exists X \ni x \colon P\]denotes
\[\exists X \mid X \ni x \colon P,\]and similarly for \(x \notin X\) and \(X \not\ni x\), and similarly for \(\exists!\) and \(\forall\).
Definition: Empty Set
The empty set is defined as
\[\varnothing \coloneqq \{\}.\]Definition: Subset
For any sets \(X,Y\),
\[X \subseteq Y,\] \[Y \supseteq X\]denote that \(X\) is a subset of \(Y\) (\(Y\) is a superset of \(X\)), i.e.,
\[\forall x \in X \colon x \in Y;\]and
\[X \subset Y,\] \[Y \supset X\]denote that \(X\) is a proper subset of \(Y\) (\(Y\) is a proper superset of \(X\)), i.e.,
\[X \subseteq Y \wedge X \neq Y.\]Theorem: \(\varnothing\) Is a Subset of All Sets
\[\forall X \mid X \text{ is a set} \colon \varnothing \subseteq X.\]Proof. For any set \(X\),
\[\begin{align*} &\neg\exists x \colon x \in \varnothing &&\text{by }\href{/foundations/sets-and-tuples#definition-empty-set}{\text{Definition: Empty Set}}\\ \implies &\neg\exists x \mid x \in \varnothing \colon x \notin X &&\because \text{there exists no } x \text{ in } \varnothing \text{ at all}\\ \iff &\forall x \mid x \in \varnothing \colon x \in X &&\text{by }\href{/foundations/basic-logic#notation-quantifiers}{\text{Notation: Quantifiers}}\\ \iff &\forall x \in \varnothing \colon x \in X &&\text{by }\href{/foundations/sets-and-tuples#notation-quantifiers-and-elementhood}{\text{Notation: Quantifiers and Elementhood}}\\ \iff &\varnothing \subseteq X &&\text{by }\href{/foundations/sets-and-tuples#definition-subset}{\text{Definition: Subset}}\text{.} \end{align*}\]Definition: Intersection
For any sets \(X,Y\),
\[X \cap Y \coloneqq \{x \mid x \in X \wedge x \in Y\}\]is called the intersection of \(X\) and \(Y\).
Definition: Union
For any sets \(X,Y\),
\[X \cup Y \coloneqq \{x \mid x \in X \vee x \in Y\}\]is called the union of \(X\) and \(Y\).
Definition: Set Difference
For any sets \(X,Y\),
\[X \backslash Y \coloneqq \{x \in X \mid x \notin Y\}\]is called the difference of \(X\) and \(Y\).
Definition: Tuple
A tuple or ordered tuple is any ordered collection of finitely many objects, called elements of the tuple. Any tuple with elements \(x_1,x_2,x_3,...,x_n\) (in that order) can be denoted by
\[(x_1,x_2,x_3,...,x_n).\]A tuple with \(n\) elements can also be called an \(n\)-tuple. A 2-tuple can also be called a pair, and a 3-tuple can also be called a triple.
Definition: Cartesian Product
For any finite number of sets \(X_1,X_2,X_3,...,X_n\), the Cartesian product of those sets is defined as
\[X_1 \times X_2 \times X_3 \times \cdots \times X_n \coloneqq \{(x_1,x_2,x_3,...,x_n) \mid x_1 \in X_1 \wedge x_2 \in X_2 \wedge x_3 \in X_3 \wedge \cdots \wedge x_n \in X_n\}.\]