Need help with finding a counterexample to: if $2^h=coeq(2^{q_1}, 2^{q_2}).$ then $h=eq(q_1,q_2)$

Question

The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes

Notations: Let $2^A$ denote the $\textit{power set}$ of all subsets of $A.$ Given $f:A\rightarrow B$, define $2^f:2^b\rightarrow 2^A$ by $2^f(S)=f^{-1}(S)=\{a\in A\mid f(a)\in B\}.$ Also let $coeq(p_1,p2_)$ denote the coequalizer of the two maps $p_1,p_2$ and similarly, let $eq(q_1,q_2)$ to denote the equalizer of the two maps $q_1,q_2.$ We also define the direct image function $2^{[f]}$ to be $2^{[f]}(A)=f(A)=\{f(a)\in S\subset B\mid a\in A\}.$ We also assume the following propositions:

Proposition 1: Every coequalizer is an epimorphism

Proposition 2: Every onto map is a coequalizer

Proposition 3: Every equalizer is a monomorphism

Proposition 4: The equalizer $B\xrightarrow{h}A$ of pair of maps $A\xrightarrow {(q_1,q_2)}R$ is the inclusion map $$h:\{a\mid a\in A \text{ and } q_1(a)=q_2(a)\}\rightarrow A, a\mapsto a.$$

Exercise: Given $p_1, p_2:R\rightarrow A, h:A\rightarrow B$ prove that $h=coeq(p_1,p_2)$ iff $2^h=eq(2^{p_1}, 2^{p_2}).$ Similarly, given $q_1, q_2;A\rightarrow R, h:B\rightarrow A$ prove that $h=eq(q_1,q_2)$ iff $2^h=coeq(2^{q_1}, 2^{q_2}).$

I have a question for the second part of the question: Given $q_1, q_2;A\rightarrow R, h:B\rightarrow A$ prove that $h=eq(q_1,q_2)$ iff $2^h=coeq(2^{q_1}, 2^{q_2}).$

I don't think both directions are true, a friend helped me with cooking up a counter example in one of the direction: Given $q_1, q_2;A\rightarrow R, h:B\rightarrow A$ prove that if $h=eq(q_1,q_2)$, then $2^h=coeq(2^{q_1}, 2^{q_2}).$

Consider the following: Consider $A=\{0,1,2,3,4,5\}$ and $R=\{0,1,2\}.$ Defome $q_1,q_2:A\rightarrow R$ as follows:

$n$	$q_1(n)$	$q_2(n)$
$0$	$0$	$0$
$1$	$1$	$1$
$2$	$0$	$2$
$3$	$1$	$0$
$4$	$0$	$1$
$5$	$1$	$2$

By proposition 4, it follows that setting $B=\{a\in A\mid q_1(a)=q_2(a)\}=\{0,1\}$ and $h:B\rightarrow A$ the inclusion map, then $h={eq}(q_1,q_2).$

Note that $2^h:2^A\rightarrow 2^B$ is defined by $2^h(P)=P\cap B,$ and since $2^{q_1},2^{q_2}:2^B\rightarrow 2^A$ is determined by the values on the singletons (since $2^{q_1}(S_1\cup S_2)=2^{q_1}(S_1)\cup 2^{q_1}(S_2))$), we note that

$n$	$2^{q_1}(\{n\})$	$2^{q_2}(\{n\})$
$0$	$\{0,2,4\}$	$\{0,3\}$
$1$	$\{1,3,5\}$	$\{1,4\}$
$2$	$\emptyset$	$\{2,5\}$

Let $B'=\{0,1,2, *\}$ and define a function $h':2^A\rightarrow B'$ as follows

$h'(\{0,3\})=h'(\{0,2,4\})=h'(\{0,2,3,5\})=0$

$h'(\{1,4\})=h'(\{1,3,5\})=h'(\{1,2,4,5\})=1$

$h'(\{\emptyset\})=h'(\{2,5\})=2$

$h'(P)=*$ for any other $P\subset R.$

Now we check that $h'\cdot 2^{q_1}=h'\cdot 2^{q_2}$

Suppose now that $\psi:2^h\rightarrow B'$ is such that $\psi\cdot 2^h=h'.$ Then

$0=h'(\{0,2,4\})=\psi \cdot 2^h(\{0,2,4\})=\psi(\{0\})$

$*=h'(\{0\})=\psi \cdot 2^h(\{0\})=\psi(\{0\})$

That is, we require that $0=\psi(\{0\})=*,$ which is a contradiction. Thus $2^h\neq{coeq}(2^{q_1},2^{q_2})$

Question:

For the converse direction: Assume $q_1,q_2: A\rightarrow R,h:B\rightarrow A,$ and $2^h={coeq}(2^{q_1},2^{q_2},$ of $q_1\cdot h\neq q_2\cdot h$, then I need to come up with example of a function $2^h$ where it coequalizes $2^{q_1},2^{q_2}.$

Thank you in advance.

Answer 1

$\newcommand{\p}{\mathscr{P}}\newcommand{\set}{\mathsf{Set}}\newcommand{\op}{^{\mathsf{op}}}\newcommand{\C}{\mathsf{C}}\newcommand{\D}{\mathsf{D}}\newcommand{\I}{\mathcal{I}}\newcommand{\J}{\mathcal{J}}$In all the below, we consider sets $A,B,C$ and functions $f,g:A\to B$.

1. If $h:B\to C$ is a coequaliser for $f,g$ then $2^h$ is an equaliser for $2^f,2^g$
2. If $2^h$ is an equaliser for $2^f,2^g$ then $h:B\to C$ is a coequaliser for $f,g$
3. If $h:C\to A$ is an equaliser for $f,g$ then $2^h$ is a coequaliser for $2^f,2^g$
4. If $2^h$ is a coequaliser for $2^f,2^g$ then $h:C\to A$ is an equaliser for $f,g$

$(1)$, $(2)$ and $(4)$ are correct (you are mistaken in guessing $(4)$ is wrong). You have given a satisfactory counterexample for $(3)$. Abstract nonsense proof for $(1),(2)$ incoming:

$(1)$:

It is a good but potentially confusing exercise to verify that $\p:\set\leftrightarrows\set\op:\p\op$ is an adjunction where $\p$ denotes the power set functor, $X\mapsto 2^X$ on objects and $f\mapsto 2^f$ (in your notation). Since $\p$ is a left adjoint, it is cocontinuous. So if $h$ is a coequaliser, $\p(h)$ is a coequaliser in $\set\op$ of $\p(f),\p(g)$. However, by easy duality we know that this means $2^h$ is an equaliser of $2^f,2^g$ in $\set$, as desired.

In proving $(2)$ I first had a concrete proof but then I noticed it could be generalised, so here is the general theorem (this is probably well known but I don't recall seeing it before):

Suppose $F:\C\to\D$ is a cocontinuous functor with a cocomplete domain. Suppose further that $F$ is faithful and $F$ reflects isomorphisms. Then for a diagram $\J:\I\to\C$ where $\I$ is small, an object $\varsigma\in\C$ and a family of arrows $\alpha=(\alpha_i:\J(i)\to\varsigma)_{i\in\I}$, we have that $\alpha$ is a colimiting cocone under $\J$ if and only if $F(\alpha)$ is a colimiting cocone under $F\circ\J$.

My proof:

Because $F$ is cocontinuous, $F(\alpha)$ is a colimiting cocone if $\alpha$ is. Suppose $F(\alpha)$ is a colimiting cocone. In particular, for all arrows $k:i\to i'$ in $\I$ we have that $F(\alpha_{i'}\circ\J(k))=F(\alpha_i)$ so by faithfulness it follows $\alpha_{i'}\circ\J(k)=\alpha_i$; it follows $\alpha$ is a cocone. There exists a colimit of $\J$ in $\C$, some $\beta:\J\implies\varsigma'$. Because $\alpha$ is a cocone we know there is a unique arrow $\gamma:\varsigma'\to\varsigma$ with $\alpha_j=\gamma\circ\beta_j$ for all $j\in\I$. Note that $F(\beta)$ is also a colimit cocone under $F\circ\J$, so the equation (in loose notation) $F(\alpha)=F(\gamma)F(\beta)$ actually implies $F(\gamma)$ is an isomorphism. Thus $\gamma$ is an isomorphism; thus $\alpha$ is a colimiting cocone.

This contains both $(1)$ and $(2)$ when we consider $\C=\set,\D=\set\op,F=\p$ and $\J,\I,\alpha$ the standard ways of presenting coequalisers as colimits. I guess I leave it as an exercise to show $\p$ is faithful and reflects isomorphisms ($\p$ is conservative).

In light of $(1)$ and $(2)$, $2^h$ is a coequaliser iff. $2^{2^h}$ is an equaliser. So $(4)$ is equivalent to: if $2^{2^h}$ is an equaliser then $h$ is an equaliser.

You were looking for a counterexample, but there are none.

Let $\eta:\mathrm{Id}_{\set}\implies T$ be the adjunction unit. Concretely, for any set $X$ we have that $\eta_X(x)$ is the principal ultrafilter on $X$ at $x$, for any $x\in X$. Assume $2^{2^h}=T(h)$ is an equaliser for $T(f),T(g)$.

Firstly, we have this nice relationship (exercise): $2^f$ is injective if and only if $f$ is surjective and $2^f$ is surjective if and only if $f$ is injective. So, $T(f)$ injects iff. $f$ injects. In particular, we know $h$ must be injective. Therefore the only thing left to check is that if $\alpha:X\to A$ is a function with $f\circ\alpha=g\circ\alpha$, then $\alpha=h\circ\gamma$ for some function $\gamma:X\to C$.

I know by naturality that $T(f)\circ(\eta_A\circ\alpha)=T(g)\circ(\eta_A\circ\alpha)$ hence $\eta_A\circ\alpha=T(h)\circ\beta$ for some (unique) $\beta:X\to T(C)$. This equation can be restated as:

For $x\in X$ and $K\subseteq B$, $\alpha(x)\in K$ if and only if $h^{-1}(K)\in\beta(x)$.

This implies that $h^{-1}(\alpha(x))$ is nonempty for all $x\in X$, so $\alpha(X)\subseteq h(C)$. But, $h$ is injective! It follows that such a $\gamma:X\to C$ exists. It further follows that $\beta=\eta_C\circ\gamma$.

Thus, $h$ is an equaliser.