11
$\begingroup$

By the work of Paul Cohen (on the continuum hypothesis), one can neither prove nor disprove from the axioms of ZFC that a bijection $f$ from the power set $\mathcal{P}(S)$ of a set $S$ to the power set $\mathcal{P}(T)$ of a set $T$ implies a bijection from $S$ to $T$.

Question. What if $f$ is also isotone, meaning that if $X \subseteq Y \subseteq S$ then $f(X) \subseteq f(Y)$? More precisely, does an isotone $f$ send singletons to singletons? Or is this also independent from ZFC?

In fact, I don't know of a single example of an isotone bijection from a power set lattice to another (or even into itself) that is not an order isomorphism (namely, whose functional inverse is not isotone too). This may be relevant, considering that if $f$ is isotone, then $f^{-1}(\{y\})$ is a singleton for each $y \in T$.

It is not difficult to show that an isotone bijection from one complete lattice to another need not be an order isomorphism. In a way, I'm asking whether power set lattices are special in this regard.

$\endgroup$
16
  • 1
    $\begingroup$ My comments on the almost disjoint coding would be aimed at constructing a counterexample. $\endgroup$ Commented Aug 3 at 18:14
  • 1
    $\begingroup$ I might ask the question about isotone almost disjoint coding as a separate we question tomorrow, inspired by this question, if that is alright. $\endgroup$ Commented Aug 3 at 22:31
  • 1
    $\begingroup$ @MihaHabič No, there is not. This is also shown in my answer. $\endgroup$ Commented Aug 4 at 7:07
  • 1
    $\begingroup$ Just noted a related thread on Math SE: math.stackexchange.com/questions/2897680 $\endgroup$ Commented Aug 4 at 9:27
  • 2
    $\begingroup$ Regarding the injective isotone map question, there can be no isotone injective map from $P(\kappa)$ to $P(\lambda)$, when $\kappa>\lambda$, since the former has chains of order type $\kappa$, but the latter does not. In particular, this also answers my question about almost-disjoint coding---we cannot find coding sets of subsets $A\subseteq\omega_1$ with $a\subseteq\omega$ that respect inclusion. $\endgroup$ Commented Aug 4 at 13:37

2 Answers 2

13
$\begingroup$

Here is a more general fact:

Proposition: Any monotone bijection $f: A \to B$ between two Boolean algebras is an isomorphism.

Claim: $f(0) = 0$ and $f(1) = 1$.

Proof of Claim: For all $a \in A$, $0 \leq a \leq 1$ implies $f(0) \leq f(a) \leq f(1)$. Since $f$ is surjective, the result follows. $\square$

Claim: $f(a^c) = f(a)^c$ for all $a \in A$.

Proof of Claim: Since $f$ is surjective, there exists $b \in A$ s.t. $f(b) = f(a)^c$. But then by monotonicity, $f(a \wedge b) \leq f(a) \wedge f(b) = f(a) \wedge f(a)^c = 0$, so $f(a \wedge b) = 0$. As $f(0) = 0$, by injectivity, $a \wedge b = 0$. Similarly, $a \vee b = 1$. Thus, $b = a^c$, i.e., $f(a^c) = f(a)^c$. $\square$

Proof of Proposition: It suffices to show that $f(a) \leq f(b)$ implies $a \leq b$ for all $a, b \in A$. As $f(a) \leq f(b)$, we have $f(a \wedge b^c) \leq f(a) \wedge f(b^c) = f(a) \wedge f(b)^c = 0$, so $f(a \wedge b^c) = 0$ and by injectivity, $a \wedge b^c = 0$, i.e., $a \leq b$. $\square$

Since the lattice of all subsets of a given set is a Boolean algebra, and any (order-)isomorphism between lattices of all subsets clearly has to preserve singletons, the result follows.

$\endgroup$
7
  • 4
    $\begingroup$ +1. I am accepting Emil Jeřábek's answer since it came first. However, I like this answer even more: it makes the proof neater and demonstrates that, after all, power set lattices are not that special with respect to the question raised in the OP. $\endgroup$ Commented Aug 4 at 8:59
  • 3
    $\begingroup$ @SalvoTringali IMHO you should accept the best answer, not the first one. $\endgroup$ Commented Aug 4 at 10:14
  • $\begingroup$ @EmilJeřábek By the time David Gao's answer was posted, I had already accepted your answer. Let's not split hairs over these non-mathematical formalities. :) $\endgroup$ Commented Aug 4 at 10:29
  • 1
    $\begingroup$ You can change which answer is accepted, it’s not a once and for all thing. I think his answer deserves it more. But anyway, it’s up to you. $\endgroup$ Commented Aug 4 at 10:46
  • 3
    $\begingroup$ @Keith In the proof of their 2nd claim, David Gao is using that $f(a \land b) \leq f(a) \land f(b)$, not that $f(a \land b) = f(a) \land f(b)$. This follows from $f$ being isotonic, plus the fact that $a \land b \leq a$ and $a \land b \leq b$. $\endgroup$ Commented Aug 4 at 17:28
13
$\begingroup$

Yes, such a mapping necessarily sends singletons to singletons.

Let $f\colon\mathcal P(S)\to\mathcal P(T)$ be a monotone bijection (or more generally, a surjective strictly monotone function). By monotony, $f(\varnothing)\subseteq f(X)\subseteq f(S)$ for all $X\subseteq S$, hence using the surjectivity of $f$, $f(\varnothing)=\varnothing$ and $f(S)=T$. Also, as noted in the question, $f$-inverses of singletons must be singletons: if $f(X)=\{t\}$, we must have $X\ne\varnothing$; if we further assume for contradiction that there exists $\varnothing\ne X'\subsetneq X$, then $\varnothing\ne f(X')\subsetneq\{t\}$, which is impossible.

Thus, there is $S'\subseteq S$ and a bijection $g\colon S'\to T$ such that $f(\{s\})=\{g(s)\}$ for all $s\in S'$. But then by monotony, $\{t\}\subseteq f(S')$ for all $t\in\operatorname{im}(g)=T$, i.e., $f(S')=T=f(S)$, which implies $S'=S$.

Furthermore, we have $f(X)=g[X]$ for all $X\subseteq S$, hence $f$ is an order isomorphism. To see this, note that for any $s\in S$, $f(S\smallsetminus\{s\})$ includes $f(\{s'\})=\{g(s')\}$ for all $s'\ne s$, but it is strictly contained in $T=f(S)$, hence $f(S\smallsetminus\{s\})=T\smallsetminus\{g(s)\}$. Then for any $X\subseteq S$, we have $\{g(s)\}\subseteq f(X)\subseteq T\smallsetminus\{g(s')\}$ for all $s\in X$ and $s'\notin X$, whence $f(X)=g[X]$.

$\endgroup$
3
  • $\begingroup$ I guess you mean $S' \subseteq S$. Apart from that, awesome! $\endgroup$ Commented Aug 4 at 6:26
  • $\begingroup$ Let me just add for my future self that $f(S) = T$: being isotone and surjective implies that f maps the max of the power set lattice of S (that is, S) to the max of the power set lattice of T (that is, T). So, $T = f(S')$ yields by injectivity that $S'=S$. $\endgroup$ Commented Aug 4 at 6:38
  • 1
    $\begingroup$ I added that point to the answer to make it more self-contained. $\endgroup$ Commented Aug 4 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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