Lower bounds for space with some probability of error There is an  information theoretic lower bound of $\log_2 {U \choose x}$  for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$.  We can in principle use this representation (perhaps inefficiently) as a data structure to test if any query is part of this subset.  

How can you show a similar information theoretic lower bound if we are happy to have false positives with some probability $p$?
In "Network applications of Bloom filters: A survey", Broder and Mitzenmacher show an $x \log_2 (1/p)$ lower bound on the space usage.