#diagonalization

This is either going to be the first installment of a long running series or something I will never do again. (We'll see, don't know yet.)

Like the name suggests each iteration will showcase a theorem with its proof, all in one picture. I will provide preliminaries and definitions, as well as some execises so you can test your understanding. (Answers will be provided below the break.)

The goal is to ease people with some basic knowledge in mathematics into set theory, and its categorical approach specifically. While many of the theorems in this series will apply to topos theory in general, our main interest will be the topos Set. I will assume you are aware of the notations of commutative diagrams and some terminology. You will find each post to be very information dense, don't feel discouraged if you need some time on each diagram. When you have internalized everything mentioned in this post you have completed weeks worth of study from a variety of undergrad and grad courses. Try to work through the proof arrow by arrow, try out specific examples and it will become clear in retrospect.

Please feel free to submit your solutions and ask questions, I will try to clear up missunderstandings and it will help me designing further illustrations. (Of course you can just cheat, but where's the fun in that. Noone's here to judge you!)

Preliminaries and Definitions:

B^A is the exponential object, which contains all morphisms A→B. I comes equipped with the morphism eval. : A×(B^A)→B which can be thought of as evaluating an input-morphism pair (a,f)↦f(a).

The natural isomorphism curry sends a morphism X×A→B to the morphism X→B^A that partially evaluates it. (1×A≃A)

φ is just some morphism A→B^A.

Δ is the diagonal, which maps a↦(a,a).

1 is the terminal object, you can think of it as a single-point set.

We will start out with some introductory theorem, which many of you may already be familiar with. Here it is again, so you don't have to scroll all the way up:

Exercises:

What is the statement of the theorem?

Work through the proof, follow the arrows in the diagram, understand how it is composed.

What is the more popular name for this technique?

What are some applications of it? Work through those corollaries in the diagram.

Can the theorem be modified for epimorphisms? Why or why not?

For the advanced: What is the precise requirement on the category, such that we can perform this proof?

For the advanced: Can you alter the proof to lessen this requirement?

Bonus question: Can you see the Sicko face? Can you unsee it now?

Expand to see the solutions:

Doppelganger: A Trip into the Mirror World, Naomi Klein. New York: Farrar, Straus and Giroux, 2023. Summary: Naomi Klein, a liberal activist and writer finds herself being confused with another Naomi, once a feminist now become an anti-vax advocate and darling of the extreme right. Last summer, an anonymous pretender created a fake version of a social media page I curate, stealing a picture of…

A collection of objects or things is called a set. For example, we can put all of the cats in your neighborhood in a set, using their name to represent each one as an element of the set. This kind of set would be called a finite set, meaning that we can count every element (or cat!) in the set and eventually run out of cats to count. However, we can also have a set that doesn’t end, also called an infinite set. If we made our set of cats into an infinite set and tried to count it, we would be counting cats forever.

We can also say that a set is countable or uncountable. A set is countable if there is a 1-to-1 mapping from the set S to the Natural Numbers. We can demonstrate countability by representing elements from the set S with the natural numbers, which is also an infinite set. We can call both finite and infinite sets countable, but all uncountable sets are infinite. Infinite sets are countable when we can assign an element from the (infinite) natural number set to each element in the infinite set. But how do we show that an infinite set is uncountable?

Diagonalization is used to show that there are infinite sets that are uncountable, which means that the set does not have 1-1 matching with the set of natural numbers, which are infinite. This technique is famously known as Cantor’s Proof. 

Look at every line and row in this 8x8 grid above. If we take each “on” light to represent a 1 and each “off” light to represent a 0, we can see how this grid could be translated into binary. We can also imagine each row and column extends infinitely, like they would if we had a set of infinite bit-strings in an infinite set. All the strings shown in the grid of rows and columns are countable, even if they are infinite, since we can assign an element from the natural numbers to each of them.

When looking at our representation, we can see that there are bits that make up a diagonal through the center of the grid. These highlighted bits create a new bit-string that is different from the counted bit-strings, meaning it’s not represented in the rows or columns. (This is the same string that we see in the 1x8 grid next to the large grid.) Since we can see that we can find an uncounted string from an already counted infinite set, this means that the superset of this set is uncountable.