Boolean Algebra

At first, the definition of a boolean algebra looks like a motley collection properties for the various operations (and relation, if one includes the order). Are they the right properties? Why those in particular (or an equivalent set) and not others?

Recall the Stone Representation Theorem: Any boolean algebra is isomorphic to a field of sets, i.e., a (nonempty) family of sets closed under complement, binary union, and binary intersection. A field of sets is really nothing more nor less than a subalgebra of a power set algebra—the algebra of all subsets of a given set.

Thus we have a \(\forall_1\)-axomatized (indeed, equational) theory \(T\) and such a class \(\mathcal{K}\) of structures that \(\mathcal{K}\subseteq\mbox{Mod }T\subseteq\mbox{Sub }\mathcal{K}\). By the consequences of Los-Tarski in the Introduction, the theory of boolean algebras is exactly the universal theory of power set algebras. That is what makes boolean algebras "right".

(An aside: We note that the theory of boolean algebras is not the entire theory of power set algebras. All power set algebras are atom(ist)ic, for example, but not all boolean algebras are.)

Order

Relatedly, there is the definition of a (n) (partial) order: a binary relation that is reflexive, transitive, and antisymmetric. (This is categorily equivalent to the "irreflexive and transitive" version.) I will contend that orders are meant to simulate inclusion among sets. Do these axioms correctly capture inclusion? We will answer this question affirmatively.

Suppose \(\langle A,\leq\rangle\) is an order. For any \(a\in A\), define \(L_a=(-\infty,a]\subseteq A\), i.e., \(L_a=\{x\in A: x\leq a\}\). Let \(\mathcal{L}=\{L_a:a\in A\}\). The \(\mathcal{L}\) is (partially) ordered by inclusion. Indeed, \(\langle\mathcal{L},\subseteq\rangle\) is a subspace of \(\langle\mathcal{P}(A),\subseteq\rangle\). We observe that

Proposition. For all \(a\in A\), \(a\in L_a\). (This is simply the reflexive property of ≤.)

We now assert that

Theorem. \(\langle A,\leq\rangle\simeq\langle \mathcal{L},\subseteq\rangle\).

Proof: Define \(\phi:A\to\mathcal{L}\) by (surprise, surprise) \(\phi(a)=L_a\). We assert that \(\phi\) is an isomorphism. We start by showing that \(\phi\) is a bijection.

- (\(\phi\) is a bijection) \(\phi\) is surjective (onto) by construction of \(\mathcal{L}\), so we need show only that \(\phi\) is injective (1-1). Suppose \(\phi(a)=\phi(b)\), i.e., that \(L_a=L_b\). Then \(a\in L_b\) and \(b\in L_a\) (by the Proposition), whence \(a\leq b\) and \(b\leq a\) by definition. By antisymmetry, \(a=b\). Thus, \(\phi\) is injective and hence bijective.

We now have that \(\phi^{-1}\) is well-defined on \(\mathcal{L}\) and, for \(L\in\mathcal{L}\), \(\phi^{-1}(L)=\mbox{max }L\). We won't actually need that. After all, any \(L\in\mathcal{L}\) is \(L_a\) for some \(a\in A\), so \(\phi^{-1}(L)=phi^{-1}(L_a)=a\).

Next, we must show that \(\phi\) and \(\phi^{-1}\) are homomorphisms.

- (\(\phi\) is a homomorphism) Suppose \(a\leq b\) in \(A\). We must show that \(\phi(a)\subseteq\phi(b)\). To that end, suppose \(x\in\phi(a)\), i.e., that \(x\in L_a\), i.e., that \(x\leq b\). Because \(a\leq b\) by hypothesis and transitivity of ≤, \(x\leq b\), whence \(x\in\phi(b)\). It follows that \(\phi(a)\subseteq\phi(b)\). This shows that \(\phi\) is a homomorphism.
- (\(\phi^{-1}\) is a homomorphism) Suppose \(L_a\subseteq L_b\) in \(\mathcal{L}\). Then \(a\in L_b\), whence \(a\leq b\), i.e., \(\phi^{-1}(L_a)\leq\phi^{-1}(L_b)\). This shows that \(\phi^{-1}\) is a homomorphism.

All together, these assertions prove that \(\phi\) is an isomorphism. It follows that \(\langle A,\leq\rangle\simeq\langle \mathcal{L},\subseteq\rangle\), as promised.

Note that the proof used exactly the three order properties: reflexivity, transitivity, and antisymmetry.

Here we are again. We have a universal theory \(T\) and such a class \(\mathcal{K}\) of structures that \(\mathcal{K}\subseteq\mbox{Mod }T\subseteq\mbox{Sub }\mathcal{K}\). We conclude that the theory of (partial) orders is exactly the universal theory of subset inclusions. Reflexiviity, transitivity, and antisymmetry get it right.

Linear Order

A strict order is linear if it is transitive and trichotomic. Do those two properties merit the description linear? To answer that question, we turn to geometry. The basic property of a line is that it is thin: Given any three distinct points on a line, one of them is between the other two. (One can define lines as maximal thin sets.) This is indeed a consequence of transitivity and trichotomy. First, the obvious definition of betweenness in this context: For any points \(a\), \(b\), and \(c\) in an ordered set, \(b\) is between \(a\) and \(c\) iff \(a<b<c\) or \(c<b<a\). (Note the implicit use of transitivity in the notation.) Now:

Theorem. An order with at least three elements is a linear order iff it is thin.

Proof: Suppose \(a\), \(b\), and \(c\) are distinct points in an order \(\langle A,<\rangle\). We will show, essentially, that thinness is equivalent to trichotomy (for orders, not logically equivalent).

- \((\Rightarrow)\) Suppose \(\langle A,<\rangle\) is a linear order. Without loss of generality, suppose \(a<c\). Suppose further that \(b\nless a\) and \(c\nless b\). By trichotomy (and the distinctness of the three), we have \(a<b\) and \(b<c\), whence \(a<b<c\).
- \((\Leftarrow)\) Suppose \(\langle A,<\rangle\) is thin. Suppose further that \(a\neq b\). By hypothesis, there is a third element \(c\neq a,b\). By thinness, there are six possibilities, which we can abbreviate as \(abc,\ acb,\ bac,\ bca,\ cab\), and \(cba\). In three of the six, we have \(a<b\) either directly or by transitivity. In the other three, we have \(b<a\). It follows that \(\langle A,<\rangle\) is trichotomic and hence linear.

Thus, an order with at least three elements is linear orders iff it is thin, as promised.

"Transitive and trichotomic" gets it right.

Discrete Linear Order

An order is discrete iff each non-maximal element has an immediate successor and each non-minimal element has an immediate predecessor. However, discreteness (discretion?) is a concept from topology, describing a topology in which all subsets are open. Does this definition get it right? We will show that, in the case of a discrete linear order, it does. (Discrete nonlinear orders are a bit of a mess, alas.)

Recall the order topology, the topology generated by all subsets (intervals) of the form \((-\infty, b)\),or \((a,\infty)\) as a subbasis or, equivalently, by all subsets of the form \((a, b)\) (allowing a, b = ±∞) as a basis.

Theorem. A linear order is a discrete order iff its order topology is discrete.

Proof: Suppose \(\langle A, \leq\rangle\) is a linear order.

- \((\Rightarrow)\) Suppose \(\langle A, \leq\rangle\) is a discrete order. We will show that all singletons are open in the order topology. Surely the one-point order is discrete, so we will proceed with orders of size at least two. There are three cases:
  - If \(a\in A\) is neither maximal nor minimal, then \(a\) has an immediate predecessor \(p\) and an immediate successor \(s\). Then \(\{a\}=(p,s)\) and hence is open.
  - If \(a\in A\) is minimal, then it is not maximal (lest the size equal one) and hence has an immediate successor \(s\). Then \(\{a\}=(-\infty,s)\) and hence is open.
  - If \(a\in A\) is maximal, then it is not maximal (lest the size equal one) and hence has an immediate predecessor \(p\). Then \(\{a\}=(p,\infty)\) and hence is open.

Thus, the order topology on a discrete linear order is discrete.

- \((\Leftarrow)\) Suppose the order topology on\(\langle A, \leq\rangle\) is discrete. Suppose \(a\in A\) is neither minimal nor maximal and has no immediate predecessor nor an immediate successor. We assert that all open neighborhoods of \(a\) contain (infinitely many!) points other than \(a\).

\(a\) must have infinitely many predecessors (lest it have an immediate one) and ditto for successors. Any subbasic set containing \(a\) has the form \(-\infty,s\) for some \(s>a\) or \(p,\infty\) for some \(p<a\). Both types contain infinitely many points other than \(a\), thus any finitary intersection of them—necessarily of the form \(s,p\), \(-\infty,s\), or \(p,\infty\)—also includes infinitely many points besides \(a\). It follows that any union of such sets contains infinitely many points besides \(a\). Such unions are the totality of all open sets that contain \(a\). Thus, \(\{a\}\) itself is not open, whence the topology is not discrete.

Thus, \(\langle A, \leq\rangle\) is a discrete order iff its order topology is discrete, as promised.