0

I've proved the De Morgan's law $\neg (x \vee y) = \neg x \wedge \neg y$.

How can I prove that in every complete Boolean algebra $\neg \bigvee_{i \in I} x_i = \bigwedge_{i \in I} \neg x_i$?

effezeta
  • 445
  • Use the fact that $\neg$ is an order-reversing involution. – Geoffrey Trang Jul 08 '23 at 15:30
  • 1
    Well, how did you prove De Morgan's law? you proof probably generalizes... – Alex Kruckman Jul 08 '23 at 15:31
  • On one side I have that $x_j \le \bigvee_{i \in I} x_i$ for every $j \in I$, then $\neg \bigvee_{i \in I} x_i \le \neg x_j$ for every $j \in I$, then $\neg \bigvee_{i \in I} x_i \le \bigwedge_{i \in I} \neg x_i$. But how can I prove the other inequality? – effezeta Jul 08 '23 at 16:18

1 Answers1

1

To show that $\neg \bigvee_{i \in I} x_i = \bigwedge_{i \in I} \neg x_i$, you need to show that $\neg \bigvee_{i \in I} x_i$ is the greatest lower bound of $\{\neg x_i\mid i\in I\}$.

One half is the argument you give in the comments: Since $x_j\leq \bigvee_{i\in I} x_i$, $\lnot \bigvee_{i\in I} x_i \leq \lnot x_j$, so $\lnot \bigvee_{i\in I} x_i$ is a lower bound of $\{\neg x_i\mid i\in I\}$.

To show it is the greatest lower bound, suppose $y\leq \lnot x_j$ for all $j\in I$. Then $x_j\leq \lnot y$ for all $j\in I$, so $\bigvee_{i\in I} x_i\leq \lnot y$, so $y\leq \lnot \bigvee_{i\in I} x_i$.

Alex Kruckman
  • 76,357