BIT predicate

In mathematics and computer science, the BIT predicate or Ackermann coding, sometimes written BIT(i, j), is a predicate that tests whether the jth bit of the number i is 1, when i is written in binary.

History[]

The BIT predicate was first introduced as the encoding of hereditarily finite sets as natural numbers by Wilhelm Ackermann in his 1937 paper The Consistency of General Set Theory.^[1][2]

In this encoding, each natural number encodes a finite set, and each finite set is represented by a natural number. If the encoding of a set ${\displaystyle X}$ is denoted ${\displaystyle \eta (X)}$, then this encoding is defined recursively by

In terms of the binary numeral system, if the number ${\displaystyle n=\eta (X)}$ encodes a finite set ${\displaystyle X}$ and the ${\displaystyle i}$th binary digit of ${\displaystyle n}$ is 1, then the set ${\displaystyle \eta ^{-1}(i)}$ encoded by ${\displaystyle i}$ is an element of ${\displaystyle X}$. Therefore, the BIT predicate of numbers directly corresponds under this encoding to the membership relation between hereditarily finite sets.

The Ackermann coding is a primitive recursive function.^[3]

Implementation[]

In programming languages such as C, C++, Java, or Python that provide a right shift operator >> and a bitwise Boolean and operator &, the BIT predicate BIT(i, j) can be implemented by the expression (i>>j)&1. Here the bits of i are numbered from the low-order bits to high-order bits in the binary representation of i, with the ones bit being numbered as bit 0.^[4]

Private information retrieval[]

In the mathematical study of computer security, the private information retrieval problem can be modeled as one in which a client, communicating with a collection of servers that store a binary number i, wishes to determine the result of a BIT predicate BIT(i, j) without divulging the value of j to the servers. Chor et al. (1998) describe a method for replicating i across two servers in such a way that the client can solve the private information retrieval problem using a substantially smaller amount of communication than would be necessary to recover the complete value of i.^[5]

Mathematical logic[]

The BIT predicate is often examined in the context of first-order logic, where systems of logic result from adding the BIT predicate to first-order logic. In descriptive complexity, the complexity class FO + BIT resulting from adding the BIT predicate to FO results in a more robust complexity class.^[6] The class FO + BIT, of first-order logic with the BIT predicate, is the same as the class FO + PLUS + TIMES, of first-order logic with addition and multiplication predicates.^[7]

Construction of the Rado graph[]

Ackermann in 1937 and Richard Rado in 1964 used this predicate to construct the infinite Rado graph. In their construction, the vertices of this graph correspond to the non-negative integers, written in binary, and there is an undirected edge from vertex i to vertex j, for i < j, when BIT(j,i) is nonzero.^[8]

References[]