Exercise 3.6.4 (Cardinal arithmetic)

Question

Prove Proposition 3.6.14.\par 

	extbf{Proposition 3.6.14} 
\begin{enumerate}[label=(\alph*)]
\item 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$.
\item 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)$.
\item Let $X$ be a finite set, and let $Y$ be a subset of $X$. Then $Y$ is finite, and $\#(Y) \leq \#(X)$. If in addition $Y 
eq X$ (i.e., $Y$ is a proper subset of $X)$, then we have $\#(Y)<\#(X)$.
\item If $X$ is a finite set, and $f: X ightarrow 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)$.
\item Let $X$ and $Y$ be finite sets. Then Cartesian product $X 	imes Y$ is finite and $\#(X 	imes Y)=\#(X) 	imes \#(Y)$.
\item Let $X$ and $Y$ be finite sets. Then the set $Y^{X}$ (defined in Axiom 3.10) is finite and $\#\left(Y^{X}ight)=\#(Y)^{\#(X)}$.
\end{enumerate}

Prakash Anand · Accepted Answer

(e) There are at least two ways to do this problem; a direct induction or the more elegant use of the Euclidean algorithm. We present the latter. We wish to exhibit a bijection between the numbers $\{0, \ldots, n m-1\}$. Given any number $q \leq n m-1$, the Euclidean algorithm gives $q=p m+r$ with $0 \leq r \leq m$ and this representation is unique. If $X$ has cardinality $n$ and $Y$ has $m$, given by the bijections $f$ and $g$ respectively, then we will use these to create a bijection h onto $X 	imes Y$. Note that we take $f(g)$ to have domain $\{0, \ldots, n-1(m-1)\}$.
ewline

So, let $q \in\{0, \ldots, n m-1\}, q=p m+r$. Define $h(q)$ to be $(f(p), g(r)$. Uniqueness of the representation of q gives that this is well defined. $h$ is one to one since $h(q)=h\left(q^{\prime}ight)$ implies $f(p)=f\left(p^{\prime}ight)$ and $g(r)=g\left(r^{\prime}ight)$. As $f$ and $g$ are one to one, $p=p^{\prime}$ and $r=r^{\prime}$, so $q=q^{\prime}$. Finally, given $(x, y) \in X 	imes Y$, since $f$ and $g$ are onto there exist $t \in\{0, \ldots, n-1\}$ and $z \in\{0, \ldots, m-1\}$ with $f(t)=x$ and $g(z)=y$. So $h(t m+z)=(x, y)$.

Exercise 3.6.4 (Cardinal arithmetic)

Answers

Comments

Exercise 3.6.4 (Cardinal arithmetic)

Answers

Comments

Add answer