3

The homomorphism theorem states that every boolean ideal $I$ of a boolean algebra $A$ is the kernel of a boolean isomorphism. I'm reading a paper where the author presents a short proof of this theorem, saying that the following definition of equivalence relation $a\equiv b \iff \exists i,j\in I: a\lor i = b \lor j$ will do the work.

I'm having trouble to prove that the complement in the quotient $A/\equiv$ (defined as $\neg[a]=[\neg a]$) does not depend on the choice of $a$. That is, if $a \lor i = b \lor j$ for some $i,j \in I$, then there will be $i',j' \in I$ such that $\neg a \lor i' = \neg b \lor j'$.

So my question is: is this equivalence really fit for the job? If so, a hint on how to prove the above will be appreciated.

Tarc
  • 509

2 Answers2

6

Let $i'=j'=k=i\vee j\in I$.

Then $a\vee k=b\vee k$.

Proof: $a\vee k=a\vee(i\vee j)=(a\vee i)\vee j=(b\vee j)\vee j=b\vee(j\vee j)=b\vee j$
$=a\vee i=a\vee(i\vee i)=(a\vee i)\vee i=(b\vee j)\vee i=b\vee(i\vee j)=b\vee k.$

Also $\neg a\vee k=k\vee\neg(a\vee k).$

Proof: $\neg a\vee k=(\neg a\vee k)\wedge(k\vee\neg k)=[(\neg a\vee k)\wedge k]\vee[(\neg a\vee k)\wedge\neg k]=k\vee(\neg a\wedge\neg k)$
$=k\vee\neg(a\vee k).$

Likewise $\neg b\vee k=k\vee\neg(b\vee k).$

Proof: same as above, with $a$ replaced by $b.$

Since $a\vee k=b\vee k$, it follows that $\neg a\vee k=k\vee\neg(a\vee k)=k\vee\neg(b\vee k)=\neg b\vee k,$
i.e., $a\equiv b$.

bof
  • 78,265
2

The short answer is: let $i' = \neg b \land a$ and $j' = \neg a \land b$.

But I only could arrive at this solution after I quit using the above definition of quotient by and ideal $I$ and learned that the following one is equivalent:

$$ a \equiv b \text{ if, and only if, } a \vartriangle b \in I$$

where $a \vartriangle b = (a \land \neg b) \lor (b \land \neg a)$, which is called the symmetric difference between $a$ and $b$. That is:

$$ \exists i,j \in I: a\lor i = b \lor j ~~\text{ if, and only if, }~~ a \vartriangle b \in I$$

The "if" part goes as follows: As $I$ is closed for all elements of the boolean algebra which are less than some element of $I$, both $a \land \neg b$ and $b \land \neg a$ are in $I$:

$$ a \land \neg b \in I ~~\text{ and }~~ b \land \neg a \in I \tag{1}$$

and then: $$ a \lor (b \land \neg a) = (a \lor b) \land (a \lor \neg a) = a \lor b = (b \lor a) \land (b \lor \neg b) = b \lor (a \land \neg b) \tag{2}$$

For the "only if" part observe that by the definition of least upper bound of $b$ and $j$ it follows that $b \leq a \lor i$. From this it can be seen that $b \land \neg a \leq i$. Similarly $a \land \neg b \leq j$ and as $I$ is closed by sups, $a \vartriangle b \in I$:

$$ \text{if } a \lor i = b \lor j \text{ with } i,j \in I \text{ then } a \vartriangle b \in I \tag{3}$$

Another property of the symmetric difference is in order: $$a \vartriangle b = \neg a \vartriangle \neg b \tag{4}$$ Summing all this up:

$$\begin{gather} a \lor i = b \lor j ~~\text{ with } i,j \in I \tag{Hyp.}\\ a \vartriangle b = \neg a \vartriangle \neg b \in I \tag{3, 4}\\ \neg a \lor (\neg b \land \neg\neg a) = \neg b \lor (\neg a \land \neg\neg b) \tag{2} \\ \neg b \land \neg\neg a ~\text{ and } \neg a \land \neg\neg b \in I \tag{1} \end{gather}$$

As $\neg\neg x = x$ in any boolean algebra, the result follows.

Tarc
  • 509