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$?