My Math Forum Relations, attributes, and counting to really big numbers

 Applied Math Applied Math Forum

 April 21st, 2010, 01:00 PM #1 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Relations, attributes, and counting to really big numbers Inspired by viewtopic.php?f=27&t=13510 Consider a finite set S with |S| = n elements. There are thus $|S\times S|=n^2$ pairs over S. A binary relation is a subset of $S\times S$ and so there are $2^{s^2}$ = A002416 binary relations over S ('only' A000595 up to isomorphism, but I'll ignore that for now). So consider an attribute of binary relations over S, like being reflexive or transitive. (We could count the number of relations *having* such attributes, as Götz Pfeiffer does in his excellent article here, but I'm looking at the number of attributes, not the number of relations.) There's one for every subset of the set of binary relations on S... and thus a staggering number, $2^{2^{s^2}}$, in total. This is (in the weak sense) super-doubly-exponential: asymptotically greater than $2^{2^{kn}}$ for any k. What other naturally-occurring objects in math are this big? Certainly there are proofs that use large numbers (famously in Ramsey theory), but where else are large collections actually studied, rather than just confined to a proof? Every high-schooler (and many/most grade-schoolers) has studied some attributes of relations in this sense, and yet how many could even comprehend the large numbers involved? With 3 objects, there are 104 essentially different relations: those not depending on the identities of the members. (Allowing labels on the objects increases this to 512, or about 5 ways per relation.) The number of attributes on 3-element sets is then comparable to the number of atoms in the universe...
April 22nd, 2010, 05:15 AM   #2
Senior Member

Joined: Oct 2007
From: Chicago

Posts: 1,701
Thanks: 3

Re: Relations, attributes, and counting to really big numbers

Interesting observation, CRG... Interesting indeed.

Quote:
 Originally Posted by CRGreathouse There's one for every subset of the set of binary relations on S... and thus a staggering number, $2^{2^{s^2}}$, in total.
I think the more interesting question is how many essentially different attributes are there on a given set S?
I would hesitate to say "contains (1,2)" is essentially different from "contains (2,3)", but I would say it's essentially different than "contains (1,1)".

I'm not quite sure how to make this idea rigorous, and I don't have time to think about it today...
Thoughts?

 April 22nd, 2010, 05:30 AM #3 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Relations, attributes, and counting to really big numbers Agreed. But just like A000595 appears to remain super-exponential (in that same weak sense), I suspect the number of essentially distinct attributes will remain super-doubly-exponential. Let's see... there are n! labelings of the elements, so relabeling gives you at least $2^{2^{n^2}}/n!>2^{2^{n^2}-n\lg n}$. Somehow I feel like you'd need to double the n lg n factor to account for starting from A000595 rather than A002416, but even so that's a superexponential factor minus a linearithmic one, not a big difference. Is there anything else to remove?

 Tags attributes, big, counting, numbers, relations

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post rhymin Applied Math 7 April 3rd, 2013 07:20 PM rhymin Number Theory 8 March 30th, 2013 05:18 PM tinaa Applied Math 7 December 31st, 2009 12:28 AM rebecca Applied Math 2 November 29th, 2009 07:55 PM CRGreathouse Number Theory 3 January 16th, 2008 06:22 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top