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$
5
  • 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
  • 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
  • $\begingroup$ How do we know that our isotone bijection preserves meets? This is required to be a boolean algebra morphism and you use this fact in your proof of the claim that it preserves compliments. I suspect I'm just missing something but this proof doesn't make sense to me. $\endgroup$
    – Keith
    Commented Aug 4 at 17:19
  • 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .