Is the set of extensive, increasing, ∅-preserving operators 2^X→2^X closed under composition?

158 Views Asked by At

Let $\Bbb E (X)$ denote the set of all operators $f:2^{X} \rightarrow 2^{X}$ such that:

  1. $f(\emptyset)=\emptyset$
  2. $A \subseteq f(A)$
  3. $A \subseteq B \implies f(A) \subseteq f(B)$
  4. $a \in f(A \cup \{b\}) \setminus f(A) \implies b \in f(A \cup \{a\}) $

Is $\Bbb E (X)$ closed under composition?

It's the final lemma I would need for a theorem I'm struggling with for few days now, but I don't really know how to approach it. There are two potentially helpful facts I was able to prove:

Fact 1 For any $f:2^{X} \rightarrow 2^{X}$ such that $f(\emptyset)=\emptyset$ there is $F \in \Bbb E (X)$ such that:

  1. $f(A) \subseteq F(A) $ for every $ A \subseteq X$
  2. If $ g \in \Bbb E (X)$ and $f(A) \subseteq g(A) $ for every $ A \subseteq X$ then $F(A) \subseteq g(A) $ for every $ A \subseteq X$

Fact 2 If $ \mathcal F \subseteq \Bbb E (X)$ is totally ordered by inclusion, ie. if for each $f,g \in \mathcal F$ either $f(A) \subseteq g(A) $ for every $ A \subseteq X$ or $g(A) \subseteq f(A) $ for every $ A \subseteq X$ then $[\bigcup \mathcal F](A)=\bigcup \{f(A) : f \in \mathcal F\} \in \Bbb E (X)$

Thererefore the structure of $\Bbb E (X)$ is somewhat similar to that of a convexity (see: M.L.J. van de Vel, "Theory of Convex Structures"), might well be a dead end though.

1

There are 1 best solutions below

5
On BEST ANSWER

No, it's not.

The first three properties are fine, but property 4 doesn't survive in general. Here is a counterexample.

Define $f: 2^{\{1,2,3\}} \to 2^{\{1,2,3\}}$ by $$ f(\varnothing)=\varnothing,\; f(\{1\}) = \{1\},\; f(\{2\}) = f(\{3\}) = \{2,3\},\\f(\{1,2\}) = f(\{1,3\}) = f(\{2,3\}) = f(\{1,2,3\}) = \{1,2,3\}. $$ It takes a bit of checking, but we can verify that all four properties hold for $f$.

However, $f(f(\{1\})) = \{1\}$ while $f(f(\{2\})) = \{1,2,3\}$, which means that $$ 1 \in f(f(\varnothing \cup \{2\})) \setminus f(f(\varnothing)) \\ 2 \notin f(f(\varnothing \cup\{1\})) $$ so the composition $f \circ f$ violates property 4 for $a = 1$, $b=2$, $A = \varnothing$.