# Fundamentals of Formalisation Level 3: Set Theoretic Relations and Enumerability

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.