TRUE and FALSE

TRUE = lambda x.lambda y.x, FALSE = lambda x.lambda y.y. Something From Nothing.

8 topics • ~925 words

The compositor has been setting type for weeks. Sticks with blanks, type pieces pressed in, results examined and set aside. One morning, reaching for a familiar composing stick -- two blanks, body uses only the first -- the compositor stops.

"This stick always keeps the first type piece and discards the second. That's... choosing. That's a decision. I didn't build a selector. I found one already living in a pattern I've had since the first lesson."

And the other stick -- the one whose body uses only the second blank -- it always discards the first and keeps the second.

One selects the first. One selects the second. We call them TRUE and FALSE.

We didn't design truth. We noticed that a pattern we already had behaves like truth.

For four topics, patterns were just patterns. Lambda terms substituted, reduced, sometimes diverged -- but never meant anything. There were no booleans, no numbers, no data of any kind. The system was purely mechanical: sticks rearranging type pieces.

Now something changes. Not because we add a new rule -- there are no more rules to add. But because we look at a pattern we already have and recognize what it does.

The Revelation

Consider two lambda terms we have already seen:

  • λx.λy.x -- takes two arguments, returns the first
  • λx.λy.y -- takes two arguments, returns the second

These are pure selectors. Given two choices, one always picks the first; the other always picks the second. That behavior -- selecting between two alternatives -- is exactly what a boolean does.

We define:

  • TRUE = λx.λy.x
  • FALSE = λx.λy.y

No new syntax. No new rules. These are ordinary lambda terms that we have been reducing since Topic 03. The only thing new is the name.

TRUE Definition

The selector stick that keeps the first type piece. Hand it two pieces and the first one stays; the second is discarded. Every time, without exception.

TRUE is defined as λx.λy.x.

Given two arguments, TRUE returns the first and discards the second:

TRUE a b = (λx.λy.x) a b →β a

This is the same curried function we reduced in Topic 03. The only difference is that we now recognize its selecting behavior and give it a name.

FALSE Definition

The other selector stick. Hand it two type pieces and the first one is discarded; the second stays. The mirror image of TRUE.

FALSE is defined as λx.λy.y.

Given two arguments, FALSE discards the first and returns the second:

FALSE a b = (λx.λy.y) a b →β b

Compare with TRUE (λx.λy.x), which returns the first. The only difference is which parameter appears in the body: x for TRUE, y for FALSE.

TRUE Applied

Two rounds of setting type with the first-selector stick. First round fills the x blank. Second round finds no y in the body. The first type piece remains; the second is discarded.

TRUE = λx.λy.x. Applying it to two arguments:

Step 1: (λx.λy.x) a →β λy.a

Step 2: (λy.a) b →β a

The first argument a is selected. The second argument b is discarded because y does not appear in the body after the first substitution.

FALSE Applied

Two rounds with the second-selector stick. First round fills the x blank -- but x is not in the body, so the first piece vanishes. Second round fills y. The second type piece is all that remains.

FALSE = λx.λy.y. Applying it to two arguments:

Step 1: (λx.λy.y) a →β λy.y (no x in body, a is discarded)

Step 2: (λy.y) b →β b

The first argument a is discarded. The second argument b is selected. Note that after step 1, the result λy.y is the identity function.

Why Selectors

In most languages, booleans and conditionals are separate:

  • A boolean is a value (true or false)
  • A conditional is a control structure (if-then-else)

Church booleans unify the two. TRUE and FALSE are not passive values waiting to be inspected -- they are active selectors that perform the choice. TRUE selects the first option; FALSE selects the second.

The boolean doesn't describe a choice. It IS the choice.

Not Magic

TRUE = λx.λy.x and FALSE = λx.λy.y are not special constructs. They are ordinary lambda terms -- the same kind of expressions we have been reducing since Topic 00. They follow the same rules as every other term: substitution, beta reduction, nothing else.

The names TRUE and FALSE are labels we chose. The lambda calculus itself has no notion of "boolean." What makes these terms act like booleans is purely their behavior: when applied to two arguments, they select one and discard the other.

Booleans Are Functions

In Church encoding, a boolean is not a value that gets inspected. It is a function that performs selection.

  • TRUE = λx.λy.x -- a function that takes two arguments and returns the first
  • FALSE = λx.λy.y -- a function that takes two arguments and returns the second

There is no separate mechanism that looks at a boolean and decides what to do. The boolean itself is the decision-maker. Apply it to two choices and it picks one.

In lambda calculus, everything is a function -- and booleans are no exception.

Ready to test your understanding?

Bitwit uses spaced repetition to help you truly master concepts like this—not just read about them. Each card generates with different values, so you can't just memorize answers.

Practice TRUE and FALSE →