A Heyting algebra is a lattice $(L,\vee, \wedge)$ with a largest (top) element $1$ and a smallest (bottom) element $0$ and a binary operation $L\times L \rightarrow L$ called $(L$-)implication, written $(a,b) \mapsto (a\rightarrow b)$ satisfying the following property:
\[(I) \quad \forall a,b,c \in L\:[\{(a\rightarrow b) \wedge a \leq b\}\:\&\:\{c\wedge a\leq b \implies c\leq (a\rightarrow b)\}]\]
That is $a\rightarrow b$ is the largest of elements $c$ of $L$ satisfying $c \wedge a \leq b$. From ($I$), we also have the characterization $c \leq a\rightarrow b \iff c \wedge a \leq b$.
It is helpful to think of $L$ as containing propositions. Then the partial order on $L$ can be given the following interpretation. If $a, b \in L$ and $a\leq b$, then from $a$ we can find a (constructive) proof of $b$, so that we can know $b$ empirically if we know $a$. We can also think of this in terms of information, $a \leq b$ means that $a$ contains at least all the information contained in $b$. Then $a\rightarrow b$ (read $a$ ($L$-)implies $b$) has the interpretation of being the element with the least information in $L$ that has the property that when paired with (a proof of) $a$ gives a proof of $b$, or completely in terms of the information interpretation: $a\rightarrow b$ is the element with the least information in $L$ that has the property that adding the information from $a \rightarrow b$ to the information from $a$ gives at least as much information as is contained in $b$.
Through $L$-implication we define $L$-negation as follows: $\forall a \in L\:[\sim a = a\rightarrow 0]$. That is, since $0$ is the bottom element of $L$ we have $\sim a\wedge a = 0$ and any other element $c\in L$ satisfying $c \wedge a = 0$ has $c\leq a$. That is, $\sim a$ is the element with least information such that adjoining it to the information contained in $a$ yields the same amount of information as is contained in $0$ (every element contains less than or equal the amount of information contained in $0$ by the way we defined the information interpretation and of $0$ as a bottom element).
Let us further develop this "information interpretation" of the partial order on $L$ because it avoids having to think of elements of $L$ as "proofs" and would seem to more readily lead to physical interpretations. To do this, since we have given $a \leq b$ the interpretation of $a$ containing at least as much information as is present in $b$, in order to avoid such awkward phrasing we are led to consider the opposite lattice $(L_{op},\cup,\cap)$ where we will write $\cup$ for the join on $L_{op}$ (meet on $L$), $\cap$ for the meet on $L_{op}$ (join on $L$), and $\subset$ for the partial order on $L_{op}$ (since it hints at information containment). Then we will write $a \cup b = c$ in $L_{op} \iff a \wedge b = c$ in $L$, $a \cap b = c$ in $L_{op} \iff a \vee b = c$ in $L$, and $b \subset a$ in $L_{op} \iff a \leq b$ in $L$. Also note that $0$ and $1$ become the top and bottom elements, respectively, of $L_{op}$ since they were the bottom and top elements, respectively, of $L$. We will then write $1_{op} = 0$ and $0_{op} = 1$. Then we get the interpretation $b \subset a$ means that $b$ contains less than or equal the amount of information contained in $a$, which is the reason for the change in notation. So, for this interpretation, we are now thinking of elements of $L_{op}$ in terms of their information content. Hence $a \rightarrow b$ is the smallest of elements (least information) $c$ in $L_{op}$ such that $b \subset c \cup a$. Then, since $0$ is top element of $L_{op}, L$-negation now has the following information interpretation in $L_{op}$: for $a\in L_{op}, \sim a$ is the element with least information among the $c \in L_{op}$ with the property that $1_{op} = a \cup c$.
A lattice is called complete if it is closed under arbitrary meets and joins. A complete Heyting algebra, or CHA for short, is a Heyting algebra that is also complete as a lattice.
A Boolean Algebra is a distributive lattice $B$ with top $1$, bottom $0$, and a unary operation $a \mapsto \sim a$ called complementation (negation), satisfying $a \vee \sim a = 1$ and $a \wedge \sim a = 0$ for $a \in B$. Note it is not difficult to show that complements are unique and then, using that result, that DeMorgan's identities hold: $\sim(a \vee b) = \sim a \wedge \sim b$ and $\sim(a \wedge b) = \sim a \vee \sim b)$.
At this point a few basic observations about Heyting algebras are in order.
1. Boolean Algebras are also Heyting Algebras but not all Heyting algebras are Boolean algebras.
2. The complement is unique in a Boolean algebra and when considered as a Heyting algebra, $\sim a = a\rightarrow 0$. So the two definitions of negation agree for a Boolean algebra.
3. Heyting Algebras are distributive lattices
4. Every complete Heyting algebra is a frame and every frame is a Complete Heyting algebra.
5. A Heyting algebra is Boolean $\iff \forall a \in A \: [\sim \sim a = a]$
Many of the following proofs are adapted from Johnstone. Some, particularly the proof of (3), are rather technical and are only placed here for completeness.
To prove (1) let $B$ be a Boolean algebra. Then to show that $B$ is a Heyting algebra we only need to demonstrate that implication exists. For $a, b \in B$ define $a \rightarrow b := \sim a \vee b$. Then we only need to show that this definition satisfies ($I$). Since $B$ is distributive, ($\sim a \vee b)\wedge a = 0\vee (b \wedge a) = b\wedge a \leq b$. Now let $c \in B$ with $c \wedge a \leq b$. Then $\sim a \vee b \geq \sim a \vee (c \wedge a) = (\sim a \vee c) \wedge 1 = \sim a \vee c \geq c$. So ($I$) holds. We will give an example of a Heyting algebra that is not a Boolean algebra later.
To prove (2) let $a \in B$ and suppose $c \in B$ satisfies $c \wedge a = 0, c \vee a = 1$. Then $\sim a = 0 \vee \sim a = (a \wedge c) \vee \sim a = c \vee \sim a = (a \wedge \sim a) \vee c = 0 \vee c = c$. So complements are unique as claimed. Then the proof of (1) shows the second claim because in a Boolean algebra $a \rightarrow 0 = \sim a \vee 0 = \sim a$.
For (3) first note that $a \wedge b \leq a$ and $a \wedge b \leq b\vee c$. So $a \wedge b \leq a \wedge (b\vee c)$. Similarly $a \wedge c \leq a \wedge (b\vee c)$. So $(a \wedge b) \vee (a \wedge c) \leq a \wedge (b\vee c)$. For the other direction recall that $c \leq a \rightarrow b \iff c \wedge a \leq b$. So $b \leq a \rightarrow (a\wedge b)$ and $c \leq a \rightarrow (a \wedge c)$. Hence $b \vee c \leq (a \rightarrow (a\wedge b)) \vee (a \rightarrow (a\wedge c))$. But $a \wedge ((a \rightarrow (a\wedge b)) \vee (a \rightarrow (a \wedge c)) \leq (a \wedge b) \vee (a \wedge c)$. So $(a \rightarrow (a\wedge b)) \vee (a \rightarrow (a\wedge c)) \leq a \rightarrow ((a \wedge b) \vee (a \wedge c))$. Therefore $b \vee c \leq a \rightarrow ((a \wedge b) \vee (a \wedge c))$. Hence $a \wedge (b \vee c) \leq (a \wedge b) \vee (a \wedge c)$ which proves (3).
For (4), to show that every CHA is a frame it suffices to show that CHAs satisfy the infinite distributive law. We will not show this and instead only show that every frame is a CHA. Let $P$ be a frame. Then for $a, b \in P$ define $a \rightarrow b := \sup \{c \in P \:|\: c\wedge a \leq b\}$. Clearly to show that this definition satisfies ($I$) we need only show only that $a \rightarrow b \in \{c \in P \:|\: c\wedge a \leq b\}$. But because frames satisfy the infinite distributive law, $a \wedge (a\rightarrow b) = a \wedge \bigvee\{c \in P \:|\: c\wedge a \leq b\} = \bigvee \{a \wedge c \:|\: a \wedge c \leq b\} \leq b$. Hence $P$ is a CHA.
To prove (5), if $A$ is a Boolean algebra, then by uniqueness of complements, since $a$ and $\sim \sim a$ are both complements of $\sim a$ we must have $\sim \sim a =a$ for an arbitrary $a \in A$. For the other implication suppose $A$ is a Heyting algebra where $\sim \sim a = a$ holds for each $a \in A$. Then this condition says that $a \mapsto \sim a$ is a bijection. Also it is not difficult to see that it is order reversing. Indeed let $a \leq b$. Then $(b \rightarrow 0) \wedge a \leq (b\rightarrow 0) \wedge b =0$. So $(b \rightarrow 0) \wedge a = 0$. Hence $b \rightarrow 0 \leq a \rightarrow 0$, that is $\sim b \leq \sim a$. So the bijection is order reversing as claimed. Then using the order reversing property, since $a \wedge b \leq a,b$ and $a \vee b \geq a,b$ we have $\sim (a \wedge b) \geq \sim a \vee \sim b$ and $\sim (a \vee b) \leq \sim a \wedge \sim b$. Then using these two inequalities, order reversing again, and that $\sim \sim a = a$ for all $a$ we get $a \wedge b \leq \sim(\sim a \vee \sim b) \leq a \wedge b$ so that negating both sides we get $\sim (a \wedge b) = \sim a \vee \sim b$. Similarly we get the other Demorgan identity $\sim (a \vee b) = \sim a \wedge \sim b$. So the condition $\sim \sim a = a$ for all $a$ is enough to establish Demorgan's identities for that space. Since we know $a \wedge \sim a =0$ and that $A$ is distributive (3), it remains only to show $a \vee \sim a =1$ to show that $A$ is a Boolean Algebra. But as we have shown, the assumptions imply Demorgan's identities, so $1 = \sim 0 = \sim (a \wedge \sim a) = \sim a \vee \sim \sim a = \sim a \vee a$. So $A$ is a Boolean algebra.
I will stop here for this post. I will return to discussing a space $X$ and its lattice of observations (topology) $\Omega X$ in the next post in this series as a setting where we can bring together many of the concepts we have introduced.
No comments:
Post a Comment