The Unapologetic Mathematician

Mathematics for the interested outsider

Characteristic Functions as Idempotents

I just talked about characteristic functions as masks on other functions. Given a function f:X\rightarrow\mathbb{R} and a subset S\subseteq X, we can mask the function f to the subset S by multiplying it by the characteristic function \chi_S. I want to talk a little more about these functions and how they relate to set theory.

First of all, it’s easy to recognize a characteristic function when we see one: they’re exactly the idempotent functions. That is, {\chi_S}^2=\chi_S, and if f^2=f then f must be \chi_S for some set S. Indeed, given a real number a, we can only have a^2=a if a=0 or a=1. That is, f(x)=0 or f(x)=1 for every x. So we can define S to be the set of x\in X for which f(x)=1, and then f(x)=\chi_S(x) for every x\in X. Thus the idempotents in the algebra of real-valued functions on X correspond exactly to the subsets of X.

We can define two operations on such idempotent functions to make them into a lattice. The easier to define is the meet. Given idempotents \chi_S and \chi_T we define the meet to be their product:

\displaystyle\left[\chi_S\wedge\chi_T\right](x)=\chi_S(x)\chi_T(x)

This function will take the value {1} at a point x if and only if both \chi_S and \chi_T do, so this is the characteristic function of the intersection

\displaystyle\chi_S\wedge\chi_T=\chi_{S\cap T}

We might hope that the join would be the sum of two idempotents, but in general this will not be another idempotent. Indeed, we can check:

\displaystyle(\chi_S+\chi_T)^2={\chi_S}^2+{\chi_T}^2+2\chi_S\chi_T=(\chi_S+\chi_T)+2\chi_{S\cap T}

We have a problem exactly when the corresponding sets have a nonempty intersection, which leads us to think that maybe this has something to do with the inclusion-exclusion principle. We’re “overcounting” the intersection by just adding, so let’s subtract it off to define

\displaystyle\left[\chi_S\vee\chi_T\right](x)=\chi_S(x)+\chi_T(x)-\chi_S(x)\chi_T(x)

We can multiply this out to check its idempotence, or we could consider its values. If x is not in T, then \chi_T(x)=0, and we find \chi_S\vee\chi_T=\chi_S — it takes the value {1} if x\in S and {0} otherwise. A similar calculation holds if x\notin S, which leaves only the case when x\in S\cap T. But now \chi_S(x) and \chi_T(x) both take the value {1}, and a quick calculation shows that \chi_S\vee\chi_T does as well. This establishes that

\displaystyle\chi_S\vee\chi_T=\chi_{S\cup T}

We can push further and make this into an orthocomplemented lattice. We define the orthocomplement of an idempotent by

\displaystyle\left[\neg\chi_S\right](x)=1-\chi_S(x)

This function is {1} wherever \chi_S is {0}, and vice-versa. That is, it’s the characteristic function of the complement

\displaystyle\neg\chi_S=\chi_{X\setminus S}

So we can take the lattice of subsets of X and realize it in the nice, concrete algebra of real-valued functions on X. The objects of the lattice are exactly the idempotents of this algebra, and we can build the meet and join from the algebraic operations of addition and multiplication. In fact, we could turn around and do this for any commutative algebra to create a lattice, which would mimic the “lattice of subsets” of some “set”, which emerges from the algebra. This sort of trick is a key insight to quite a lot of modern geometry.

December 23, 2009 Posted by | Algebra, Fundamentals, Lattices | 2 Comments

Galois Connections

I want to mention a topic I thought I’d hit back when we talked about adjoint functors. We know that every poset is a category, with the elements as objects and a single arrow from a to b if a\leq b. Functors between such categories are monotone functions, preserving the order. Contravariant functors are so-called “antitone” functions, which reverse the order, but the same abstract nonsense as usual tells us this is just a monotone function to the “opposite” poset with the order reversed.

So let’s consider an adjoint pair F\dashv G of such functors. This means there is a natural isomorphism between \hom(F(a),b) and \hom(a,G(b)). But each of these hom-sets is either empty (if a\not\leq b) or a singleton (if a\leq b). So the adjunction between F and G means that F(a)\leq b if and only if a\leq G(b). The analogous condition for an antitone adjoint pair is that b\leq F(a) if and only if a\leq G(b).

There are some immediate consequences to having a Galois connection, which are connected to properties of adjoints. First off, we know that a\leq G(F(a)) and F(G(b))\leq b. This essentially expresses the unit and counit of the adjunction. For the antitone version, let’s show the analogous statement more directly: we know that F(a)\leq F(a), so the adjoint condition says that a\leq G(F(a)). Similarly, b\leq F(G(b)). This second condition is backwards because we’re reversing the order on one of the posets.

Using the unit and the counit of an adjunction, we found a certain quasi-inverse relation between some natural transformations on functors. For our purposes, we observe that since a\leq G(F(a)) we have the special case G(b)\leq G(F(G(b))). But F(G(b))\leq b, and G preserves the order. Thus G(F(G(b)))\leq G(b). So G(b)=G(F(G(b))). Similarly, we find that F(G(F(a)))=F(a), which holds for both monotone and antitone Galois connections.

Chasing special cases further, we find that G(F(G(F(a))))=G(F(a)), and that F(G(F(G(b))))=F(G(b)) for either kind of Galois connection. That is, F\circ G and G\circ F are idempotent functions. In general categories, the composition of two adjoint functors gives a monad, and this idempotence is just the analogue in our particular categories. In particular, these functions behave like closure operators, but for the fact that general posets don’t have joins or bottom elements to preserve in the third and fourth Kuratowski axioms.

And so elements left fixed by G\circ F (or F\circ G) are called “closed” elements of the poset. The images of F and G consist of such closed elements

May 18, 2009 Posted by | Algebra, Category theory, Lattices | 6 Comments

DeMorgan’s Laws

And here’s the post I wrote today:

Today, I want to prove two equations that hold in any orthocomplemented lattice. They are the famous DeMorgan’s laws:

\displaystyle\neg(x\vee y)=\neg x\wedge\neg y
\displaystyle\neg(x\wedge y)=\neg x\vee\neg y

First, we note that x\leq x\vee y by definition. Since our complementation reverses order, we find \neg(x\vee y)\leq\neg x. Similarly, \neg(x\vee y)\leq\neg y. And thus we conclude that \neg(x\vee y)\leq\neg x\wedge\neg y.

On the other hand, \neg x\wedge\neg y\leq\neg x by definition. Then we find x=\neg\neg x\leq\neg(\neg x\wedge\neg y) by invoking the involutive property of our complement. Similarly, y\leq\neg(\neg x\wedge\neg y), and so x\vee y\leq\neg(\neg x\wedge\neg y). And thus we conclude \neg x\wedge\neg y\leq\neg(x\vee y). Putting this together with the other inequality, we get the first of DeMorgan’s laws.

To get the other, just invoke the first law on the objects \neg x and \neg y. We find

\displaystyle\begin{aligned}\neg x\vee\neg y&=\neg\neg(\neg x\vee\neg y)\\&=\neg(\neg\neg x\wedge\neg\neg y)\\&=\neg(x\wedge y)\end{aligned}

Similarly, the first of DeMorgan’s laws follows from the second.

Interestingly, DeMorgan’s laws aren’t just a consequence of order-reversal. It turns out that they’re equivalent to order-reversal. Now if x\leq y then x=x\wedge y. So \neg x=\neg(x\wedge y)=\neg x\vee\neg y. And thus \neg y\leq\neg x.

May 8, 2009 Posted by | Algebra, Lattices | 8 Comments

Orthogonal Complements and the Lattice of Subspaces

We know that the poset of subspaces of a vector space V is a lattice. Now we can define complementary subspaces in a way that doesn’t depend on any choice of basis at all. So what does this look like in terms of the lattice?

First off, remember that the “meet” of two subspaces is their intersection, which is again a subspace. On the other hand their “join” is their sum as subspaces. But now we have a new operation called the “complement”. In general lattice-theory terms, a complement of an element x in a bounded lattice L (one that has a top element {1} and a bottom element {0}) is an element \neg x\in L so that x\vee\neg x=1 and x\wedge\neg x=0.

In particular, since the top subspace is V itself, and the bottom subspace is \mathbf{0} we can see that the orthogonal complement U^\perp satisfies these properties. The intersection U\cap U^\perp is trivial, since the inner product is positive-definite as a bilinear form, and the sum U+U^\perp is all of V, as we’ve seen.

Even more is true. The orthogonal complement is involutive (when V is finite-dimensional), and order-reversing, which makes it an “orthocomplement”. In lattice-theory terms, this means that \neg\neg x=x, and that if x\leq y then \neg y\leq\neg x.

First, let’s say we’ve got two subspaces U\subseteq W of V. I say that W^\perp\subseteq U^\perp. Indeed, if p is a vector in W^\perp then it \langle w,p\rangle=0 for all w\in W. But since any u\in U is also a vector in W, we can see that \langle u,p\rangle=0, and so p\in U^\perp as well. Thus orthogonal complementation is

Now let’s take a single subspace U of V, and let u be a vector in U. If v is any vector in U^\perp, then \langle v,u\rangle=\overline{\langle u,v\rangle}=0 by the (conjugate) symmetry of the inner product and the definition of U^\perp. Thus u is a vector in \left(U^\perp\right)^\perp, and so U\subseteq U^{\perp\perp}. Note that this much holds whether V is finite-dimensional or not.

On the other hand, if V is finite-dimensional we can take an orthonormal basis \left\{e_i\right\}_{i=1}^n of U and expand it into an orthonormal basis \left\{e_i\right\}_{i=1}^d of all of V. Then the new vectors \left\{e_i\right\}_{i=n+1}^d form a basis of U^\perp, so that V=U\oplus U^\perp. A vector in V is orthogonal to every vector in U^\perp exactly when it can be written using only the first n basis vectors, and thus lies in U. That is, U^{\perp\perp}=U when V is finite-dimensional.

May 7, 2009 Posted by | Algebra, Lattices, Linear Algebra | 7 Comments

Lattices

A poset which has both least upper bounds and greatest lower bounds is called a lattice. In more detail, let’s say we have a poset (P,\preceq) and give it two operations: meet (written \wedge) and join (written \vee). These satisfy the requirements that

  • x\preceq x\vee y and y\preceq x\vee y.
  • If x\preceq z and y\preceq z then x\wedge y\preceq z.
  • x\wedge y\preceq x and x\wedge y\preceq y.
  • If z\preceq x and z\preceq y then z\preceq x\wedge y.

Not every poset has a meet and a join operation, but if these operations do exist they are uniquely specified by these requirements. In fact, we can see this sort of like how we saw that direct products of groups are unique up to isomorphism: if we have two least upper bounds for a pair of elements then they must each be below or equal to the other, so they must be the same.

We can derive the following properties of the operations:

  • a\vee(b\vee c)=(a\vee b)\vee c and a\wedge(b\wedge c)=(a\wedge b)\wedge c.
  • a\vee b=b\vee a and a\wedge b=b\wedge a.
  • a\vee(a\wedge b)=a and a\wedge(a\vee b)=a.

from these we see that there’s a sort of duality between the two operations. In fact, we can see that these provide two commutative semigroup structures that happen to interact in a certain nice way.

Actually, it gets even better. If we have two operations on any set satisfying these properties then we can define a partial order: x\preceq y if and only if x=x\wedge y. So we can define a lattice either by the order property and get the algebraic properties, or we can define it by the algebraic properties and get the order property from them.

In many cases, a lattice also satisfies x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z), or equivalently x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z). In this case we call it “distributive”. A bit weaker is to require that if x\preceq z then x\vee(y\wedge z)=(x\vee y)\wedge z for all y. In this case we call the lattice “modular”.

A lattice may have elements above everything else or below everything else. We call a greatest element of a lattice 1 and a least element {0}. In this case we can define “complements”: x and y are complements if x\vee y=1 and x\wedge y=0. If the lattice is distributive, then the complement of x is unique if it exists. A distributive lattice where every element has a complement is called “Boolean”.

May 14, 2007 Posted by | Algebra, Lattices, Orders | 8 Comments

   

Follow

Get every new post delivered to your Inbox.

Join 366 other followers