Fundamentals of Formalisation Level 3: Set Theoretic Relations and Enumerability

Fol­lowup to Fun­da­men­tals of For­mal­i­sa­tion level 2: Ba­sic Set The­ory.

The big ideas:

  • Ordered Pairs

  • Relations

  • Functions

  • Enumerability

  • Diagonalization

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

  • Define func­tions in terms of re­la­tions, re­la­tions in terms of or­dered pairs, and or­dered pairs in terms of sets.

  • Define what a one-to-one (or in­jec­tive) and onto (or sur­jec­tive) func­tion is. A func­tion that is both is called a one-to-one cor­re­spon­dence (or bi­jec­tive).

  • Prove a func­tion is one-to-one and/​or onto.

  • Ex­plain the differ­ence be­tween an enu­mer­able and a non-enu­mer­able set.

Why this is im­por­tant:

  • Estab­lish­ing that a func­tion is one-to-one and/​or onto will be im­por­tant in a myr­iad of cir­cum­stances, in­clud­ing proofs that two sets are of the same size, and is needed in es­tab­lish­ing (most) iso­mor­phisms.

  • Di­ag­o­nal­iza­tion is of­ten used to prove non-enu­mer­abil­ity of a set and also it sketches out the bound­aries of what is log­i­cally pos­si­ble.

You can find the les­son in our ihat­es­tatis­tics course. Good luck!

P.S. From now on I will post­ing these an­nounce­ments in­stead of Toon Alfrink.