herp, derp, math nerd

But assuming you've stuck around, let's pick up where we left off last time. In particular, we were talking about the convergence of a sequence of random variables. The conclusion was that convergence in distribution is the weakest notion of convergence out of all of the ones that I definition-dumped. There's a small exception, and that is when a sequence of random variables converges in distribution to a constant. A constant random variable is just a random variable that assigns some constant to every single event, and it isn't particularly interesting as a random variable. But what IS useful is that if a sequence converges in distribution to a constant random variable, then it also converges in probability to that constant random variable, too.

Turns out there's also this pretty useful result called the continuous mapping theorem that makes life 100% easier. It basically tells us that if a sequence {X1, X2, ... } of random variables converges in distribution to X, then the sequence {g(X1), g(X2), ... } converges in distribution to g(X) as long as g is continuous. Actually, g doesn't even need to be continuous everywhere. We just need the section D on which it is continuous to occur with probability 1 under the distribution of the limit X. You may have heard of Slutzky's theorem, which is basically an application of the continuous mapping theorem combined with the observation above.

The next two results are probably the most famous in probability, and they are the law of large numbers and (everybody's favourite) the CeNtRaL LiMiT tHeOrEm!!! These two results help us a lot with proper actual real statistics, where we try to estimate population parametres from a set of data. But I'm getting ahead of myself. I want to try to get through the statements of these results without much notation, but we'll see how I do.

The law of large numbers applies to a length-n sequence of random variables which each have some mean and variance. The catch is that every pair of random variables must have zero covariance; and that the average variance divided by n must tend towards 0. In this case, then, the average of the random variables converges almost surely to the average of their means. In practice, this result usually gets applied to some kind of data collection or sampling. With a random sample, the sequence of random variables is iid, and so the law of large numbers in that case simply states that the sample mean converges almost surely to the true population mean.

The central limit theorem is similar, but makes a statement about the distribution of this sample mean, m. So if we're given a length-n sequence of iid random variables, then (√n)(m - μ) converges in distribution to a normal distribution centred at 0 with variance σ2, where μ and σ are the population parametres. A more general statement of the theorem ditches the iid assumption by allowing the variance of each draw to differ. Then, the theorem is revised to reflect this change just by replacing the population variance (which doesn't exist any more) with the average of the variances.

So to recap (since these results can be kind of dense): the law of large numbers gives us the asymptotic value of the sample mean, while the central limit theorem gives us a description of how the values of the asymptotic sample mean vary.

As a side note, I should probably point out that the sample mean is a random variable itself. It's just a linear combination of n random variables (namely with weights 1/n for each one), and so you can construct a sequence of sample means by just recalculating the sample mean at each added data point. In fact, that's implicitly what's going on in the above two statements, since they both use language that describes the convergence of a sequence of random variables. The asymptotics, then, tell you what happens to the sample mean when the sample size is really big! In general, that's why we want big samples--because we get more information about the true population, and because we get closer to the asymptotic results that we know about.

It's hard to imagine any statistics class that doesn't mention the central limit theorem. I know I first saw it when I was around fifteen. But of course, I didn't really get it. Like... what was the point? And why did it even matter? But actually, this theorem is, as my metrics professor would say, basically the perfect theorem. It is totally applicable in a huge variety of settings, and it's also a somewhat surprising and non-obvious result. The full significance didn't really hit me in high school, and I'm not even sure it has now. But, over five years later, it's finally left a deeper impression. We actually went through a proof of the theorem in class, which was pretty cool and made the whole thing seem more legitimate. Maybe I'll get around to TeXing it later, since it would be a total nightmare to present otherwise.

The last little chunk of this post is the delta method, which in a way is analogous to the continuous mapping theorem. The delta method basically tells you what to do if you have some setup like the central limit theorem, but there has been a transformation applied. Words are hard sometimes, so let's just see it with notation. Given a sequence of random variables where (√n)(Xn - x) converges in distribution to a normal N(0, σ2), then applying a continuously differentiable transformation g to the sequence is no big deal! We just get that (√n)(g(Xn) - g(x)) converges in distribution to a normal N(0, (g'(x))2σ2). That's not too bad, right?

I've previously talked about what it means for a sequence of numbers to converge. We defined epsilon-delta concepts painfully and I learned that any convergence proof probably uses the triangle inequality at least 239847293 times. But what does it mean for a sequence of random variables to converge?

As a refresher, a random variable is not really a variable at all! It's, in fact, a function, which assigns a real number to some event. That is, a random variable X: Ω → R where Ω is the "event space". Basically, you observe something happening, and you attach a number to this random occurence. In practice, these random variables are usually quite natural; for example, the random variable that assigns a number from {1, 2, 3, 4, 5, 6} to a roll of a die. In fact, the event space is all possible rolls of the die, where an event is a certain face being rolled; the random variable assigns the event of a certain face being rolled to the number on the face of the die. You can imagine a whole array of functions defined on this event space that are not the one I just described. For example, instead of assigning 6 to the event that 6 is rolled, you could assign e6 instead. Really, the random variable just a function, and you could define this function however you'd like.

Of course, as I said, usually random variables are pretty natural given the event space, because usually we'd like to say something useful about the events, and these random variables are just a tool we use along the way. A random variable also comes with a distribution, or a function that describes the likelihood of the random variable taking on each value in its range (the "support" of the random variable). Here's where a random variable is different from any old function. The distribution is usually described using a cumulative distribution function FX(x) = P(X < x) for each x ∈ R. CDFs can be any function from R to [0, 1] which have the following properties:

F is nondecreasing;

limx → -∞ FX(x) = 0, limx → ∞FX(x) = 1

F is right continuous, ie as you approach x from the right, F(x + Δ) converges to F(x).

So now that we're clear on the definition of a random variable, let's consider what it means for a sequence of random variables to converge. Of course, random variables are functions by definition, so you can think about them as points in a functional space. That is, we can think about functional spaces and their associated metrics (like the sup norm), and consider sequences of random variables that converge under a normal sequential definition. This option seems like the easiest way out, since it's using machinery we already know. Indeed, functional convergence and pointwise convergence do come in handy sometimes, but these concepts aren't super interesting from a probabilistic point of view...we could have just stuck to functional analysis if we wanted to think about these convergence concepts.

So let's think about convergence concepts that actually take advantage of the additional information we're given: namely the probability structure or distribution of the random variable over R. We'll go from strongest to weakest notion, since the stronger notions may seem a bit more familiar. (So each convergence concept implies the convergence concepts below it.)

The first is almost sure convergence, which is essentially pointwise convergence for each event in the event space. There's a small catch though: we only care about events with positive probability. Technically we define the random variable with the domain as the entire event space, but really we don't care about its values for an event that never happens, right? So here's the formal definition: a sequence of random variables {Xn} converges to the random variable X if there is some subset of the event space, A ⊆ Ω where Xn(ω) → X(ω) for every ω ∈ A, and PX(A) = 1. Deep breath; what does that mean? It means the sequence converges to some random variable X if it does so pointwise for some subset of the event space that has probability 1 under the distribution of X. It's worth noticing that some events could have positive probability for some random variable Xn in the sequence, but 0 probability for X. In that case, it doesn't really matter in the end. Here's an example: say we define Xn: [0, 1] → {0, 1} with Xn(ω) = 0 if ω is between 0 and 1 - 1/n. Then we let Xn(ω) = 1 for ω between 1 - 1/n and 1. Then, Xn → X = 0. Of course, we notice that X(1) = 0 while Xn(1) → 1, so the sequence of random variables viewed simply as functions does not converge perfectly to our proposed limit. However, P(X = 1) = 0 since X is a continuous random variable, so we essentially just forget about 1. It never happens under X, so it's irrelevant! How sad. Note we used the distribution of X, the limit, in this case, but we didn't really say anything about the distributions of any of the sequence elements. That's why this notion is particularly strong; because we are basically just sticking to the functional convergence idea, but throwing out some points in the end.

The next strongest notion of convergence is rth mean convergence, which requires E[ |Xn - X|r ] → 0. What was that all about? Well...given a distribution of a random variable, we're also able to calculate all sorts of information, including expectation. This convergence concept transforms the sequence of random variables into a sequence of plain old numbers in a different way than above, by simply evaluating the expectation for the difference between the sequential random variable and the limiting random variable. You can blow up this difference by raising it to the power of r, and so a larger r is a stronger condition for convergence than a smaller r. This definition just says that the expected difference between the sequential variable and the limiting variable goes to 0, so that the sequence of variables is becoming like the limiting variable on average. Now we're starting to use the distributions of each of the random variables. To clarify, almost sure convergence and rth mean convergence are not comparable -- there are cases where a sequence of random variables can converge under what definition but not under the other.

Next, we have convergence in probability. This definition is probably the most used one, and the other two are generally used in one way or another to show convergence in probability. Similarly to the other convergence concepts, we need to find a way to make this sequence of functions into a sequence of numbers, since we know how to think about convergence of numbers. Convergence in probability uses the actual probabilities of the random variables as follows: Xn → X in probability if P( |Xn - X | > ε) → 0 for every value of ε > 0. Now, this definition is taking on a comforting old form, with its epsilons. But notice: it's not exactly the same. Say we fix ε and consider P( |Xn - X | > ε). That's in fact a sequence of numbers, so we need to choose another small number, ε' > 0, and find N so that P( |Xn - X | > ε) < ε' for all n > N. The main thing here is to remember that each value of ε generates a new sequence for us to evaluate, and we need to show that the limit of each of these sequences is 0. In English words, this definition is asking for the probability that a deviation of any size between Xn and X to get arbitrarily small.

The last convergence concept is basically totally different from the previous ones, and it's convergence in distribution. This one, at least, is easy to state. Xn converges in distribution to X if the CDFs of Xn converge to the CDF of X pointwise. This definition makes no statements about the actual values of Xn! For example, say you start drawing numbers from the interval [0, 1 + 1/n], where each number has the same chance of being drawn. So for each Xn, you draw a number from the corresponding interval [0, 1 + 1/n]. Clearly, this sequence is not guaranteed to converge. It's possible you could draw the sequence {0, 0.5, 0, 0.5, 0, 0.5, ... } forever. But you can tell that these random variables are converging in some sense... precisely in the sense of distribution! Sooner or later, once you get far enough down the sequence of random variables, the draws are going to look verrryyyy suspiciously as if they came out of the interval [0, 1]. Of course, they haven't. But you can say at the limit that the CDF is going to look like the CDF for random draws out of [0, 1], and that is what convergence in distribution aims to capture.

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.

First off, I want to assert that the class of ordinal numbers (because there are too many ordinal numbers to fit into a set) is well-ordered by inclusion. I don't feel like proving this statement. Onwards we go.

Where we left off last time, we had defined the ordinal numbers, and noticed that an ordinal number is well-ordered by ∈. So it should be no surprise that every ordinal number is a transitive set, because orderings are transitive, and our ordering in question is precisely inclusion.

In fact, any transitive set well-ordered by ∈ is an ordinal number. Basically, we have to show that the ∈-image of our transitive set is the set itself. So let's call our transitive set α. We want to show that F defined on α is just the identity function. We'll do this proof by transfinite induction (similar flavour to strong induction).

So first notice that since our ordering mechanism is just inclusion, the segment of any t ∈ α is just t. See, segt = {x ∈ α | x ∈ t} = t. So for our inductive step, suppose F(s) = s. We show for any t with s < t, that F(t) = t.

F(t) = {F(s) | s ∈ t} = {s | s ∈ t} = t. Whoop de whoop. We've done it. So basically we can create ordinal numbers be just creating transitive sets that are well-ordered by inclusion. Since the class of ordinals are well-ordered by inclusion, it follows that any transitive set of ordinal numbers is itself an ordinal. Like I said, they breed each other!

Something that's useful to remember when doing proofs with ordinals is that F(t) is the range of F on the segment of t. Therefore, any element x of F(t) is F(s) for some s < t. We use this fact specifically to prove things like F(t) cannot be an element of F(t), or s < t iff F(s) is an element of F(t).

So what's a well-ordering? Well, first, we need some elements to put into an order. So let A be set. We can define an ordering < on A, which is simply a relation on A with the following properties:

irreflexivity: x < x is never the case for any x ∈ A. In other words, there are no elements of the form < x, x > ∈ <.

transitivity: if x < y and y < z, then x < z.

trichotomy: for any pair x, y, at most one of the three x < y, y < x, x = y holds. It's not necessary for any of them to hold, either. In this case, we get a partial ordering. If it's the case that exactly one holds for all pairs x, y, then we have a linear ordering (correct me if I'm wrong, but I believe it could also be called a total ordering).

So for < to be a well-ordering, it has to be a linear ordering with the added property that any subset B ⊆ A has a least element. An element b ∈ B is a least element if b < b' for every b' ∈ B where b' ≠ b. Okay, so now that we've got our structures, let's measure their lengths!

To construct the ordinal numbers, we need this weird thing called transfinite recursion. I had to read this section of the text at least ten times before I actually understood it. I think it read it around four times the first night I was going through the material, and then let it marinate for a while before reading it several times again a few weeks later. I kind of got it, but I don't think it was until yesterday, when I was going back through my book to really solidify and catch up, did I truly get the concept. Well, better late than never right? So I'm going to try and be as slow and clear as possible. The general idea is pretty simple, but it get really wonky with the notation.

Let's first think about induction. To construct something inductively, you take what you had previously, then do something to it. So if you were trying to construct something for n+, you take whatever value you had for n, and then manipulate it according to some pre-specified rule. So what about "strong induction", which I covered in my discrete math posts (toc)? That's basically what transfinite recursion is. Instead of constructing the next value by simply using the previous value, you need to take into account all the previous values. That's the intuition. So now, here's the formalism.

Let's start with an easy definition. Start with a linearly-ordered set, A. Let a be an element of A. Then the segment of a, seg(a), is the set of all elements less than a, i.e. {x ∈ A | x < a}.

Suppose you have some rule, a function G, that assigns the next value based on all previous values. Let's say that G picks out an element from B, based on its previous values on A. How do we actually formalise G? Well, the codomain of G is easy: it's B. What about the domain? It's not actually A, because G is taking all previous values of itself as input. In fact, G is defined on the set {f | f a function from some segment in A to B}. For example, G(t) takes as input some function defined on seg(t); in particular, the previous values of G on seg(t). It takes this input, then spits out the next value in B. So in fact G goes from this weird set of functions on segments to B.

So the idea is we want to define some function on A that follows this rule G. It's pretty easy to see how it would work intuitively. First, we need A to be well-ordered. Then, A has a least element a0, so we calculate G of a0. That's the value of F at a0. Now, A - {a0} has a least element, a1. a1 is like the "next smallest" element in A. We calculate F(a1) as G of F so far. And on and on. Notationally, we say that F(t) = G(F ↑ segt), i.e. we find the value of t by applying G to the function F defined on the segment of t (all the values of F before t).

The transfinite recursion theorem says that this "on and on" is rigourous. In other words, there indeed exists a function F that can be defined this way, given G. In fact, F is unique. So for every rule G, there is a unique function that is defined by G recursively.

In fact, G doesn't actually need to be a function at all. It can go from a class to a class, not necessarily restricted to going from sets to sets. (Remember, there are "classes" or groups of elements that are too big to be sets, such as the class of all sets. What I'm saying here is that G doesn't need to be a function, so it doesn't need to go from a set to a set.) So the more general way of reformulating transfinite recursion is as follows: instead of a function G, we can simply take a formula γ(f, y) which specifies some relationship between f and y. As long as there is exactly one y for each f such that γ(f, y) holds, we can build a function using transfinite recursion constructed using γ.

The particular γ that we use to build the ordinal numbers is y = ranf. Of course, given a specific function f, the range is completely determined and unique, so there is exactly one y to go with each f such that y = ranf. So our rule checks out and we are good to go to use it.

Finally, all the legwork is out of the way. Time for a test drive! Let's use transfinite recursion to build a function F constructed by this rule on a well ordered set! We'll start easy, with a four-element well-ordered set. Say we use A = {w, x, y, z} where it's ordered alphabetically, so w < x < y < z.

first we evaluate F at the least element, w. F(w) = G(F ↑ segw) = ran(F ↑ ∅) = ran(∅) = ∅. Here, the segment of w is the empty set, so F has no preceding values. So the range of F is empty.

x, is next, so F(x) = G(F ↑ segx) = ran(F ↑ w) = F[w] = {∅}.

now, y. F(y) = G(F ↑ segy) = ran(F ↑ {w, x}) = F[{w, x}] = {∅, {∅}}

last of all, z F(z) = G(F ↑ segy) = ran(F ↑ z) = ran(F ↑ {w, x, y}) = F[{w, x, y}] = {∅, {∅}, {∅ {∅}}}

Hmmm... those values of F look a lot like the natural numbers. In fact, they are. The first is 0, then 1, then 2, then 3. And notice that ranF is well-ordered by inclusion, ∈, the exact same way our original set was ordered by its own well-ordering. How curious.

In fact, this "coincidence" is not a coincidence at all. We call <ranF, ∈> the ∈-image ("epsilon image") of the original well-ordered structure <A, < >, precisely because the ∈-image of any well-ordered structure will be isomorphic to the original structure.

Isomorphisms again? Yes. I've defined isomorphisms over and over on this blog, and the general concept never changes. An isomorphism is a map between two structures that is a bijection of the underlying sets which preserves the structure. Here, we have a set together with a relation (to define an isomorphism, the relation need not be an ordering at all). For the map f: <A, R> → <B, S> to be an isomorphism, it must:

be a bijection of the sets A and B

preserve the relation. In other words, given a and a' in A, we have aRa' iff f(a)Sf(a'). Notice f(a) and f(a') are elements in B, so we use the relation S on B.

Therefore, when we say the ∈-image of any well-ordered set A is isomorphic to the well-ordered set, we mean that it is in bijection with A, and that it is well-ordered precisely in the same way A is ordered. The ordering used on ranF is that of inclusion, ∈. So given a, a' in A, then a < a' iff F(a) ∈ F(a'). Basically, ranF is a collection of elements equinumerous to the original set that also has the same ordering structure.

In fact, this process is how we define the ordinal numbers. Any ∈-image is an ordinal number. As long as a set is the ∈-image of another set, then it is an ordinal number. Notice the ∈-images of any finite well-ordered structure is simply a natural number. Therefore, every natural number is an ordinal number.

You can think of ordinal numbers as a way of "standardising" well-ordered sets. In other words, two well-ordered structures will have the same ordinal number (∈-image) iff they are isomorphic...just like two sets will have the same cardinal number if they are equinumerous.

So the cardinal numbers "standardise" sets based on size (because equinumerous sets look identical from a distance; their elements are simply renamed from one set to another), and ordinal numbers "standardise" well-ordered sets. Because isomorphic structures look fairly similar from far away, structure-wise, their elements are also just relabelled from structure to structure.

To recap (since this concept is new and weird):

we construct the ordinal number of a set A by applying to A the function F constructed by transfinite recursion where y = ranf, then taking ranF ordered by inclusion.

the ordinal number is well-ordered by inclusion.

the ordinal number together with inclusion is isomorphic to the original well-ordered structure.

two well-ordered structures have the same ordinal number iff they are isomorphic.

the finite ordinals are exactly the natural numbers.

How about the ordinal number of our simplest infinite set, ω? Well, like we calculated above, F(n) = n. So ranF = ω itself, and ω is therefore also an ordinal number.

You may be wondering how the ordinals and cardinal numbers are different. The short answer is that there are more ordinal numbers than cardinal numbers. Let me demonstrate with a (hopefully) simple example. Let's consider the well-ordered structure where the underlying set is the natural numbers, and the ordering is defined 1 < 2 < 3 < ... < 0, i.e. just take 0, and make it bigger than everything else. Let's call this structure < A, < >. The cardinality of this set is just ℵ0, because we haven't messed with which elements are in the set; we've simply reordered the set. But what's the ordinal number? Let's calculate the ∈-image.

Well, the structure 1 < 2 < 3 < ... is isomorphic to the natural numbers under the usual ordering. Then, the ∈-image of this "substructure" of <A , < > is therefore just ω. So now, what about F(0)? F(0) = ran(F ↑ seg0) which is simply the ∈-image of the substructure we previously calulated. So F(0) = {ω}. Then, ranF = ω ∪ {ω} = ω+. (Note: F maps A one to one onto its ∈-image, so ω^+ is equinumerous to ω. Therefore, some ordinal numbers will have the same cardinality, even though they are different ordinal numbers. This fact will become important later.)

The idea is that this structure we've constructed, <A, < >, is fundamentally different from the original natural numbers. The big difference is that <A, < > has a maximum element, 0, which is certainly not true for the natural numbers. So although A and the natural numbers are the same set, and have the same cardinality, the way it's ordered (or the "length" of the ordering, if you will) is different. The ordinal numbers capture this added nuance of the well-ordering that the cardinal numbers do not.

In this way, we can actually think about "infinity + 1", just like proofsareart mentioned briefly here. So now I've motivated and constructed the ordinal numbers, next time I might review some results about the them. While most math students have some degree of familiarity with cardinal numbers, ordinal numbers are generally a bit new and more uncomfortable to think about, precisely because they allow this sort of weird business of "infinity + 1"...so we get to deal with all the additional ramifications that come with it. Excited??

So having (partially) defined the cardinal numbers last time around, I'm going to go over a few of their properties for this post. Basically, when you get a number system, you could be interested in a few things: ordering and arithmetic. How do you go about comparing cardinal numbers? And what about adding them together?

Ordering is as follows. A set A is dominated by a set B (A ≾ B) if there is a one to one map from A into B. In that case, cardA ≤ cardB. This definition gives us the nice properties of an ordering, namely:

A ≾ A, reflexivity

A ≾ B, B ≾ C → A ≾ C, transitivity

A ≾ B or B ≾ A; if both, then A ≈ B.

The second part of the last point is actually nontrivial and requires the axiom choice to show. But since we've got it, we may as well use it. What I listed above is actually an ordering on sets, and not on cardinal numbers; but the ordering on cardinal numbers follows. In particular, we have that cardω = ℵ0 is the smallest infinite cardinal. If cardA is strictly smaller than that of the natural numbers, A is finite.

Onto arithmetic. Suppose we have two sets, K and L, with cardinalities κ and λ respectively. Then,

κ + λ = card(K ∩ L), provided K and L are disjoint.

κ ⋅ λ = card(K × L)

κλ = card(LK), where LK is the set of all functions from L to K.

The nice thing about the way we've defined arithmetic on the cardinals is that basically all the properties we're used to hold with the cardinal numbers: associativity, commutativity, distributivity, exponent rules... The arithmetic also plays nice with ordering too.

The big hooplah that's new with this stuff is what happens when you start messing around with infinite cardinals. It turns out that arithmetic is almost trivial when we're working with infinite cardinals. To start us off, we have the theorem that κ ⋅ κ = κ for any infinite cardinal. From this property, we get the absorption law as follows.

Suppose we have two cardinal numbers, κ and λ, with κ nonzero, λ infinite, and κ ≤ λ just for concreteness. Let's see what happens when we start adding them: λ ≤ κ + λ ≤ λ + λ = 2 ⋅ λ = λ, so κ + λ = λ. Similarly for multiplication, λ ≤ κ ⋅ λ ≤ λ ⋅ λ = λ. So κ + λ = λ. Basically, the smaller cardinal gets "absorbed" by the bigger one. It's kind of weird, but we should have expected it since we were dealing with infinity!

Anyway, following that long preamble, here is my relatively unimpressive first post on cardinals. We've already kind of encountered the concept in my post about countability under real analysis (toc). I guess what set theory is kind of doing for us now is fleshing out the whole concept.

Let's start with an easy definition. Two sets, A and B, are equinumerous (notationally, A ≈ B) if there is a one-to-one onto function f: A → B, i.e. there is a bijection between the two. The book calls such a function a one-to-one correspondence...but I prefer bijection since it's easier.

There are a few different formulations of equinumerosity. If we want to show that A and B are equinumerous, then obviously we could try to construct a bijection between the two. Alternatively, you could show that there is a map from A onto B and a map from B onto A. Similarly, you could show there is a one-to-one map from A into B and a one-to-one map from B into A. Yet another way of showing A and B are equinumerous is to start with a one to one map from A into B, and then show that it must be onto. Likewise, you could start with a map from A onto B, and show it must be one-to-one.

One last note about equinumerosity before we move on: it has the flavour of an equivalence relation (only equivalence relations are defined on sets, and the collection of all sets is not a set). In other words,

A ≈ A;

A ≈ B → B ≈ A;

A ≈ B, B ≈ C → A ≈ C.

These properties are pretty easy to prove using the identity, inverse, and composition of appropriate bijections, respectively. Okay. Onto the real meat of the discussion.

Intuitively, we'd like to say that sets that are equinumerous have "the same number of elements", or that they are "the same size" in some way. Cardinal numbers help us formalise this idea. Basically, we pick out a few special sets (how we pick these sets comes later). We declare these sets "cardinal numbers", so each special set is a cardinal number. Then, if any set A is equinumerous to a specific cardinal number κ (since, remember, cardinal numbers were sets themselves), then the cardinality of A is κ; cardA = κ.

The basic hope is to define the cardinal numbers so that cardA = cardB iff A ≈ B. We can start by allowing all elements of ω (the natural numbers) to be cardinal numbers. Then, cardn = n ∀n ∈ ω. Defining the particular sets which will be infinite cardinal numbers is a bit trickier, so we save that for later. But we're off to a good start--we have all the finite cardinal numbers! In order to make sure that each finite set gets associated with one unique cardinal number, we need to pull in the our good dude, the pigeonhole principle.

I'm sure you've seen the pigeonhole principle before--I first wrote about it in my discrete math post set. We're going to rework it a little bit for this content, but the pigeonhole principle by any other name is still the pigeonhole principle. Here we go.

The Pigeonhole Principle asserts that no natural number n is equinumerous to a proper subset of itself (including, of course, any natural number less than n). For the proof, we use induction. Of course, everything in set theory must be reformulated for set theory, so let's reformulate induction first.

From before, we saw that any inductive set must contain the natural numbers; i.e. the natural numbers are the smallest inductive set. Then, if we prove a property for any inductive set, it most certainly holds for the natural numbers. Thus, say we want to use induction to prove some property xyz. We first show that xyz holds for 0, or the empty set. Then, we show that, given xyz holds for some a, it holds for the successor of a, a+. Now, we've shown that the "class" (might not even be a set) of all elements with the property xyz is inductive; so this class must contain the natural numbers, ω. Then, xyz holds for every element in ω. Alternatively, ω is the smallest inductive set, so if a subset of ω is inductive, it must be ω itself. We can then define some subset T ⊆ ω consisting of all natural numbers for which xyz holds. If we prove that it is inductive, we can conclude T must equal ω, so every element in ω has the property xyz.

Let's do a test drive on the pigeonhole principle. We'll define the set T = {n ∈ ω | n is not equinumerous to a proper subset of itself}. 0 ∈ T because there are no proper subsets of 0, and the property holds vacuously. Now, let's suppose n ∈ T. How do we show n+ ∈ T?

Let's start with some map f: n+ → n+ that is one-to-one. We show it's onto.

case 1: f is closed under n, i.e. f[n] ⊆ n. Then, considering the map f restricted to n, it is a one to one map from n into n. From the inductive assumption, it must be onto. Finally, f({n}) must go to {n}, because f is one-to-one. Then, the range of f is n ∪ {n} = n+.

case 2: f is NOT closed under n, i.e. {n} ∈ f[n]. f is one to one, so there is a particular k ∈ n with f(k) = {n}. Similarly, f is one to one, so f({n}) cannot be {n}, and thus f({n}) = m where m ∈ n. We can simply define a new function, g, with all the old values of f, except we interchange f(k) and f({n}) so that g(k) = m and f({n}) = {n}. Now, g has the same range as f, but g is closed under n. From case 1, g is onto n+. g has the same range as f, so f is also onto n+.

Now, we have n+ ∈ T, so T is inductive and we have T = ω. Thank god, I was starting to sweat a little.

We have that every natural number cannot be equinumerous to a proper subset of itself. And obviously a natural number can't be equinumerous to a natural number bigger than itself, because then the bigger natural number would be equinumerous to a proper subset of itself. Of course, every natural number is equinumerous to itself, with the identity function. So we conclude that cardn = n is well defined and unambiguous.

Now, we can define the concept of a finite set really easily, by just saying A is finite if cardA ∈ ω. It's pretty peanuts to have as a side effect of the pigeonhole principle that all finite sets cannot be equinumerous to proper subsets of itself. Let's take some finite set, A, and a proper subset B ⊂ A. There's an n ∈ ω with cardA = n, so n ≈ A. Let's just choose a bijection f: A → n. Then, f[B] ⊂ f[A] = n. If A ≈ B, then let the bijection be g: A → B. Then, using composition, we'd have a bijection n → A → B → f[B] where f[B] is a proper subset of n. Of course, we just showed that cannot be the case, so A cannot be equinumerous to B. Then, each finite set is equinumerous to a unique cardinal number, so the cardinal numbers are well defined (for finite ones, at least).

In fact, generally speaking, that's how you show something related to cardinality when it comes to finite sets. Show it for ω first (usually using induction); then kind of "copy-paste" the property back to the original sets.

We have the concept of transitivity for relations: R is transitive if it's the case that given aRb and bRc, it's the case that aRc. Defining what it means for a set to be transitive kind of is in line with this idea, only we use ∈ for the relation.

Specifically, a set A is transitive if x ∈ a and a ∈ A implies that x ∈ A. Remember, a is an element of A, but a is also a set itself. For A to be transitive, all the elements of a must be in A: the elements of elements.

Confusing? Yeah, a little. There isn't too much to say about transitivity, but it's a handy little property to have. Some alternate formulations are: ∪A ⊆ A; and A ⊆ PA. Let's see why these conditions are equivalent to the original definition of transitivity.

Suppose A is transitive, We'll show ∪A ⊆ A. Let x ∈ ∪A. Then, there is a ∈ A with x ∈ a. By transitivity, a ∈ A. So ∪A ⊆ A.

Suppose ∪A ⊆ A. We'll show A ⊆ PA. Let a ∈ A. Then, for every x ∈ a, x ∈ A. Then, we have a ⊆ A. So a ∈ PA, and A ⊆ PA. In fact, that gives us another slightly different way of having transitivity: A is transitive if a ∈ A → a ⊆ A.

Suppose A ⊆ PA. We show A is transitive. Let x ∈ a and a ∈ A. Then, a ∈ PA so a ⊆ A. Then, x ∈ A, so A is transitive.

Cute, huh? I guess what's important is that every natural number is transitive. Extending further, ω, the set of natural numbers, is also transitive.

The first problem is a write off. It's basically an application of the subset theorem. It might be something like "given A is a set, prove A x A is a set". And then you would notice that an element of A x A is of the form {{a}, {a, a'}}, which is a subset of the power set of A, PA. Then a set of these things, e.g. A x A, would be a subset of PPA. By the subset axiom, A x A is a set. Easy.

(Time out: I haven't actually defined ordered pairs yet for you guys. The concept of an ordered pair is pretty simple: it's something of the form <a, b>, where knowing a, knowing b, and knowing the order they go in completely determines the ordered pair. There were several propositions on how to go about formally defining this idea, but the one that stuck is to let <a, b> = {{a}, {a, b}}. Then, the set {a, b} completely determines the elements of the ordered pair, and the element in the singleton, i.e. {a}, is the first element in the ordered pair. Like I said, there have been other equally valid formulations that work, and it might be interesting to look them up. This method is popular because it is convenient and easy to work with.

Then, given two sets A and B, A x B is defined to be the set of all ordered pairs <a, b> where a comes from A and b comes from B. This set is the cross product of A and B.)

The second question is of the form "given a set A, show there is a smallest subset B satisfying conditions xyz". The trick here is to create a set, T, containing all subsets that satisfy the desired conditions. T is a subset of PA, so it's a set. Then, you show the intersection over all the elements in T is still in T, i.e. ∩T satisfies xyz. Then, ∩T is the smallest subset satisfying conditions xyz. It's the smallest because it's contained in all other subsets that satisfy the conditions, since it's the intersection over all of the subsets that satify the conditions. If there were a set contained in ∩T that satisfied the conditions, then it would be in T and therefore ∩T would have to be a subset of it.

The third question is an application of Zorn's Lemma. Oh yeah! Zorn's Lemma is some new material for this blog. Let's do a quick refresher on the axiom of choice. At this point in the class, we've got several alternate formulations of the axiom of choice:

For any function R, there is a function f contained in R, with the same domain as R.

If H is a function defined on I, and H(i) is nonempty for every i ∈ I, then there is a function with domain I and f(i) ∈ H(i). In other words, the cross product of nonempty sets is nonempty.

For any set A, there is a function f whose domain is the set of nonempty sets of A, and f(B) ∈ B for all nonempty B ⊆ A. In this case, f is called the choice function on A.

For sets C, D, either there is a one to one function from C into D, or there is a one to one function from D into C. We say C is dominated by D if there is a one to one function from C into D. This formulation says that, given a pair of sets, one must be dominated by another.

If A is a set so that for every chain B ⊆ A, we have that the union over B is an element of A, i.e. ∪B ∈ A, then A has a maximal element. This statement is Zorn's Lemma. There's quite a few new terms in this one, so let's go through it slowly. B is a chain iff for any C, D in B, either C ⊆ D or D ⊆ C. An element M ∈ A is maximal if M is not a subset of any other set in A.

So the third question on the qual is simply an application of Zorn's Lemma: "given a set A with some qualities, show that A contains a maximal element". You must show that A satisfies the conditions for Zorn's Lemma, i.e. for every chain in A, the union over the chain is an element of A (has whatever qualities qualify a set to be in A).

The last question is just an identification of the axiom of choice within a proof or statement. This question is generally pretty easy: you just look for some statement "for every A, there is a B, so let BA be this B". This statement evokes the axiom of choice if there are an infinite amount of As. In general, you are looking for some sort of choice or specification of one element out of a group of similar elements--and this choice is made for an infinite number of groups.

Anyways so let's set about making some numbers! Along the way, we will uncover another axiom. It's all just fun and games here today!

Let's start with a little informal discussion first before we get into it. As it stands right now, the only thing that exists in the universe is sets. The most basic one is, of course, ∅ the empty set. We can then use the various axioms to create new sets; for example, we get {∅} from the pairing axiom, and {∅, {∅}} from the power set axiom...and so on. So we've built kind of a universe of sets that are just sets of sets of sets of sets ... of the empty set. How might we use these sets to model the natural numbers?

Here's the proposal:

0 = ∅

1 = {0} = {∅}

2 = {0, 1} = {∅,{∅}}

3 = {0, 1, 2} = {∅,{∅},{∅,{∅}}}

So in effect, every number is defined recursively as the set of all numbers preceding it. The cardinality of each set also coincides with our normal notion of what each number means. Curiously, we get from this construction that each number is both an element and a subset of the succeeding number. Interesting. This property actually turns out to be kind of useful later. So useful that it's going to get its own definition. But that's going to come in a later post.

For now, let's notice that the way we have constructed each natural number a+1 so far can be described as a+1 = a ∪ {a}. In fact, for any set a, its successor a+ is defined to be a ∪ {a}. We can then describe a set A being closed under successor, or inductive, as a set that for all members a ∈ A, we have a+ ∈ A.

Unfortunately, as of yet, we have no evidence that any such set exists. To be quite honest, we've only been looking at finite sets, and it seems that a set would need to be infinite to be inductive (besides the empty set, of course). Well, that's an easy enough fix: let's just axiom this problem away! The infinity axiom asserts that there exists an inductive set A with ∅ ∈ A, i.e., A is nonempty.

We can see that natural numbers we proposed at the beginning have been successors of each other, and throwing all these natural numbers into one set would give us an inductive set, almost by definition. In fact, we will actually proceed to define the natural numbers (finally!) in this way: a natural number is an element that belongs to every inductive set. From the infinity axiom and the subset axiom, we can be sure that the set containing the natural numbers, or the set of natural numbers is indeed a well-defined set that most definitely emerges from our axiomatic approach.

This class is taking the "axiomatic approach" to set theory, which basically means starting with a list of statements that we declare to be true. From these statements, we build up basically the entirety of set theory. This approach is contrasted to "naive set theory", which is loosely what most people encounter when they work with sets in any other kind of math class.

The motivation for axiomatic set theory (among others) is that we run into the kind of paradoxes I mentioned in the previous set theory post if we don't explicitly specify what is and is not allowed. For this reason, axiomatic set theory really starts with nothing and builds up all the sets we are allowed to have. After all, stating axioms and finding subsequent results is basically how math works.

As a preface, we start with this weird notion that nothing in the universe exists besides sets. In other words, the elements of sets can only be sets themselves. This restriction is actually not as much a restriction as it first appears. Turns out we can basically produce everything organically, without having to assume the existence of numbers, or people, or any other object to serve as members of our sets. It's kind of a weird concept to consider at first, but it becomes natural pretty quickly.

I believe we will have ten axioms over the course of the class, and we've seen seven of them so far. Here's the partial laundry list:

Extensionality Axiom: two sets are equal set-wise iff they have exactly the same members.

Empty Set Axiom: there is a set having exactly no members.

Pairing Axiom: for any two sets u and v, there is a set having as members exactly (only) u and v: {u, v}.

Union Axiom: For any set A, there is a set whose elements are exactly the members of members of A. In this case, it's helpful to explicitly think of A as a collection of sets (remember: for the purposes of this class, all sets are just sets of more sets). What does it mean to take the union over A? You basically take every set in A and throw all their members together: you want members of members. The axiom says that such a set exists for all sets A.

Power Set Axiom: for any set a, there is a set whose members are exactly all and only the subsets of a.

Subset Axioms: suppose we already have the set c. There exists a set, d, whose members are exactly those within c which satisfy a specific formula, as long as the formula doesn't contain d. Basically, suppose you want the set of all things that satisfy a certain condition. The subset axiom says that as long as all the elements that satisfy this condition belong to some set (along with potentially other members which don't satisfy the condition), then the set containing exactly the elements that do satisfy the condition also exists. Namely, it's a subset of the bigger set.

Axiom of Choice (v1.0): For any relation R, there is a function H ⊆ R with domH = domR.

I don't think I've ever really defined relations on my blog before, so let's patch that gap. A relation on a set S is any set of ordered pairs (x, y), where x and y are both elements of S. We say x is related to, or xRy, if (x, y) ∈ R. The domain of a relation is the set of all first coordinates; the range of the relation is the set of all section coordinates, and the field of a relation is the union of these two. In this language, a function is a special kind of relation. A relation is a function if for every element x in the domain, there is a unique y in the range so xRy.

We can verify that indeed the three conjuncts on the right hand side are the usual group properties-- associativity of the operation, the identity property, and the existence of inverses. We're a little fast and loose about this, but we also know that the set is closed under the operation. (For review, check here.) So now we have this string of symbols, but that's really all they are. Consider the set of symbols:

If we throw a bunch of elements of this set together, how do we know if the resulting sequence of symbols is meaningful? This is where we begin. Almost. First, some notation. Let A be a set. Then:

What we want to consider is SentP: the set of sentences over P, where P is a set of symbols (much like the one above). For now, say we have:

Except a bunch of those strings aren't going to be sensible, so we want to restrict SentP to only well-formed sentences. That is, only those sentences formed by the following rules:

Sentences formed by the first rule are usually called atomic. The second rule gives us a way to recursively define more complex sentences by combining the sentences we already have with some of the other symbols in P.

First of all, I want to start off with a pretty elementary definition of a set. A set is a collection of members, or elements. For every single mathematical object, it is either true that the object is in the set, or is not in the set. In other words, we can't have any wishy-washy flakiness.

Playing around with definitions: anyone who's done much math has probably encountered sets. And unfortunately I think the easier something is on the surface, the weirder it has the potential to get, because we're all just so comfortable with it we really don't think about it too hard. Here's something that happened in the textbook that kind of tripped me out.

Clearly, we all know what ∈ and ⊆ mean: x ∈ A means that x is an element of A. A ⊆ B means that A is a subset of B: so every element of A is also an element of B. What gets kind of weird is when we start trying to apply this stuff to sets. For example, A ∈ B is fundamentally different from A ⊆ B, of course. A ∈ B means A is an element of B. So we look for the entity A, and check if it's sitting inside B as a whole. Meanwhile, A ⊆ B means we check if every single element in A is an element of B.

Here are two examples, with the empty set (which is weird too). ∅ ⊆ ∅ since vacuously all the elements of the empty set are in the empty set. But ∅ ∉ ∅, since now we are checking if the set ∅ is in ∅; which it obviously is not, since ∅ is... well, empty. On the flip side, {∅} ∈ {{∅}}, but {∅} ⊈ {{∅}}, since ∅ ∉ {{∅}}. Think about it.

The other thing that we covered is Russell's Paradox, which is also kind of trippy but not too bad. Basically, the premise is this: we let the set R be the collection of all sets that are not members of themselves. Symbolically, R = {x | x ∉ x}. There are quite a few things that could belong to R. For example, {1} ∈ R, since {1} is not an element of {1}. But now we have a problem, since we cannot determine whether or not R is in R. If we put R in R, then R ∈ R, so R does not satisfy the condition to be an element of R, so it cannot be in R. But if we say R is not in R, then R does satisfy the required condition, so we must put R in R. The takeaway our professor gave us was (for now) to try and form sets where "we already have all the potential elements of the set", more or less.

A contour integral is a line integral along a piecewise smooth curve (with the usual rules for parameterization). Contours are called simple if they do not self-intersect and are called closed if they start and end at the same point. Note that we can bound the value of a contour integral above by the product of the length of the contour and the maximum value of the integrand along the contour. This fact will be exceptionally useful later (for improper integrals).

Hey look-- a result! Say we have a continuous function f on some domain (remember a domain is an open connected set), D, a subset of the complex plane. Then the following three conditions are equivalent:

contour integrals are independent of path

f has an an antiderivative, F, on D

integrals over closed contours are zero

Recalling that the usually way to show equivalence is to show mutual implication, we will prove 1 → 2 → 3 → 1. The first part is the hardest. If contour integrals are independent of path, then we can define F equal to the integral of f from z0 to z. I claim that this F will be an antiderivative, so let's consider a difference quotient of F at z, but only consider values of delta-z that keep us within D. Then parameterize a path from z0 to z + delta-z that first goes from z0 to z and then from z to z + delta-z. With these params, we can rewrite the numerator of the difference quotient in terms of integrals of f along these parameterizations. Using the (delta-epsilon definition of) continuity of f, you can then show that the difference quotient (aka the derivative) of F converges to f. Thus f has an antiderivative, F, on D.

So that was the really ugly part and I skipped a little bit by leaving the parameterization in the air, but it works out. These next bits should be super intuitive. Let's suppose that f has an antiderivative, F, on D. Now consider integrating f over a closed contour, pick your favorite parameterization for it, and let's say the contour is from z(t1) to z(t2). Since we have an antiderivative, we can evaluate the integral using the fundamental theorem of calculus as F(z(t1)) - F(z(t2)), but remember that a contour being closed means that z(t1) = z(t2) and so the integral is zero.

That was cool, right?! It gets even better. Suppose we have that integrals over closed contours are zero. Then choose any contour from z0 to z. Now choose any other contour from z back to z0. The path made by connecting these two contours is a closed contour and so the integral along it must be zero (by our supposition). Recalling from calculus that we can reverse the endpoints and switch the sign, we see that our contour integrals are equal, regardless of their path. Thus, contour integrals are independent of path.

So cool! And hey, while we're talking about integrals over closed contours evaluating to zero, our old friend Cauchy (and his friend Goursat) have something else to share. The Cauchy-Goursat theorem states that the integral of an analytic function along a simple closed contour is zero.

The proof of this is some algebra and some calculus so I will omit it, but the basic idea is:

parameterize the integrand

split the integrand into real and imaginary parts

split into two integrals (one real and one imaginary)

realize that you have u dx - v dy and v dx + u dy

apply Green's Theorem to get double integrals of partial derivatives

remember analytic means Cauchy-Riemann equations are satisfied

both integrands are zero and so the integral evaluates to zero

Cauchy's been working really hard so he has to go home right now, but when he comes back next time he wants to show off a fancy new formula. He claims that by disturbing an analytic function and deliberately creating a defect, he can use a carefully constructed singularity to read off the value of the original function at a given point. Somehow, he's found a way to integrate along a boundary and, based on a stone tossed in the pond, learn something about the pond at the place he threw the rock. Anyways, I need to go eat something so farewell for now friends~