In the last post I gave the definition of a Heyting algebra and stated and proved many properties about Heyting algebras and Boolean algebras, a proper subclass of Heyting algebras. Moreover I showed how the implication and negations operations on a Heyting algebra can be interpreted ("proof" and "information" interpretation) as logical operations within a lattice of propositions. We also had the important result that, when considered as spaces alone, frames and complete Heyting algebras are equivalent. In a later post we shall add yet another class of space that is equivalent when considered as a space alone to the former two. Eventually we shall be able to distinguish them, however, when considered in the context of category theory. Specifically we shall see later that they each have different "morphisms".
Let us return to our "lattice of observations" approach to a topology $\Omega X$ on an abstract space $X$ that we began to develop in part 1. We know that $\Omega X$ is a frame, hence it is also a complete Heyting algebra (cHa). Now recall for $x \in X$ that $x \in U \in \Omega X \implies x \in \mathscr{N}(x)$. Conversely if $U \in \mathscr{N}(x)$ then $x \in U$, which recall that by $x\in U$, under the lattice of observations interpretation we mean that we have observed (know empirically, have a "proof" that $x \in U$) $x$ to be in the "region" $U$ of the abstract space $X$. So let $y \in U$. Then by definition (different defintion of $\in$ here than is usual) we have a proof that $y \in U$ so $U \in \mathscr{N}(y)$. So $U$ is a (intuitionistic) neighborhood of each of its points, hence $U \in \Omega X$. (Caution: This is not classically true! It depends entirely of the particular interpretation of $\in$ I was using. This type of reasoning was used at the end of my second post, however I never mentioned that it forces us to have that neighborhoods are (intuitionistically) open (only due to interpretation!). Really, as I remarked in a similar paragraph in the second post, I am using a different definition of set containment than is standard in classical logic for the above reasoning. Therefore let us use an alternate symbol for when we mean this type of containment rather than the standard usage so it is no longer necessary to remind the reader for which paragraphs to "suspend disbelief". From now on in the lattice of observations interpretation, for $x \in X$ and $U\subset X$ we shall write \[definition: \qquad x\vdash U \iff U \in \mathscr{N}(x)\] and say $x$ inhabits $U$ when we mean this type of membership. Note that by definition $x$ can only inhabit a neighborhood. So this definition depends entirely on $\Omega X$. To emphasize this dependence on $\Omega X$ we may write $\vdash_{\Omega}$. For instance if one were speaking of another topology $\Gamma X$ on $X$ distinct from $\Omega X$ then distinction must be made between $\vdash _{\Omega}$ and $\vdash_{\Gamma}$.
We have not yet considered $\vdash_{\mathscr{P}}$ where $\mathscr{P}(X)$ is the classical lattice of observations. Well if $A \subset X$ and $x \in A$ then $x\ \in A \in \mathscr{P}(x)$. So $A$ is a n-hood of $x$ (relative to $\mathscr{P}(X)$. Hence $x \vdash_{\mathscr{P}} A$. Therefore $\in$ = $\mathscr{P}$. So when we deviate from the classical lattice of observations we also deviate from classical inclusion if we keep the internalized logic of the lattice.
Now we can see in the claim earlier than neighborhoods are forced to be open, what was really meant using our new notation is that neighborhoods are open in the internal logic of $\Omega$ because the classical
\[U \in \Omega X \iff \{\forall x \in U\:[\:x\vdash_\Omega U]\}\]
becomes a trivial statement when we replace $\in$ with $\vdash_{\Omega}$ (that is n-hoods are open under $\vdash$ (internal logic of $\Omega$ but not necessarily under $\in$). On the other hand $x \vdash U$ can also have the interpretation $x$ is known empirically to be in $U$ (a type of metalogic) and can be used to recover $\mathscr{N}(x)$ for each $x \in X$. In this latter sense only topologies "coarser" than $\Omega X$ ($\Gamma X \subset \Omega X$) may be produced.
Now that we have two concepts of membership we get two distinct concepts of set inclusion: the standard one induced by $\in$ and a now one induced by $\vdash$. For the latter we shall define
\[definition: \qquad \forall A, B \in \Omega X \:[\:A\sqsubset B \iff \{\forall x\in X \:[\:x\vdash A \implies x\vdash B]\}]\] and sometimes write $A \sqsubset_{\Omega} B$ to show dependence on $\Omega X$.
Now $\Omega X$ is a cHa. Let us examine implication and negation in this case. Recall from part 1 that the partial order on $\Omega X$ is subset inclusion $\subset$ and that we have \[\forall \alpha \subset \Omega X \:[\bigvee \alpha = \bigcup \alpha \: \: \&\:\: \bigwedge \alpha = (\bigcap \alpha)^{\circ}]\]
So arbitrary joins are unions but in general arbitrary meets are equal to the interior of the intersection. Since $\Omega X$ is a topology, the condition that $\Omega X$ is closed under finite intersections translates to finite meets are the same as finite intersections.
Note that if we have $A, B \in \Omega X$ and $A \subset B$ then we may consider the proposition $x \vdash A$. Then we also have $x \vdash B$ because $\mathscr{N}(x)$ is a filter. So any observation that can be made in $A$ can also be made in $B$. This follows the "proof interpretation" model that I mentioned in the last post because a proof of $x$ being contained in $A$ is $x \vdash A$ which implies that we have a proof of $x$ being contained in $B$ or $x\vdash B$.
Let's see what $A \rightarrow B$ looks like for $A, B \in \Omega X$. Since $\Omega X$ is complete, we must have $A \rightarrow B = \bigvee\{C \in\Omega X \: | \:A \wedge C \leq B\} = \bigcup \{ C\in \Omega X \:|\:A \cap C \subset B\}$. Then $\sim A =A \rightarrow \emptyset = \bigcup \{C\in \Omega X\:|\:A \cap C = \emptyset\} = \bigcup \{C\in \Omega X\:|\: C \subset A^c\} = (A^c)^{\circ}$. So the negation of $A$ is the interior of its complement. But from property (5) from the last post we know that a Heyting algebra is boolean $\iff \sim \sim a = a$ for each $a \in L$. So $\Omega X$ is boolean $\iff \forall A \in \Omega X \:[\sim \sim A = ((A^c)^{{\circ}})^c)^{\circ}=A]$.
Let's try to simplify $\sim \sim A = ((A^c)^{{\circ}})^c)^{\circ}$ using that $(A^c)^{{\circ}} = (\bar{A})^c$. Plugging this in we get $\sim \sim A = (((\bar{A})^c)^c)^{\circ} = (\bar{A})^{\circ}$. Hence $\sim \sim A$ is the interior of the closure of $A$. So we have that a topology is Boolean $\iff$ for all $A \in \Omega X$ we have that $(\bar{A})^{\circ} = A$. In general topology open sets $A$ that satisfy the condition $(\bar{A})^{\circ} = A$ are called normal open sets. So for our characterization an open set $A$ is normal when $\sim \sim A = A$ and a topology is Boolean $\iff$ every open set is normal.
Therefore we now have a multitude of examples of Heyting algebras that
are not Boolean. Take any topology $\Omega X$ on $X$ that is not closed
under complementation. Then it will be Heyting but not Boolean. This is
because if $A \in \Omega X$ but $A^c \notin \Omega X$ then $\sim A
\subsetneq A^c$. So $A \vee \sim A = A \cup \sim A \subsetneq A \cup A^c
= X$. So $\sim A$ is not the Boolean negation of $A$. So $\Omega X$ is
not Boolean. The proceeding argument also shows that if we have that
$\Omega X$ is not Boolean then excluded middle does not hold internally
on $\Omega X$. To see this note that if $\Omega X$ is not Boolean then
$\exists A \in \Omega X \:[A^c \notin \Omega X]$. Then apply the
proceeding argument to show that $\sim A \cup A \neq X$ which shows
excluded middle does not hold internally.
For an example take $\mathbb{R}$ with its standard topology. Then it clearly is not Boolean because $\sim (0, 1) = (\infty,0) \cup (1,\infty) \neq (0,1)^c$. So that means there must exist open sets that are not normal. Let's try to find one. $(0, 1)$ is normal because $\sim ((\infty,0) \cup (1,\infty))= (0, 1)$. Let's try $(0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$. Well $\sim ((0, \frac{1}{2}) \cup (\frac{1}{2}, 1)) = (\infty,0) \cup (1,\infty)$ and $\sim ((\infty,0) \cup (1,\infty) = (0,1) \neq (0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$. So $(0, \frac{1}{2}) \cup (\frac{1}{2}, 1)$ is an open set that is not normal.
Tuesday, May 8, 2012
Saturday, May 5, 2012
"Boolean algebras are to powersets as complete Heyting algebras are to topologies", or topology from logic (part 2)
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.
\[(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.
Thursday, May 3, 2012
Technical aside to the previous post.
This is not a part 2 of the previous post. In this post I will clarify a remark I made offhandedly in the previous post.
In the last post I informally introduced topologies by constructing them as a natural lattice of observations on an abstract space. For each $x \in X$ a filter $\mathscr{N}(x)$ was constructed with the interpretation that $U \in \mathscr{N}(x) \iff x$ was observed to be in $U$. Recall that we have assumed that the space $X$ is an abstract mental construction where it may be the case that idealized mental points $x \in X$ may not always be empirically observed, that is it is possible that we do not have $\{x\} \in \mathscr{N}(x)$. Here I am giving the possibility of $\{x\} \in X$ the interpretation of empirically determining the precise position of $x$. (I later gave the space where it is always possible to determine the precise position of abstract points empirically a name, classical space, and I showed that its lattice of observations is $\mathscr{P}(X)$ and that its logic is classical.)
Moreover I claimed that since we had such a filter $\mathscr{N}(x)$ for each $x \in X$ then we could make a topology $\Omega X$ from these filters which I called "neighborhood filters". However that is imprecise and seemingly not quite right since neighborhood filters has a technical definition. We must put more conditions on the original filters to ensure that the resulting topology induced by those filters has neighborhood filters that are the same as the originals. The point of this post is to make more precise that remark. Since the sufficient condition is rather technical I chose to gloss over this point in the earlier post since I did not feel it was essential to introducing topologies through a "lattice of observations" interpretation. However, we shall see that even this extra technical requirement is naturally satisfied by the filter system constructed through the "lattice of observations" construction. So we were still quite right to call it a neighborhood system.
First let us define some terms: Let $X$ be a space and $\mathscr{F} \subset \mathscr{P}(X)$. Then $\mathscr{F}$ is a filter (of sets) on $X \iff$ (definition) the following conditions hold:
\[1.\qquad \forall A \in \mathscr{F} \forall B \in \mathscr{P}(X)\:[A \subset B \implies B\in \mathscr{F}]\]
\[2. \qquad \forall A,B \in \mathscr{F}\:[A \cap B \in \mathscr{F}]\]
Now suppose for each $x \in X$ we let $\mathscr{F}(x)$ be a filter such that $\forall A \in \mathscr{F}(x)$ we have $x \in A$. Then we shall call the resulting collection of filters $(\mathscr{F}(x))_{x\in X}$ a filter system for $X$. Now let us use a filter system to construct a topology.
Let \[\Omega_{\mathscr{F}} X = \Omega X := \{U \subset X\:|\: \forall x \in U \exists V \in \mathscr{F}(x)\:[V \subset U]\}\]
Then the $\forall x$ term in the conditions on the set ensures that $\emptyset \in \Omega X$ vacuously. Also clearly $X \in \Omega X$ because each $\mathscr{F}(x)$, as a filter, must contain $X$. Also it is not difficult to see that $\Omega X$ is closed under arbitrary unions. Lastly to show $\Omega X$ is closed under finite intersections, let $A, B \in \Omega X$. Then we may suppose $A \cap B$ is nonempty, because we already know that $\Omega X$ contains the empty set. So let $x \in A \cap B$. Then, by definition of $\Omega X$, $\exists V_1,V_2 \in \mathscr{F}(x)$ such that $V_1 \subset A$ and $V_2 \subset B$. But $\mathscr{F}(x)$ is a filter so $V:=V_1 \cap V_2 \in \mathscr{F}(x)$ and clearly $V \subset A \cap B$. So it follows $A \cap B \in \Omega X$. Hence $\Omega X$ is a topology. We shall call it the topology induced by the filter system $(\mathscr{F}(x))_{x\in X}$.
Now let $\Omega X$ be defined as above (the topology induced by the filter system $(\mathscr{F}(x))_{x\in X}$). Let us make a new filter system, which we shall call the neighborhood filter system or n-hood system, from $\Omega X$. To do this define
\[\mathscr{N}(x) := \{N\subset X\:|\:\exists U \in \Omega X \:[x\in U \subset N]\}\]
Then it is not difficult to check that $x$ is in every $N \in \mathscr{N}(x)$ and that each $\mathscr{N}(x)$ is a filter. We shall call each $\mathscr{N}(x)$ the neighborhood filter (or n-hood filter) at $x$. Then $(\mathscr{N}(x))_{x\in X}$ is a filter system for $X$ called the n-hood system for $X$ induced by $\Omega X$.
So the question naturally arises: When do we have that $\forall x \in X \: [\mathscr{F}(x) = \mathscr{N}(x)]$? To begin to answer this question let us note that we already have $\mathscr{N}(x) \subset \mathscr{F}(x)$ for each $x$. To see this let $x \in X$ and $N \in \mathscr{N}(x)$. Then $\exists U \in \Omega X$ such that $x \in U$ and $U \subset N$. But $x \in U \in \Omega X \implies \exists V \in \mathscr{F}(x) \:[V\subset U]$. So $V \subset N$. But $\mathscr{F}(x)$ is a filter and $V \in \mathscr{F}(x)$. So $N \in \mathscr{F}(x)$. Hence $\mathscr{N}(x) \subset \mathscr{F}(x)$, as desired.
However to show the other containment, that is $\mathscr{F}(x) \subset \mathscr{N}(x)$ for each $x \in X$, we need an extra condition on the filter system $\mathscr{F}(x)$. This is the technical condition I mentioned earlier. The condition is as follows:
\[(*) \qquad \forall x \in X \forall U \in \mathscr{F}(x) \exists V \in \mathscr{F}(x) \forall y \in V \exists W \in \mathscr{F}(y) \:[W \subset U]\]
Let us show that this condition is sufficient. Let $x \in X$ and $U \in \mathscr{F}(x)$ Now let $A:= \{z \in U\:|\: \exists W \in \mathscr{F}(z)\:[W\subset U]\}$. Clearly $A \subset U$. Also, since $z \in A \implies \exists W \in \mathscr{F}(z)\:[W \subset U]$, we have that $A \in \Omega X$ (A is open). Moreover, by ($*$) and the definition of $A$, $\exists V \in \mathscr{F}(x) \forall y \in V [y \in A]$. That is $V \subset A$. So in particular $x \in A \in \Omega X$. So $A \in \mathscr{N}(x)$. But $A \subset U$. So $U \in \mathscr{N}(x)$. Therefore $\mathscr{F}(x) \subset \mathscr{N}(x)$, as desired.
The condition $*$ is actually necessary. This is because $(\mathscr{N}(x))_{x\in X}$ satisfies $*$. Indeed if $x \in X$ and $U \in \mathscr{N}(x)$ then by definition of $\mathscr{N}(x)$, there exists a $V \in \Omega X$ with $x \in V \subset U$. Then with such a $V$, and using that open sets are neighborhoods of each of their points, it is not difficult to verify $*$. For additional reference see General Topology by Stephen Willard.
Hence we have shown that a filter system induces a topology whose n-hood system is the original filter system $\iff$ the original filter system satisfies $*$.
Now let us show that we were correct all along to call our filter system from the last post induced by observations on the space $X$ a neighborhood system. That is it naturally satisfies $*$ so it induces a topology (lattice of observations) whose n-hood system is the original filter system. To see this let $x$ be an abstract point in space and $U \in \mathscr{N}(x)$ (where $\mathscr{N}(x)$ is as defined in the previous post). Then by definition $x$ has been empirically observed to be in $U$. Then we may take $U = V$ and still satisfy $*$. Indeed if $y \in U = V$, then we may interpret this containment as knowing empirically that $y \in U$. Therefore $U \in \mathscr{N}(y)$ because $\mathscr{N}(y)$ is defined to be the list of areas of $X$ where we have empirically observed $x$. That is areas $A \subset X$ where we know that $y \in A$. Hence $U \in \mathscr{N}(y)$. So take $W = U \in \mathscr{N}(y)$ and clearly $*$ is satisfied.
Note to the reader: Some of the reasoning from the previous paragraph may seem strange. In the previous paragraph we were not considering $X$ as a set containing points but rather as an abstract space, as I mentioned in my previous post, where containment is only defined through the lattice of observations (topology). Formally we have switched to an alternative logic (intuitionism induced by the lattice of observations) which ensures that points are only defined when observed (and they can only be observed in neighborhoods by definition of the lattice of observations). This is a confusing point and it is in my hope that in later posts I will be able to clarify it. We may eventually be able to put this on more rigorous ground through topos theory and pointless topology which I hope to introduce in later posts.
In the last post I informally introduced topologies by constructing them as a natural lattice of observations on an abstract space. For each $x \in X$ a filter $\mathscr{N}(x)$ was constructed with the interpretation that $U \in \mathscr{N}(x) \iff x$ was observed to be in $U$. Recall that we have assumed that the space $X$ is an abstract mental construction where it may be the case that idealized mental points $x \in X$ may not always be empirically observed, that is it is possible that we do not have $\{x\} \in \mathscr{N}(x)$. Here I am giving the possibility of $\{x\} \in X$ the interpretation of empirically determining the precise position of $x$. (I later gave the space where it is always possible to determine the precise position of abstract points empirically a name, classical space, and I showed that its lattice of observations is $\mathscr{P}(X)$ and that its logic is classical.)
Moreover I claimed that since we had such a filter $\mathscr{N}(x)$ for each $x \in X$ then we could make a topology $\Omega X$ from these filters which I called "neighborhood filters". However that is imprecise and seemingly not quite right since neighborhood filters has a technical definition. We must put more conditions on the original filters to ensure that the resulting topology induced by those filters has neighborhood filters that are the same as the originals. The point of this post is to make more precise that remark. Since the sufficient condition is rather technical I chose to gloss over this point in the earlier post since I did not feel it was essential to introducing topologies through a "lattice of observations" interpretation. However, we shall see that even this extra technical requirement is naturally satisfied by the filter system constructed through the "lattice of observations" construction. So we were still quite right to call it a neighborhood system.
First let us define some terms: Let $X$ be a space and $\mathscr{F} \subset \mathscr{P}(X)$. Then $\mathscr{F}$ is a filter (of sets) on $X \iff$ (definition) the following conditions hold:
\[1.\qquad \forall A \in \mathscr{F} \forall B \in \mathscr{P}(X)\:[A \subset B \implies B\in \mathscr{F}]\]
\[2. \qquad \forall A,B \in \mathscr{F}\:[A \cap B \in \mathscr{F}]\]
Now suppose for each $x \in X$ we let $\mathscr{F}(x)$ be a filter such that $\forall A \in \mathscr{F}(x)$ we have $x \in A$. Then we shall call the resulting collection of filters $(\mathscr{F}(x))_{x\in X}$ a filter system for $X$. Now let us use a filter system to construct a topology.
Let \[\Omega_{\mathscr{F}} X = \Omega X := \{U \subset X\:|\: \forall x \in U \exists V \in \mathscr{F}(x)\:[V \subset U]\}\]
Then the $\forall x$ term in the conditions on the set ensures that $\emptyset \in \Omega X$ vacuously. Also clearly $X \in \Omega X$ because each $\mathscr{F}(x)$, as a filter, must contain $X$. Also it is not difficult to see that $\Omega X$ is closed under arbitrary unions. Lastly to show $\Omega X$ is closed under finite intersections, let $A, B \in \Omega X$. Then we may suppose $A \cap B$ is nonempty, because we already know that $\Omega X$ contains the empty set. So let $x \in A \cap B$. Then, by definition of $\Omega X$, $\exists V_1,V_2 \in \mathscr{F}(x)$ such that $V_1 \subset A$ and $V_2 \subset B$. But $\mathscr{F}(x)$ is a filter so $V:=V_1 \cap V_2 \in \mathscr{F}(x)$ and clearly $V \subset A \cap B$. So it follows $A \cap B \in \Omega X$. Hence $\Omega X$ is a topology. We shall call it the topology induced by the filter system $(\mathscr{F}(x))_{x\in X}$.
Now let $\Omega X$ be defined as above (the topology induced by the filter system $(\mathscr{F}(x))_{x\in X}$). Let us make a new filter system, which we shall call the neighborhood filter system or n-hood system, from $\Omega X$. To do this define
\[\mathscr{N}(x) := \{N\subset X\:|\:\exists U \in \Omega X \:[x\in U \subset N]\}\]
Then it is not difficult to check that $x$ is in every $N \in \mathscr{N}(x)$ and that each $\mathscr{N}(x)$ is a filter. We shall call each $\mathscr{N}(x)$ the neighborhood filter (or n-hood filter) at $x$. Then $(\mathscr{N}(x))_{x\in X}$ is a filter system for $X$ called the n-hood system for $X$ induced by $\Omega X$.
So the question naturally arises: When do we have that $\forall x \in X \: [\mathscr{F}(x) = \mathscr{N}(x)]$? To begin to answer this question let us note that we already have $\mathscr{N}(x) \subset \mathscr{F}(x)$ for each $x$. To see this let $x \in X$ and $N \in \mathscr{N}(x)$. Then $\exists U \in \Omega X$ such that $x \in U$ and $U \subset N$. But $x \in U \in \Omega X \implies \exists V \in \mathscr{F}(x) \:[V\subset U]$. So $V \subset N$. But $\mathscr{F}(x)$ is a filter and $V \in \mathscr{F}(x)$. So $N \in \mathscr{F}(x)$. Hence $\mathscr{N}(x) \subset \mathscr{F}(x)$, as desired.
However to show the other containment, that is $\mathscr{F}(x) \subset \mathscr{N}(x)$ for each $x \in X$, we need an extra condition on the filter system $\mathscr{F}(x)$. This is the technical condition I mentioned earlier. The condition is as follows:
\[(*) \qquad \forall x \in X \forall U \in \mathscr{F}(x) \exists V \in \mathscr{F}(x) \forall y \in V \exists W \in \mathscr{F}(y) \:[W \subset U]\]
Let us show that this condition is sufficient. Let $x \in X$ and $U \in \mathscr{F}(x)$ Now let $A:= \{z \in U\:|\: \exists W \in \mathscr{F}(z)\:[W\subset U]\}$. Clearly $A \subset U$. Also, since $z \in A \implies \exists W \in \mathscr{F}(z)\:[W \subset U]$, we have that $A \in \Omega X$ (A is open). Moreover, by ($*$) and the definition of $A$, $\exists V \in \mathscr{F}(x) \forall y \in V [y \in A]$. That is $V \subset A$. So in particular $x \in A \in \Omega X$. So $A \in \mathscr{N}(x)$. But $A \subset U$. So $U \in \mathscr{N}(x)$. Therefore $\mathscr{F}(x) \subset \mathscr{N}(x)$, as desired.
The condition $*$ is actually necessary. This is because $(\mathscr{N}(x))_{x\in X}$ satisfies $*$. Indeed if $x \in X$ and $U \in \mathscr{N}(x)$ then by definition of $\mathscr{N}(x)$, there exists a $V \in \Omega X$ with $x \in V \subset U$. Then with such a $V$, and using that open sets are neighborhoods of each of their points, it is not difficult to verify $*$. For additional reference see General Topology by Stephen Willard.
Hence we have shown that a filter system induces a topology whose n-hood system is the original filter system $\iff$ the original filter system satisfies $*$.
Now let us show that we were correct all along to call our filter system from the last post induced by observations on the space $X$ a neighborhood system. That is it naturally satisfies $*$ so it induces a topology (lattice of observations) whose n-hood system is the original filter system. To see this let $x$ be an abstract point in space and $U \in \mathscr{N}(x)$ (where $\mathscr{N}(x)$ is as defined in the previous post). Then by definition $x$ has been empirically observed to be in $U$. Then we may take $U = V$ and still satisfy $*$. Indeed if $y \in U = V$, then we may interpret this containment as knowing empirically that $y \in U$. Therefore $U \in \mathscr{N}(y)$ because $\mathscr{N}(y)$ is defined to be the list of areas of $X$ where we have empirically observed $x$. That is areas $A \subset X$ where we know that $y \in A$. Hence $U \in \mathscr{N}(y)$. So take $W = U \in \mathscr{N}(y)$ and clearly $*$ is satisfied.
Note to the reader: Some of the reasoning from the previous paragraph may seem strange. In the previous paragraph we were not considering $X$ as a set containing points but rather as an abstract space, as I mentioned in my previous post, where containment is only defined through the lattice of observations (topology). Formally we have switched to an alternative logic (intuitionism induced by the lattice of observations) which ensures that points are only defined when observed (and they can only be observed in neighborhoods by definition of the lattice of observations). This is a confusing point and it is in my hope that in later posts I will be able to clarify it. We may eventually be able to put this on more rigorous ground through topos theory and pointless topology which I hope to introduce in later posts.
Wednesday, May 2, 2012
"Boolean algebras are to powersets as complete Heyting algebras are to topologies", or topology from logic (part 1)
EDIT on 5/23/12 adding discussion about $T_0$ separation.
The inspiration for this post (first in a series) comes from the most excellent book Topology Via Logic by Steven Vickers.
Let $X$ be a space. I am saying space instead of set because I don't want to bring up in the readers mind all of the baggage that comes with calling it a set. Now suppose we want to explore this space. We do not know a priori where specific points are nor do we have the ability to distinguish points in all cases. Indeed let us even go so far to say that the idea of individual points is a comforting abstraction and a mental construct, just as someone would do if they tried to imagine actual space itself as consisting of identifiable points in a vector space. Now suppose in our minds we choose one of these hypothetical and abstract "points" in $X$ and ask questions about it. We first can say "I definitely know (at least) that $x \in X$." Then looking closer, possibly after much energy expenditure, we might identify a smaller region $U$ of $X$ and say "aha, $x \in U$. Then we start recording the regions known to contain $x$, placing them in a list called $\mathscr{N} (x)$. After much time we are able to generate quite a long list, however we may never get $\{x\} \in \mathscr{N}(x)$. Suppose this process is allowed to continue indefinitely. What are some obvious rules of this list. Well, if $U \in \mathscr{N}(x)$ and $U \subset V$ then we should have $V \in \mathscr{N}(x)$ because if $V$ contains $U$ and $x$ is known to be in $U$, then it certainly is known to be in $V$. Also if $U, V \in \mathscr{N}(x)$ then $x$ is known to be in both $U$ and $V$. So $x$ is known to be in $U \cap V$. Hence $\mathscr{N}(x)$ is closed under finite intersections. As some readers might recognize, $\mathscr{N}(x)$ is a filter. If we repeat this process for each $x \in X$ we can use the resulting system of neighborhood filters to get a topology $\Omega X$ on $X$. Hence $\Omega X$ represents a lattice of observations on $X$. That is if we take a $U \in \Omega X$ then for some abstract $x \in X$ we know (observation) that $x \in U$ (except for the empty set which is defined by the property that we know for sure that no x can be observed there).
It is interesting to note that the only space for which you can actually observe all points precisely, that is for all, originally hypothetical $x \in X$, we actually have $\{x\} \in \mathscr{N}(x)$, is for $\Omega X = \mathscr{P}(X)$. Let us call this space classical space and let us call $\mathscr{P}(X)$ the lattice of classical observations. Now $\mathscr{P}(X)$ is well known to be a boolean algebra and a model for classical logic. That is the logic of observations of points (questions about whether certain $x$ are in certain elements of $\Omega X$) on classical space is classical. So if the proposition $p$ is "$x \in U"$ then $\sim p$ (read not $p$) is "$x \in U^c$", which makes perfect sense because in classical space $\Omega X = \mathscr{P}(X)$, that is "$x \in U^c$" is a always a possible observation for any $U$. Then since $X = U \cup U^c \in \Omega X$ ($U^c$ is the complement of $U$), we certainly have that "$x \in U$" ($p$) or "$x \in U^c$" ($\sim p$) . So $p \vee \sim p$ is true for all observations in the lattice of classical observations about points in classical space. That is the law of excluded middle holds on observations in classical space. Let us rephrase noting that the law of excluded middle holding on a lattice of observations on a space $X$ is equivalent to $\forall U \in \Omega X \: [U^c \in \Omega X]$. That is it is equivalent to the lattice of observations (topology) on $X$ being closed under complementation. It is not hard to see that for a $T_0$ space, the "excluded middle property" actually ensures that the lattice of observations is classical ($T_0$ means that for any two distinct points there exists a neighborhood of one of the points not containing the other). This is because if $x \in X$ and $y \in \{x\}^c$ then $\exists U \in \Omega X$ such that $x \in U$ and $y \notin U$ or $y \in U$ and $x \notin U$. However since complements are open by assumption that $\Omega X$ is boolean, $U^c$ is open in either case. So either way $y$ is in an open set not containing $x$. Hence $\{x\}^c$ is open. So $\{x\}$ is open by the assumption that $\Omega X$ is boolean. So $\Omega X$ contains all singletons. Hence it is discreet. This ultimately will not be good enough for us because the definition of a $T_0$ space requires that every time some $x$ is "objectively" (in the Platonic sense of classical mathematics) not equal to some $y$ we must have that we can observe one without observing the other. We would like to rephrase and state that if $x$ is known (observed) to be distinct from $y$ then this means literally that we can produce a neighborhood in the lattice of observations containing one point and not the other and $T_0$ separation for us becomes a necessity since it literally means that the points are known to be distinct (known by means of the lattice of observations), otherwise we cannot know objectively. From this we can now characterize the excluded middle property on the lattice of observations on a space: A space $X$ with lattice of observations $\Omega X$ is classical $\iff$ every abstract $x \in X$ can be observed objectively ($\{x\}\in \Omega X$) $\iff$ the lattice of observations satisfies the excluded middle property and it can be observed that any two hypothetical distinct points (mental abstraction) are observably distinct ($T_0$ separation).
Let us formalize some of these ideas. First some vocabulary.
Let $(P,\leq)$ be a partially ordered set. We will call $(P,\leq)$ a frame if
\[1. \qquad \forall A \subset P \: [\bigvee A \in P]\]
\[2. \qquad \forall A \subset P, |A| < \infty \:[\bigwedge A \in P]\]
\[3. \qquad \forall A \subset P\:\forall x\in P\:[x\wedge \bigvee A = \bigvee \{x\wedge a\:|\:a\in A\}]\]
Now note, as Vickers does, that 2. is wholly unnecessary and in fact unduly restrictive. We can get a property stronger that 2. using only 1. and the fact that $P$ is a poset as follows. First note that 1. guarantees that we have a least element, call it $0$, in P. This is because $0 = \bigvee \emptyset$. So let $A \subset P$. Then let $L$ be the set of lower bounds of $A$, which is non-empty because $0 \in A$. Then by 1., $s:=\bigvee L \in P$. Let $a \in A$. Then $a$ is a u.b. for $L$. So $s \leq a$. Hence $s$ is a l.b. for $A$. Let $t$ be another l.b. for $A$. Then $t \in L$. So $t \leq s$. Hence $s = \bigwedge A \in P$. So we automatically get that $P$ contains arbitrary infimums.
So why are we even considering these frames? Well, let $X$ be a space and $\Omega X$ a topology on $X$. Then $\Omega X$ is a frame under set inclusion. Indeed properties 1-3 follow immediately because $\Omega X$ is closed under arbitrary unions (joins) and finite intersections (meets). But wait, we have just shown that $\Omega X$ must then contain arbitrary meets. Doesn't that imply that it contains arbitrary intersections? No. Let $A \subset \Omega X$. Then $\bigwedge A$ is the largest set in $\Omega X$ that is $\leq$ (contained in) every $a \in A$. So it is the union (join) of all open sets contained in the intersection of $A$. It is the interior of $\bigcap A$. Hence $\bigwedge A = (\bigcap A)^\circ$.
I will stop here for now. In the next post I will introduce (complete) Heyting Algebras and develop a logic of observations on an arbitrary topology. Just as the classical logic of propositions on $X$ has lattice of observations $\mathscr{P}(X)$ (discrete topology) and satisfies the excluded middle, the logic of propositions on an arbitrary topology $\Omega X$ (we shall call it an intuitionist logic of propositions on $X$) has lattice of observations $\Omega X$ and the excluded middle property need not hold. I may also discuss some intuition (if I haven't hinted at it already) as to why these notions are useful, particularly the abandonment of the excluded middle property.
The inspiration for this post (first in a series) comes from the most excellent book Topology Via Logic by Steven Vickers.
Let $X$ be a space. I am saying space instead of set because I don't want to bring up in the readers mind all of the baggage that comes with calling it a set. Now suppose we want to explore this space. We do not know a priori where specific points are nor do we have the ability to distinguish points in all cases. Indeed let us even go so far to say that the idea of individual points is a comforting abstraction and a mental construct, just as someone would do if they tried to imagine actual space itself as consisting of identifiable points in a vector space. Now suppose in our minds we choose one of these hypothetical and abstract "points" in $X$ and ask questions about it. We first can say "I definitely know (at least) that $x \in X$." Then looking closer, possibly after much energy expenditure, we might identify a smaller region $U$ of $X$ and say "aha, $x \in U$. Then we start recording the regions known to contain $x$, placing them in a list called $\mathscr{N} (x)$. After much time we are able to generate quite a long list, however we may never get $\{x\} \in \mathscr{N}(x)$. Suppose this process is allowed to continue indefinitely. What are some obvious rules of this list. Well, if $U \in \mathscr{N}(x)$ and $U \subset V$ then we should have $V \in \mathscr{N}(x)$ because if $V$ contains $U$ and $x$ is known to be in $U$, then it certainly is known to be in $V$. Also if $U, V \in \mathscr{N}(x)$ then $x$ is known to be in both $U$ and $V$. So $x$ is known to be in $U \cap V$. Hence $\mathscr{N}(x)$ is closed under finite intersections. As some readers might recognize, $\mathscr{N}(x)$ is a filter. If we repeat this process for each $x \in X$ we can use the resulting system of neighborhood filters to get a topology $\Omega X$ on $X$. Hence $\Omega X$ represents a lattice of observations on $X$. That is if we take a $U \in \Omega X$ then for some abstract $x \in X$ we know (observation) that $x \in U$ (except for the empty set which is defined by the property that we know for sure that no x can be observed there).
It is interesting to note that the only space for which you can actually observe all points precisely, that is for all, originally hypothetical $x \in X$, we actually have $\{x\} \in \mathscr{N}(x)$, is for $\Omega X = \mathscr{P}(X)$. Let us call this space classical space and let us call $\mathscr{P}(X)$ the lattice of classical observations. Now $\mathscr{P}(X)$ is well known to be a boolean algebra and a model for classical logic. That is the logic of observations of points (questions about whether certain $x$ are in certain elements of $\Omega X$) on classical space is classical. So if the proposition $p$ is "$x \in U"$ then $\sim p$ (read not $p$) is "$x \in U^c$", which makes perfect sense because in classical space $\Omega X = \mathscr{P}(X)$, that is "$x \in U^c$" is a always a possible observation for any $U$. Then since $X = U \cup U^c \in \Omega X$ ($U^c$ is the complement of $U$), we certainly have that "$x \in U$" ($p$) or "$x \in U^c$" ($\sim p$) . So $p \vee \sim p$ is true for all observations in the lattice of classical observations about points in classical space. That is the law of excluded middle holds on observations in classical space. Let us rephrase noting that the law of excluded middle holding on a lattice of observations on a space $X$ is equivalent to $\forall U \in \Omega X \: [U^c \in \Omega X]$. That is it is equivalent to the lattice of observations (topology) on $X$ being closed under complementation. It is not hard to see that for a $T_0$ space, the "excluded middle property" actually ensures that the lattice of observations is classical ($T_0$ means that for any two distinct points there exists a neighborhood of one of the points not containing the other). This is because if $x \in X$ and $y \in \{x\}^c$ then $\exists U \in \Omega X$ such that $x \in U$ and $y \notin U$ or $y \in U$ and $x \notin U$. However since complements are open by assumption that $\Omega X$ is boolean, $U^c$ is open in either case. So either way $y$ is in an open set not containing $x$. Hence $\{x\}^c$ is open. So $\{x\}$ is open by the assumption that $\Omega X$ is boolean. So $\Omega X$ contains all singletons. Hence it is discreet. This ultimately will not be good enough for us because the definition of a $T_0$ space requires that every time some $x$ is "objectively" (in the Platonic sense of classical mathematics) not equal to some $y$ we must have that we can observe one without observing the other. We would like to rephrase and state that if $x$ is known (observed) to be distinct from $y$ then this means literally that we can produce a neighborhood in the lattice of observations containing one point and not the other and $T_0$ separation for us becomes a necessity since it literally means that the points are known to be distinct (known by means of the lattice of observations), otherwise we cannot know objectively. From this we can now characterize the excluded middle property on the lattice of observations on a space: A space $X$ with lattice of observations $\Omega X$ is classical $\iff$ every abstract $x \in X$ can be observed objectively ($\{x\}\in \Omega X$) $\iff$ the lattice of observations satisfies the excluded middle property and it can be observed that any two hypothetical distinct points (mental abstraction) are observably distinct ($T_0$ separation).
Let us formalize some of these ideas. First some vocabulary.
Let $(P,\leq)$ be a partially ordered set. We will call $(P,\leq)$ a frame if
\[1. \qquad \forall A \subset P \: [\bigvee A \in P]\]
\[2. \qquad \forall A \subset P, |A| < \infty \:[\bigwedge A \in P]\]
\[3. \qquad \forall A \subset P\:\forall x\in P\:[x\wedge \bigvee A = \bigvee \{x\wedge a\:|\:a\in A\}]\]
Now note, as Vickers does, that 2. is wholly unnecessary and in fact unduly restrictive. We can get a property stronger that 2. using only 1. and the fact that $P$ is a poset as follows. First note that 1. guarantees that we have a least element, call it $0$, in P. This is because $0 = \bigvee \emptyset$. So let $A \subset P$. Then let $L$ be the set of lower bounds of $A$, which is non-empty because $0 \in A$. Then by 1., $s:=\bigvee L \in P$. Let $a \in A$. Then $a$ is a u.b. for $L$. So $s \leq a$. Hence $s$ is a l.b. for $A$. Let $t$ be another l.b. for $A$. Then $t \in L$. So $t \leq s$. Hence $s = \bigwedge A \in P$. So we automatically get that $P$ contains arbitrary infimums.
So why are we even considering these frames? Well, let $X$ be a space and $\Omega X$ a topology on $X$. Then $\Omega X$ is a frame under set inclusion. Indeed properties 1-3 follow immediately because $\Omega X$ is closed under arbitrary unions (joins) and finite intersections (meets). But wait, we have just shown that $\Omega X$ must then contain arbitrary meets. Doesn't that imply that it contains arbitrary intersections? No. Let $A \subset \Omega X$. Then $\bigwedge A$ is the largest set in $\Omega X$ that is $\leq$ (contained in) every $a \in A$. So it is the union (join) of all open sets contained in the intersection of $A$. It is the interior of $\bigcap A$. Hence $\bigwedge A = (\bigcap A)^\circ$.
I will stop here for now. In the next post I will introduce (complete) Heyting Algebras and develop a logic of observations on an arbitrary topology. Just as the classical logic of propositions on $X$ has lattice of observations $\mathscr{P}(X)$ (discrete topology) and satisfies the excluded middle, the logic of propositions on an arbitrary topology $\Omega X$ (we shall call it an intuitionist logic of propositions on $X$) has lattice of observations $\Omega X$ and the excluded middle property need not hold. I may also discuss some intuition (if I haven't hinted at it already) as to why these notions are useful, particularly the abandonment of the excluded middle property.
Subscribe to:
Comments (Atom)