BIT predicate

Summary

In mathematics and computer science, the BIT predicate, sometimes written $\text{BIT}(i,j)$, is a predicate that tests whether the $j$th bit of the number $i$ (starting from the least significant bit) is 1, when $i$ is written as a binary number. Its mathematical applications include modeling the membership relation of hereditarily finite sets, and defining the adjacency relation of the Rado graph. In computer science, it is used for efficient representations of set data structures using bit vectors, in defining the private information retrieval problem from communication complexity, and in descriptive complexity theory to formulate logical descriptions of complexity classes.