Home MATH 318 Friday, September 23, 2011

Friday, September 23, 2011 CC-BY-NC
Atoms and complements

Maintainer: admin

1Lattice from last class continued

Going back to the lattice that looks like four stacked squares, shifted 45 degrees. It's definitely modular, as there are no copies of five in there. It's also distributive I think? Reasoning: if you take any three points, at least 2 are on the same side and so are comparable in this lattice.

2Facts about any lattice

$$\underbrace{x \land y = x} \iff \underbrace{x \leq y} \iff \underbrace{x \lor y = y} \tag{ all equivalent}$$

  • $x \land \top = x$, $x \lor \top = \top$
  • $x \land \bot = \bot$, $x \lor \bot = x$
  • $x \land x = x$, $x \lor x = x$
  • $x \land y = y \land x$, $x \lor y = y \lor x$ (symmetry)
  • $x \land (y \land z) = (x \land y) \land z$ (associativity)
  • $x \land (x \lor y) = x = x \lor (x \land y)$ (absorption)

For example, if $w = x \land (y \land z)$, then $w \leq x$, $w \leq y \land z$, and if $v \leq x$, $v \leq y \land z$ then $v \leq w \iff w \leq x$, $w \leq y$, $w \leq z$ and anything $\leq$ all three of $x$, $y$ and $z$ is $\leq w$. The same is true when you switch the parentheses, due to associativity.

2.1Atoms

An atom in a lattice is $a \in L$ such that it is above the bottom ($\bot \leq a$) but there is nothing between $a$ and the bottom (so nothing just below it). Similarly, a co-atom is an element that is just below the top.

In a finite lattice, there is at least one atom $\leq b$ for any $b \in L$, but the situation is different for infinite lattices.

Consider $(\mathbb{R}; \leq)$ - a totally ordered set, but not a lattice as there are no top and bottom elements. So we join it with $\{ -\infty, \infty\}$, and make them the top and bottom elements, respectively. Now, $\mathbb{R} \cup \{ -\infty, \infty \}$ is a lattice, but there are no atoms - you can always go longer than any real number, for instance by subtracting one.

In the power set lattice $(P(X); \subseteq)$, which is a distributive, complemented lattice (i.e. a boolean algebra), all the singleton ($\{a\}, \{b\}$, etc) are atoms.

In the lattice for the representative set ($\mathcal{F}$ - discussed in the lecture on Monday, September 19), all the formulas with just one variable are atoms. So $p$ and $\neg p$ for some $p$.

2.1.1Finite boolean algebras

Let $B$ be a finite boolean algebra, and let $b \in B$ be an element $\neq \bot$. There are then $k$ distinct atoms below $b$, where $k \geq 1$. So $b$ can be said to be the join of all those atoms: $b = a_1 \lor a_2 \lor a_3 \lor ... \lor a_k$ where $a_1 ... a_k$ are the atoms.

This is not true for all lattices, although it might be true for some non-finite boolean algebrasconfirm?

2.1.2De Morgan laws for complements

  • $(x \land y)^c = x^c \lor y^c$
  • $(x \lor y)^c = x^c \land y^c$
  • $(x^c)^c = x$

2.1.3More on complements

Note: anything that acts like a complement to an element is that element's complement.

Also, note that if $x \leq y$ then $y^c \leq x$ not sure why.

Consider $b \land a_1^c ... a_k^c$. If this is not equal to the bottom element, then there is an atom $a \leq b \land a_1^c ... a_k^c$. In particular, $a \leq b$, so $a = a_j$ for some $j$ but $a_j \land a_j^c = \bot$. But $a \land a_j^c = a$. So this is impossible, meaning, $b \land a_1^c ... a_k^c = \bot$. Okay.

So $b \land (a_1 \lor ... \lor a_k)^c = \bot$. So, $b^c = (a_1 \lor ... \lor a_k)^c$ and $b = (a_1 \lor ... \lor a_k)^c$. So $b^c \leq (a_1 \lor ... \lor a_k)^c$. So $b \lor b^c \leq \underbrace{b \lor (a_1 \lor ... a_k)^c}_{= \top}$

2.1.4Complements and atoms

So say $B$ is a finite, boolean algebra and $a_1, k$ are all the distinct atoms. Let $x = \{a_1, ... a_n\}$. Consider the boolean algebra of the power set $(P(X); \subseteq)$ - for each $b \in B$, if $b \neq \bot$, let $a$ be the atoms under $b$. Send $b$ to $\{a_1,...a_k\}$. $f: B \to P(X)$ is a bijection, and an isomorphism of boolean algebraswhat?. ($b \leq c \in B \iff f(b) \leq f(c) \in f$.)