PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (23)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: Very high
Brouwerian lattice (Definition)

Let $ L$ be a lattice, and $ a,b\in L$. Then $ a$ is said to be pseudocomplemented relative to $ b$ if the set

$\displaystyle T(a,b):=\lbrace c \in L \mid c \wedge a \le b\rbrace$
has a maximal element. The maximal element (necessarily unique) of $ T(a,b)$ is called the pseudocomplement of $ a$ relative to $ b$, and is denoted by $ a\to b$. So, $ a\to b$, if exists, has the following property
$\displaystyle c\wedge a\le b$    iff $\displaystyle c\le a\to b.$
If $ L$ has 0, then the pseudocomplement of $ a$ relative to 0 is the pseudocomplement of $ a$.

An element $ a\in L$ is said to be relatively pseudocomplemented if $ a\to b$ exists for every $ b\in L$. In particular $ a\to a$ exists. Since $ T(a,a)=L$, so $ L$ has a maximal element, or $ 1\in L$.

A lattice $ L$ is said to be relatively pseudocomplemented, or Brouwerian, if every element in $ L$ is relatively pseudocomplemented. Evidently, as we have just shown, every Brouwerian lattice contains $ 1$. A Brouwerian lattice is also called an implicative lattice.

Here are some other properties of a Brouwerian lattice $ L$:

  1. $ b\le a\to b$ (since $ b\wedge a\le b$)
  2. $ 1=a\to 1$ (consequence of 1)
  3. (Birkhoff-Von Neumann condition) $ a\le b$ iff $ a\to b=1$ (since $ 1\wedge a=a\le b$)
  4. $ a\wedge (a\to b)= a\wedge b$
    Proof. On the one hand, by 1, $ b\le a\to b$, so $ a\wedge b\le a\wedge (a\to b)$. On the other hand, by definition, $ a\wedge (a\to b)\le b$. Since $ a\wedge (a\to b)\le a$ as well, $ a\wedge (a\to b)\le a\wedge b$, and the proof is complete. $ \qedsymbol$
  5. $ a=1\to a$ (consequence of 4)
  6. if $ a\le b$, then $ (c\to a)\le (c\to b)$ (use 4, $ c\wedge (c\to a)=c\wedge a\le a\le b$)
  7. if $ a\le b$, then $ (b\to c)\le (a\to c)$ (use 4, $ a\wedge (b\to c)\le b\wedge (b\to c)=b\wedge c\le c$)
  8. $ a\to (b\to c)=(a \wedge b)\to c = (a\to b)\to (a\to c)$
    Proof. We shall use property 4 above a number of times, and the fact that $ x=y$ iff $ x\le y$ and $ y\le x$. First equality:
    $\displaystyle \big( a\to (b\to c) \big) \wedge (a\wedge b)$ $\displaystyle =$ $\displaystyle \big( a \wedge (b\to c)\big) \wedge b$  
      $\displaystyle =$ $\displaystyle \big( b\wedge (b\to c)\big) \wedge a$  
      $\displaystyle =$ $\displaystyle (b\wedge c)\wedge a\le c.$  

    So $ a\to (b\to c)\le (a\wedge b)\to c$.

    On the other hand, $ \big( (a\wedge b)\to c \big)\wedge a \wedge b=a\wedge b\wedge c\le c$, so $ \big( (a\wedge b)\to c \big)\wedge a\le b\to c$, and consequently $ (a\wedge b)\to c \le a\to (b\to c)$.

    Second equality: $ \big( (a\wedge b)\to c \big) \wedge (a\to b) \wedge a = \big( (a\wedge b)\to c \big)\wedge (a\wedge b)=(a\wedge b)\wedge c\le c$, so $ \big( (a\wedge b)\to c \big) \wedge (a\to b) \le a\to c$ and consequently $ (a\wedge b)\to c \le (a\to b)\to (a\to c)$.

    On the other hand,

    $\displaystyle \big( (a\to b)\to (a\to c)\big) \wedge (a\wedge b)$ $\displaystyle =$ $\displaystyle \big( (a\to b)\to (a\to c)\big) \wedge \big( a\wedge (a\to b)\big)$  
      $\displaystyle =$ $\displaystyle \big( (a\to b)\wedge (a\to c)\big) \wedge a$  
      $\displaystyle =$ $\displaystyle (a\wedge b)\wedge (a\to c)$  
      $\displaystyle =$ $\displaystyle b\wedge (a\wedge c)\le c ,$  

    so $ (a\to b)\to (a\to c)\le (a\wedge b)\to c$. $ \qedsymbol$
  9. $ L$ is a distributive lattice.
    Proof. By the proposition found in entry distributive inequalities, it is enough to show that
    $\displaystyle a\wedge (b\vee c)\le (a\wedge b)\vee (a\wedge c).$
    To see this: note that $ a\wedge b\le (a\wedge b)\vee (a\wedge c)$, so $ b\le a\to \big( (a\wedge b)\vee (a\wedge c)\big)$. Similarly, $ c\le a\to \big( (a\wedge b)\vee (a\wedge c)\big)$. So $ b\vee c \le a\to \big( (a\wedge b)\vee (a\wedge c)\big)$, or $ a\wedge (b\vee c)\le (a\wedge b)\vee (a\wedge c)$. $ \qedsymbol$

Remarks.

  • Brouwerian lattice is named after the Dutch mathematician L. E. J. Brouwer, who rejected classical logic and proof by contradiction in particular. The lattice was invented as the algebraic counterpart to the Brouwerian intuitionistic (or constructionist) logic, in contrast to the Boolean lattice, invented as the algebraic counterpart to the classical propositional logic.
  • In the literature, a Brouwerian lattice is sometimes defined to be synonymous as a Heyting algebra (and sometimes even a complete Heyting algebra). Here, we shall distinguish the two related concepts, and say that a Heyting algebra is a Brouwerian lattice with a bottom.
  • In the category of Brouwerian lattices, a morphism between a pair of objects is a lattice homomorphism $ f$ that preserves relative pseudocomplementation:
    $\displaystyle f(a\to b)=f(a)\to f(b).$
    As $ f(1)=f(a\to a)=f(a)\to f(a)=1$, this morphism preserves the top elements as well.

Example. Let $ L(X)$ be the lattice of open sets of a topological space. Then $ L(X)$ is Brouwerian. For any open sets $ A,B\in X$, $ A\to B=(A^c\cup B)^{\circ}$, the interior of the union of $ B$ and the complement of $ A$.

Bibliography

1
G. Birkhoff, Lattice Theory, AMS Colloquium Publications, Vol. XXV, 3rd Ed. (1967).
2
R. Goldblatt, Topoi, The Categorial Analysis of Logic, Dover Publications (2006).



"Brouwerian lattice" is owned by CWoo.
(view preamble | get metadata)

View style:

See Also: pseudocomplemented lattice, pseudocomplement, relative complement

Other names:  relatively pseudocomplemented, pseudocomplemented relative to, Brouwerian algebra, implicative lattice
Also defines:  relative pseudocomplement
Log in to rate this entry.
(view current ratings)

Cross-references: complement, union, interior, topological space, open sets, top, preserves, lattice homomorphism, objects, morphism, category, bottom, even, Heyting algebra, propositional logic, Boolean lattice, logic, algebraic, proof by contradiction, classical logic, distributive inequalities, proposition, distributive lattice, equality, number, complete, proof, iff, consequence, contains, pseudocomplement, property, maximal element, lattice
There are 4 references to this entry.

This is version 15 of Brouwerian lattice, born on 2007-01-09, modified 2007-05-24.
Object id is 8733, canonical name is BrouwerianLattice.
Accessed 2977 times total.

Classification:
AMS MSC: 06D15 (Order, lattices, ordered algebraic structures :: Distributive lattices :: Pseudocomplemented lattices)
 06D20 (Order, lattices, ordered algebraic structures :: Distributive lattices :: Heyting algebras)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)