4 - Cardinality

Question 1

A function F is a mapping from the _______** to the **_______\_.

This means that a function F is a subset of the ______** **______\_ of these two sets.

Answer 1

A function F is a mapping from the domain** to the **codomain.

This means that a function F is a subset of the Cartesian Product of these two sets.

Question 2

Transfinite** **________** is a constructive technique which lets you build some math object, while **transfinite** **_______\_ is a proof technique which lets you then prove stuff about that math object.

Answer 2

Transfinite** **recursion** is a constructive technique which lets you build some math object, while **transfinite** **induction is a proof technique which lets you then prove stuff about that math object.

Question 3

Name the following transfinite method and explain it in layman’s terms:

If I have a map 𝐼:𝑋<𝛼→𝑋 (for 𝛼 some ordinal - here “𝑋<𝛼” denotes the set of maps from 𝛽 to 𝑋, for any 𝛽<𝛼),

then there is a unique function 𝑓:𝛼→𝑋 such that for all 𝛽<𝛼, 𝑓(𝛽) = 𝐼(𝑓↾𝛽).

Answer 3

Transfinite Recursion is a method for constructing sets.

If I have a map 𝐼:𝑋<𝛼→𝑋 (for 𝛼 some ordinal - here “𝑋<𝛼” denotes the set of maps from 𝛽 to 𝑋, for any 𝛽<𝛼),

then there is a unique function 𝑓:𝛼→𝑋 such that for all 𝛽<𝛼, 𝑓(𝛽) = 𝐼(𝑓↾𝛽).

• Note that we can conflate a set and its characteristic function, so even if you stick to this definition of transfinite recursion, it’s still meaningful to define a set 𝐴 via transfinite recursion. What you’re doing is recursively answering questions of the form, “Is 𝛽 in 𝐴?”*
• This is quite abstract on the face of it, but what it’s saying is not too complicated. We’re trying to build a function 𝛼→𝑋. Now, 𝐼 is a method for extending a partial function “one step further”:*
• if I feed 𝐼 a map 𝑝:𝛽→𝑋for some 𝛽<𝛼, 𝐼 tells me what 𝑓(𝛽)”ought” to be given that 𝑝=𝑓↾𝛽. That is, if I’ve defined 𝑓 for the first 𝛽-many inputs, 𝐼 tells me how to define 𝑓 for the next input.*
• This lets us “build 𝑓ffrom below”.*