
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
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 pairs over S. A binary relation is a subset of and so there are = 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, , in total. This is (in the weak sense) superdoublyexponential: asymptotically greater than for any k. What other naturallyoccurring 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 highschooler (and many/most gradeschoolers) 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 3element 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:
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 superexponential (in that same weak sense), I suspect the number of essentially distinct attributes will remain superdoublyexponential. Let's see... there are n! labelings of the elements, so relabeling gives you at least . 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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Relations  rhymin  Applied Math  7  April 3rd, 2013 07:20 PM 
Relations  rhymin  Number Theory  8  March 30th, 2013 05:18 PM 
Relations  tinaa  Applied Math  7  December 31st, 2009 12:28 AM 
Relations  rebecca  Applied Math  2  November 29th, 2009 07:55 PM 
Finding modular relations among numbers of the form 2^k + n  CRGreathouse  Number Theory  3  January 16th, 2008 06:22 AM 