# Church encoding

A Church encoding is a way of representing data values, such as booleans and natural numbers, purely as functions in the lambda calculus, a formalism that has no primitive data types at all. The method is named for [Alonzo Church](https://www.edgepedia.org/alonzo-church), the logician who invented the lambda calculus in the 1930s and devised the encodings of the natural numbers now called Church numerals.<sup>[1](https://kahsolt.github.io/downloads/pdf/Lecture%20Notes%20on%20the%20Lambda%20Calculus%20-%20Peter%20Selinger.pdf)</sup><sup> • </sup><sup>[2](https://www.cs.cornell.edu/courses/cs212/2000sp/notes/lectures/l26-lambda.htm)</sup>

| Key fact | Detail |
|---|---|
| Core idea | Data is represented as its own eliminator: a datum is the function that uses it, so a boolean is a chooser and a numeral is an iterator<sup>[3](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)</sup> |
| Church numerals | The numeral \( n \) is \( \lambda f.\,\lambda x.\, f^{n}\,x \), a function that applies \( f \) exactly \( n \) times to \( x \)<sup>[1](https://kahsolt.github.io/downloads/pdf/Lecture%20Notes%20on%20the%20Lambda%20Calculus%20-%20Peter%20Selinger.pdf)</sup> |
| Church booleans | true = \( \lambda x.\,\lambda y.\,x \) and false = \( \lambda x.\,\lambda y.\,y \); applying a boolean to two arguments selects one of them<sup>[4](https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/ChurchNumerals.html)</sup> |
| Arithmetic | succ = \( \lambda nfx.\,f(nfx) \); add = \( \lambda nmfx.\,nf(mfx) \); mult = \( \lambda nmf.\,n(mf) \)<sup>[1](https://kahsolt.github.io/downloads/pdf/Lecture%20Notes%20on%20the%20Lambda%20Calculus%20-%20Peter%20Selinger.pdf)</sup> |
| Predecessor | Found by Stephen Kleene after Church believed it undefinable; it carries a shifting pair \((a,b) \mapsto (b, b+1)\) through \( n \) iterations<sup>[3](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)</sup> |
| Typed setting | In System F the encodings become universal data types, for example Bool = ∀α. α → α → α<sup>[5](https://notes.camadkins.com/cs/pl/lambda-calculus-encodings-booleans-pairs-church-numerals)</sup> |
| Alternative | The Scott encoding represents data by its case analysis instead of its fold and has a constant-time predecessor<sup>[6](https://www.funcp.org/wiki/church-encoding)</sup> |

## Why encode data as functions

The pure lambda calculus contains only one kind of entity: functions, built from variable abstraction and application. To use it as a model of computation, one must still be able to manipulate boolean constants, logical operators, conditionals, integers, and arithmetic, none of which exist as primitives.<sup>[4](https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/ChurchNumerals.html)</sup> Church's solution was to define each kind of data by what can be done with it. The guiding idea is data as its own eliminator: a datum is the function that consumes it.<sup>[3](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)</sup>

This works because the calculus is computationally universal: any computable function can be expressed and evaluated in it, and it is equivalent in power to Turing machines.<sup>[7](https://arxiv.org/abs/1503.09060)</sup>

## Church booleans

A boolean's only job is to choose between two alternatives, so a boolean is a two-argument function that returns one of them:

\[ \mathtt{true} = \lambda t.\,\lambda f.\,t, \qquad \mathtt{false} = \lambda t.\,\lambda f.\,f, \qquad \mathtt{if} = \lambda b.\,\lambda t.\,\lambda e.\,b\,t\,e. \]

Then \( \mathtt{if}\ \mathtt{true}\ a\ b \) reduces to \( a \) and \( \mathtt{if}\ \mathtt{false}\ a\ b \) reduces to \( b \): the boolean itself performs the branch selection, so no separate conditional construct is needed.<sup>[3](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)</sup> The logical connectives follow directly. For example AND = \( \lambda p.\,\lambda q.\,p\,q\,\mathtt{false} \), and TRUE AND FALSE β-reduces to FALSE as expected.<sup>[4](https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/ChurchNumerals.html)</sup> A pair can be viewed as a generalization of this choice: the boolean simply selects between its two arguments.<sup>[5](https://notes.camadkins.com/cs/pl/lambda-calculus-encodings-booleans-pairs-church-numerals)</sup>

## Church numerals

A Church numeral is an iterator. For each natural number \( n \), the numeral is

\[ \overline{n} = \lambda f.\,\lambda x.\, f^{n}\,x, \]

so that \( \overline{0} = \lambda fx.x \), \( \overline{1} = \lambda fx.fx \), \( \overline{2} = \lambda fx.f(fx) \), and so on: applied to a function \( f \) and a starting value \( x \), the numeral applies \( f \) exactly \( n \) times.<sup>[1](https://kahsolt.github.io/downloads/pdf/Lecture%20Notes%20on%20the%20Lambda%20Calculus%20-%20Peter%20Selinger.pdf)</sup> Church's own 1941 presentation began the sequence at 1; beginning at 0 is the now-common convention.<sup>[8](https://seop.illc.uva.nl/entries/church/supplementD.html)</sup>

Arithmetic falls out of iteration. The successor adds one more application,

\[ \mathtt{succ} = \lambda n.\,\lambda f.\,\lambda x.\, f\,(n\,f\,x), \]

and β-reduction confirms that \( \mathtt{succ}\ \overline{n} = \overline{n+1} \). Addition composes two iterations, \( \mathtt{add} = \lambda nmfx.\,nf(mfx) \), and multiplication iterates the iteration, \( \mathtt{mult} = \lambda nmf.\,n(mf) \).<sup>[1](https://kahsolt.github.io/downloads/pdf/Lecture%20Notes%20on%20the%20Lambda%20Calculus%20-%20Peter%20Selinger.pdf)</sup> Testing for zero uses the booleans: ISZERO = \( \lambda n.\,(n\,(\lambda x.\,\mathtt{false}))\ \mathtt{true} \), which returns true exactly when the numeral never applies its function.<sup>[4](https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/ChurchNumerals.html)</sup>

One ambiguity is worth noting: \( \overline{0} \) is the same term as the false boolean, so a program interpreting a result must know in advance whether to read it as a boolean or a numeral.<sup>[1](https://kahsolt.github.io/downloads/pdf/Lecture%20Notes%20on%20the%20Lambda%20Calculus%20-%20Peter%20Selinger.pdf)</sup>

## Predecessor: the hard case

Successor, addition, and multiplication all build the iterator up; the predecessor must peel one application off, and a Church numeral offers no direct handle on "one fewer application." Historically this was the crux: Church believed the predecessor was undefinable until his student Stephen Kleene found a construction, sometimes called the "wisdom-teeth trick."

Kleene's idea is to carry a shifting pair through the iteration: applying the transformation \((a,b) \mapsto (b,\,b+1)\) repeatedly to \((0,0)\) yields \((n-1,\,n)\) once it has been applied \( n \) times, and the first component then reads off as \( n-1 \). For \( n = 0 \) no step is taken, so the result is 0.<sup>[3](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)</sup> Written directly on Church-encoded pairs, the standard closed form is

\[ \mathtt{pred} = \lambda n.\,\lambda f.\,\lambda x.\, n\,(\lambda g.\,\lambda h.\,h\,(g\,f))\,(\lambda u.\,x)\,(\lambda u.\,u), \]

where \( \lambda g\,h.\,h\,(g\,f) \) is the pair-shift, and it satisfies \( \mathtt{pred}\ \overline{0} = \overline{0} \) and \( \mathtt{pred}\ \overline{n+1} = \overline{n} \).<sup>[3](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)</sup><sup> • </sup><sup>[4](https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/ChurchNumerals.html)</sup> [Subtraction](https://www.edgepedia.org/subtraction) is then repeated predecessor, truncated at zero, and comparison tests follow.<sup>[3](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)</sup>

## Pairs and recursion

A Church pair packages two values as a function awaiting a selector; in typed notation its shape is `type ChurchPair a b = (a -> b -> c) -> c`, with projections fst = \( \lambda p.\,p\,(\lambda a\,b.\,a) \) and snd = \( \lambda p.\,p\,(\lambda a\,b.\,b) \).<sup>[9](https://cs.pomona.edu/~michael/courses/csci131f15/lec/lec07.html)</sup> Pairs are what make the Kleene predecessor work, since the iteration must carry a "previous" value alongside the current one.<sup>[10](https://bnaskrecki.faculty.wmi.amu.edu.pl/lambda/notebooks/05_church_numerals.html)</sup>

The lambda calculus has no named functions and no built-in recursion, but recursion is still definable through the Y combinator,

\[ Y = \lambda f.\,(\lambda x.\,f\,(x\,x))\,(\lambda x.\,f\,(x\,x)), \]

which satisfies \( Y\,e =_\beta e\,(Y\,e) \), making \( Y \) a fixed-point combinator that lets a self-reference be regenerated at each step.<sup>[14](https://www.cl.cam.ac.uk/~mom22/fp/lec1-intro.pdf)</sup> With the encodings in place, a definition such as the factorial can be rewritten to use conditionals on Church booleans and arithmetic on Church numerals, then expressed with Y.<sup>[9](https://cs.pomona.edu/~michael/courses/csci131f15/lec/lec07.html)</sup>

## Typed encodings and alternatives

In a polymorphically typed setting such as [System F](https://www.edgepedia.org/system-f), the same encodings become universal data types: the type of Church booleans is \( \forall \alpha.\,\alpha \to \alpha \to \alpha \), and a numeral has the iterator type \( \forall \alpha.\,(\alpha \to \alpha) \to \alpha \to \alpha \). This connection is a foundation for typed functional programming.<sup>[5](https://notes.camadkins.com/cs/pl/lambda-calculus-encodings-booleans-pairs-church-numerals)</sup> In System F, Church encoding is the standard way to represent data types.<sup>[11](https://www.researchgate.net/publication/319361324_Parametric_quantifiers_for_dependent_type_theory)</sup>

The main alternative is the Scott encoding, which represents a value by its case analysis rather than its fold: each constructor becomes a function that invokes the corresponding branch of a case expression. Unlike Church numerals, the Scott encoding gives a constant-time predecessor, since the successor case directly exposes its argument.<sup>[6](https://www.funcp.org/wiki/church-encoding)</sup><sup> • </sup><sup>[12](https://theory.stanford.edu/~blynn/compiler/scott.html)</sup> The Church encoding has also been extended beyond two-valued logic: an encoding of McCarthy's three-valued logic exists in a suitable infinitary extension of the lambda calculus.<sup>[13](https://arxiv.org/abs/1810.07667)</sup>

## References

1. [Peter Selinger. Lecture Notes on the Lambda Calculus.](https://kahsolt.github.io/downloads/pdf/Lecture%20Notes%20on%20the%20Lambda%20Calculus%20-%20Peter%20Selinger.pdf)
2. [Cornell CS212, Lecture 26: Lambda Calculus.](https://www.cs.cornell.edu/courses/cs212/2000sp/notes/lectures/l26-lambda.htm)
3. [Lecture 2: Simple calculations with the Church λ-calculus, Automatic Theorem Proving in Mathematics.](https://bnaskrecki.faculty.wmi.amu.edu.pl/vietnam2026/book/lectures/l2_lambda_calculus.html)
4. [OpenDSA: Church Numerals and Booleans.](https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/ChurchNumerals.html)
5. [Lambda Calculus: Encodings of Booleans, Pairs, and Church Numerals.](https://notes.camadkins.com/cs/pl/lambda-calculus-encodings-booleans-pairs-church-numerals)
6. [The Functional Programmer wiki: Church encoding.](https://www.funcp.org/wiki/church-encoding)
7. [Raul Rojas. A Tutorial Introduction to the Lambda Calculus. arXiv:1503.09060.](https://arxiv.org/abs/1503.09060)
8. [Stanford Encyclopedia of Philosophy: Alonzo Church, Supplement D, The λ-Calculus and Type Theory.](https://seop.illc.uva.nl/entries/church/supplementD.html)
9. [CSCI 131, Pomona College: Church encodings, functions all the way down.](https://cs.pomona.edu/~michael/courses/csci131f15/lec/lec07.html)
10. [Church Numerals and Arithmetic, Lambda Calculus to Logic.](https://bnaskrecki.faculty.wmi.amu.edu.pl/lambda/notebooks/05_church_numerals.html)
11. [Parametric quantifiers for dependent type theory.](https://www.researchgate.net/publication/319361324_Parametric_quantifiers_for_dependent_type_theory)
12. [Ben Lynn. Compilers: The Scott encoding.](https://theory.stanford.edu/~blynn/compiler/scott.html)
13. [Encoding many-valued logic in λ-calculus. arXiv:1810.07667.](https://arxiv.org/abs/1810.07667)
14. [cl.cam.ac.uk](https://www.cl.cam.ac.uk/~mom22/fp/lec1-intro.pdf)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Logical calculi and logical syntax › Lambda calculus and type theory › Untyped lambda calculus*

*Initially written Sep 17, 2026 · Reviewed: Sep 17, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026; Oct 25, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license