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

Solution 1:

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$.

Solution 2:

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$.

Solution 3:

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}}$.