Exercise 3.6.4
Prove Proposition 3.6.14.
Proposition 3.6.14 contains six proposals so let's look at each as we develop solutions to each.
(a) 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$.
The finite set $X$ has a cardinality of $\#X$, which by Definition 3.6.10 is a natural number. This also means, by Definition 3.6.5, there is a bijection $g:X \to \{1, \ldots, \#X\}$.
Since $x$ is not in $X$, the bijection $g$ doesn't map $x$ to an element of $\{1, \ldots, \#X\}$. We can define a new bijection $h$ which maps just as $g$ for $x' \in X$, and maps $x$ to $\#X +1$, since $\#X+1$ is not in $\{1, \ldots, \#X\}$.
This $h$ is a bijection from $X \cup \{x\}$ to $\{1, \ldots, \#X+1\}$. This means $X \cup \{x\}$ has a cardinality $\#X +1$, and because this is a natural number (successor to $\#X$), it is also a finite set. $\square$
(b) 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 (i.e., $X \cap Y = \emptyset$), then $\#(X \cup Y) = \#(X) + \#(Y)$.
There are two cases to consider, $X$ and $Y$ are disjoint, and $X$ and $Y$ are not disjoint.
Let's consider the disjoint case first.
Since both sets are finite, their cardinalities $\#X$ and $\#Y$ are natural numbers (Definition 3.6.10). This means there exist bijections (Definition 3.6.5) $f: X \to \{1, \ldots, \#X\}$ and $g: Y \to \{\#X+1, \ldots, \#X+\#Y\}$. Since the two sets are disjoint, they share no common elements, and so we can define a new bijection $h: X \cup Y \to \{1, \ldots, \#X+\#Y\}$. Thus, if $X$ and $Y$ are disjoint, then $\#(X+Y)=\#X+\#Y$. $\square$
Now consider the non-disjoint case.
Since both sets are finite, their cardinalities $\#X$ and $\#Y$ are natural numbers. This means there exist bijections $f: X \to \{1, \ldots, \#X\}$ and $g: Y \to \{\#X+1, \ldots, \#X+\#Y\}$.
Here $X$ and $Y$ do share at least one common element. That means there exists an $x \in X$ that is also in $Y$. Therefore, a bijection $h: X \cup Y \to \{1, \ldots, m\}$ requires $m < \#X + \#Y$.
To see this more clearly, consider $Y'=Y \setminus X$, the set $Y$ without any elements that are also in $X$. Therefore the cardinality of $Y'$ is $\#Y' < \#Y$. We have $(X \cup Y) = (X \cup Y')$ and so $\#(X \cup Y) = \#X + \#Y' < \#X +\#Y$
Thus, in the general case, $\#(X \cup Y) \leq \#(X) + \#(Y)$. $\square$
(c) Let $X$ be a finite set, and let $Y$ be a subset of $X$. Then $Y$ is finite, and $\#(Y) ≤ \#(X)$. If in addition $Y \neq X$ (i.e., $Y$ is a proper subset of $X$), then we have $\#(Y) < \#(X)$.
$X$ is a finite set so it has a natural number cardinality $\#X$, and there is a bijection $f: X \to \{1, \ldots, \#X\}$.
If $Y$ is a subset of $X$, then it is finite too. We can define a function $g$ with domain $Y \subseteq X$ and which maps as $g(y) = f(y)$ . Since $f$ is a bijection, so is $g$.
This $g$ is bijective with $g': Y \to \{1, \ldots, \#Y\}$, where $\#Y \leq \#X$ because the domain of $g$ is some or all of $X$. That is, $\#(Y) ≤ \#(X)$. $\square$
In the case $Y$ is a proper subset of $X$, then there is at least one element of $X$ that is not in $Y$. And so the domain of $g$ is not equal to the domain of $f$. This means $g$ is bijective with $g': Y \to \{1, \ldots, \#Y\}$ where now $\#Y < \#X$ because the domain of $g$ is some but not all of $X$. That is, $\#(Y) < \#(X)$. $\square$
(d) If $X$ is a finite set, and $f:X \to Y$ is a function, then $f(X)$ is a finite set with $\#( f (X)) \leq \#(X)$. One has equality $\#( f (X)) = \#(X)$ if and only if $f$ is one-to-one.
The definition of a function $f:X \to Y$ requires it to map each element of $X$ to a single element of $Y$. Furthermore, for each element $y \in f(X)$, there exists an $x \in X$ such that $f(x)=y$.
There are two cases: there could be a unique $x$ for each $y \in f(X)$, or there could be more than one element of $X$ that maps to $y \in f(X)$.
In the case there is a unique $x$ for each $y \in f(X)$, the function $f$ is one-to-one, a bijection, and so $\#f(X) = \#X$. $\square$
In the case there is more than one element of $X$ that map to the same $y \in f(X)$, the function $f$ is not one-to-one. In this case there is a bijection between $f(X)$ and $\{1, \ldots, m\}$, where $m < \#X$.
Thus in general, $\#f(X) \leq \#X$. $\square$
(e) Let $X$ and $Y$ be finite sets. Then Cartesian product $X \times Y$ is finite and $\#(X × Y) = \#(X) \times \#(Y)$.
Consider $X=\{x_1, x_2, \ldots, x_m\}$ where $m=\#X$, and $Y=\{y_1, y_2, \ldots, y_n\}$ where $n=\#Y$. Since both sets are finite, $m$ and $n$ are natural numbers.
The Cartesian product is the set of ordered pairs,
$$\begin{align}X \times Y = & \{ (x_1, y_1), (x_1, y_2), \ldots , (x_1, y_n), \\ \\ & (x_2, y_1), (x_2, y_2), \ldots , (x_2, y_n), \\ \\& \ldots \\ \\ & (x_m, y_1), (x_m, y_2), \ldots , (x_m, y_n) \} \end{align}$$
For each of the $m$ elements of $X$ there are $n$ elements of the form $(x_i, y_j)$ in $X \times Y$. All of these elements are unique because each element of $X$ and $Y$ is unique.
Therefore, there are $m \times n$ elements of $X \times Y$, which is $\#X \times \#Y$. This is a natural number, and so the cartesian product is finite. $\square$
(f) Let $X$ and $Y$ be finite sets. Then the set $Y^X$ (defined in Axiom 3.11) is finite and $\#(Y^X) = \#(Y)^{\#(X)}$.
Let's remind ourselves of Axiom 3.1.1
(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$.
We'll prove this proposition by induction.
Let $P(n)$ be the statement: $\#(Y^X) = \#(Y)^{\#(X)}$ where $n=\#X$.
For the base case $n=1$, we have $X=\{x_1\}$, a singleton set. The power set $Y^X$ is the set of all functions from $X=\{x_1\}$ to $Y$. Since there is only one element of $X$, there are $\#Y$ possible functions from $X$ to $Y$. That is, $\#(Y^X) = \#Y^{\#(X)}=\#Y^1=\#Y$, and so the base case $P(1)$ is true.
Let's now assume $P(n)$ is true, and show $P(n+1)$ is true. The statement $P(n)$ is $\#(Y^X) = \#(Y)^{\#(X)}$ where $n=\#X$.
If we extend the set $X$ with an element it doesn't currently have $x'$, we have $X'=X \cup \{x'\}$, and $\#X'=n+1$. The addition of one extra element to $X$ means that for each of the existing functions $f \in X \times Y$, there are an additional $\#Y$ new possible functions $f' \in X' \times Y$.
More specifically, each function $f \in X \times Y$ can be extended to map $x'$ to any one of $\#Y$ elements of $Y$.
Thus $\#(Y^{X'}) = \#Y \times \#Y^{\#X} = \#Y^{\#X+1}$, and so $P(n+1)$ is true.
We have shown by induction that $\#(Y^X) = \#(Y)^{\#(X)}$. $\square$
Since $X$ and $Y$ are finite, then $\#X$, $\#Y$ and $\#X+1$ are natural numbers. This means the cardinality of the power set is also a natural number, and so is finite too. $\square$
No comments:
Post a Comment