---
tag: 1VFCE6G5KA
kind: concept
name: BIT predicate
sources:
  - wikipedia: en:7639504@r1375441228
    locator: BIT predicate
    note: adopted
    mention: wikipedia://en/7639504
    sections: [Summary]
same_as:
  wikidata: Q4835745
  wikipedia: BIT predicate
inventory: [NV7Z7XZ8S8]
---

## 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.