# lazy counting - failing to check equivalence classes are distinct

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?

-
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