herp, derp, math nerd

no really... just shut up miss rowan

[whatilearninmath]

some rambling about asymptotics

part 5 of statistics (toc)

So we continue with the probability that is pretending to be statistics that is presented on a math blog. What is even happening?

Right off the bat, maybe I should say I think this post is going to just be all over the damn place. Honestly, at the time of writing, I have my midterm tomorrow, I'm not wearing pants, and I'm both full and hungry at the same time. Maybe you should reevaluate whether you should be reading a math blog written by a weirdo.

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?

Of course, we still have one small problem: the central limit theorem makes use of the population variance in its description of the asymptotic distribution of the sample mean. A lot of the time, we don't have the variance of a population. Ah--well, just like we can use the sample values to guess at the population's true mean, we can use the sample values to guess at the population's true variance. Is that enough of a cliffhangery teaser? (Probably not...) In any case, I'll try to tackle estimation next time, and hopefully I'll be wearing pants too.

[whatilearninmath]

convergence concepts with random variables

part 4 of statistics (toc)

So it's been a while... is this blog even mine any more or has it been lost to the ether, doomed to a life of internet dust bunnies and neglect?

I really apologise for the lack of content--as I may have mentioned, I didn't take any math classes in the last semester of my undergraduate degree (opted for French instead...) but now that my graduate program has started, I again have so much stuff to learn and procrastinate from writing about...

I know I've facetiously denounced the place of statistics in math before, and I still hold the opinion that statistics doesn't really belong in math. But let me be 100% clear right now: statistics doesn't belong in math in the same why physics doesn't belong in math. While they are both heavily rooted in, and make extensive use of, math... they are both independent subjects with their own qualities and questions. To put them under the category of math would be a minimisation of their independence and fullness as their own separate topics.

With all that said...let's just talk about some statistics on the damn math blog, ok? (To be perfectly accurate, this post is actually probability instead of statistics...but we'll get there sooner or later.)

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.

I know this post was very definition-dump-y but hopefully I got some insightful comments in there (or maybe it was just a load of waffle). In any case, I think this stuff is pretty cool. I remember disliking statistics/probability when I took the course in high school, and again when I took the introductory version in undergrad. The problem with those kinds of classes are that they are very "cookbook"--they show you the methods of calculating things without really going through the underlying reasons for why these methods work! In the end, classes like these ones feel like a lot of memorisation and not a lot of thinking--and, worse, really important and profound results just sound like another line from the textbook to memorise. I guess since some smart people already did the legwork to come up with these methods, it doesn't make much sense to teach the theory to people who are only going to need to use these concepts practically. But of course, as someone whose head is constantly in the clouds, it's a lot more interesting for me to see under the hood with these kinds of things. You really get to appreciate the results once you see how much work is needed to produce them. Probability and statistics, like I said, have deep roots in math, and the farther down you go, the more interesting it gets (in my opinion). Thankfully, I'm taking a class that's more on the theoretical side, and so hopefully I will have some more insights as the class goes on. But for now...my midterm revision sadly beckons!

[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).

[whatilearninmath]

results for ordinals

part 10 of set theory (toc)

Ordinal numbers are weird, man. And they breed themselves.

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).

(Thanks zuven for catching a typo.)

[whatilearninmath]

infinity + 1

part 9 of set theory (toc)

Let's get cracking on ordinals. No time wasted or lost.

Enderton introduces ordinal numbers as a way to measure the "length" of a well-ordering, just as cardinal numbers were a way to measure the "size" of an arbitrary set.

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??

(Playlist for this post: a whole lot of Armin van Buuren.)

[whatilearninmath]

Hey errboday. If anyone’s wondering about the girl behind this blog, or if you want to get to know me a bit better, here is my personal tumblr (:

Dun wry though. The math posts will resume their original programming shortly. No fear!

[whatilearninmath]

reblog, since I have gained a substantial number of followers since the inception of this blahg. I’d also love to learn more about my followers! leave me an ask or something in one of my inboxes (:

(say anything you want… why you like math, your favourite tv show, if you like ponies, what your favourite cheese is… the possibilities are endless!)

[whatilearninmath]

working with cardinals

part 8 of set theory (toc)

And we go a-blazin forward, on the trail of set theory catchup.

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!

Hopefully I'll start defining the infinite cardinals or get cracking on ordinal numbers next time. See y'all on the floopsood, home skillets.

[whatilearninmath]

debts paid in set theory

part 7 of set theory (toc)

So I submitted five graduate school applications yesterday. That $100 application fee per university hurts, man. I'd been working pretty much exclusively on my thesis up until this point, getting it presentable enough to submit with my applications. No doubt I will need to polish it more, but it was good enough to be sent in. So now I'm playing catch up with my classes, especially set theory.

I've basically lagged behind for two chapters, which are cardinals and ordinals. I think I will probably do at least two posts on each chapter. The notions are related, and (in very broad terms) can be thought of as two different ways of dealing with infinity. Proofsareart has a brief discussion here. Going along with this kind of parallelism, my professor structured the material so that we'd learn something about cardinals, then the similar thing about the ordinals, and so on, so we kind of straddled the two chapters at once. I appreciate him kind of suggesting the similarity this way, but I found it kind of confusing to constantly be switching paradigms, in a way. So I think I'll just keep them separate and do cardinals first, then ordinals. Maybe if I can be bothered, I'll remark on some links between the two along the way.

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.

Sweet. The ball is rolling on catchup. Hopefully I will feel like I'm on more secure footing soon. Until later, xoxo.

[whatilearninmath]

a quick exposition on transitive sets

part 6 of set theory (toc)

Meant to do this post ages ago. Forgot. #sorrynotsorry

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.

I think this post might be the shortest post I've ever done. Don't worry, the next one is a beast of a post. Ciao bellas.

[whatilearninmath]

the four things you need to pass a set theory class

part 5 of set theory (toc)

So several people have been on my case for not posting enough. All right, you caught me. But I've been really overwhelmed with my imminent graduation, graduate school applications, and my research... but, hey, time's a-wastin' and you aren't here to hear me complain.

So my set theory professor has a qualifying exam that every student must ace in order to pass the class. And I'm serious about acing. I forgot the exact mark you need to get, but I think it's somewhere north of 95%. It's pretty fair though, because we are told in advance exactly the flavour of questions we're going to get. Well...if he's emphasising these things so heavily, they must be important. Onto the blog they go.

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.

I apologise again for the dry spell and this relatively short post. To be honest, I'm not sure I have an incredibly solid footing when it comes to the later material we've done in this class. I've also been unfortunately preoccupied with a whole lot of other stuff that's gone down in my life. When I have time to sit down and really review set theory, I will definitely be using my blog to do some of the legwork. Look forward to it (or not). Until next time, chicas.

[whatilearninmath]

I'm all about construction

part 4 for set theory (toc)

At this point I'm convinced it isn't a math class unless you construct some sort of number system. Reals from rationals in analysis, rationals from integers in algebra, and now the natural numbers from... well, from literally nothing at all. Construction ain't so bad, although I've seen a lot of hype for wrecking balls lately too...

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.

Who thought counting could be so complicated? But still, going back to the basics is always an oddly mind-boggling experience. Thinking about how people in the past constructed the axiomatic framework that we use today, and foregoing alternative definitions and axioms, is pretty unreal. As much as math is found in nature, the human choices and progess we've made with making it rigorous has also been pretty impressive. (Not sure you agree? Check out the history behind the definition of a compact set.)

[whatilearninmath]

hark! a midterm approaches!

part 3 of set theory (toc)

Super super quick thing. Interesting problem on this week's homework.

PDFed. Here it is.

[whatilearninmath]

The most common formulation of the axiom of choice is: for any set S, there exists a function whose domain is the set of non-empty subsets of S and such that for all X ⊂ S, f(X) ∈ X. Such a function is called a choice function for obvious reasons: for all X, it "chooses" an element of X as its value f(X). The controversy (which is much less fierce nowadays than it used to) arises only when S is infinite: then the other axioms do not provide a way to construct a choice function.

as always, thank you (:

[whatilearninmath]

STARTED FROM THE BOTTOM NOW I'M A SET

part 2 of set theory (toc)

I literally can't deal with set theory right now. My brain wants to explode. Here, have some set theory.

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.

This statement of the axiom says that given a relation which is not necessarily single-valued, i.e. not necessarily a function, we can construct a function from the relation by just picking values for domain elements that are associated with more than one value in the range. I was obviously a little surprised the book just threw in the axiom of choice so cavalierly, since it's had its fair share of controversy. Regardless, the fact that it was introduced as Axiom of Choice, first iteration, suggests we will be seeing more of it soon. 

[whatilearninmath]

If she weighs the same as a duck..

part 1 of logic (toc)

This is probably my last year as an undergrad as well (!) but I'm trying cram a lot in. Since Set Theory already has an initial post, I think I'll start in on some of the first notes for the other math class I'm taking this semester which is Mathematical Logic. Some of the goals of this course are to:

Provide a foundation for mathematics;

Define a language for mathematics;

Define a notion of mathematical truth; and

Define what a proof is.

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.

Next time, we'll look at generating a closure and the Principle of Induction! For now, this is all the sentences I have to share.

[whatilearninmath]

beginning the mindwarp

part 1 of set theory (toc)

Hello everyone, and welcome back to my final (!) year of undergrad. I'm only taking one math class this semester because of my other major, and that class is set theory. I can already tell this class is going to be really confusing if I don't try and keep things straight from the outset.

Anyways, what better way to ease back into the whole writing-about-math thing than doing one of those elusive short and sweet posts? Here are two weird things from set theory that have already happened so far...and we've only had one day of class!

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.

Anyway, those starting school again, I wish you an easy first few days back. If someone asks you if you are a freshman (despite being older than them), resist the temptation to point out that you are not wearing your ID around your neck. Rock on, cool kids.

[whatilearninmath]

Ready to take some prisoners sightseeing? We're doing con-tours!

part 4 of complex analysis (toc)

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~

[PS: Let me know if you have any suggestions on improving my writing!]