These are my markdown notes for an in-progress project (see below sections for details). I've found that I learn best by grouping information into small sequential chunks, and writing it as if it's an explainer (except the goal is for me to understand by writing it and the audience is an afterthought, so I might skip some stuff I don't feel like writing out) published directly from my Obsidian vault (hence the [[links]].) I found that, when learning about philosophy, anchoring myself in time and tracing the development of ideas over its course helped me [[Conceptual organization|conceptually organize]] the material and avoid getting stressed over the sheer volume of information I wanted to consume.

Note: I defined a bijection symbol using code from stack overflow as follows:

\newcommand{\twoheadrightarrowtail}\mathrel{\mathrlap{\rightarrowtail}}\mathrel{\mkern2mu\twoheadrightarrow}

Looks like:

$\newcommand{\twoheadrightarrowtail}\mathrel{\mathrlap{\rightarrowtail}}\mathrel{\mkern2mu\twoheadrightarrow}$

Godel, Tarski, and Hilbert

The foundations of mathematics

Goal of this presentation: get myself acquainted with the through line between Hilbert, Godel, Tarski, Church, Turing. All these interesting formalization things.

The local/temporary goal is to figure out Godel's incompleteness theorems in detail.

Where do we start?

It's hard to get anchored in math

I'll go high-level and then go into more detail.

Broad Strokes

High-level ideas, stuff I sort of get before starting

• Cantor introduces set theory

• Set theory is kinda cool

• Uh oh, Russell's paradox

• Zermelo: axiom of choice

• Russell and Whitehead try to formalize everything with Principia Mathematica

• Hilbert says we should formalize everything; 23 unsolved problems

• Intuitionism vs. Formalism? <— I don't understand this

• Godel publishes incompleteness theorems; lots of other cool stuff like tarski and Church/Turing

• Then we re-evaluate and we get ZFC

Other related concepts I'd like to think about:

• Church-Turing thesis

• Lambda calculus

• This connects into Wittgenstein tractatus, cool

Euclid and the parallel postulate

• Begins with [[Euclid]], geometry -- the notion of proof.

• Euclid has 5 postulates.

• [[Parallel postulate]]: An essential part of geometry as we think of it conventionally -- but if we don't accept it, we get [[Non-euclidean geometry]], geometric systems that are formally consistent despite not representing physical space in the conventional way we might perceive it.

Intuition and formality

• A parallel current going on: the need for formalization

• Before Cantor, math mostly deals with concrete, mathematical objects, and intuitions. Distinct disciplines.

  • Take a look at, e.g. islamic mathematicians, Euclid, etc. — proofs are like paragraphs, no symbolic notation
  • [[Newton]] and [[Leibniz]] developed calculus, but didn't really formalize it — e.g. used the notion of the infinitesimal. It worked, but wasn't formal. Hence, mathematicians wanted a formal notion of it.

• There's a need to formalize [[infinity]]. Ideas about infinite series, functions, limits, etc. could have paradoxes.

• Also, how do we unify math?

[[Georg Cantor]] introduces [[Set theory]]

• In a single paper — "On a Property of the Collection of All Real Algebraic Numbers" — Cantor introduced set theory.

  - *To be studied later: set theory as the [[formalization]] — the giving of notation — to notions of… idk, [[concepts]]? Categories?

• [[Sets]] can contain any kind of object — sets, numbers, etc.

  • Potential to unify all the different [[branches of mathematics]]

• Can deal with infinity — different notions of infinity, etc.

• Why is this cool?

Key ideas in set theory: Set and Subset

• [[Set]]: A collection of distinct objects.

  • E.g. $A = {1, 2, 3}$

• [[Subset]]: Set B is a subset of A if every element contained in B is also in A.

  • $B = {2, 3}$, therefore $B \subset A$
  • $B = {4, 5}$, therefore $B \not\subset A$
  • Not like a folder/hierarchy kind of thing. It's not that Set A contains only Set B, and set B contains the elements; There's no hierarchy to sets. You're just selecting pieces of them.

Key ideas in set theory: Power Sets

• The [[power set]] of set $A$, written as $\mathcal{P}(A)$ , is the set of all possible subsets of $A$, including $A$ itself and the empty set (the set containing no elements, often denoted as $\varnothing$ ).

  • For example, given that $A = {0, 1, 2},$ we can say that $\mathcal{P}(A) = {\varnothing, {0}, {1}, {2}, {0, 1}, {1, 2}, {0, 2}, {0, 1, 2}}$

• Think of this as all possible ways to group the elements in set A: to make each subset you're allowed to take any number of items from A, however you choose. (You can't add extra elements, though.)

Keys to Set Theory: Cardinality

• [[Cardinality]]: How many elements are in a set

  • $A = {1, 2, 3}$, therefore $|A| = 3$

• Cardinality will be an integer if the set is finite.

• If the set is infinite, it gets more complicated.

• Cardinality is also related to the notion of [[isomorphism]], correspondence, etc. I'll get there in a sec. For now we need to talk a little about how set theory let us deal with infinity.

Cool sidebar: Cardinality of the Power Set

• A cool thing to note: the cardinality of $\mathcal{P}(A)$ will always be equal to $2^{|A|}$. This is [[Cantor's theorem]], which we'll see in a moment.

  • This seems unintuitive at first, but if you think about it, it makes sense; there are $|A|$ elements, and for each subset, each element in $A$ can either be included or not included. (It's a binary choice.)
  • If you imagine it as a binary tree, the $2^{|A|}$ number makes a lot of sense intuitively.

Interlude: Number systems

• One of the cool things that set theory lets us do is talk about different kinds of infinity.

• First, a quick review of "kinds of ":

  • The [[natural numbers]], $\mathbb{N}$, are the numbers that we count with "naturally" — they're basically the most basic idea of numbers.

    • You can list them out in order: $\mathbb{N} = {1, 2, 3, 4, 5 ...}$

  • The [[integers]], $\mathbb{Z}$ (just by convention I guess), are all the whole numbers. They stretch out on both sides of 0: $\mathbb{z} = {... -3, -2, -1, 0, 1, 2, 3, ...}$

  • The [[real numbers]], $\mathbb{R}$, are all the numbers that we might normally talk about. This contains all the natural numbers, 0, fractions, infinite decimals, etc.

    • Any normal "number" you might operate with in reality is a real number.
    • You can't list out the real numbers in order — where do you start? 0? then what? 0.1, or 0.001, or 0.0000000001? or 1?

  • (see more at Varsity Tutors)

Interlude: Bijections

• We need one more key idea to start talking about infinite cardinality: relationships between elements in sets — a special kind of correspondence called a [[Bijection]], also known as a "one-to-one correspondence."

  • Set $A$ has a bijection with Set $B$ if each element in $A$ has a corresponding element in set $B$.
  • Imagine we take a random element in set $A$. Now let's take a random element in $B$, and draw a line between the two.
  • Keep drawing lines until we can't draw any more lines. If there are no elements left un-connected in either set, there's a bijection between them; if there are elements left over that don't have a pair, they're not bijective.

• If you're curious about the formal way we talk about bijection, we have to define it as a function that maps one set onto another: We define a function $f$ that maps (mapping is just the formal way to talk about drawing lines) set $A$ onto set $B$ as follows: $f : A \rightarrow B$ The function $f$ is bijective if $\forall b \in B$ — "for all elements (labeled $b$) in the set B" — $\exists ! a \in A$ — "there exists exactly one element in A" — such that $f(a) = b$ ("if you put $a$ into $f$, you get an element $b$ as an output").

• How this relates to cardinality: if two sets are bijective, they must have the same cardinality. If they have the same cardinality, they must be bijective.

  • Why? Think about it — same number of elements in each guarantees that you'll be able to draw an arrow between the two.

• There are more kinds of -jections (injection, surjection) which we'll get to later. For now, we'll leave this idea of Bijection cause it's intuitive.

Key ideas in set theory: Infinite cardinality

• There are lots of different kinds of infinity.

• One easy distinction between kinds of infinity is where we talk about countable and uncountable infinity.

  • We talked about this earlier with the naturals and the reals ($\mathbb{N}$ and $\mathbb{R}$) — you can count out the naturals. Start at 1, just keep going.
  • Versus with $\mathbb{R}$, we don't know where to go next — there's no sense of order.

• Formally, we actually use $\mathbb{N}$ in some of our definitions.

• The simplest kind of infinite cardinality is countable infinity: there's no limit to the amount of elements in the set, but you can list them out in some meaningful order.

  • A set is countably infinite if we can draw a bijection between it and the natural numbers: $ A \newcommand{\twoheadrightarrowtail}\mathrel{\mathrlap{\rightarrowtail}}\mathrel{\mkern2mu\twoheadrightarrow} \mathbb{N}$
  • We denote the cardinality of $\mathbb{N}$ as $\aleph0$ ("[[aleph null]]", a [[hebrew]] [[letter]] — don't ask me why, maybe they just used it cause it looks like N lol). I.e. $|\mathbb{N}| = \aleph0$ A nicer way to say that there's a bijection between $A$ and $\mathbb{N}$ is to talk about it in terms of cardinality of N: $|A| = \aleph_0$
  • You can think about this also as "numbering" all the elements in $A$. If they have a bijective relationship, that means you could give a number to each element in $A$; e.g. you could select an element in $A$ and number it 1, then choose a different element in a and call it number 2, and continue on in this fashion infinitely.

  • The key idea here is that there must be a systematic way, some sort of [[algorithm]] to do this — you can't just select random elements, otherwise $\mathbb{R}$ would have cardinality $\aleph_0$, which would make the concept useless and defeat the point of distinguishing countable and uncountable infinity.

    • For example, we can prove that $\mathbb{Z}$ (the [[integers]], if you remember) is countably infinite because there's an algorithm that maps every element in $\mathbb{Z}$ onto another element in $\mathbb{N}$.
    • One way to do this is using odd and even: zero maps onto zero, then each negative number in $\mathbb{Z}$ maps onto each odd number in $\mathbb{N}$ (e.g. $-1 \rightarrow 1$, then -$2 \rightarrow 3$, then $-3 \rightarrow 5$, and $-4 \rightarrow 7$, etc.) and each positive number maps onto each even number ($1 \rightarrow 2$, then $2 \rightarrow 4$, then $4 \rightarrow 6$, etc.)

  • Hopefully this idea of map $A$ onto $\mathbb{N}$ makes sense, but if not I don't think it's essential.

• It seems intuitive that $|\mathbb{R}| > \aleph_0$ — there's some idea of, like, "bigger-ness" in the real numbers. There's just more of them, they don't really make sense, you can't map them onto $\mathbb{N}$. But how do we prove this?

Key results in early set theory: [[Cantor's diagonalization proof]]

• Cantor came up with a cool method in order to prove that $|\mathbb{R}| \not = \aleph_0$, called [[Diagonalization]]. Diagonalization [[generalization|generalizes]] in all sorts of cool ways, but for now I'm going to give you just this one argument.

• Let's assume for a moment that $|\mathbb{R}| = \aleph_0$ . This means that we can write out all the elements in $\mathbb{R}$ in an ordered list.

• For simplicity, we'll look at just a subset of $\mathbb{R}$: we'll use the numbers between 0 and 1 — if these numbers aren't countable, then since they're a subset of $\mathbb{R}$, $\mathbb{R}$ isn't countable either.

• (For finite decimals we'll just add add 0s on the end to make them the same length as our infinite decimals.)

• I'm going to use just some random numbers for illustration:

| Index | Number | | | | | | |

| ------- | ------ | --- | --- | --- | --- | --- | --- |

| 1 | 0. | 1 | 0 | 0 | 0 | 0 | ... |

| 2 | 0. | 7 | 7 | 7 | 7 | 7 | ... |

| 3 | 0. | 7 | 1 | 8 | 2 | 8 | ... |

| 4 | 0. | 1 | 0 | 2 | 0 | 1 | ... |

| 5 | 0. | 9 | 9 | 0 | 0 | 0 | ... |

| 6 | 0. | 3 | 9 | 8 | 4 | 6 | ... |

| ... | ... | ... | ... | ... | ... | ... | |

(Using a markdown table is hard for this visually, sorry, so feel free to watch this video version created by Trefor Bazett or just search "diagonalization argument demonstration" or something like that online. I'm sure that there are plenty of other representations out there, this is just one that works well enough and which I found within like 5 minutes of searching.)

• Let's assume that we have every single possible number in this list.

• If we can come up with a new number that isn't in our list somehow, we prove that there would be a logical contradiction created if $\mathbb{R}$ were countable, and therefore that it cannot be countable.

• Turns out, there is a way. Let's do something clever. Let's select the digits going diagonally down the list, i.e. the 1st digit of the 1st number, 2nd digit of the 2nd number, etc. going down the whole list (so that there is a digit selected from every single number in the list)

| Index | Number | | | | | | |

| ------- | ------ | --- | --- | --- | --- | --- | --- |

| 1 | 0. | [1] | 0 | 0 | 0 | 0 | ... |

| 2 | 0. | 7 | [7] | 7 | 7 | 7 | ... |

| 3 | 0. | 7 | 1 | [8] | 2 | 8 | ... |

| 4 | 0. | 1 | 0 | 2 | [0] | 1 | ... |

| 5 | 0. | 9 | 9 | 0 | 0 | [0] | ... |

| 6 | 0. | 3 | 9 | 8 | 4 | 6 | ... |

| ... | ... | ... | ... | ... | ... | ... | |

• And let's add 1 to each value, turning 1 into 2, 5 into 6, and 9 into 0 (just rolling over instead of turning into 10).

| Index | Number | | | | | | |

| ------- | ------ | --- | --- | --- | --- | --- | --- |

| 1 | 0. | [2] | 0 | 0 | 0 | 0 | ... |

| 2 | 0. | 7 | [8] | 7 | 7 | 7 | ... |

| 3 | 0. | 7 | 1 | [9] | 2 | 8 | ... |

| 4 | 0. | 1 | 0 | 2 | [1] | 1 | ... |

| 5 | 0. | 9 | 9 | 0 | 0 | [1] | ... |

| 6 | 0. | 3 | 9 | 8 | 4 | 6 | ... |

| ... | ... | ... | ... | ... | ... | ... | |

• There's our new number, 0.28911...

• And guess what? It can't be in the list already. Why? Because it is guaranteed to have at least 1 place value different from every single number in the list, since we generated it by taking a digit from every number from the list and adding 1 to the digit.

• Its 1st digit is different from the first number on the list, 2nd digit different from the 2nd, 3rd different from the 3rd, et cetera.

• Hence, we've created a contradiction. We said we had all the real numbers between 0 and 1 in our countable list, but then turned out that no matter how we list the numbers, we can always come up with a number that's not in our list. Turns out our list isn't countable after all.

• Since our premise that $|\mathbb{R}| = \aleph0$ led to a contradiction, our premise must be false; therefore $|\mathbb{R}| \not= \aleph0$ $\blacksquare$

• This will reappear in all sorts of ways down the line, in everything from [[Russell's paradox]] to [[Godel's Incompleteness Theorems]] to [[Alan Turing]]'s [[Halting problem]]. Diagonalization gets really abstract, though, so I think the best way to get to that abstraction is through seeing a bunch of examples, and then coming back and figuring out what they all have in common. So for now, we'll leave diagonalization. :)

Key results in early set theory: Cantor's theorem

• Actually I don't have this in me right now, but I'll cover it when we talk about diagonalization more later.

• This video looks pretty interesting. #to-consume