Proving Boolean Lattice Complementarity in [a,b]

  • MHB
  • Thread starter Aryth1
  • Start date
  • Tags
    Lattice
In summary, we have shown that the interval $[a,b]$ in a Boolean lattice $L$ is a Boolean lattice under the partial ordering inherited from $L$. This was proven by first showing that $[a,b]$ is a sublattice of $L$ and then proving that it is complemented. This result follows from the fact that $L$ is a Boolean lattice and thus has a complement for any element.
  • #1
Aryth1
39
0
The problem is this:

Let $L$ be a Boolean lattice. For all $a<b\in L$, prove that the interval $[a,b] = \uparrow a \cap \downarrow b$ is a Boolean lattice under the partial ordering inherited from $L$.

What I've managed to do so far:

I used the fact that $[a,b]$ was a poset and showed that, for any $x,y\in [a,b]$, $x\vee y\in [a,b]$ and $x\wedge y\in [a,b]$ which proved that $[a,b]$ was a sublattice of $L$. From this we get that $[a,b]$ is distributive for free, since if $L$ had a sublattice that wasn't distributive, then $L$ would not be distributive. All that remains is to show that $[a,b]$ is complemented. I cannot seem to figure this out. I know that, if we take some $x\in [a,b]$ then a complement exists in $L$ since $L$ is a Boolean lattice, but I don't know how to show that that complement is in $[a,b]$ also.

Any hints would be greatly appreciated!
 
Physics news on Phys.org
  • #2
Nevermind, I figured it out. Close or delete if you like.
 
  • #3
Aryth said:
Nevermind, I figured it out. Close or delete if you like.

If you want, and it is entirely up to you, you could post your solution for the benefit of others who might gain from your solution. :D
 
  • #4
MarkFL said:
If you want, and it is entirely up to you, you could post your solution for the benefit of others who might gain from your solution. :D

Ah, OK then.

I'll limit the problem to proving that $[a,b]$ is complemented.

Let $x\in [a,b]$. Then, since $L$ is a Boolean lattice, $x$ has a complement in $L$, call it $y$. We claim that the complement of $x$ in $[a,b]$ is $z = (y\vee a)\wedge b$. To see this, observe that:
$x\wedge z = x\wedge (y\vee a)\wedge b = [(x\wedge y)\vee (x\wedge a)]\wedge b = (\bot\vee a)\wedge b = a$​
Similarly, $x\vee z = b$ and $z$ suffices as a complement for $x$ in $[a,b]$. Since $x$ was arbitrary, $[a,b]$ is complemented.
 
  • #5


First of all, great job on proving that $[a,b]$ is a sublattice of $L$ and that it is distributive. To show that $[a,b]$ is complemented, we need to show that for every $x\in [a,b]$, there exists a unique element $x^*\in [a,b]$ such that $x\vee x^* = b$ and $x\wedge x^* = a$.

To start, let's consider the set $S = \{x^*\in L | x\vee x^* = b \text{ and } x\wedge x^* = a\}$. We want to show that $x^*$ exists and is unique.

First, let's show that $x^*$ exists. Since $b\in L$, we know that $x\vee b = b$. This means that $b$ is an upper bound for $x$ in $L$. Similarly, $a$ is a lower bound for $x$ in $L$. Since $L$ is a Boolean lattice, we can take the supremum of all upper bounds of $x$ and the infimum of all lower bounds of $x$ to get the unique element $x^*\in L$ such that $x\vee x^* = b$ and $x\wedge x^* = a$. Therefore, $x^*\in S$ and $x^*$ exists.

Next, we need to show that $x^*$ is unique. Suppose there exists another element $y^*\in S$ such that $x\vee y^* = b$ and $x\wedge y^* = a$. Then, we have $x\vee x^* = b = x\vee y^*$. Since $L$ is a lattice, this means that $x^* = y^*$. Similarly, we have $x\wedge x^* = a = x\wedge y^*$, which again implies that $x^* = y^*$. Therefore, $x^*$ is unique.

Hence, we have shown that for every $x\in [a,b]$, there exists a unique element $x^*\in [a,b]$ such that $x\vee x^* = b$ and $x
 

FAQ: Proving Boolean Lattice Complementarity in [a,b]

1. What is the Boolean Lattice Problem?

The Boolean Lattice Problem is a mathematical problem that involves finding a lattice structure that satisfies a set of Boolean equations. In simpler terms, it is a problem of finding a set of values that satisfy a system of logical equations.

2. What is a lattice structure?

A lattice structure is a mathematical structure that consists of a set of elements and two binary operations, usually called meet and join. These operations allow for the creation of a partially ordered set, where every pair of elements has a unique greatest lower bound (meet) and least upper bound (join).

3. What are Boolean equations?

Boolean equations are equations that involve Boolean variables and logical operators such as AND, OR, and NOT. These equations are used to represent logical relationships between variables and are commonly used in computer science and mathematics.

4. Why is the Boolean Lattice Problem important?

The Boolean Lattice Problem has applications in many areas, including computer science, engineering, and physics. It is used to solve problems in logic design, optimization, and decision-making, making it a crucial problem in various fields.

5. What are some strategies for solving the Boolean Lattice Problem?

There are several techniques for solving the Boolean Lattice Problem, including brute-force search, heuristic search, and genetic algorithms. These methods involve systematically searching for a solution or using evolutionary principles to find an optimal solution.

Similar threads

Back
Top