7
$\begingroup$

Let $W$ be any non-empty set. We call a subset $A$ of $\mathscr{P}(W)$ a 3-fold filter on $W$ if the following hold:

(i) $W\in A$ and $\varnothing\notin A$;

(ii) If $a\in A$ and $a\subset b$ then $b\in A$;

(iii) If $a,b,c\in A$ then $(a\cap b)\cup(b\cap c)\cup(c\cap a)\in A$.

Now let $A,B$ be two 3-fold filters on $W$. Let $X=\{a\times W\mid a\in A\}$ and $Y=\{W\times b\mid b\in B\}$. Prove that $X\cup Y$ can be extended to a 3-fold filter on $W\times W$, i.e., $\varnothing$ is not contained in the closure of $X\cup Y$ under the operation $(a\cap b)\cup(b\cap c)\cup(c\cap a)$.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

First, a bit of notation: if $a_1,\dots,a_n\subseteq W$, let $\chi_{a_1,\dots,a_n}\colon W\to\{0,1\}^n$ denote the “$n$-fold characteristic function” $$\chi_{a_1,\dots,a_n}(u)=([u\in a_1],\dots,[u\in a_n]),\qquad u\in W,$$ where $[\ ]$ is the Iverson bracket. For a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$, let $S_f\colon\mathcal P(W)^n\to\mathcal P(W)$ be the corresponding set operator $$S_f(a_1,\dots,a_n)=\{u\in W:f(\chi_{a_1,\dots,a_n}(u))=1\}.$$

In this notation, a 3-fold filter is a nonempty upper subset $A\subseteq\mathcal P(W)$ closed under $S_m$, where $m(x,y,z)$ is the ternary majority function. (I am allowing $\varnothing\in A$ here; I will call a 3-fold filter proper if $\varnothing\notin A$.)

I will also need a little information on Boolean clones, see Post’s lattice. The majority function $m(x,y,z)$ generates the clone of all monotone self-dual Boolean functions. It follows that for a nonempty set $X\subseteq\mathcal P(W)$, the 3-fold filter generated by $X$ consists of sets $a$ such that $$a\supseteq S_f(a_1,\dots,a_n)$$ for some $a_1,\dots,a_n\in X$, and a monotone self-dual function $f\colon\{0,1\}^n\to\{0,1\}$.

It will be actually more convenient to use a slightly different characterization. Since 3-fold filters are closed upwards, they are closed under $S_f$ not only for monotone self-dual $f$, but also for Boolean functions $f$ such that $f(x_1,\dots,x_n)\ge g(x_1,\dots,x_n)$ for some monotone self-dual function $g$. Now, the collection of all such functions $f$ forms the clone denoted $T_1^2$ on the linked page; it can be described intrinsically as the set of all functions $f\colon\{0,1\}^n\to\{0,1\}$ such that $$\alpha\lor\beta=\mathbf1\implies f(\alpha)\lor f(\beta)=1$$ for all $\alpha,\beta\in\{0,1\}^n$, where $\alpha\lor\beta$ is defined coordinatewise, and $\mathbf1=(1,\dots,1)$. (That is, $f$ is polymorphism of the relation $\{(1,1),(1,0),(0,1)\}$.)

So, the 3-fold filter generated by $X\subseteq\mathcal P(W)$ is $$\langle X\rangle=\{a\subseteq W:\exists a_1,\dots,a_n\in X\,\exists f\in T_1^2\,a\supseteq S_f(a_1,\dots,a_n)\}.$$

Lemma: If $A\subseteq\mathcal P(W)$ is a proper 3-fold filter, and $a_1,\dots,a_n\in A$, there exist $u,u'\in W$ such that $\chi_{a_1,\dots,a_n}(u)\lor\chi_{a_1,\dots,a_n}(u')=\mathbf1$.

Proof: Define a function $f\colon\{0,1\}^n\to\{0,1\}$ by $$f(\alpha)=0\iff\exists u\in W\,\chi_{a_1,\dots,a_n}(u)=\alpha.$$ By definition, $S_f(a_1,\dots,a_n)=\varnothing\notin A$, hence $f\notin T_1^2$. Thus, there are $\alpha,\beta$ such that $\alpha\lor\beta=\mathbf1$, and $f(\alpha)=f(\beta)=0$. The latter means there are $u,u'\in W$ such that $\alpha=\chi_{a_1,\dots,a_n}(u)$ and $\beta=\chi_{a_1,\dots,a_n}(u')$. QED

Now, let $A$, $B$, $X$, and $Y$ be as in the question, and assume for contradiction that $\varnothing\in\langle X\cup Y\rangle$. Thus, there are $a_1,\dots,a_n\in A$, $b_1,\dots,b_m\in B$, and a function $f\in T_1^2$ such that $$S_f(a_1\times W,\dots,a_n\times W,W\times b_1,\dots,W\times b_m)=\varnothing.$$ Using the lemma, there are $u,u',v,v'\in W$ such that $$\begin{align} \chi_{a_1,\dots,a_n}(u)\lor\chi_{a_1,\dots,a_n}(u')&=\mathbf1,\\ \chi_{b_1,\dots,b_m}(v)\lor\chi_{b_1,\dots,b_m}(v')&=\mathbf1. \end{align}$$ Put $w=(u,v)$ and $w'=(u',v')$. Then $w,w'\in W\times W$ satisfy $$\chi_{a_1\times W,\dots,a_n\times W,W\times b_1,\dots,W\times b_m}(w)\lor\chi_{a_1\times W,\dots,a_n\times W,W\times b_1,\dots,W\times b_m}(w')=\mathbf1,$$ thus $$f(\chi_{a_1\times W,\dots,a_n\times W,W\times b_1,\dots,W\times b_m}(w))\lor f(\chi_{a_1\times W,\dots,a_n\times W,W\times b_1,\dots,W\times b_m}(w'))=1$$ as $f\in T_1^2$. However, this means that $w$ or $w'$ is an element of $S_f(a_1\times W,\dots,a_n\times W,W\times b_1,\dots,W\times b_m)$, a contradiction.

$\endgroup$
2
  • $\begingroup$ Thank you very much. By the way, are there some good references on Post’s lattice or clone theory besides the ones in Wikipedia? $\endgroup$ Commented Jun 30, 2017 at 1:37
  • $\begingroup$ I’m afraid I don’t. What I know about the subject, I learned by bits and pieces from various papers etc. $\endgroup$ Commented Jun 30, 2017 at 11:23

You must log in to answer this question.

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