How many different functions are there from Bool to Bool?

user_5825294 0
Viewed 195

Since this is (at least it seems to me) tightly related to programming, I'm asking here rather than on math or cs, but if you it think it best fits there or in another side, please just give your opinion.

At the end of Chapter 2 of Bartosz Milewski's Category Theory for Programmers, there's this question:

How many different functions are there from Bool to Bool? Can you implement them all?

This is my reasoning:

  • Bool has only two elements in it, True and False;
  • different refers to what the functions do if considered blackboxes, regardless of what happens within them (for instance, two functions coding the sum of two Ints as arg1 + arg2 and arg2 + arg1 respectively, would be the same function from Int to Int);
  • so the different functions are those going from one of the two Bools to another of the two Bools:
    1. T to T
    2. T to F
    3. F to T
    4. F to F
  • What functions do I need to make those in-out scenarii possible? Well, I think I need only two, for instance the identity function, which would allow 1 and 4, and the negation, which would allow 2 and 3.

Is my reasoning correct?

category-theory boolean-logic functional-programming
3 Answers

the different functions are those going from one of the two Bools to another of the two Bools

No. A function does map every value from its domain to one value from its codomain. You need to consider all possible combinations of mappings. For this, it might make sense to look at the function as a relation, and list them all:

  • f -> f, t -> f
  • f -> f, t -> t
  • f -> t, t -> f
  • f -> t, t -> t

These correspond to the 4 functions

  • x => f (constant false)
  • x => x (identity)
  • x => not(x) (negation)
  • x => t (constant true)
user_10485720

The fact that you asked on Programming, rather than math or CS, is important.

On Math, they'd tell you there are four such functions, listed by the other answers.

On CS, they'd tell you there are 27: one for each of three possible inputs T F and ⊥ to each of three possible outputs T F and ⊥.

Here in programming, I can tell you there are eleven:

  • (T->T, F->F, ⊥->⊥) identity
  • (T->F, F->T, ⊥->⊥) not
  • (T->T, F->T, ⊥->T) lazy constant true
  • (T->F, F->F, ⊥->F) lazy constant false
  • (T->T, F->T, ⊥->⊥) strict constant true
  • (T->F, F->F, ⊥->⊥) strict constant false
  • (T->⊥, F->F, ⊥->⊥) identity fail on true
  • (T->T, F->⊥, ⊥->⊥) identity fail on false
  • (T->⊥, F->T, ⊥->⊥) not fail on true
  • (T->F, F->⊥, ⊥->⊥) not fail on false
  • (T->⊥, F->⊥, ⊥->⊥) fail

(This answer is quite tongue-in-cheek: I think in reality most scholarly CS types would say either 4 or 11.)

user_43477300

There are four functions:

1

false -> false
true -> false

2

false -> false
true -> true

3

false -> true
true -> false

4

false -> true
true -> true

Explanation

Your reasoning is mostly correct. The functions are blackboxes, we view them as values. Since the input is a boolean and has two possible values and the function might have two separate values, basically the number if 2^2 = 4

user_4365600
Related