Approximate the size of a set given random items from the set. I'd like to know how would it be possible to approximate the size of a set that has no duplicate elements.
We can make a limited amount of requests. Each request gives us a random element from the set (Without removing it).
How do we approximate the size of the set given the amount of duplicate elements gotten from the set when doing $x$ requests?
 A: There are "capture/recapture" techniques that are generally used in ecological studies (population of birds, or what have you), but those approaches are subtly different than what you are proposing (since your "recapture" set is not predefined).
From a maximum likelihood perspective, as long as you have at least one duplicate value, then you would estimate the number of elements in the set $N$ as the number of unique values in your sample ($\hat N$). To infer any more than $\hat N$ would make your sample less likely, and to infer less than $\hat N$ would make your sample impossible. However, this approach will have a negative bias, since it will, on average, underestimate the actual N. Of course, it is asymptotically unbiased, so larger samples will yield less biased estimates.
Another approach is the counting approach:
If you sample $M$ times, then there are $N^M$ possible samples. Now, if you only sample $U<M$ unique values, so there are $D=M-U$ duplicate values, then there are only ${M\choose D}U!$ ways to create a sample of size $M$ with these particular $U$ unique values. However, there are a total of ${N \choose U}$ ways to select these $U$ unique values from the original set $N$. Therefore, the probability you observe $D$ duplicates by sampling $M$ times from a set of size $N$ is:
$${N\choose U}{M \choose D} \frac{U!}{N^M}$$
Your task is then to find the value of $N$ that maximizes this probability. This will be the maximum likelihood estimate of $N$, and will likely be biased for small samples as well. 
