The characteristic function of a subset

Before we talk about operations (union, intersection, etc.) on multisets, it will be helpful to talk a bit more about a particular construction associated with the power set of a set.

To start with, let’s look at the finite field \mathbb{F}_2. The operation tables for \mathbb{F}_2 are:

\begin{array}{r|rr} + & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} and \begin{array}{r|rr} \cdot & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \\ \end{array}

If we take 0 as false and 1 as true, then multiplication corresponds to conjunction \left(\wedge\right) in classical logic and addition corresponds to exclusive disjunction \left(\underline{\vee}\right).

Definition

Let X be a set and A\subseteq X. The characteristic function of A (relative to X) is the function \chi_A: X\to \mathbb{F}_2 defined by

\chi_A: x\mapsto \left\{ \begin{array}{r@{\quad:\quad}l} 0 & x\not\in A \\ 1 & x\in A \end{array} \right.

With this definition, we actually have a bijective correspondence between the power set \wp\left(X\right) and the functions \left\{\chi \: | \: \chi: X\to\mathbb{F}_2\right\}.

Let’s consider the sums and products of characteristic functions. If A, B\subseteq X, then \chi_A + \chi_B and \chi_A\chi_B are both well defined functions from X to \mathbb{F}_2—in other words, the sum and the product of two characteristic functions are again characteristic functions for some subsets of X.

For the product \chi_C = \chi_A\chi_B, we will have \chi_C\left(x\right) = 1 if and only if \chi_A\left(x\right) = \chi_B\left(x\right) = 1, so the product yields the characteristic function of the set C = A \cap B. This isn’t particularly surprising, since multiplication in \mathbb{F}_2 corresponds to logical conjunction. The sum, however, does not correspond to intersection (remember that the sum in \mathbb{F}_2 corresponds to exclusive disjunction). If \chi_D = \chi_A + \chi_B, then \chi_D\left(x\right) = 1 whenever exactly one of \chi_A\left(x\right) and \chi_B\left(x\right) equals 1, so we have D = A\vartriangle B, the symmetric difference.

Using these two results, we can easily determine the formulas involving characteristic functions that correspond to the other typical set operations. For the difference (relative complement) of two subsets of a set X, we have

C = A - B = A\vartriangle \left(A\cap B\right) \:\Leftrightarrow\:\chi_C = \chi_A + \chi_A\chi_B.

One of the identities among the set operations applied to \wp\left(X\right) is A \cup B = X - \left(\left(X-A\right)\cap\left(X-B\right)\right). The characteristic function \chi_X is the constant value 1; combining this identity with the previous results, we find that

\begin{aligned} A\cup B &\Leftrightarrow 1 + 1\left(1+1\chi_A\right)\left(1+1\chi_B\right)\\ &\Leftrightarrow \chi_A+\chi_B+\chi_A\chi_B.\end{aligned}

Incidentally, in \mathbb{F}_2 each element is its own additive inverse, so we have a - b = a + b for all a, b\in \mathbb{F}_2, so each of the formulas we have derived above can also be expressed in terms of subtraction.

If we further consider \mathbb{F}_2 as an ordered field, we obtain two additional ways to represent unions and intersections in terms of their characteristic functions:

C = A\cap B \:\Leftrightarrow\: \chi_C = \min\left(\chi_A, \chi_B\right)

and

C = A\cup B \:\Leftrightarrow\: \chi_C = \max\left(\chi_A, \chi_B\right).

One final observation. If A \subseteq B \subseteq C and \chi_A: B\to \mathbb{F}_2 is the characteristic function of A relative to B, then \chi_A has a unique extension \chi^{\,\prime}_A: C\to \mathbb{F}_2 defined by

\chi^{\,\prime}_A: x\mapsto\left\{ \begin{array}{r@{\quad:\quad}l} 0 & x\not\in B \\ \chi_A\left(x\right) & x\in B \end{array} \right.

In order for the sums and products of characteristic functions to be well-defined, they must have a common domain. The existence of this unique extension ensures that we can always find a common domain in which to represent any family of sets by their characteristic functions.

Copyright © 2008 Michael L. McCliment.

Advertisements

5 Responses to The characteristic function of a subset

  1. Vishal Lama says:

    Michael,

    I hope you don’t take this any other way, but would you kindly consider changing the black background of your blog to something lighter if not white? The current design is certainly very attractive; however, one has to strain one’s eyes quite a bit to read the posts on your blog. But if you wish to keep things as they are, that is totally fine! :)

    Best,
    Vishal

  2. Vishal,

    I’ve actually been thinking about this issue already. I like the layout of this theme, but I’m not entirely happy with it. Light-on-dark designs really need a larger, heavier font than dark-on-light designs from a graphic design perspective, which didn’t happen. I’m also not satisfied with the way that the \LaTeX rendering interacts with the color scheme and font sizes.

    I just need to figure out whether I can fix it by buying the CSS upgrade and tweaking things, or whether I need to change the theme entirely. Any ideas on which themes work best with \LaTeX and the longer posts?

  3. Vishal Lama says:

    Michael,

    I guess the only way to make sure you like the layout/design/font-size is to try every theme available before you settle on the one you like best. If you are willing to shell out a little money to buy the CSS upgrade to improve the design, that should be fine too!

    Obviously I will give you a biased answer to your last question, but let me give it anyway. So far, the theme I think “meshes” very well with \LaTeX is the one I use for my own blog. I discovered it through Terry Tao’s blog, which you surely must have visited. I also do like the theme at Secret Blogging Seminar.

  4. […] be represented as functions In fact, for every function we can define Combining this with the definition of the characteristic function, we have the […]

  5. […] When we looked at the characteristic function for the subset of a set, we started by examining both sums and products of the characteristic […]

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

%d bloggers like this: