Ackermann coding

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

In Set theory Ackermann coding (or Ackermann interpretation) is the encoding of finite sets as natural numbers as devised 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]

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.