Indexing Set Elements

My research ideas come much faster than I can work on them, so from now on I’ll regularly post about some early ideas that I’ve had but probably won’t work on. I hope they’re interesting to think about 😉

2010-12-17

(That’s the date I got the idea, in Gregorian big-endian!)

In computer programming, we usually specify sets of objects by listing them down in order:

List = [1, "teacup", f(x) = x^2]

This inevitably involves some kind of order among the elements of the set, which can be undesirable in some circumstances. I propose a way to destroy that order (to some extent).

Consider a countable set U that contains all of the objects that we will be interested in (i.e. the “universe”). We index its elements with primes by choosing some injective function p : U \to P to the set of all primes P. Every set S \subseteq U is then associated with an integer \lVert S\rVert, which is the product of all the primes corresponding to its elements. That is, \lVert S\rVert = \prod_{x \in S} p(x) . Note that by unique factorization, any integer cannot correspond to two different subsets of U. Thus we can represent every subset of U using a unique integer. Moreover, since multiplication is commutative and associative, order is “destroyed” (unless you count the “global order” imposed by the size of integers).

Some basic properties:

  1. \lVert\emptyset \rVert = 1. (actually, this is more of a good definition than a property)
  2. \lVert\{x\}\rVert = p(x).
  3. A \subseteq B \iff \lVert A\rVert \text{ divides } \lVert B\rVert.
  4. \lVert A \cup B\rVert = \text{lcm}(\lVert A\rVert, \lVert B \rVert). (greatest common divisor)
  5. \lVert A \cap B\rVert = \gcd(\lVert A\rVert, \lVert B \rVert). (least common multiple)
  6. \lVert S^\complement\rVert = \lVert U \setminus S\rVert = \lVert U\rVert/\lVert S\rVert.

(4) and (5) got me really excited when I chanced upon them.

Where can we go from here? This might be a useful exercise to train the ability to produce original ideas, so think about possible ways to generalize this setup.

Suggestions

For starters, try replacing P with any set of integers in which every pair of elements must be coprime. Is there potential for “efficient” storage of sets, in terms of computational complexity?Further down… Unique Factorization Domains, anyone?

Advertisements

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