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.

About these ads

December 23, 2009 - Posted by | Algebra, Fundamentals, Lattices

2 Comments »

  1. [...] Now that we know a little more about characteristic functions, let’s see how they can be used to understand the inclusion-exclusion principle. Our first [...]

    Pingback by Inclusion-Exclusion Again « The Unapologetic Mathematician | December 28, 2009 | Reply

  2. Meet and join seem equally easy to define if we have max as a binary operation for join, and min as a binary operation for meet. Really, any t-norm should work for meet, and any s-norm (t-conorm) should work for join, but min and max come as the only ones for which idempotence holds everywhere.

    Comment by Doug Spoonwood | May 16, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 388 other followers

%d bloggers like this: