Skip to content

Latest commit

 

History

History
32 lines (25 loc) · 1.3 KB

README.md

File metadata and controls

32 lines (25 loc) · 1.3 KB

Story of the Agreeable Bird

Conditions

  • Two birds are said to "agree" on an input if both respond to that input with the same output
  • A bird is "agreeable" if for every other bird, there is at least one input on which the two agree
  • We're given the conditions of problem 1 (composition holds), but rather than a Mockingbird, the forest holds at least one agreeable bird

Problem

Can we still show that every bird is fond of at least one bird?

(Bonus: How is problem 1 nothing more than a special case of this problem? Is the Mockingbird agreeable?)

Solution

We known there's at least one agreeable bird present; call it A. Under the composition condition, we can compose any arbitrary bird x with A:

const composed = compose(x, A);

Because A is agreeable, we know there is some bird (call it y) on which A and composed agree.

A(y) === composed(y);

Unpacking the composition, we can restate that as:

A(y) === x(A(y));

Thus, bird x is fond of A(y).

Notes

The Mockingbird (x => x(x)) is agreeable, because for any bird x, it agrees with x on x itself. So, because the Mockingbird is one of many possible agreeable birds, the conditions of problem 3 include those of problem 1, making it just a special case.

Next =>