Problem 4: Let $$A$$ be a nonempty finite simply ordered set.
• (a) Show that $$A$$ has a largest element.
• (b) Show that $$A$$ has the order type of a section of the positive integers.
Since $$A$$ is finite and simply ordered, we can define the order-preserving bijection $$f: A \rightarrow \{1, \ldots, n\}$$. Since $$n$$ is the largest element in the image and $$f$$ is a bijection, it follows that $$f^{-1}(n)$$ is the largest element in $$A$$. The answer to (b) is fairly obvious since we're able to construct an order-preserving bijection.

Problem 6:
• (a) Let $$A = \{1, \ldots, n\}$$. Show there is a bijection of $$\mathcal{P}(A)$$ with the cartesian product $$X^n$$ where $$X = \{0, 1\}$$.
• (b) Show that if $$A$$ is finite, then $$\mathcal{P}(A)$$ is finite.
(a) We know that, given $$A= \{1, \ldots, n\}$$, the cardinality of $$\mathcal{P}(A)$$ is $$2^{n}$$. So we must prove that the cardinality of $$X^n$$ is also $$2^{n}$$. To be thorough, we will also prove the cardinality of the power set. Starting with $$\mathcal{P}(A)$$, given $$A = \{1\}$$, $$\mathcal{P}(A) = \{\varnothing, \{1\}\}$$, which validates our claim ($$2^{1} = 2$$). Having shown this for $$n$$, we show that this is also true for $$n+1$$. Let $$B = \{1, \ldots, n, n+1\}$$. Then $$\mathcal{P}(B)$$ contains every $$s \in \mathcal{P}(A)$$, and, since $$B = A \cup \{n+1\}$$, $$\mathcal{P}(B)$$ also contains every $$s \cup \{n+1\}$$ (for every $$s \in \mathcal{P}(A)$$, we can define a $$s \cup \{n+1\} \in \mathcal{P}(B)$$ ). Thus, since there are the same number of elements $$s$$ as there are $$s \cup\{n+1\}$$, $$B$$'s cardinality is precisely double the cardinality of $$A$$.

Now onto $$X^{n}$$. For $$n=1$$, the cardinality of $$X^{n}$$ is 2, since $$X^{1} = X$$.Having shown this is true for $$n$$, we show it is true for$$n+1$$. Any tuple in $$X^{n+1}$$ takes on the form $$(x_1, x_2, \ldots, x_n, x_{n+1})$$ where the elements $$(x_1, \ldots, x_{n})$$ correspond to a tuple in $$X^{n}$$. Thus, half the tuples in $$X^{n+1}$$ take on the form $$(x_1, x_2, \ldots, 0)$$, and half take on the form $$(x_1, x_2, \ldots, 1)$$, meaning that $$X^{n+1}$$ has double the cardinality of $$X^{n}$$. If $$|X^{n}|=2^{n}$$, and $$|X^{n+1}|=2|X^{n}|$$, then the cardinality of $$X^{n+1}$$ also follows the $$2^{n}$$ rule. Thus, since both $$\mathcal{P}(A)$$ and $$X^{n}$$ have the same cardinality, we can find a bijection between the two sets. An example of such a bijection would be a function that converts numbers in base 10 to binary numbers.
(b) If $$A$$ is finite, then $$|A| = n, n \in \mathbb{Z}_+ \implies |\mathcal{P}(A)| = 2^{n}$$.