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 The operation tables for are:

and

If we take 0 as false and 1 as true, then multiplication corresponds to conjunction in classical logic and addition corresponds to exclusive disjunction

Definition

Let be a set and The characteristic function of (relative to ) is the function defined by

With this definition, we actually have a bijective correspondence between the power set and the functions

Let’s consider the sums and products of characteristic functions. If then and are both well defined functions from to —in other words, the sum and the product of two characteristic functions are again characteristic functions for some subsets of

For the product we will have if and only if , so the product yields the characteristic function of the set . This isn’t particularly surprising, since multiplication in corresponds to logical conjunction. The sum, however, does not correspond to intersection (remember that the sum in corresponds to exclusive disjunction). If then whenever exactly one of and equals 1, so we have 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 we have

One of the identities among the set operations applied to is The characteristic function is the constant value 1; combining this identity with the previous results, we find that

Incidentally, in each element is its own additive inverse, so we have for all so each of the formulas we have derived above can also be expressed in terms of subtraction.

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

and

One final observation. If and is the characteristic function of relative to , then has a unique extension defined by

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.

This entry was posted on Monday, May 12th, 2008 at 4:00 am and is filed under Mathematics, Set theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

5 Responses to The characteristic function of a subset

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! :)

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 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 and the longer posts?

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 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.

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

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

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 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 and the longer posts?

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 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.

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

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