BIT predicate

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

History[edit]

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

Each natural number encodes a finite set and each finite set is represented by a natural number. This mapping uses the binary numeral system. If the number n encodes a finite set A and the ith binary digit of n is 1 then the set encoded by i is element of A. The Ackermann coding is a primitive recursive function.[3]

Implementation[edit]

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 retrieval[edit]

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 logic[edit]

The BIT predicate is often examined in the context of first-order logic, where we can examine the system resulting 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[edit]

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[edit]

  1. ^ Ackermann, Wilhelm (1937). "Die Widerspruchsfreiheit der allgemeinen Mengenlehre". Mathematische Annalen 114: 305–315. doi:10.1007/bf01594179. 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. Retrieved 31 May 2011. 
  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. .
  6. ^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. ISBN 0-387-98600-6. 
  7. ^ Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. pp. 14–16. ISBN 0-387-98600-6. 
  8. ^ Rado, Richard (1964). "Universal graphs and universal functions". Acta Arith. 9: 331–340. .