Sound and Fury

Signifying nothing

Enumerating structure on sets, again.

with one comment

The number of partitions on an N-membered set is called its “Bell number“. The number of strict total orders, I’m not sure about that… There is some relevant information here.

Well it’s good to see those problems solved, and I’m glad they weren’t trivial… Here is a more general issue. How many relations are there on a set? How many transitive? And so on.

So, a relation is simply a set of ordered pairs. So there are 2^X possible relations if there are X ordered pairs. For a set with N elements, there are N^2 ordered pairs. Thus 2^(N^2) relations on N elements. To give you an idea of scale, there are 65,536 relations on the 4 element set. But there are only 15 partitions on the 4 element set (not 18 as I said before; I counted each 2+2 partition twice.) So the properties of being transitive, reflexive and symmetrical must seriously cut down the number of relations! The only thing I’ve concluded in answer to this question is that there is an upper bound on the number of possible total relations on N elements: 2^(N^2) – 2^([n^2]/2). This is because the property of being total means that the size of the set of ordered pairs has to be big enough to contain at least one of (a,b) or (b,a) for every a,b. So small sets of pairs are ruled out.


Written by Seamus

February 12, 2009 at 3:36 pm

Posted in maths

Tagged with , ,

One Response

Subscribe to comments with RSS.

  1. In my opinion the lesson you learn is this.
    If someone gives you an explicit definition of a relation it is usually fairly easy to check that it is reflexive, symmetric and transitive (if this is the case).
    But to specify a “random” equivalence relation on a set, it is much simpler to give the partition instead.

    Peter Cameron

    December 7, 2009 at 6:38 pm

Leave a Reply

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

You are commenting using your 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: