Chapter 2 Set theory
2.1 Fundamentals
Definition 2.1 (Informal) We define a set A to be any unordered collection of objects. If \(x\) is an object, we say that \(x\) is an element of \(A\) or \(x\in A\) if \(x\) lies in the collection; other wise, we say that \(x \not\in A\).
However, which collections of objects are considered to be sets? Which sets are equal to other sets? How one defines operations on sets? We need some axioms to illustrate these problems.
Axiom 3.1 (Set are objects) If \(A\) is a set, then \(A\) is also an object.
Remark 3.1.3 Comments on pure set theory from a logical point of view and a conceptual point of view respectively.
Definition 2.2 (Equality of sets) Two sets \(A\) and \(B\) are equal iff every element in \(A\) is an element in \(B\) and vice versa.
The definition is well-defined, i.e., it obeys the axiom of substitution, see Chapter 11.
Axiom 3.2 (Empty set) There exists a set \(\varnothing\), known as the empty set, which contains no elements, i.e., for every object \(x\) we have \(x \not\in \varnothing\).
There is only one singleton set for each object \(a\), and there is only one pair set formed by \(a\) and \(b\) thanks to Definition 2.2. Also, Definition 2.2 ensures that \(\{a,b\} = \{b,a\}\) and \(\{a,a\} = \{a\}\). Thus the singleton set axiom is in fact redundant, being a consequence of the pair set axiom.
Lemma 2.1 (Single choice) Let \(A\) be a non-empty set. Then there exists an object \(x\) such that \(x\in A\).
The proof is quite easy once with the concept of “vacuously true”, see Chapter 11.
Remark 3.1.8 Similarly, for finite number of non-empty sets, we have “finite choice” (2.5), and for an infinite number of sets, we need an additional axiom, the axiom of choice, see Chapter 7.
Axiom 3.3 (Singleton sets and pair sets) If \(a\) is an obiect, then there exists a set \(\{a\}\) whose only element is \(a\), i.e., for every object \(y\), we have \(y \in \{a\}\) iff \(y = a\); we refer to \(\{a\}\) as the singleton set whose element is \(a\). Furthermore, if \(a\) and \(b\) are object, then there exists a set \(\{a,b\}\) whose only elements are \(a\) and \(b\); i.e., for every object \(y\), we have \(y\in \{a,b\}\) iff \(y=a\) or \(y=b\); we refer to this set as thepair set formed by \(a\) and \(b\).
Axiom 3.4 (Pairwise union) Given any two sets \(A,B\), there exists a set \(A\cup B\), called the union \(A\cup B\) of \(A\) and \(B\), whose elements consists of all the elements which belongs to \(A\) or \(B\) or both. In other words, for any object \(x\), \[ x\in A\cup B \iff (x\in A\ \ or\ \ x\in B ). \]
Lemma 2.2 if \(a\) and \(b\) are objects, then \(\{a,b\} =\{a\} \cup \{b\}\). If \(A,B,C\) are sets, then the union operation is commutative and associative. Also, we have \(A\cup A = A\cup \varnothing = \varnothing \cup A = A\) .
Since the union operation is associative, we can now define ${a,b,c} := {a}{b} {c} $ if \(a,b,c\) are three objects; if \(a,b,c,d\) are four objects, then we define \(\{a,b,c,d\} := \{a\}\cup \{b\} \cup \{c\} \cup \{d\}\), and so forth.
Definition 2.3 (Subsets) Let \(A,B\) be sets. We say that \(A\) is a subset of \(B\), denote \(A\subseteq B\). iff every element of \(A\) is also an element of \(B\) i.e. \[ \text{For any object }x,\quad x\in A \Longrightarrow x\in B. \] We say that \(A\) is a proper subset of \(B\), denote \(A \subsetneq B\), if \(A \subseteq B\) and \(A\ne B\).
The definition is well-defined, i.e., it obeys the axiom of substitution, see Chapter 11.
Proposition 2.1 Let \(A,B,C\) be sets. If \(A \subseteq B\) and \(B\subseteq C\) then \(A \subseteq C\). If \(A \subseteq B\) and \(B\subseteq A\), then \(A=B\). Finally, if \(A \subsetneq B\) and \(B\subsetneq C\), then \(A \subsetneq C\).
Sets are partially ordered, whereas the natural numbers are totally ordered.
Axiom 3.5 (Axiom of specification) Let \(A\) be a set, and for each \(x\in A\), let \(P(x)\) be a property pertaining to \(x\) (i.e., \(P(x)\) is either a true statement or a false statement). Then there exists a set, called \(\{x\in A: P(x) \text{ is true}\}\) (or simply \(\{x\in A: P(x)\}\)) for short), whose elements are precisely the elements \(x\) in \(A\) for which \(P(x)\) is true. In other words, for any object \(y\), \[ y \in \{x\in A: P(x)\} \iff (y\in A\ \ and\ \ P(y) \text{ is true}). \] This axiom is also known as the axiom of separation. One can verify that the axiom of substitution works for specification, see Chapter 11
Definition 2.4 (Intersections) The intersection \(S_1\ \cap S_2\) of two sets is defined to be the set \[ S_1 \cap S_2 := \{x\in S_1 : x\in S_2 \}. \] In other words, for all objects \(x\), \[ x\in S_1\ \cap S_2 \iff (x\in S_1\ \ and\ \ x\in S_2) \]
The definition is well-defined, i.e., it obeys the axiom of substitution, see Chapter 11. Two set \(A,B\) are said to be disjoint if \(A\cap B=\varnothing\). Note that this is not the same concept as being distinct, \(A\ne B\).
Definition 2.5 (Difference sets) Given two sets \(A\) and \(B\), we define the set \(A-B\) or \(A \setminus B\) to be the set \(A\) with elements of \(B\) removed: \[ A\setminus B:=\{x\in A: x\not \in B\}. \]
Proposition 2.2 (Sets from a boolean algebra) Let \(A,B,C\) be sets, and let \(X\) be a set containing \(A,B,C\) as subsets.
- (Minimal element) \(A\cup \varnothing = A\) and \(A \cap \varnothing = \varnothing\).
- (Maximal element) \(A\cup X =X\) and \(A\cap X = A\).
- (Identity) \(A\cap A = A\cup A = A\)
- (Commutativity) \(A\cup B = B\cup A\) and \(A\cap B = B\cap A\)
- (Associativity) \((A\cup B)\cup C = A\cup (B\cup C)\) and \((A\cap B)\cap C = A\cap (B\cap C)\)
- (Distributivity) \(A\cap (B\cup C) = (A\cap B)\cup (A\cap C)\) and \(A\cup (B\cap C) = (A\cup B)\cap(A\cup C)\)
- (Partition) \(A\cup (X\setminus A) = X\) and \(A\cap (X\setminus A) = \varnothing\)
- (De Morgan laws) \(X\setminus (A\cup B) = (X\setminus A)\cap (X\setminus B)\) and \(X\setminus (A\cap B) = (X\setminus A)\cup (X\setminus B)\)
Such symmetry in the laws between \(\cup\) and \(\cap\), and between \(X\) an \(\varnothing\), is an example of duality - two distinct properties or objects being dual to each other. In this case, the duality is manifested by the complementation relation \(A \mapsto X\setminus A\); the de Morgan laws assert that this relation converts unions and intersections and vice versa.
Axiom 3.6 (Replacement) Let \(A\) be a set. For any object \(x\in A\), and any object \(y\), suppose we have a statement \(P(x,y)\) pertaining to \(x\) and \(y\), such that for each \(x\in A\) there is at most one \(y\) for which \(P(x,y)\) is true, Then ther exists a set \(\{y: P(x,y) \text{ is true for some }x\in A\}\), such that for any object \(z\), \[ \begin{aligned} z\in \{y&: P(x,y) \text{ is true for some }x\in A\}\\ &\iff P(x,z) \text{ is true for some }x\in A \end{aligned} \]
Axiom 3.7 (Infinity) There exists a set \(\mathbb{N}\), whose elements are called natural numbers,as well as an object \(0\) in \(\mathbb{N}\), and an object \(n+\!\!+\) assigned to every natural number \(n \in \mathbb{N}\), such that the Peano axioms (Axiom 2.1 - 2.5) hold.
This is a more formal version of Assumption 2.6. It introduces the most basic example of an infinite set.
Exercise 2.1 Show that the axiom of replacement implies the axiom of specification.
2.2 Russell’s paradox
Axiom 3.8 (Universal specification) Suppose for every object \(x\) we have a property \(P(x)\) pertaining to \(x\) (so that for every \(x\), \(P(x)\) is either a true statement or a false statement). Then there exists a set \(\{x:P(x) \text{ is true}\}\) such that for every object \(y\), \[ y \in \{x:P(x) \text{ is true}\} \iff P(y) \text{ is true} \]
The axiom is also known as the axiom of comprehension. This axiom cannot be introduced into set theory, because it creates a logical logical contradiction known as Russell’s paradox, discovered by the philosopher nd logician Bertrand Russell in 1901. The paradox runs as follows. Let \(P(x)\) be the statement \[ P(x) \iff ``x \text{ is a set, and }x\not \in x \text{''}; \] Now use the axiom of universal specification to create the set \[ \Omega := \{x:P(x) \text{ is true}\} = \{x:x \text{ is a set, and }x\not \in x\} \] If \(\Omega \in \Omega\), then it can be deduced that \(\Omega \not \in \Omega\); If \(\Omega \not\in \Omega\), then it can be deduced that \(\Omega \in \Omega\). Thus in either case the conclusion is absurd. One way to informally resolve the issue that sets are allowed to contain themselves is to think of objects as being arranged in a hierarchy. To actually formalize the intuition of a hierarchy of objects is rather complicated, so we shall simply postulate an axiom which ensures that absurdities such as Russell’s paradox do not occur.
Axiom 3.9 (Regularity) If \(A\) is a non-empty set, then there is at least one element \(x\) of \(A\) which is either not a set, or is disjoint from \(A\).
The axiom is also known as the axiom of foundation.
Exercise 2.2 Show that Axiom 3.8, if assumed to be true, would imply Axiom 3.2, 3.3, 3.4, 3.5 and 3.6.
Exercise 2.3 Use the axiom of regularity (and the singleton set axiom) to show that \(A\) is a set, then \(A\not \in A\). Furthermore, show that if \(A\) and \(B\) are two set sets, then either \(A\not\in B\) or \(B\not\in A\) (or both).
The first statement is trivial. As for the latter one, for the sake of contradiction, suppose that \(A\in B\) and \(B\in A\), then \(A\in A\cup B\); however, \(A\cap (A\cup B) \ne \varnothing\) which contradict Axiom 3.9.
Exercise 2.4 Show that the axiom of comprehension is equivalent to an axiom postulating the existence of a “universal set” \(\Omega\) consisting of all objects. (If such set exists, then \(\Omega \in \Omega\), thus the axiom of foundation rules out the axiom of comprehension).
2.3 Functions
Definition 2.6 (Functions) Let \(X,Y\) be sets, and let \(P(x,y)\) be a property pertaining to an object \(x\in X\) and an object \(y\in Y\), such that for every \(x\in X\), there is exactly one \(y\in Y\) for which \(P(x,y)\) is true (this is sometimes known as the vertical line test). Then we define the function \(f:X\to Y\) defined by \(P\) on the domain \(X\) and range \(Y\) to be the object which, given any input \(x\in X\), assigns an output \(f(x) \in Y\), defined to be the unique object \(f(x)\) for which \(P(x,f(x))\) is true. Thus, for any \(x\in X\) and \(y\in Y\), \[ y=f(x) \iff P(x,y) \text{ is true.} \]
Functions are also referred to maps, transformations or morphisms.
Definition 2.7 (Equality of functions) Two functions \(f:X\to Y\), \(g:X\to Y\) with the same domain and range are said to be equal, \(f=g\), if and only if \(f(x) = g(x)\) for all \(x\in X\).
The empty function \(f:\varnothing\to X\) is a function from the empty set to an arbitrary set \(X\). Note that from Definition 2.7 it can be infered that for each set \(X\), there is only one function from \(\varnothing\) to \(X\).
Definition 2.8 (Composition) Let \(f: X\to Y\) and \(g:Y\to Z\) be two functions,such that the range of \(f\) is the same as the domain of \(g\). We the define composition \(g \circ f:X\to Z\) of the two functions \(g\) and \(f\) to be the function defined explicitly by the formula \[ (g\circ f)(x):= g(f(x)) \] If the range of \(f\) does not match the domain of \(g\), we leave the composition \(g\circ f\) undefined.
Lemma 2.3 (Composition is associative) Let \(f:Z\to W\), \(g:Y\to Z\), and \(h:X\to Y\) be functions. Then \(f\circ(g\circ h) = (f\circ g)\circ h\).
Proof. First it should be interpreted that they have the same domain and range.
Definition 2.9 (One-to-one functions) A function \(f\) is one-to-one (or injective) if different elements map to different elements: \[ x\ne x^{\prime} \Longrightarrow f(x) \ne f(x^{\prime}). \]
Definition 2.10 (Onto functions) A function \(f\) is onto (or surjective) if \(f(X)=Y\), i.e., every element in \(Y\) comes from applying \(f\) to some element in \(X\): \[ \text{For every }y\in Y,\text{ there exists }x\in X \text{ such that }f(x) = y. \]
Definition 2.11 (Bijective functions) Functions \(f:X\to Y\) which are both one-to-one and onto are also called bijective or invertible.
Exercise 2.5 (Cancellation laws for composition) Let \(f_1: X\to Y\), \(f_2: X\to Y\), \(g_1:Y \to X\) and \(g_2:Y \to X\) be functions. Show that if \(g_1\circ f_1 = g_1\circ f_2\) and \(g_1\) is iniective, then \(f_1=f_2\). Is the same statement true if \(g\) is not injective? Show that if \(g_1\circ f_1 = g_2\circ f_1\) and \(f_1\) is surjective, then \(g_1=g_2\). Is the same statement true if \(f_1\) is not surjective?
Exercise 2.6 Let \(f:X\to Y\) nd \(g:Y\to Z\) be functions. Show that if \(g\circ f\) is injective, then \(f\) must be injective, then \(f\) must be injective. Is it true that \(g\) must also be injective? Show that if \(g\circ f\) is surjective, then \(g\) must be surjective, then \(g\) must be surjective. Is it true that \(f\) must also be injective?
One may make a mistake when considering “Is it true that \(g\) must also be injective?” as follow. \(g\circ f (x) = g\circ f(x') \Longrightarrow x=x' \Longrightarrow f(x) = f(x')\), so \(g\) must also be injective. The proof is wrong because \(g\) is injective means that \(\forall y,y'\in Y, y\ne y' \Longrightarrow g(y)\ne g(y')\), while the proof only considers the situation that \(y,y' \in f(X)\), which is a subset of \(Y\). For example, let’s consider \(X = \{1,2\}\) and \(Y=Z=\{1,2,3\}\). Let’s define the function \(f\) as the mapping \(f(1)=1\), \(f(2)=2\). Let’s define the function \(g\) as the mapping \(g(1) = 1,\ g(2)=2,\ g(3)=2\). Here, \(f\) is injective, so is \(g\circ f\), but \(g\) is not injective. The latter question is similar to the former one.
Exercise 2.7 Let \(f:X\to Y\) be a bijective function, and let \(f^{-1}:Y\to X\) be its inverse. Verify that cancellation laws \(f^{-1}(f(x)) = x\) for all \(x\in X\) and \(f(f^{-1}(y))=y\) for all \(y\in Y\). Conclude that \(f^{-1}\) is also invertible, nd has \(f\) as its inverse.
Exercise 2.8 Let \(f:X\to Y\) nd \(g:Y\to Z\) be functions. Show that if \(f\) and \(g\) are bijective, then so is \(g\circ f\), and we have \((g\circ f)^{-1} = f^{-1} \circ g^{-1}\).
Exercise 2.9 If \(X\) is a subset of \(Y\), let \(\iota_{X\to Y}\) be the inclusion map from \(X\) to \(Y\), defined by mapping \(x\mapsto x\) for all \(x\in X\), i.e.m \(\iota_{X\to Y}:=x\) for all \(x\in X\). The mape \(\iota_{X\to X}\) is in particular called the identity map on \(X\).
- Show that if \(X\subseteq Y\subseteq Z\) then \(\iota_{Y\to Z}\circ \iota_{X\to Y} = \iota_{X\to Z}\).
- Show that if \(f:A\to B\) is any function, then \(f= f\circ \iota_{A\to A} = \iota_{B\to B}\circ f\).
- Show that if \(f:A\to B\) is a bijective function, then \(f\circ f^{-1} = \iota_{B\to B}\) and \(f^{-1}\circ f =\iota_{A\to A}\).
- Show that if \(X\) and \(Y\) are disjoint sets, and \(f:X\to Z\) and \(g: Y\to Z\) are functions, then there is a unique function \(h\): \(X\cup Y \to Z\) such that \(h \circ \iota_{X\to X\cup Y} =f\) and \(h \circ \iota_{Y\to X\cup Y} =g\).
2.4 Images and inverse images
Definition 2.12 If \(f:X\to Y\) is a function from \(X\) to \(Y\), and \(S\) is a set in \(X\), we define \(f(S)\) to be the set \[ f(S):=\{f(x):x\in S\}; \] this set is a subset of \(Y\), and is sometimes called the image of \(S\) under the map \(f\). We sometimes call \(f(S)\) the forward image of \(S\) to distinguish it from the concept of the inverse image \(f^{-1}(S)\) of \(S\), which is defined below.
Note that the set \(f(S)\) is well-defined thanks to the axiom of replacement or the axiom of specification.
Definition 2.13 If \(U\) is a subset of \(Y\), we define the set \(f^{-1}(U)\) to be the set \[ f^{-1}(U):=\{x\in X: f(x) \in U\}. \]
We call \(f^{-1}(U)\) the inverse image of \(U\).
Axiom 3.10 (Power set axiom) Let \(X\) and \(Y\) be sets. Then there exists a set, denoted \(Y^X\), which consists of all the functions from \(X\) to \(Y\), thus \[ f\in Y^X \Longrightarrow (f\text{ is a function with domain }X\text{ and range }Y). \]
For more details, see Proposition 2.3.
One consequence of this axiom is
Lemma 2.4 Let \(X\) be a set. Then the set \[ \{Y: Y \text{ is a subset of } X\} \] is a set.
The set \(\{Y: Y \text{ is a subset of } X\}\) is known as the power set of \(X\) and is denoted \(2^X\). For more details, see Chapter 7.
Axiom 3.11 (Union) Let \(A\) be a set, all of whose elements re themselves sets. Then there exists a set \(\bigcup A\) whose elements are precisely those objects which are elements of \(A\), thus for all objects \(x\) \[ x\in \bigcup A \iff (x\in S \text{ for some }S\in A) \] Thanks to the axiom of replacement and the axiom of union, if one has some set \(I\), and for every element \(\alpha \in I\) we have some set \(A_{\alpha}\), then we can form the union set \(\bigcup_{\alpha\in I}A_{\alpha}\) by defining \[ \bigcup_{\alpha\in I}A_{\alpha}:=\bigcup \{A_{\alpha}:\alpha\in I\} \] In some situation, we refer to \(I\) as an index set, and the elements \(\alpha\) of this index set as labels; the sets \(A_{\alpha}\) are then called a family of sets, and are indexed by the labels \(\alpha\in I\).
Given any non-empty set \(I\), and given an assignment of a set \(A_{\alpha}\) to each \(\alpha\in I\), we can define the intersection \(\bigcap_{\alpha\in I}A_{\alpha}\) by first choosing some elements \(\beta\) of \(I\) (which we can da since \(I\) is non-empty), and setting \[ \bigcap_{\alpha\in I}A_{\alpha}:=\{x\in A_{\beta}: x\in A_{\alpha} \text{ for all }\alpha \in I\}, \] which is a set by the axiom of specification. For more details, see Exercise ??.
The axiom we’ve introduced in this chapter (excluding Axiom 3.8) are known as the Zermelo-Fraenkel axiom of set theory. There is one further axiom we will need, axiom of choice (see Chapter 7), giving rise to the Zermelo-Fraenkel-Choice axiom of set theory (ZFC) axiom of set theory.
2.5 Cartesian products
If \(x\) and \(y\) are any objects, we defined the ordered pair \((x,y)\) to be a new object. Two ordered pairs \((x,y)\) and \((x',y')\) are considered equal iff both their components match, i.e. \[ (x,y)=(x',y') \iff (x=x'\ and\ y=y') \]
If \(X\) and \(Y\) are sets, then we define the Cartesian product \(X\times Y\) to be the collection of ordered pairs whose first component lies on \(X\) and second component lies in \(Y\), thus \[ X\times Y = \{(x,y):x\in X, y\in Y\} \] or equivalently \[ a\in(X\times Y) \iff (a=(x,y) \text{ for some }x\in X \text{ and }y \in Y) \]
The addition operation \(+\) on the natural numbers can now be re-interpreted as a function \(+: \mathbb{N}\times \mathbb{N}\to \mathbb{N}\), define by \((x,y)\mapsto x+y\).
Let \(n\) be a natural number. An ordered \(n\)-tuple \((x_i)_{1\leq i\leq n}\) (also denoted \((x_1,\dots,x_n)\)) is a collection of objects \(x_i\) as the \(i^{th}\) component of the ordered \(n\)-tuple. Two ordered \(n\)-tuples \((x_i)_{1\leq i\leq n}\) and \((y_i)_{1\leq i\leq n}\) are said to be equal iff \(x_i=y_i\) for all \(1\leq i\leq n0\). If \((X_i)_{1\leq i\leq n}\) is an ordered \(n\)-tuple of sets, we define their Cartesian product \(\prod_{1\leq i\leq n}X_i\) (also denoted \(\prod_{i=1}^nX_i\) or \(X_1\times \dots\times X_n\)) by \[ \prod_{1\leq i\leq n}X_i :=\{(x_i)_{1\leq i\leq n}:x_i\in X_i \text{ for all }1\leq i \leq n\}. \]
An ordered \(n\)-tuple is also called an order sequence of \(n\) elements, or a finite sequence for short. For more details, see 4.
The empty Cartesian product \(\prod_{1\leq i\leq 0}X_i\) gives, not the empty set \(\{\}\), but rather the singleton set \(\{()\}\) whose only element is the \(0\)-tuple \(()\), also known aas the empty tuple.
Lemma 2.5 Let \(n\geq 1\) be a natural number, and for each natural number \(1\leq i\leq n\), let \(X_i\) be a non-empty set. Then there exists an \(n\)-tuple \((x_i)_{1\leq i\leq n}\) such that \(x_i\in X_i\) for all \(1\leq i\leq n\). In other words, if each \(X_i\) is non-empty set, then the set \(\prod_{1\leq i\leq n}X_i\) is also non-empty.
2.6 Cardinality of sets
The purpose of this section is to address this issue by noting that the natural numbers can be used to count the cardinality of sets, as long as the set is finite.
Definition 2.14 (Equal cardinality) We say that two sets \(X\) and \(Y\) have equal cardinality iff there exists a bijection \(f:X\to Y\) from \(X\) to \(Y\).
The property is commutative and associative.
Definition 2.15 (Equal cardinality) Let \(n\) be a natural number. A set \(X\) is said to have cardinality \(n\), iff it has equal cardinality with \(\{i\in \mathbb{N}:1\leq i\leq n\}\). We also say that \(X\) has n elements iff it has cardinality \(n\).
Let \(X\) be a set with some cardinality \(n\). Then \(X\) cannot have any other cardinality, i.e., \(X\) cannot have cardinality \(m\) for any \(m\ne n\).
To prove the proposition, we need the following lemma.
Lemma 2.6 Suppose that \(n\geq 1\), and \(X\) has cardinality \(n\). Then \(X\) is non-empty, and if \(x\) is element of \(X\), then the set \(X-\{x\}\) has cardinality \(n-1\).
Theorem 2.1 The set of natural numbers \(\mathbb{N}\) is infinite.
Proposition 2.3 (Cardinality arithmetic)
- Let \(X\) be a finite set, and let \(x\) be an object which is not an element of \(X\). Then \(X\cup\{x\}\) is finite and \(\#(X\cup\{x\}) = \#(X)+1\).
- Let \(X\) and \(Y\) be finite sets. Then \(X \cup Y\) is finite and \(\#(X\cup Y) \leq \#(X) +\#(Y)\). If in addition \(X\) and \(Y\) are disjoint, \(\#(X\cup Y) =\#(X) +\#(Y)\).
- Let \(X\) be a finite set, and let \(Y\) be a subset \(X\). Then \(Y\) is finite, and \(\#(Y) \leq \#(X)\). In addition \(Y\ne X\), then \(\#(X\cup Y) < \#(X)\).
- Let \(X\) be a finite set, and \(f:X\to Y\) is a function, then \(F(X)\) is a finite set with \(\#(f(X)) \leq \#(X)\). If in addition \(f\) is one-to-one, then \(\#(f(X)) = \#(X)\).
- Let \(X\) and \(Y\) be finite sets. Then Cartesian product \(X\times Y\) is finite and \(\#(X\times Y) = \#(X)\times \#(Y)\).
- Let \(X\) and \(Y\) be finite sets. Then the set \(Y^X\) is finite and \(\#(Y^X) = \#(Y)^{\#(X)}\).