Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Declaring that a set has 10 elements requires two things:

  • find some elements
  • show they are all distinct
  • showing you have all of them

Sometimes these are easier said than done.

E.g. count all the triangles

E.g. count all the Republicans in Nebraska

E.g. count all the files in this database

Is there a theory of enumeration for when you are too lazy (or lack the resources) to check your list of elements is distinct an exhaustive?



EDIT I'm not even 100% sure what I am looking for here.

I know that in current technology trends, the idea of "cardinality" is being somewhat challenged. If one could go through all your bins and index all the pieces of information being stored, it would be possible to give an order of magnitude estimate. There are situation where the amount of information being stored is so large and unpredictible that it's not even possible to do that. Enter probabilistic counting.

The task is to count all the elements in your database that satisfy property Q.
\[ n = |\{x \in S : Q(x)=true \} | \] Ideally, we would go through the elements of $X$ and verify one-by-one whether $Q$ is true. In some real-world cases, this is not not a realistic model.

In the sample "count all the Republicans" it may not be possible to test membership. Even if we came up with a well-defined criterion for "Republican" it may not be meaningful for a particular application "Will this person vote for Proposition X?"

What can we do when set theory fails to be a realistic model of relations? Can there be a meaningful theory of cardinality?

share|improve this question
    
You question is not clear. May be you're asking fo this? en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle –  Mohan Jan 9 '13 at 21:03
    
It seems like you want ways to do approximations of counts. There are certainly ways to do this. Most of them involve statistics. –  Thomas Andrews Jan 9 '13 at 21:15
    
I recently saw a lovely article that described an algorithm that took in a stream of objects and gave a good estimate of the number of distinct objects without keeping track of all objects received. It was a very cute statistical trick. It doesn't quite satisfy your condition, since it reads the entire stream. –  Thomas Andrews Jan 9 '13 at 21:22
    
@Thomas link, please? –  Mr.Wizard Jan 9 '13 at 22:49
    
Yeah, I'm waiting for an email back from a former coworker on the link. Sorry, I only saw the printout on his desk and read through it. It was relatively simple, actually. –  Thomas Andrews Jan 9 '13 at 22:51
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.