Is $2^{\frak{c}}$ separable?

Question

Let $2 = \{0,1\}$ be endowed with the discrete topology. My hunch was the following:

Let $e_\mathbb{N}: \mathbb{N} \to 2^{2^{\mathbb{N}}}$ be the "evaluation map", that is, it is given by $$e_\mathbb{N}(n): 2^\mathbb{N}\ni f\mapsto f(n).$$

Then I hoped that $\text{im}(e_\mathbb{N})\subseteq 2^{2^{\mathbb{N}}}$ is dense, but I fear that if $\underline{1}\in 2^\mathbb{N}$ is the constant $1$-sequence, then $\pi^{-1}_{\underline{1}}(\{0\}) \cap \text{im}(e_\mathbb{N}) =\emptyset$.

So am I just misremembering something, or is the mistake elsewhere? Maybe $2^{2^{\mathbb{N}}}$ is not separable at all?

Answer 1

You need to take the set of all (finite) Boolean combinations of your elements $e_\mathbb{N}(n)\in 2^{2^{\mathbb{N}}}$ (here I mean "Boolean combination" in the usual sense when you think of elements of $2^{2^{\mathbb{N}}}$ as subsets of $2^{\mathbb{N}}$). These Boolean combinations will still form a countable set, and actually are dense.

Indeed, given a finite subset $S\subset 2^{\mathbb{N}}$, you can find a finite subset of $A\subset\mathbb{N}$ that distinguishes all the elements of $S$. Any function $2^A\to 2$ can then be written as a Boolean combination of the functions given by restricting $e_\mathbb{N}(n)$ for $n\in A$, and in particular this means that for any function $f:S\to 2$ there is a Boolean combination of the $e_\mathbb{N}(n)$ that agrees with $f$ on $S$.

Answer 2

To get a countable dense subset of $2^\mathbb R,$ take the set of all step functions with finitely many jumps at rational points on the line. By a similar argument, any product of continuum many separable spaces is separable. (Separability of the product space $Q^Q$ where $Q=[0,1]$ is part (a) of exercise N in Chapter 3 of John L. Kelley's General Topology, which is available at the Internet Archive.) "Continuum many" is best possible here, seeing as the maximum possible cardinality of a separable Hausdorff space is $2^{2^{\aleph_0}}$.

Answer 3

The following is a detailed presentation of Eric Wofsey's beautiful answer. If Wofsey's answer is an algorithm, my answer is a careful implementation of it, intended to serve future readers, who, like me, understand best by seeing both the forest and the trees.

Typographical conventions: $$ \begin{align} Q, R, S, T, X &...\text{ sets} \\ q, r, s, t, x &...\text{ set members} \\ \mathbb{N}, \mathbb{Z} &...\text{ sets of numbers} \\ i, k, m &...\text{ numbers} \\ \mathbf{E}, \mathbf{F}, \mathbf{G}, \mathbf{H} &...\text{ sets of sets (a.k.a. families of sets)} \\ \mathcal{A}, \mathcal{B}, \mathcal{C}, \mathcal{D}, \mathcal{F} &...\text{ sets of functions} \\ f, g, h &...\text{ functions} \\ \eta, \xi &...\text{ functions returning sets/functions} \\ \Phi, \Psi &...\text{ Boolean algebras} \\ \mathfrak{I}, \mathfrak{P} &... \text{a function's image, a set's power set, respectively} \end{align} $$

---

Define $\mathbb{Z}_2 := \{0,1\}$, $\mathbb{N}:=\{1, 2, \dots\}$, $\mathbb{N}_0 := \{0, 1, 2, \dots\}$. Denote by $\mathbf{H}_0$ the discrete topology on $\mathbb{Z}_2$. Let $X$ be a non empty set, and denote by $\mathbf{H}$ the resulting product topology on $\mathcal{B}:=\mathfrak{P}X\rightarrow\mathbb{Z}_2$ ($\mathcal{B}$ can be seen as the set of all indicator functions on $\mathfrak{P}X$). We will show:

If $X$ is countable, the topological space $(\mathcal{B}, \mathbf{H})$ is separable.

Overview

We prove the highlighted statement by defining a certain set $\mathcal{A} \subseteq \mathcal{B}$ (section IX), and then showing (1) if $X$ is countable, so is $\mathcal{A}$ (section IX), (2) $\mathcal{A}$ is $\mathbf{H}$-dense in $\mathcal{B}$ (section X Corollary 8).

The proof follows the outline of Wofsey's answer, but with all the nitty-gritty details and implicit assumptions fully fleshed out. Sections I - VIII build up the necessary footing, in terms of notation, terminology and associated facts, on which the proof, given in the last two sections IX and X, rests. Section X begins with an overview of the results proved in it. Throughout this post I have proved just those facts, whose proofs I felt I might struggle to recreate if challenged to do so in the distant future.

The three pillars of Wofsey's answer are: (a) the concept of a distinguishing set, (b) the notion of Boolean combinations generated by members of $\mathcal{B}$, and (c) the technique of restricting the domain of $\mathcal{B}$'s member functions. To these I add a fourth pillar that was not mentioned in Wofsey's answer explicitly, but that is nonetheless essential to the proof, namely (d) the concept of a homomorphism between Boolean algebras. It is this concept that will prove to be the glue that binds the other three.

Distinguishing sets are defined in section III. A Boolean algebra structure on $\mathcal{B}$ is described in section IV, while Boolean combinations are defined in section VII. Section VII is also where the tools necessary for proving $\mathcal{A}$'s countability are presented (see the second bullet point in the section's end). Restricting the domain of all members of some set of functions endows the set with a natural partition. This type of partition is introduced in section II. Acting on functions whose domain has been restricted is tantamount to acting on these partitions. Functions whose domain is a partition are studied in sections V.

Section VI specializes the results of section V to the case that the partitioned space is a Boolean algebra. Homomorphisms between partitioned Boolean algebras are studied, culminating in Theorem 3 that ties together the four "pillars" mentioned above. This topic is picked up again in section VIII, which is devoted to studying the relationship between homomorphisms and Boolean combinations.

Since the principal object at the focus of our concern, the topological space $(\mathcal{B}, \mathbf{H})$, is made up of indicator functions, we open the discussion, in section I, by describing the relationship that enables us to translate between statements about indicator functions and those about their underlying sets.

I) Applying a set function to an indicator

Let $S$ be a set. We shall regard every function $f:S\rightarrow S$ dually as a function $(S\rightarrow\mathbb{Z}_2) \rightarrow (S\rightarrow\mathbb{Z}_2)$ as follows. For every $R \subseteq S$, we define $f(\mathbb{1}_R) := \mathbb{1}_{f(R)}$. We shall regard every function $g:\mathbf{P}S\rightarrow\mathbf{P}S$ dually as a function $(S\rightarrow\mathbb{Z}_2) \rightarrow (S\rightarrow\mathbb{Z}_2)$ as follows. For every $R \subseteq S$, we define $g(\mathbb{1}_R) := \mathbb{1}_{g(R)}$.

II) The equivalence relation induced on a set of functions by restricting its members' domain

Let $S, T$ be non-empty sets. Every $R \subseteq S$ induces an equivalence relation, $\cong_R$, on $S\rightarrow T$ as follows. For every $f, g : S\rightarrow T$, $f \cong_R g$ iff the two functions coincide on $R$: $$ \forall r \in R,\ f(r) = g(r). $$

For every $f : S\rightarrow T$, denote by $[f]_R$ the equivalence class of $f$. For every $\mathcal{D} \subseteq (S\rightarrow T)$ we abbreviate $$ [\mathcal{D}]_R := \big\{[f]_R\ :|\ f \in \mathcal{D}\big\}. $$

III) Distinguishing sets

Let $T$ be a set, and let $S$ be a subset of $T$. We define a function, $\eta_{\hspace{0cm}_{\large{S}}}:\mathfrak{P}T\rightarrow\mathfrak{P}T$, as follows. For every $R \subseteq T$, $$ \eta_{\hspace{0cm}_{\large{S}}}(R) := R\cap S. $$

A subset, $S$, of $T$, is called a distinguishing set for a family, $\mathbf{F}$, of subsets of $T$ iff the restriction, $\eta_{\hspace{0cm}_{\large{S}}}\big|_\mathbf{F}$, of $\eta_{\hspace{0cm}_{\large{S}}}$ to $\mathbf{F}$, is injective.

Theorem 1 Let $T$ be a set. Every family, $\mathbf{F}$, of subsets of $T$, has a distinguishing set, $S$. Moreover, if $\mathbf{F}$ is finite, $S$ may be chosen to be finite.

Proof

For every pair of distinct $Q, R \in \mathbf{F}$ choose some $s_{\{Q,R\}} \in Q\Delta R$. Define $$ S := \big\{s_{\{Q,R\}}\ :\big|\ (Q,R) \in \mathbf{F}\times \mathbf{F},\ Q\neq R\big\}. $$

Then for every pair of distinct $Q, R \in \mathbf{F}$, $$ s_{\{Q,R\}} \in (Q\Delta R)\cap S = (Q\cap S)\Delta (R\cap S) = \eta_{\hspace{0cm}_{\large{S}}}(Q) \Delta \eta_{\hspace{0cm}_{\large{S}}}(R), $$ and so $\eta_{\hspace{0cm}_{\large{S}}}(Q) \Delta \eta_{\hspace{0cm}_{\large{S}}}(R) \neq \emptyset$, which is equivalent to saying that $\eta_{\hspace{0cm}_{\large{S}}}(Q) \neq \eta_{\hspace{0cm}_{\large{S}}}(R)$.

Q.E.D.

For every family, $\mathbf{G}\subseteq\mathbf{P}S$, of subsets of $S$, we define a function $\eta_{\hspace{0cm}_{\large{S,\mathbf{G}}}}$ that maps families of subsets of $S$ to same, as follows. For every $\mathbf{F} \subseteq \mathbf{P}S$, $$ \eta_{\hspace{0cm}_{\large{S,\mathbf{G}}}}(\mathbf{F}) := \eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G}). $$

IV) The Boolean algebra induced on the family of Boolean functions

Let $\Phi = (S, \vee, \wedge, \neg, 0, 1)$ be a Boolean algebra. For every non-empty set, $R$, the sextet $(R \rightarrow S, \vee, \wedge, \neg, 0, 1)$ becomes a Boolean algebra if we apply the Boolean operations component-wise and if we regard $0$ and $1$ as constant functions on $R$. We shall refer to the latter Boolean algebra as $\Phi^R$.

We shall denote by $\Psi_0$ the standard two element Boolean algebra on $\mathbb{Z}_2$, and by $\Psi$ the induced Boolean algebra $(\Psi_0)^{\mathfrak{P}X}$.

V) Consistent partitions

Let $S, T$ be non empty sets. For every $i \in \mathbb{N}_0$ consider the set $\mathcal{F}^{S, T}_i$ consisting of all functions $f:S^i\rightarrow T$. Define $\mathcal{F}^{S, T} := \bigcup_{i=0}^\infty \mathcal{F}^{S, T}_i$. For every $f \in \mathcal{F}^{S, T}$ define $f$'s degree, $\deg(f)$, to be the unique number $i\in\mathbb{N}_0$ such that $f \in \mathcal{F}^{S, T}_i$. If $S = T$, we simplify and write $\mathcal{F}^S := \mathcal{F}^{S, T}$.

A pair $(\mathbf{F}, \mathbf{G})$, where $\mathbf{F}$ is a partition of $S$ and $\mathbf{G}$ is a partition of $T$, is called consistent with some subset $\mathcal{D}$ of $\mathcal{F}^{S, T}$ iff for every $f\in\mathcal{D}$ the following holds, with $m:=\deg(f)$. Whenever $s_1, \dots, s_m, t_1, \dots, t_m \in S$ are such that for every $i \in \{1, \dots, m\}$, $[s_i]_{\mathbf{F}} = [t_i]_{\mathbf{F}}$, then $\big[f(s_1, \dots, s_m)\big]_{\mathbf{G}} = \big[f(t_1, \dots, t_m)\big]_{\mathbf{G}}$. If $\mathbf{G} = \langle T\rangle$, where $\langle T\rangle$ is defined to be $T$'s finest partition, namely $\langle T\rangle := \big\{\{t\}\ :\!|\ t\in T\big\}$, we simplify and write that $\mathbf{F}$ is consistent with $\mathcal{D}$. If $T = S$ and $(\mathbf{F}, \mathbf{F})$ is consistent with $\mathcal{D}$, we simplify and write that $\mathbf{F}$ is self-consistent with $\mathcal{D}$. We denote by $\mathcal{F}^{S, T}_{\mathbf{F}, \mathbf{G}}$ the largest subset of $\mathcal{F}^{S, T}$ with which $(\mathbf{F}, \mathbf{G})$ is consistent. We write $\mathcal{F}^{S, T}_\mathbf{F}$ as an abbreviation for $\mathcal{F}^{S, T}_{\mathbf{F}, \langle T\rangle}$, and $\mathcal{F}^S_\mathbf{F}$ as an abbreviation for $\mathcal{F}^{S, S}_{\mathbf{F}, \mathbf{F}}$.

The following results, which the reader should verify, are immediate consequences of the definitions.

• Every partition, $\mathbf{F}$, of a non-empty set, $S$, is self-consistent with $\{\mathrm{Id}_S\}$, the identity function on $S$.

• $\langle S\rangle$ is self-consistent with $\mathcal{F}^S$.

• Every pair, $(\mathbf{F}, \mathbf{G})$ of partitions of the non-empty sets $S, T$, respectively, is consistent with $$ \big\{f(g_1, \dots, g_k)\ :\!\big|\ f \in \mathcal{F}^{S, T}_{\mathbf{F}, \mathbf{G}},\ k = \deg(f),\ g_1, \dots, g_k \in \mathcal{F}^S_\mathbf{F}\big\}, $$ where $f(g_1, \dots, g_k)$ is to be understood as the function $S^{\deg(g_1) + \cdots + \deg(g_k)}\rightarrow S$ that assigns to every $$ (s^{(1)}_1, \dots, s^{(1)}_{\deg(g_1)}, \dots, s^{(k)}_1, \dots, s^{(k)}_{\deg(g_k)}) \in S^{\deg(g_1) + \cdots + \deg(g_k)} $$ the value $$ f\Big(g_1\big(s^{(1)}_1, \dots, s^{(1)}_{\deg(g_1)}\big), \dots, g_k\big(s^{(k)}_1, \dots, s^{(k)}_{\deg(g_k)}\big)\Big). $$

Let $\mathbf{F}, \mathbf{G}$ be partitions of the non-empty sets $S, T$, respectively, that are consistent with some $\mathcal{D}\subseteq\mathcal{F}^{S, T}$.

Every $f \in \mathcal{D}$ with $m := \deg(f)$ induces a function $\overline{f}:\mathbf{F}^m\rightarrow\mathbf{G}$, by assigning to every $R_1, \dots, R_m \in \mathbf{F}$, $\overline{f}(R_1, \dots, R_m) := [f(r_1, \dots, r_m)]_\mathbf{G}$, where for every $i \in \{1, \dots, m\}$, $r_i$ is an arbitrary member of $R_i$.

For every $f:S\rightarrow T$, the family of sets $f^{-1}(T)$ is a partition of $S$, which we shall denote by $[S]_f$. For every $s \in S$, we will denote $s$'s equivalence class in this partition by $[s]_f$. The reader should verify that $[S]_f$ is consistent with $\{f\}$, that $\overline{f}$ is injective, and that $\overline{f}$ is surjective iff $f$ is surjective.

If $f$ is surjective, we define the pullback operator, $f^*$, to be the function $f^*:\mathcal{F}^S_{[S]_f}\rightarrow\mathcal{F}^T$, which maps every function $g \in \mathcal{F}^S_{[S]_f}$, i.e. every function with which $[S]_f$ is consistent, to the function $f^*(g) \in \mathcal{F}^T_k$, where $k:=\deg(g)$, which to every $t_1, \dots, t_k \in T$ assigns the unique value $f^*(g)(t_1, \dots, t_k) \in T$ that satisfies $$ \{f^*(g)(t_1, \dots, t_k)\} = \overline{f}\Big(\overline{g}\big(f^{-1}(\{t_1\}), \dots, f^{-1}(\{t_k\})\big)\Big). $$

The reader should verify The Fundamental Characterization of Pullbacks: For every $g \in \mathcal{F}^S_{[S]_f}$, $f^*(g)$ is the unique function in $\mathcal{F}^T$ that satisfies: for every $s_1, \dots, s_k \in S$, $$ f\big(g(s_1, \dots, s_k)\big) = f^*(g)\big(f(s_1), \dots, f(s_k)\big). $$ The reader should also verify that $f^*$ is on $\mathcal{F}^T$ (i.e. that $f^*$'s image is all of $\mathcal{F}^T$).

VI) Consistent partitions of a Boolean algebra

Let $\Phi = (S, \vee, \wedge, \neg, 0, 1)$ be a Boolean algebra. If $\mathbf{F}$ is a partition of $S$ that is self-consistent with $\{\vee, \wedge, \neg\}$, then $(\mathbf{F}, \overline{\vee}, \overline{\wedge}, \overline{\neg}, [0]_\mathbf{F}, [1]_\mathbf{F})$ is a Boolean algebra, which we will denote by $\Phi_\mathbf{F}$, and the mapping $s \mapsto [s]_\mathbf{F}$ is a homomorphism from $\Phi$ to $\Phi_\mathbf{F}$. In particular, $\Phi$ is naturally isomorphic with $\langle\Phi\rangle := \big(\langle S\rangle, \overline{\vee}, \overline{\wedge}, \overline{\neg}, \{0\}, \{1\}\big)$.

Note the difference between $\Phi_\mathbf{F}$ and $\Phi^R$ (the latter was defined in section IV). Both are Boolean algebras that are derived from $\Phi$, but whereas $\Phi^R$ has $R\rightarrow S$ for underlying set, $\Phi_\mathbf{F}$'s underlying set is $\mathbf{F}$, a partition of $S$. The following theorem relates these two constructions.

Theorem 2 Let $\Phi = (S, \vee, \wedge, \neg, 0, 1)$ be a Boolean algebra, let $R$ be a non-empty set, and let $Q\subseteq R$. Then $[R\rightarrow S]_Q$ is self-consistent with $\{\vee, \wedge, \neg\}$, so that the derived Boolean algebra $(\Phi^R)_{[R\rightarrow S]_Q}$ is well-defined.

Proof

Let $f_1, f_2, g_1, g_2 \in R\rightarrow S$ be such that $$ \begin{align} [f_1]_Q &= [f_2]_Q \\ [g_1]_Q &= [g_2]_Q \end{align} $$

For every $q \in Q$ we have $$ \begin{alignat*}{3} (f_1\vee g_1)(q)\ &=&\ f_1(q)\vee g_1(q)\ &=&\ f_2(q)\vee g_2(q)\ &=\ (f_2\vee g_2)(q) \\ (f_1\wedge g_1)(q)\ &=&\ f_1(q)\wedge g_1(q)\ &=&\ f_2(q)\wedge g_2(q)\ &=\ (f_2\wedge g_2)(q) \\ (\neg f_1)(q)\ &=&\ \neg\big(f_1(q)\big)\ &=&\ \neg\big(f_2(q)\big)\ &=\ (\neg f_2)(q) \end{alignat*} $$

Therefore $$ \begin{align} [f_1\vee g_1]_Q &= [f_2\vee g_2]_Q \\ [f_1\wedge g_1]_Q &= [f_2\wedge g_2]_Q \\ [\neg f_1]_Q &= [\neg f_2]_Q \end{align} $$

Q.E.D.

Theorem 2 guarantees that the notation $(\Phi^R)_{[R\rightarrow S]_Q}$ is well-defined. We shall abbreviate this complicated notation as follows: $(\Phi^R)_Q := (\Phi^R)_{[R\rightarrow S]_Q}$. In particular for every $\mathbf{F} \subseteq \mathfrak{P}X$, $\Psi_\mathbf{F}$ is a shorthand for $\Psi_{\mathcal{B}_\mathbf{F}}$.

Let $\Phi_i = (S_i, \vee_i, \wedge_i, \neg_i, 0_i, 1_i)$, $i \in \{1, 2\}$, be Boolean algebras, and let $h:S_1\rightarrow S_2$ be a homomorphism. The reader should verify the following facts.

• The sextet $\big(h(S_1), \vee_2, \wedge_2, \neg_2, 0_2, 1_2\big)$ is a Boolean algebra.

• $[S]_h$ is self-consistent with $\{\vee_1, \wedge_1, \neg_1\}$.

• If $\mathbf{F}_i$ is a partition of $S_i$ that is self-consistent with $\{\vee_i, \wedge_i, \neg_i\}$ ($i \in \{1, 2\}$), and if, additionally, $(\mathbf{F}_1, \mathbf{F}_2)$ is consistent with $\{h\}$, then $\overline{h}$ is a homomorphism from $\Phi_{\mathbf{F}_1}$ to $\Phi_{\mathbf{F}_2}$.

Theorem 3 Let $\mathbf{G}$ be a family of subsets of $X$, and let $S$ be a distinguishing set for $\mathbf{G}$. Then $(\mathcal{B}_\mathbf{G}, \mathcal{B}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})})$ is consistent with $\{\eta_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\}$, and $\overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}$ is an isometry from $\Psi_\mathbf{G}$ to $\Psi_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}$.

Proof

We begin by showing consistency. Let $\big[\mathbb{1}_\mathbf{E}\big]_\mathbf{G} = \big[\mathbb{1}_\mathbf{F}\big]_\mathbf{G}$ for some $\mathbf{E}, \mathbf{F} \subseteq \mathfrak{P}X$. We need to show that $\big[\eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbb{1}_\mathbf{E})\big]_\mathbf{G} = \big[\eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbb{1}_\mathbf{F})\big]_\mathbf{G}$, i.e. that for every $R \in \mathbf{G}$, $\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbf{E})}(R) = \mathbb{1}_{\eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbf{F})}(R)$. Let $R \in \mathbf{G}$. By symmetry it suffices to show that if $\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbf{E})}(R) = 1$, then $\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbf{F})}(R) = 1$. Suppose then that $\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbf{E})}(R) = 1$, i.e. that $R \in \eta_{\hspace{0cm}_{\large{S, \mathbf{G}}}}(\mathbf{E}) = \eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G})$. We need to show that $R \in \eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})$. Let $T \in \mathbf{E}\cap\mathbf{G}$ be such that $R = \eta_{\hspace{0cm}_{\large{S}}}(T)$. It suffices to show that $T \in \mathbf{F}$. Since $T \in \mathbf{G}$ and since $\big[\mathbb{1}_\mathbf{E}\big]_\mathbf{G} = \big[\mathbb{1}_\mathbf{F}\big]_\mathbf{G}$, $\mathbb{1}_\mathbf{E}(T) = \mathbb{1}_\mathbf{F}(T)$, i.e. $T\in\mathbf{F}\iff T\in\mathbf{E}$. Since $T \in \mathbf{E}$ we have $T\in\mathbf{F}$, as desired.

Before we proceed, we state an equality that will be used repeatedly in the rest of this proof. For every $\mathbf{F} \subseteq \mathfrak{P}X$ we have $\overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{F}]_\mathbf{G}\big) = \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}$. Indeed, $$ \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{F}]_\mathbf{G}\big) = \big[\eta_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big(\mathbb{1}_{\mathbf{F}}\big)\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} = \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}, \mathbf{G}}}(\mathbf{F})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} = \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}. $$

We now show that $\overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}$ is a bijection (from $\mathcal{B}_\mathbf{G}$ onto $\mathcal{B}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}$). We start by showing that $\overline{\eta}_{\hspace{0cm}_{\large{S},\mathbf{G}}}$ is injective. Let $[\mathbb{1}_\mathbf{E}]_\mathbf{G}, [\mathbb{1}_\mathbf{F}]_\mathbf{G} \in \mathcal{B}_\mathbf{G}$ for some $\mathbf{E}, \mathbf{F} \subseteq \mathfrak{P}X$ be such that $\overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{E}]_\mathbf{G}\big) = \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{F}]_\mathbf{G}\big)$. Then $\big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} = \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}$. Then $\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G})\cap\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G}) = \eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})\cap\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})$. Then $\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G}) = \eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})$. Since the restriction of $\eta_S$ to $\mathbf{G}$ is injective (as $S$ is a distinguishing set for $\mathbf{G}$), we get $\mathbf{E}\cap\mathbf{G} = \mathbf{F}\cap\mathbf{G}$, which implies that $[\mathbb{1}_\mathbf{E}]_\mathbf{G} = [\mathbb{1}_\mathbf{F}]_\mathbf{G}$. Next we show that $\overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}$ is surjective. Let $[\mathbb{1}_\mathbf{F}]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \in \mathcal{B}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}$ for some $\mathbf{F} \subseteq \mathfrak{P}X$. Let $\mathbf{E}\subseteq\mathbf{G}$ be such that $\eta_S(\mathbf{E}) = \mathbf{F} \cap \eta_S(\mathbf{G})$. Then $$ \begin{align} \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{E}]_{\mathbf{G}}\big) &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\mathbb{1}_{\mathbf{F}\ \cap\ \eta_S(\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= [\mathbb{1}_\mathbf{F}]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}. \end{align} $$

Finally, we show that $\overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}$ is a homomorphism from $\Psi_\mathbf{G}$ to $\Psi_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})}$. It suffices to show that $\overline{\vee}$ and $\overline{\neg}$ are homomorphic (why?).

1. Let $[\mathbb{1}_\mathbf{E}]_\mathbf{G}, [\mathbb{1}_\mathbf{F}]_\mathbf{G} \in \mathcal{B}_\mathbf{G}$ for some $\mathbf{E}, \mathbf{F} \subseteq \mathfrak{P}X$. Then $$ \begin{align} \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{E}]_\mathbf{G} \overline{\vee} [\mathbb{1}_\mathbf{F}]_\mathbf{G}\big) &= \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{E} \vee \mathbb{1}_\mathbf{F}]_\mathbf{G}\big) \\ &= \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_{\mathbf{E} \cup \mathbf{F}}]_\mathbf{G}\big) \\ &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G}\ \cup\ \mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G})\ \cup\ \eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G})}\ \vee\ \mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{E}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \overline{\vee} \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{E}]_\mathbf{G}\big) \overline{\vee} \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{F}]_\mathbf{G}\big). \end{align} $$

2. Let $[\mathbf{1}_F]_\mathbf{G} \in \mathcal{B}_\mathbf{G}$ for some $\mathbf{F} \subseteq \mathfrak{P}X$. Then $$ \begin{align} \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big(\overline{\neg}[\mathbb{1}_\mathbf{F}]_\mathbf{G}\big) &= \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\neg\mathbb{1}_\mathbf{F}]_\mathbf{G}\big) \\ &= \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big(\big[\mathbb{1}_{\mathbf{F}^c}\big]_\mathbf{G}\big) \\ &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G}\setminus\mathbf{F}})\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &\overset{(*)}{=} \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})\ \setminus\ \eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})\ \cap\ (\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G}))^c}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\mathbb{1}_{(\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G}))^c}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \big[\neg\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \overline{\neg}\big[\mathbb{1}_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{F}\cap\mathbf{G})}\big]_{\eta_{\hspace{0cm}_{\large{S}}}(\mathbf{G})} \\ &= \overline{\neg}\ \overline{\eta}_{\hspace{0cm}_{\large{S}, \mathbf{G}}}\big([\mathbb{1}_\mathbf{F}]_\mathbf{G}\big), \end{align} $$ $(*)$ is due to $S$ being a distinguishing set for $\mathbf{G}$.

Q.E.D.

VII) Boolean combinators and combinations

Let $\Phi = (S, \vee, \wedge, \neg, 0, 1)$ be a Boolean algebra. We define the set, $\mathcal{C}^\Phi_1$, of Boolean combinators of height at most $1$, to be $$ \mathcal{C}^\Phi_1 := \{\vee, \wedge, \neg, \mathrm{Id}_S\}. $$

For every $i \in \mathbb{N}$ with$i > 1$ we define the set $\mathcal{C}^\Phi_i$, of Boolean combinators of height at most $i$, to consist of all the functions $f \in \mathcal{F}^S$ that satisfy at least one of the following conditions.

1. $\deg(f) = k + m$, for some $k, m \in \mathbb{N}$, and there are some $g, h \in \mathcal{C}^\Phi_{i-1}$, with $k = \deg(g), m = \deg(h)$, such that $f = g\vee h$ in the sense that for every $s_1, \dots, s_k, t_1, \dots, t_m \in S$, $$ f(s_1, \dots, s_k, t_1, \dots, t_m) := g(s_1, \dots, s_k) \vee h(t_1, \dots, t_m). $$

2. $\deg(f) = k + m$, for some $k, m \in \mathbb{N}$, and there are some $g, h \in \mathcal{C}^\Phi_{i-1}$, with $k = \deg(g), m = \deg(h)$, such that $f = g\wedge h$ in the sense that for every $s_1, \dots, s_k, t_1, \dots, t_m \in S$, $$ f(s_1, \dots, s_k, t_1, \dots, t_m) := g(s_1, \dots, s_k) \wedge h(t_1, \dots, t_m). $$

3. $f = \neg g$ for some $g \in \mathcal{C}^\Phi_{i-1}$.

4. $f \in \mathcal{C}^\Phi_{i-1}$.

We define the set $\mathcal{C}^\Phi$, of Boolean combinators, to be $$ \mathcal{C}^\Phi := \bigcup_{i = 1}^\infty \mathcal{C}^\Phi_i. $$

The reader should verify the following consequences of this definition.

• It can be shown by induction on $i \in \mathbb{N}$ that $\mathcal{C}^\Phi_i$ is finite. Hence $\mathcal{C}^\Phi$ is countable.

• If $\Phi' := (R, \vee, \wedge, \neg, 0, 1)$ is a sub-Boolean algebra of $\Phi$ ($R\subseteq S$), then it can be shown by induction on $i \in \mathbb{N}$ that $f \in \mathcal{C}^{\Phi'}_i$ iff there is some $g \in \mathcal{C}^\Phi_i$ such that $\deg(f) = \deg(g)$ and such that $f$ is the restriction of $g$ to $R^{\deg(f)}$. Thus $f \in \mathcal{C}^{\Phi'}$ iff $f$ is the restriction to $R^{\deg(f)}$ of some $g \in \mathcal{C}^\Phi$.

For every subset, $R$, of $S$, the set $\mathcal{C}^\Phi(R)$, of Boolean combinations generated by $R$, is defined to be the set of every possible instantiation of every Boolean combinator, with arguments taken from $R$: $$ \mathcal{C}^\Phi(R) := \bigcup_{i = 1}^\infty \underset{=:\mathcal{C}^\Phi_i(R)}{\underbrace{\big\{f(s_1, \dots, s_{\deg(f)})\ :|\ f \in \mathcal{C}^\Phi_i,\ s_1, \dots, s_{\deg(f)} \in R\big\}}}. $$ Equivalently, $$ \mathcal{C}^\Phi(R) = \bigcup_{f \in \mathcal{C}^{\Phi_1}}\big\{f(s_1, \dots, s_k)\ :\!\big|\ s_1, \dots, s_k \in R,\ k=\deg(f)\big\}. $$

The reader should verify the following consequences of this definition.

• If $R\neq\emptyset$, then $0 \in \mathcal{C}^\Phi(R)$. Indeed, take any $r \in R$. Then $0 = r\ \wedge\ \neg\ r \in \mathcal{C}^\Phi$.

• If $R$ is countable, then for every $f \in \mathcal{C}^\Phi$ there are $|R|^{\deg(f)} \leq \aleph_0^{\deg(f)} = \aleph_0$ ways of instantiating $f$, and therefore $\mathcal{C}^\Phi(R)$ is countable.

• If $\Phi' := (R, \vee, \wedge, \neg, 0, 1)$, is a sub-Boolean algebra of $\Phi$ ($R\subseteq S$), then for every $Q\subseteq R$, $\mathcal{C}^{\Phi'}(Q) = \mathcal{C}^\Phi(Q)$.

• For every $Q \subseteq \mathcal{C}^\Phi(R)$ it can be shown by induction on $i \in \mathbb{N}$ that $\mathcal{C}^\Phi_i(Q) \subseteq \mathcal{C}^\Phi(R)$, hence $\mathcal{C}^\Phi(Q) \subseteq \mathcal{C}^\Phi(R)$.

• Given a partition, $\mathbf{F}$, of $S$ that is self-consistent with $\{\vee, \wedge, \neg\}$, it can be shown by induction on $i \in \mathbb{N}$ together with the third bullet point in section V, that $\mathbf{F}$ is self-consistent with $\mathcal{C}^\Phi_i$. Therefore, $\mathbf{F}$ is self-consistent with $\mathcal{C}^\Phi$.

Answer 4

VIII) Homomorphic Boolean combinations

Let $\Phi_i = (S_i, \vee_i, \wedge_i, \neg_i, 0_i, 1_i)$, $i \in \{1, 2\}$, be Boolean algebras, and let $h:S_1\rightarrow S_2$ be a homomorphism. If $h$ is surjective, then the pullback $h^*$ (see section V) is well-defined for every $f \in \mathcal{C}^{\Phi_1}$, and we have the following result.

Theorem 4 If $h$ is surjective, $\mathcal{C}^{\Phi_2} = h^*\big(\mathcal{C}^{\Phi_1}\big)$.

Proof

It suffices to show that for every $i \in \mathbb{N}$, $\mathcal{C}^{\Phi_2}_i = h^*\big(\mathcal{C}^{\Phi_1}_i\big)$. We proceed by induction on $i$. Firstly suppose that $i = 1$. Then we need to show that $$ \{\vee_2, \wedge_2, \neg_2, \mathrm{Id}_{S_2}\} = \big\{h^*(\vee_1), h^*(\wedge_1), h^*(\neg_1), h^*(\mathrm{Id}_{S_1})\big\}. $$

1. For every $s, t \in S_1$, $h(s\vee_1t) = h(s)\vee_2h(t)$. Therefore, by The Fundamental Characterization of Pullbacks (see section V), $\vee_2 = h^*(\vee_1)$.

2. For every $s, t \in S_1$, $h(s\wedge_1t) = h(s)\wedge_2h(t)$. Therefore, by The Fundamental Characterization of Pullbacks, $\wedge_2 = h^*(\wedge_1)$.

3. For every $s \in S_1$, $h(\neg_1\ s) = \neg_2\ h(s)$. Therefore, by The Fundamental Characterization of Pullbacks, $\neg_2 = h^*(\neg_1)$.

4. For every $s \in S_1$, $h\big(\mathrm{Id}_{S_1}(s)\big) = \mathrm{Id}_{S_2}\big(h(s)\big)$. Therefore, by The Fundamental Characterization of Pullbacks, $\mathrm{Id}_{S_2} = h^*(\mathrm{Id}_{S_1})$.

Next suppose that $i > 1$ and that $\mathcal{C}^{\Phi_2}_{i-1} = h^*\big(\mathcal{C}^{\Phi_1}_{i-1}\big)$. We show two-way containment. To see that $\mathcal{C}^{\Phi_2}_i \subseteq h^*\big(\mathcal{C}^{\Phi_1}_i\big)$, let $f \in \mathcal{C}^{\Phi_2}_i$. We consider the four possible cases.

1. $f = g_1 \vee_2 g_2$ for some $g_1, g_2 \in \mathcal{C}^{\Phi_2}_{i-1}$ with $k = \deg(g_1), m = \deg(g_2)$.

   Let $g_1', g_2' \in \mathcal{C}^{\Phi_1}_{i-1}$ be such that $g_1 = h^*(g_1')$ and $g_2 = h^*(g_2')$, and define $f' := g_1'\vee_1 g_2'$. Note that $f' \in \mathcal{C}^{\Phi_1}_i$.

   Let $s_1, \dots, s_k, t_1, \dots, t_m \in S$. Then $$ \begin{align} h\big(f'(s_1, \dots, s_k, t_1, \dots, t_m)\big) &= h\big(g_1'(s_1, \dots, s_k) \vee_1 g_2'(t_1, \dots, t_m)\big) \\ &= h\big(g_1'(s_1, \dots, s_k)\big) \vee_2 h\big(g_2'(t_1, \dots, t_m)\big) \\ &= h^*(g_1')\big(h(s_1), \dots, h(s_k)\big) \vee_2 h^*(g_2')\big(h(t_1), \dots, h(t_m)\big) \\ &= g_1\big(h(s_1), \dots, h(s_k)\big) \vee_2 g_2\big(h(t_1), \dots, h(t_m)\big) \\ &= f\big(h(s_1), \dots, h(s_k), h(t_1), \dots, h(t_m)\big). \end{align} $$

   Therefore, by The Fundamental Characterization of Pullbacks, $f = h^*(f')$.

2. $f = g_1 \wedge_2 g_2$ for some $g_1, g_2 \in \mathcal{C}^{\Phi_2}_{i-1}$ with $k = \deg(g_1), m = \deg(g_2)$.

   Let $g_1', g_2' \in \mathcal{C}^{\Phi_1}_{i-1}$ be such that $g_1 = h^*(g_1')$ and $g_2 = h^*(g_2')$, and define $f' := g_1'\wedge_1 g_2'$. Note that $f' \in \mathcal{C}^{\Phi_1}_i$.

   Let $s_1, \dots, s_k, t_1, \dots, t_m \in S$. Then $$ \begin{align} h\big(f'(s_1, \dots, s_k, t_1, \dots, t_m)\big) &= h\big(g_1'(s_1, \dots, s_k) \wedge_1 g_2'(t_1, \dots, t_m)\big) \\ &= h\big(g_1'(s_1, \dots, s_k)\big) \wedge_2 h\big(g_2'(t_1, \dots, t_m)\big) \\ &= h^*(g_1')\big(h(s_1), \dots, h(s_k)\big) \wedge_2 h^*(g_2')\big(h(t_1), \dots, h(t_m)\big) \\ &= g_1\big(h(s_1), \dots, h(s_k)\big) \wedge_2 g_2\big(h(t_1), \dots, h(t_m)\big) \\ &= f\big(h(s_1), \dots, h(s_k), h(t_1), \dots, h(t_m)\big). \end{align} $$

   Therefore, by The Fundamental Characterization of Pullbacks, $f = h^*(f')$.

3. $f = \neg_2\ g$ for some $g \in \mathcal{C}^{\Phi_2}_{i-1}$ with $k = \deg(f)$.

   Let $g' \in \mathcal{C}^{\Phi_1}_{i-1}$ be such that $g = h^*(g')$, and define $f' := \neg_1\ g'$. Note that $f' \in \mathcal{C}^{\Phi_1}_i$.

   Let $s_1, \dots, s_k \in S$. Then $$ \begin{align} h\big(f'(s_1, \dots, s_k)\big) &= h\big(\neg_1\ g'(s_1, \dots, s_k)\big) \\ &= \neg_2\ h\big(g'(s_1, \dots, s_k)\big) \\ &= \neg_2\ h^*(g')\big(h(s_1), \dots, h(s_k)\big) \\ &= \neg_2\ g\big(h(s_1), \dots, h(s_k)\big) \\ &= f\big(h(s_1), \dots, h(s_k)\big). \end{align} $$

   Therefore, by The Fundamental Characterization of Pullbacks, $f = h^*(f')$.

4. $f \in \mathcal{C}^{\Phi_2}_{i-1}$. Then $f \in h^*\big(\mathcal{C}^{\Phi_1}_{i-1}\big) \subseteq h^*\big(\mathcal{C}^{\Phi_1}_i\big)$.

To see that $\mathcal{C}^{\Phi_2}_i \supseteq h^*\big(\mathcal{C}^{\Phi_1}_i\big)$, let $f \in \mathcal{C}^{\Phi_1}_i$. We consider the four possible cases.

1. $f = g_1 \vee_1 g_2$ for some $g_1, g_2 \in \mathcal{C}^{\Phi_1}_{i-1}$, with $k = \deg(g_1), m = \deg(g_2)$.

   Define $f' := h^*(g_1)\vee_2 h^*(g_2)$. Note that since $h^*(g_1), h^*(g_2) \in \mathcal{C}^{\Phi_2}_{i-1}$, we have $f' \in \mathcal{C}^{\Phi_2}_i$.

   Let $s_1, \dots, s_k, t_1, \dots, t_m \in S$. Then $$ \begin{align} h\big(f(s_1, \dots, s_k, t_1, \dots, t_m)\big) &= h\big(g_1(s_1, \dots, s_k) \vee_1 g_2(t_1, \dots, t_m)\big) \\ &= h\big(g_1(s_1, \dots, s_k)\big) \vee_2 h\big(g_2(t_1, \dots, t_m)\big) \\ &= h^*(g_1)\big(h(s_1), \dots, h(s_k)\big) \vee_2 h^*(g_2)\big(h(t_1), \dots, h(t_m)\big) \\ &= f'\big(h(s_1), \dots, h(s_k), h(t_1), \dots, h(t_m)\big). \end{align} $$

   Therefore, by The Fundamental Characterization of Pullbacks, $f' = h^*(f)$.

2. $f = g_1 \wedge_1 g_2$ for some $g_1, g_2 \in \mathcal{C}^{\Phi_1}_{i-1}$, with $k = \deg(g_1), m = \deg(g_2)$.

   Define $f' := h^*(g_1)\wedge_2 h^*(g_2)$. Note that since $h^*(g_1), h^*(g_2) \in \mathcal{C}^{\Phi_2}_{i-1}$, we have $f' \in \mathcal{C}^{\Phi_2}_i$.

   Let $s_1, \dots, s_k, t_1, \dots, t_m \in S$. Then $$ \begin{align} h\big(f(s_1, \dots, s_k, t_1, \dots, t_m)\big) &= h\big(g_1(s_1, \dots, s_k) \wedge_1 g_2(t_1, \dots, t_m)\big) \\ &= h\big(g_1(s_1, \dots, s_k)\big) \wedge_2 h\big(g_2(t_1, \dots, t_m)\big) \\ &= h^*(g_1)\big(h(s_1), \dots, h(s_k)\big) \wedge_2 h^*(g_2)\big(h(t_1), \dots, h(t_m)\big) \\ &= f'\big(h(s_1), \dots, h(s_k), h(t_1), \dots, h(t_m)\big). \end{align} $$

   Therefore, by The Fundamental Characterization of Pullbacks, $f' = h^*(f)$.

3. $f = \neg_1\ g$ for some $g \in \mathcal{C}^{\Phi_1}_{i-1}$, with $k = \deg(g)$.

   Define $f' := \neg_2\ h^*(g)$. Note that since $h^*(g) \in \mathcal{C}^{\Phi_2}_{i-1}$, we have $f' \in \mathcal{C}^{\Phi_2}_i$.

   Let $s_1, \dots, s_k \in S$. Then $$ \begin{align} h\big(f(s_1, \dots, s_k)\big) &= h\big(\neg_1\ g(s_1, \dots, s_k)\big) \\ &= \neg_2\ h\big(g_1(s_1, \dots, s_k)\big) \\ &= \neg_2\ h^*(g_1)\big(h(s_1), \dots, h(s_k)\big) \\ &= f'\big(h(s_1), \dots, h(s_k)\big). \end{align} $$

   Therefore, by The Fundamental Characterization of Pullbacks, $f' = h^*(f)$.

4. $f \in \mathcal{C}^{\Phi_1}_{i-1}$. Then $h^*(f) \in \mathcal{C}^{\Phi_2}_{i-1} \subseteq \mathcal{C}^{\Phi_2}_i$.

Q.E.D.

Corollary 5 For every $R \subseteq S_1$, $h\big(\mathcal{C}^{\Phi_1}(R)\big) = \mathcal{C}^{\Phi_2}\big(h(R)\big)$. ($h$ needs not be surjective.)

Proof

We may assume, w.l.g., that $h$ is surjective, because if not, define $\Phi_2'$ to be the sub-Boolean algebra $\Phi_2' := \big(h(S_1), \vee_2, \wedge_2, \neg_2, 0_2, 1_2\big)$ (see the first bullet-point before Theorem 3 in section VI). Then $h$ is a surjective homomorphism from $\Phi_1$ to $\Phi_2'$, and, by the third bullet point in the end of the previous section, $\mathcal{C}^{\Phi_2'}\big(h(R)\big) = \mathcal{C}^{\Phi_2}\big(h(R)\big)$. Then $$ \begin{align} h\big(\mathcal{C}^{\Phi_1}(R)\big) &= h\Bigg(\bigcup_{f \in \mathcal{C}^{\Phi_1}}\big\{f(s_1, \dots, s_k)\ :\!\big|\ s_1, \dots, s_k \in R,\ k=\deg(f)\big\}\Bigg) \\ &= \bigcup_{f \in \mathcal{C}^{\Phi_1}}\big\{(h\circ f)(s_1, \dots, s_k)\ :\!\big|\ s_1, \dots, s_k \in R,\ k=\deg(f)\big\} \\ &= \bigcup_{f \in \mathcal{C}^{\Phi_1}}\big\{(h\circ f)(s_1, \dots, s_k)\ :\!\big|\ s_1, \dots, s_k \in R,\ k=\deg(h\circ f)\big\} \\ &= \bigcup_{f \in \mathcal{C}^{\Phi_1}}\big\{h^*(f)\big(h(s_1), \dots, h(s_k)\big)\ :\!\big|\ s_1, \dots, s_k \in R,\ k=\deg\big(h^*(f)\big)\big\} \\ &= \bigcup_{f \in \mathcal{C}^{\Phi_1}}\big\{h^*(f)\big(t_1, \dots, t_k\big)\ :\!\big|\ t_1, \dots, t_k \in h(R),\ k=\deg\big(h^*(f)\big)\big\} \\ &= \bigcup_{g \in \mathcal{C}^{\Phi_2}}\big\{g\big(t_1, \dots, t_k\big)\ :\!\big|\ t_1, \dots, t_k \in h(R),\ k=\deg(g)\big\} \\ &= \mathcal{C}^{\Phi_2}\big(h(R)\big). \end{align} $$

Q.E.D.

IX) Defining $\mathbf{\mathcal{A}}$ and showing that if $\mathbf{X}$ is countable, so is $\mathbf{\mathcal{A}}$

Consider the function $\xi:X\rightarrow\mathcal{B}$ that assigns to every $x \in X$ the indicator function of the subsets of $X$ that contain $x$: $$ \xi(x) := \mathbb{1}_{\big\{S \subseteq X\ \big|\!:\ x \in S\big\}}. $$ To reiterate, for every $x \in X$, $\xi(x)$ is a function, whose domain is the collection of all subsets of $X$, and such that, for every $S \subseteq X$, $$ \xi(x)(S)=\begin{cases} 1 &, x \in S, \\ 0 &, x \notin S. \end{cases} $$

We define $\mathcal{A} := \mathcal{C}^\Psi\big(\mathfrak{I}(\xi)\big)$. In words, $\mathcal{A}$ is the set of all Boolean combinations generated by the indicator functions in $\xi$'s image. If $\xi$'s domain, $X$, is countable, so is $\xi$'s image, and therefore so is $\mathcal{A}$ (see the second bullet point in the end of section VII).

X) Proving that $\mathbf{\mathcal{A}}$ is $\mathbf{\mathbf{H}}$-dense in $\mathbf{\mathcal{B}}$

We finally arrive at the heart of our proof, the part that mirrors Wofsey's answer. This section consists of three results: a lemma, a theorem, and a corollary. Before getting our hands dirty with the details, let's take an overview.

The product topology, $\mathbf{H}$, on $\mathcal{B}$ will be shown in Corollary 8 to possess a natural basis, whose members have a particularly simple structure: each of them has the form $[\mathbb{1}_\mathbf{F}]_\mathbf{G}$, where $\mathbf{G}$ is a finite family of subsets of $X$, and $\mathbf{F} \subseteq \mathbf{G}$.

Theorem 7, capturing the core of Wofsey's answer, will show that each of these basis members is a Boolean combination of the elements of $\mathcal{A}$, when restricted to $\mathbf{G}$. It is in Theorem 7'th proof that the significance of distinguishing sets comes to light: they enable us to reduce the "intractable" case where some of the subsets comprising $\mathbf{G}$ are infinite to the case where all the members of $\mathbf{G}$ are finite. We tap into this finiteness in representing $[\mathbf{1}_\mathbf{F}]_\mathbf{G}$ as a Boolean combination, which is by definition a finitely generated object.

In order to reduce the general case to the finite one, Theorem 7 will make use of three results: Theorem 3 from section VI, Corollary 5 from section VIII, and Lemma 6 from this section, all of which use homomorphisms of Boolean algebras to synthesize the three fundamental concepts of Wofsey's answer: (a) the concept of a distinguishing set, (b) the notion of Boolean combinations generated by members of $\mathcal{B}$, and (c) the technique of restricting the domain of $\mathcal{B}$'s member functions.

Corollary 8 will tie all the loose ends and finish the proof.

Lemma 6 Let $\mathbf{G} \subseteq \mathfrak{P}X$, and let $T \subseteq X$. Then $$ \mathcal{C}^{\Psi_{\eta_{\hspace{0cm}_T}(\mathbf{G})}}\big([\mathfrak{I}(\xi)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\big) \subseteq \mathcal{C}^{\Psi_{\eta_{\hspace{0cm}_T}(\mathbf{G})}}\bigg(\Big[\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\big(\mathfrak{I}(\xi)\big)\Big]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\bigg). $$

Proof

By the first bullet point in the end of section VII, $[0]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} \in \mathcal{C}^{\Psi_{\eta_{\hspace{0cm}_T}(\mathbf{G})}}\bigg(\Big[\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\big(\mathfrak{I}(\xi)\big)\Big]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\bigg)$. Therefore, by the third bullet point in the end of section VII, it suffices to show that $$ [\mathfrak{I}(\xi)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} \subseteq \Big[\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\big(\mathfrak{I}(\xi)\big)\Big]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\ \cup\ \big\{[0]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\big\}. $$

A typical member of $[\mathfrak{I}(\xi)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}$ is of the form $[\xi(x)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}$, for some $x \in X$. Let $x \in X$. If $x \notin T$, then for every $R \in \mathfrak{P}T$, $\xi(x)(R) = 0$. Therefore, $[\xi(x)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} = [0]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}$. So suppose that $x \in T$. We will show that $[\xi(x)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} = \big[\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\big(\xi(x)\big)\big]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}$. Define $\mathbf{E} := \{S \subseteq X\ |\!:\ x \in S\}$, so that $\xi(x) = \mathbb{1}_\mathbf{E}$. Then $[\xi(x)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} = \big[\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\big(\xi(x)\big)\big]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}$ iff for every $S \in \mathbf{G}$, $(S\cap T) \in \mathbf{E} \iff (S\cap T) \in \eta_{\hspace{0cm}_{\large{T}}}(\mathbf{E\cap\mathbf{G}})$, iff for every $S \in \mathbf{G}$, $(S\cap T) \in \mathbf{E} \iff \exists R \in \mathbf{E}\cap\mathbf{G},\ S\cap T = R\cap T$, iff for every $S \in \mathbf{G}$, $x \in S\cap T \iff \exists R \in \mathbf{G}\ (x \in R\ \wedge\ S\cap T = R\cap T)$. So let $S \in \mathbf{G}$. If $x \in S\cap T$, then set $R := S$. Conversely, if $R \in \mathbf{G}$ is such that $x \in R$ and $S\cap T = R\cap T$, then since $x \in T$ by assumption, we have $x \in S\cap T$.

Q.E.D.

Theorem 7 For every finite $\mathbf{G}\subseteq\mathfrak{P}X$, and for every $\mathbf{F} \subseteq \mathbf{G}$, $[\mathbb{1}_\mathbf{F}]_\mathbf{G} \in \mathcal{C}^{\Psi_\mathbf{G}}\Big(\big[\mathfrak{I}(\xi)\big]_\mathbf{G}\Big)$.

Proof

1. Case 1: There is some finite $T\subseteq X$, such that $\mathbf{G}\subseteq\mathfrak{P}T$.

   It suffices to show that $$ [\mathbb{1}_\mathbf{F}]_\mathbf{G} = \Bigg[\bigvee_{S \in \mathbf{F}}\Bigg(\Bigg(\bigwedge_{s \in S} \xi(s)\big)\ \wedge\ \Bigg(\bigwedge_{t \in T\setminus S} \neg \xi(t)\Bigg)\Bigg)\Bigg]_\mathbf{G}, $$ since then the fact that the mapping $f\mapsto[f]_\mathbf{G}$ is a homomorphism (see the first paragraph of section VI), will yield $$ [\mathbb{1}_\mathbf{F}]_\mathbf{G} = \bigvee_{S \in \mathbf{F}}\Bigg(\Bigg(\bigwedge_{s \in S} \big[\xi(s)\big]_\mathbf{G}\Bigg)\ \wedge\ \Bigg(\bigwedge_{t \in T\setminus S} \neg \big[\xi(t)\big]_\mathbf{G}\Bigg)\Bigg) \in \mathcal{C}^{\Psi_\mathbf{G}}\big([\mathfrak{I}(\xi)]_\mathbf{G}\big). $$ Note that, thanks to our assumptions, all the disjunctions and conjunctions in the expressions above are finite.

   Let $R \in \mathbf{G}$. We need to show that $$ \mathbb{1}_\mathbf{F}(R) = \Bigg(\bigvee_{S \in \mathbf{F}}\Bigg(\Bigg(\bigwedge_{s \in S} \xi(s)\Bigg)\ \wedge\ \Bigg(\bigwedge_{t \in T\setminus S} \neg \xi(t)\Bigg)\Bigg)\Bigg)(R). \tag{1}\label{apple} $$

   Firstly suppose that $R \in \mathbf{F}$. Then the left hand side of \eqref{apple} equals $1$. To show that the right hand side of \eqref{apple} equals $1$ we need to show that, for some $S \in \mathbf{F}$, $$ \Bigg(\Bigg(\bigwedge_{s \in S} \xi(s)\Bigg)\ \wedge\ \Bigg(\bigwedge_{t \in T\setminus S} \neg \xi(t)\Bigg)\Bigg)(R) \tag{2}\label{banana} $$ equals $1$. We will show that this holds for $S = R$. We need to show that both $$ \Bigg(\bigwedge_{s \in S} \xi(s)\Bigg)(R) \tag{3}\label{cucumber} $$ and $$ \Bigg(\bigwedge_{t \in T\setminus S} \neg \xi(t)\Bigg)(R) \tag{4}\label{date} $$ equal $1$. To show that \eqref{cucumber} equals $1$ we need to show that for all $s \in S$, that is to say for all $s \in R$, $\xi(s)(R) = 1$, but this follows directly from $\xi$'s definition. To show that \eqref{date} equals $1$, we need to show that for all $t \in T\setminus S$, that is to say for all $t \in T\setminus R$, $(\neg \xi(t))(R) = 1$, i.e. that for all $t \in T\setminus R$, $\xi(t)(R) = 0$, which, again, follows directly from $\xi$'s definition.

   Next suppose that $R \notin \mathbf{F}$. This time the left hand side of \eqref{apple} equals $0$. To show that the right hand side of \eqref{apple} equals $0$ we need to show that, for every $S \in \mathbf{F}$, \eqref{banana} equals $0$. Let $S \in \mathbf{F}$. To show that \eqref{banana} equals $0$ it suffices to show that either \eqref{cucumber} or \eqref{date} equals $0$. We claim that if $S\setminus R \neq \emptyset$, then \eqref{cucumber} equals $0$, and that otherwise \eqref{date} equals $0$. To see it, suppose firstly that $S\setminus R \neq \emptyset$. To show that \eqref{cucumber} equals $0$ it suffices to show that for some $s \in S$, $\xi(s)(R) = 0$, i.e. that for some $s \in S$, $s \notin R$, and indeed this is the case for every $s \in S\setminus R$. Next suppose that $S\setminus R = \emptyset$. To see that \eqref{date} equals $0$, it suffices to show that for some $t \in T\setminus S$, $(\neg\xi(t))(R) = 0$, i.e. that for some $t \in T\setminus S$, $\xi(t)(R) = 1$, i.e. that for some $t \in T\setminus S$, $t \in R$. Since $S\setminus R = \emptyset$, then necessarily $R\setminus S \neq \emptyset$ (since otherwise we would have $R = S$, but $R \notin \mathbf{F}$ whereas $S \in \mathbf{F}$). For all $t \in R\setminus S$ we have $t \in R$, and since $R \in \mathbf{G} \subseteq \mathfrak{P}T$, we have $R\setminus S \subseteq T\setminus S$.

2. Case 2: The general case

   Let $T$ be a distinguishing set for $\mathbf{G}$ (see Theorem 1 in section III). Since $\mathbf{G}$ is finite, we may choose $T$ to be finite (ibid.). Since $\mathbf{F} \subseteq \mathbf{G}$, we have $\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}(\mathbf{F}) \subseteq \eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}(\mathbf{G}) = \eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G}) \subseteq \mathfrak{P}T$. Therefore, by case 1, $$ [\mathbb{1}_{\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}(\mathbf{F})}]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} \in \mathcal{C}^{\Psi_{\eta_{\hspace{0cm}_T}(\mathbf{G})}}\big([\mathfrak{I}(\xi)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\big). \tag{5}\label{eggplant} $$

   But $$ [\mathbb{1}_{\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}(\mathbf{F})}]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} = \big[\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}(\mathbb{1}_\mathbf{F})\big]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})} \overset{\text{Theorem 3}}{=} \overline{\eta}_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\big([\mathbb{1}_\mathbf{F}]_\mathbf{G}\big), \tag{6}\label{figs} $$ and $$ \begin{align} \mathcal{C}^{\Psi_{\eta_{\hspace{0cm}_T}(\mathbf{G})}}\big([\mathfrak{I}(\xi)]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\big) &\overset{\text{Lemma 6}}{\subseteq} \mathcal{C}^{\Psi_{\eta_{\hspace{0cm}_T}(\mathbf{G})}}\bigg(\Big[\eta_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\big(\mathfrak{I}(\xi)\big)\Big]_{\eta_{\hspace{0cm}_{\large{T}}}(\mathbf{G})}\bigg) \\ &\overset{\text{Theorem 3}}{=} \mathcal{C}^{\Psi_{\eta_{\hspace{0cm}_T}(\mathbf{G})}}\bigg(\overline{\eta}_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\Big(\big[\mathfrak{I}(\xi)\big]_\mathbf{G}\Big)\bigg) \\ &\overset{\text{Corollary 5}}{=} \overline{\eta}_{\hspace{0cm}_{\large{T, \mathbf{G}}}}\Big(\mathcal{C}^{\Psi_\mathbf{G}}\big([\mathfrak{I}(\xi)]_\mathbf{G}\big)\Big). \tag{7}\label{guava} \end{align} $$

   Since, by Theorem 3, the restriction of $\overline{\eta}_{\hspace{0cm}_{\large{T, \mathbf{G}}}}$ to $\mathcal{B}_\mathbf{G}$ is injective, \eqref{eggplant}, \eqref{figs} and \eqref{guava} imply that $$ [\mathbb{1}_\mathbf{F}]_\mathbf{G} \in \mathcal{C}^{\Psi_G}\big([\mathfrak{I}(\xi)]_\mathbf{G}\big). $$

Q.E.D.

Corollary 8 $\mathcal{A}$ is $\mathbf{H}$-dense in $\mathcal{B}$.

Proof

We quote from Bourbaki (1, chapter 4.1, p. 44, a couple phrases were deleted for readability):

Hence, since the set $\big\{\{0\}, \{1\}\big\}$ is a base for the topology $\mathbf{H}_0$, the following set is a base for $\mathbf{H}$: $$ \Big\{[\mathbb{1}_\mathbf{F}]_\mathbf{G}\ :\!\Big|\ \mathbf{F}\subseteq \mathbf{G}\subseteq\mathfrak{P}X,\ \mathbf{G}\text{ finite}\Big\}. $$

Accordingly, to show that $\mathcal{A}$ is $\mathbf{H}$-dense in $\mathcal{B}$, it suffices to show that for every finite $\mathbf{G}\subseteq \mathfrak{P}X$ and for every $\mathbf{F}\subseteq \mathbf{G}$, $$ [\mathbb{1}_\mathbf{F}]_\mathbf{G} \cap \mathcal{A} \neq \emptyset. $$

Since $$ [\mathbb{1}_\mathbf{F}]_\mathbf{G} \overset{\text{Theorem 7}}{\in} \mathcal{C}^{\Psi_\mathbf{G}}\big([\mathfrak{I}(\xi)]_\mathbf{G}\big) \overset{\text{Corollary 5}}{=} \Big[\mathcal{C}^\Psi\big(\mathfrak{I}(\xi)\big)\Big]_\mathbf{G} = [\mathcal{A}]_\mathbf{G}, $$ there is some $f \in \mathcal{A}$ such that $[\mathbb{1}_\mathbf{F}]_\mathbf{G} = [f]_\mathbf{G}$, and so $f \in [\mathbb{1}_\mathbf{F}]_\mathbf{G} \cap \mathcal{A}$.

Q.E.D.

---

References

1 N. Bourbaki. Elements of Mathematics: General Topology, Chapters 1-4. 1995. Springer. ISBN-13: 978-3-540-64241-1.