Let $X$ and $Y$ be two sets such that $f \in Y^X$ then follows that those from $f$ induced functions $f : \mathcal {P}(X) \rightarrow \mathcal{P}(Y) $ and $f^{-1} : \mathcal{P}(Y) \rightarrow \mathcal {P}(X) $ are monotonically increasing.

My questions:

1) are the sets $X$ and $Y$ by nature ordered?

2) If so how does this order reflect on the induced functions from $f$ on the powersets? If not, how can an order on the induced functions $f$ even arise?

A nicely constructed example is welcome.


No, the sets are not ordered by nature. The power set of any set is naturally a poset with the inclusion relation; this doesn't reflect anything about the underlying sets. This (partial) order is defined as $A \leq B$ if and only if $A \subseteq B$. Note that not every pair of sets is comparable, for example $\{1,2\}$ is neither less than nor greater than $\{2,3\}$.

Any function $f$ from $X$ to $Y$ induces monotonic functions $f$ (I don't love this notation, since this is a different function from $f$) from $\mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ and $f^{-1}$ from $\mathcal{P}(Y) \rightarrow \mathcal{P}(X)$. "Monotonic" in this case means that:

For any subsets of $X$, say $X' \subseteq X''$, $f(X') \subseteq f(X'')$

For any subsets of $Y$, say $Y' \subseteq Y''$, $f^{-1}(Y') \subseteq f^{-1}(Y'')$.

Here is a small example: Let $X$ and $Y$ both be the set of real numbers $\mathbb{R}$. Then the two intervals $[1,2]$ and $[1,3]$ are both subsets of the reals, making them elements of $\mathcal{P}(X)$ and of $\mathcal{P}(Y)$, and $[1,2] \leq [1,3]$ in the order on the powerset, because one is a subset of the other. Let $f$ be the function $f(x) = x^2$. Then $f([1,2]) = [1,4]$ and $f([1,3]) = [1,9]$. As expected, $[1,4] \subseteq [1,9]$, meaning that the order is preserved.

In the opposite direction, we see that $f^{-1}([1,2]) = [-\sqrt{2},-1] \cup [1, \sqrt 2]$, and $f^{-1}([1,3]) = [-\sqrt{3}, -1] \cup [1, \sqrt{3}]$. Again, the first set is a subset of the second, so the order was preserved.


Not the answer you're looking for? Browse other questions tagged or ask your own question.