On
> **Puzzle 17.** Show that \$$f_{\ast} : PX \to PY \$$ is a monotone function.

Here is my try:

First, observing that
$$f_{\ast} : PX \to PY$$

sending each subset \$$S \subseteq X\$$ to its **[image](https://en.wikipedia.org/wiki/Image_(mathematics)#Image_of_a_subset)** under \$$f\$$

is producing the subsets in Y of the same cardinality, or less compared to the the subset in X that's being mapped by \$$f_{\ast}\$$. This is from the definition of the image in wikipedia linked above.
Specifically, important to note it is possible to get images of 'smaller' cardinality (because the mapping can be surjective), but not higher cardinality, because then the mapping would not be a function.

I will use this observation in below.

Now let's proof that \$$f_{\ast}\$$ is monotone, by contradiction.

Assume, that for some subsets \$$px_1 \subseteq px_2 \in PX , f_{\ast}(px_2) \subseteq f_{\ast}(px_1) \in PY \$$.

In other words, when we apply \$$f_{\ast}\$$ to px_1, it produces a superset (not a subset) of \$$f_{\ast}(px_2) \$$.
Superset means that cardinality (number of elements) of \$$f_{\ast}(px_1) \$$ is greater than the cardinality of \$$f_{\ast}(px_2) \$$.

But this also means that \$$f_{\ast}\$$ is producing images of higher cardinality than the one in PX. However, that would contradict the definition of the image of a subset definition.

Therefore, our assumption was wrong.

(did not read any other comments sofar, so hope I am not too far off :-) )