Fundamentals of Formalisation Level 7: Equivalence Relations and Orderings



Followup to Fundamentals of Formalisation Level 6: Turing Machines and the Halting Problem. First post.

This is a new lesson of our online course on math formalizations required for AI safety research.

The big ideas:

  • Equivalence Relations
  • Partitions
  • Orderings

To move to the next level you need to be able to:

  • Explain the relationship between equivalence relations and partitions.
  • Name two different kinds of orderings and the conditions on the ordering relations required for these kinds.

Why this is important:

  • This level is about further building up your mathematical toolbox. While equivalence relations and orderings currently seem like random abstract notions, they are both very important. The former gives you a way to instantiate different notions of equality, which is important in modeling. The latter appears in constructing models for another turing machine equivalent notion of computability, the lambda calculus.

For every lesson you have 2 options: do the whole thing, or skip to the questions and exercises in the end. The latter option is for people who suspect they already know the subject. It serves as a means of verifying or falsifying that hypothesis.