#ordinal arithmetic

[jagernuke]

Ordinal Arithmetic II: Sets

okay so we did logic now we need actual stuff to do the logicking on. because you can't just do logic on nothing. it's like having a skeleton with no fat or muscle or skin like it's cool but it'd be way cooler if you had something to be a skeleton for

so let me introduce you to sets. let's just get all the obvious stuff out first: sets aren't lists. stop pretending that they are lists. you can have lists but sets are not lists. sets are:

unordered: doesn't matter how you sort it, it'll always be the same set. {a,b} = {b,a}

no multiplicity: doesn't matter how many times you repeat an element, that's the same as having it in there once. {a,a,a,a} = {a}

okay if we are clear on that let's actually get to notating sets properly. I'll also for now touch on some "basic sets" that we'll use for convenience to make the explanation easier. otherwise I'd have to start really abstractly and ion wanna do that:

ℕ is the set of natural numbers {0,1,2,3...}

ℤ is the set of integers {...-3,-2,-1,0,1,2,3...}

alright so we can first show sets as just their raw elements like I kinda did there. you usually enclose the raw elements of a set in braces. so like. let S = {1,2,3}. Then 1,2 and 3 are it's elements. you show this relationship with an ∈ symbol. so

1 ∈ S, 2 ∈ S, 3 ∈ S

and when it isn't you put a line through it

4 ∉ S

next, you can show them as a common property they share. you can just do this on it's own but it is heavily preferred that you do it to other sets.

{x∈ℕ|x is odd} would give you the elements of ℕ that are odd.

and lastly you can construct sets from other sets:

{x²|x∈ℕ} gives you the set of all perfect squares.

if you know python list comprehension comparsion becomes a lot easier:

S = [1,2,3,5] (S = {1,2,3,4}) S = [x for x in N if isOdd(x)] (S = {x∈ℕ|x is odd} S = [x**2 for x in N] (S = {x²|x∈ℕ}

now of course don't you ever DARE forget that sets are not lists so pretend that you put all of that trough a set() function too

anyways, just like with logic you can take all these sets and combine them in interesting ways

how combine the set

there are many ways:

union: A ∪ B is the set that has elements that are in either set. {1,2,3}∪{2,3,4} = {1,2,3,4}

intersection: A ∩ B is the set that has elements that are in both sets and nothing else. {1,2,3}∩{2,3,4} = {2,3}

subtraction: A \ B is the set that has elements from A but not from B. {1,2,3}\{2,3,4} = {1}

cartesian product: A × B is the set that has pairs of elements from A and B (in that order). {1,2,3}×{2,3,4} = {(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

now let's look at some properties a set can have too:

subset: A ⊆ B (A is a subset of B) only when every element of A is in B. Note that A ⊆ A. If you don't want A = B, then you can use A ⊂ B.

singleton set: a set that only has one element. like {1}

empty set: the set with no elements. there is only one empty set. you show it as ∅ or {}.

note that the empty set is a subset of every set

there is also the power set which is the set of all subsets. You show it as 𝒫(x) but I'll just use P(x) and be obvious when I mean the power set. For example: P({1,2}) = {∅,{1},{2},{1,2}}

finally, let's talk about hereditary sets. these are sets whose elements are hereditary sets themselves too. essentially, you will not find anything other than a set in them.

stuff like {{},{{}},{{},{{}}}} is a hereditary set. for the next parts, we will work strictly with hereditary sets. in part III, we will use them to define ℕ properly.

[jagernuke]

Ordinal Arithmetic I: Logic

whats up dipshits I am here to teach you ordinal arithmetic from the ground up but I'll do it accurately unlike every youtube video on it for some reason

we will begin with logic which is like the code that makes math run properly. without logic all is chaos and death and suffering.

how logic????

very good question mon ami the answer is simple.

propositions

propositions are the very basic statements not made by connecting two other statements. shit like "2 = 3" and "1 + 1 = 2" are propositions. propositions are either true (1) or false (0)

there are many ways to show true and false: T and F, 1 and 0, ⊤ and ⊥. I use the 0 and 1 notation because it's basically like binary. maybe if you code that should be familiar.

usually you show propositions as p,q,r,s,t etc.

logical connectives

now we will look at the different kinds of logical connectives. you tack on your propositions onto these to make even cooler statements called sentences

usually you show sentences with the greek letters φ (phi) and ψ (psi)

just like propositions they can also be true or false

here's the most common ones you'll see:

conjunction (AND): φ ∧ ψ is true only if both ψ and φ are true

disjunction (OR): φ ∨ ψ is true if at least one out of ψ and φ are true

negation (NOT): ¬φ reverses φ. if φ is true then ¬φ is false and vice versa

implication (IMPLIES): φ → ψ is a bit complicated but know that if φ is false it's always true and if φ is true then ψ has to be true for φ→ψ to be true

bi-implication/equivalence (IFF): φ ↔ ψ is true when φ and ψ are the same (both are true or both are false)

now let's look at implication more closely because the part where it being always true when the lefthand side is false is a bit weird. the reason you would do this is because if the first statement is false there isn't really anything that you could imply. anything can be true if you can't get past step one.

anyways just memorise these and you should be golden

quantifiers

these guys are those weird upside down letters you might see. they tell you about a whole bunch of stuff rather than just one thing

for example let's say I have a statement P and you apply it to x to mean "x is orange" and you show this as P(x). P(x) can be true or false

the existential quantifier means there is at least one thing that satisfies the condition you put at the front. like:

∃x(P(x)) means there exists an x such that x is orange. and there is. ginger people have orange hair so there clearly is an x that is orange. this is true.

the universal quantifier means everything satisfies the condition.

∀x(P(x)) means for all x, x is orange. this is false. I am not orange. so the statement is false.

oh and you can check these things for just a set a well. we'll explore sets too in the next part but for now know that for a set S, you would show "for all x in S, P(x) is true" as: ∀x∈S(P(x))

and I believe you're smart enough to understand what it means when you replace the ∀ in there with an ∃

thank you for coming to my ted talk

[somervta]

That feel when you know that x + 0 = x  and that y = 0 + (1+1+1+... [x times}) but not that a+b =b+a.

[whatilearninmath]

hierarchy of sets and ordinal arithmetic

part 11 of set theory (toc)

Semester's over, jokers. Here's the last contenty set theory post (I might get around to uploading solutions later to some problems that I thought were interesting).

I'm just going to dump some stuff from the end of the semester to wrap up for now. It's kind of a pity because (in my opinion) this stuff was by far the coolest stuff of the semester. Oh well.

First, as we noticed intuitively, if we only start with the empty set, basically all elements subsequent sets will just be sets of sets of sets... of the empty set over and over again. If you union union union union a whole lot of times, you should just come down to the empty set. So we're going to formalise this notion before getting into ordinal arithmetic.

Basically we define a hierarchy of sets, indexed by the ordinal numbers. First of all, there are three kinds of ordinal numbers: 0, successor ordinals, and limit ordinals. 0 is 0, pretty self-explanatorily. Successor ordinals are ordinals of the form α+ for some ordinal α. Limit ordinals are any other ordinal. For example, ω is a limit ordinal. When we define things recursively over the ordinals (there is a theorem saying transfinite recursion checks out for ordinals, even though the class of ordinals is not a proper set), we usually define the function for each sort of ordinal. Here's how we build up the hierarchy of sets:

V0 = ∅

Vα+ = P Vα, the power set of the previous set

Vλ = ∪ {Vα | α < λ} for λ a limit ordinal

In fact, we can't actually prove that every set belongs to one of these sets. Clearly, we need to will it to be the case, so we do. The regularity axiom asserts that every set is a subset of one of these Vδs, for δ and ordinal. Once we have the regularity axiom in place, we define the rank of a set A is the least ordinal δ so that A ⊆ Vδ. Note, then, that δ+ is the smallest ordinal so that A ∈ Vδ+.

Rank is actually pretty cool. Like. We've basically made every single set there is. Using transfinite recursion on the ordinals. Just let that sink in. (Of course, we need to use transfinite recursion over a class that is not a proper set, because the class of all sets is not a proper set.)

Okay, now that we've sufficiently had a moment to admire this hierarchy of sets, let's get on with ordinal arithmetic. The isomorphism type of a structure <A, R> (not necessarily even a poset) is the set of all structures <B, S> where <A, R> and <B, S> are isomorphic. Unfortunately, this collection of <B, S>s is not a proper set, so we need to add one more restriction. It must be that any structure of rank less than rank<B, S> cannot be isomorphic to <B, S> (and, thus, <A, R>). Now, we have a proper set. This set is it<A, R>, the isomorphism type of <A, R>. (To convince yourself it's a set, we can take the rank of all structures isomorphic to <A, R>. The ordinals are well-ordered under inclusion, so there is a minimal rank δ. Then, all <B, S> ∈ it<A, R> must be an element of Vδ+, so the rank of it<A, R> is Vδ+.)

We call the isomorphism type of a loset (linearly-ordered set) an order type, for no seeming reason except to make more terminology to deal with. (As a wise mathematician once said, math is just coming up with better terminology than someone else.) We define the addition of order types and multiplication as follows. Consider two losets <A, R> and <B, S> (we need A ∩ B ≠ ∅ for addition).

For addition of order types, generally speaking we want first A, then B. So define R ⊕ S = R ∪ S ∪ A × B. So we keep the ordering on A and B the way it is, but we also have anything in A less than anything in B. it<A, R> + it<B, S> = it<A ∪ B, R ⊕ S >.

For multiplication of order types, generally speaking we want A, B times. So define <a1, b1> R ∗ S <a2, b2> if b1 S b2 OR b1 = b2 and a1 R a2. In other words, if one element is in an earlier iteration of A, then it is smaller. If it is in the same iteration of A, then we use the ordering on A. So it<A, R> * it<B, S> = it<A × B, R ∗ S>.

Finally, with ordinal numbers, we work backwards from addition and multiplication on order types. For example, given the ordinal numbers δ and γ, ordinal addition given by δ + γ equals the ordinal α such that it<δ, ∈δ> + it<γ, ∈γ> = it<α, ∈α>. (Notice we need to pick structures with the same order types of the ordinals such that the underlying sets are disjoint.) Similarly for ordinal multiplication. This ordinal will always exist and is unique.

Notice that, by the definition of addition/multiplication of order types, addition/multiplication of ordinals is not commutative. However, it is associative and left distributive.

Okay. As I said, that's the last of the material for set theory. Hopefully I get around to uploading our set-theoretic approach to proving the Tychonoff theorem from topology. It was pretty cool. Since set theory was my last class required for the major, I don't know if I'll have quite as much content for this blog as before. At the moment I am self-studying ODEs (finally!) using the book that I bought when I was taking ODEs before I dropped the class. I've been making some pretty good progress during the break, but all bets are off once classes start again. Hopefully I can post some stuff on ODEs but (similarly to the algebraic topology problem) some of it is diagram-heavy. And...ODEs are not particularly interesting to write about (yet).