BIT predicate

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

HistoryEdit

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   is denoted  , then this encoding is defined recursively by

 
In terms of the binary numeral system, if the number   encodes a finite set   and the  th binary digit of   is 1, then the set   encoded by   is an element of  . 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]

ImplementationEdit

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(ij) 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 retrievalEdit

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(ij) 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 logicEdit

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 graphEdit

 
The Rado graph: for instance there is an edge from 0 to 3 because the 0th bit of 3 is non zero.

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]

ReferencesEdit

  1. ^ Ackermann, Wilhelm (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre". Mathematische Annalen. 114: 305–315. doi:10.1007/bf01594179. S2CID 120576556. Retrieved 2012-01-09.
  2. ^ Kirby, Laurence (2009). "Finitary Set Theory". Notre Dame Journal of Formal Logic. 50 (3): 227–244. doi:10.1215/00294527-2009-009.
  3. ^ Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic (3rd ed.). New York: Springer Science+Business Media. p. 261. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.
  4. ^ Venugopal, K. R. (1997). Mastering C++. Muhammadali Shaduli. p. 123. ISBN 9780074634547..
  5. ^ Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudan, Madhu (1998). "Private information retrieval". Journal of the ACM. 45 (6): 965–981. doi:10.1145/293347.293350. S2CID 544823..
  6. ^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6.
  7. ^ Immerman (1999, pp. 14–16)
  8. ^ Rado, Richard (1964). "Universal graphs and universal functions" (PDF). Acta Arith. 9 (4): 331–340. doi:10.4064/aa-9-4-331-340..