My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
April 21st, 2010, 02:00 PM   #1
Global Moderator
 
CRGreathouse's Avatar
 
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) super-doubly-exponential: asymptotically greater than 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...
CRGreathouse is offline  
 
April 22nd, 2010, 06: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, , 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?
cknapp is offline  
April 22nd, 2010, 06:30 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
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 . 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?
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 08:20 PM
Relations rhymin Number Theory 8 March 30th, 2013 06:18 PM
Relations tinaa Applied Math 7 December 31st, 2009 01:28 AM
Relations rebecca Applied Math 2 November 29th, 2009 08:55 PM
Finding modular relations among numbers of the form 2^k + n CRGreathouse Number Theory 3 January 16th, 2008 07:22 AM





Copyright © 2019 My Math Forum. All rights reserved.