7:38 AM

I keep thinking that the Friday Random Ten overrepresents how much Bach I have. I'm starting to think that maybe I have more Bach than I realize.

1. Amadeus Quartet/Cecil Aronowitz - Johannes Brahms: String Quintet #2, Op. 111, 1st Movement
2. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #90, "So Löschet Im Eifer:
3. The Sixteen Choir & Orchestra - Johann Sebastian Bach: Christmas Oratorio, BWV 248, "Und Liess Versammeln Alle Hohepriester"
4. Yo-Yo Ma/Kenneth Cooper - Johann Sebastian Bach - Sonata #1 for Viola da Gamba & Harpsichord, BWV 1027
5. Dream Theater - Lifting Shadows Off A Dream/Scarred
6. Pieter-Jan Belder - Johann Sebastian Bach, Anna Magdalena Bach Notebook, Menuet, BWV Anh. 114
7. Rush - The Seeker
8. Flanders and Swann - Vanessa
9. Queen - One Vision
10. La Stravaganza Köln - Johann Sebastian Bach: Orchestral Suite #2, Badinerie

0 comments

6:15 PM

Let's look at some examples of countable sets. Along the way, we'll develop some rules for countable sets in general.

By definition, a set X is countable if there exists a one-to-one, onto function from that set to the natural numbers. This means that countable sets are infinite. This also means that all countable sets are the same size, but the concept of size is misleading when it comes to countable sets.

For example, take the set of even positive numbers. If x is a member of this set, f(x)=x/2 is a function that maps to the natural numbers and is both one-to-one and onto. Therefore, the even numbers are countable, and the set of even numbers is the same size as the set of natural numbers.

The fact that both sets are the same size is somewhat counterintuitive. If we start listing off even numbers, the list begins 2, 4, 6, …. But the list of natural numbers begins 1, 2, 3, 4, 5, 6, …. In general, for any number n, there are n natural numbers less than or equal to n, but there are only n/2 even numbers less than or equal to n. At first glance, it looks like there are twice as many natural numbers as even numbers, so even though both sets are infinite, the natural numbers are twice as big.

This thinking would be valid for finite sets, but the fact that the sets are infinite causes this reasoning to go wrong. A better way of thinking about the problem is that for any number n, the number of points in the first n members of the set is always n. For example, the first 5 even numbers are 2, 4, 6, 8, and 10, and the first 5 natural numbers are 1, 2, 3, 4, and 5. Both sets have 5 members. Since both sets are infinite, we can count off through both sets like this, and the number of members of each set will always be the same.

Essentially, we add members, one at a time, to each set, and the members we add are specified by the function showing the relationship between the sets. We will never repeat numbers in either list (this is because the function is one-to-one), and we will eventually get to every member of each set (this is because the function is onto).

The striking thing here is that the even numbers are a proper subset of the natural numbers. (A proper subset is a subset which is not equal to the original set.) One property of infinite sets is that they have proper subsets which have the same cardinality as the set itself. This cannot happen for finite sets. Any proper subset of a finite set is (obviously) smaller than the original set.

Taking this a step further, we can prove that any infinite subset of a countable set is countable. All finite sets are smaller than all infinite sets. There may be infinite sets which are larger than countable sets (we'll come back to this later), but there are no infinite sets smaller than countable.

This has a useful implication. If we have an infinite set, and a one-to-one function from that set to the natural numbers, that function does not have to be onto in order to prove that the infinite set is countable. If it is one-to-one and the set is infinite, the range of the function is an infinite subset of the natural numbers. As a result of this theorem, the subset of the natural numbers is countable. The function is both one-to-one and onto that countable subset, and therefore the original infinite set is countable. When trying to prove that a set is countable, it may be easier to define a one-to-one function than a function that is both one-to-one and onto, and as long as the set is infinite, just being one-to-one is good enough to show that it is countable.

The topic this time was showing that infinite sets which look smaller than the natural numbers in fact have the same cardinality as the natural numbers. Next time we will look at sets which look larger than the natural numbers.

0 comments

6:53 PM

We can use cardinality to compare the size of different sets. Last time we discussed how to show that two sets have the same cardinality. This time we will look at three basic classes of cardinality. Sets can have finite cardinality, countable cardinality, or uncountable cardinality.

Finite cardinality is the most straightforward. Mathematically, take a set of natural numbers, such that the set includes every natural number less than or equal to some natural number k. Call this set J_k. For some set X, if we can define a one-to-one, onto function f which maps every member of J_k to every member of X, then J_k∼X and the cardinality of X is k. This is pretty much as simple as lining the members of X up in a row and counting them off. Finite sets are easy to understand and make intuitive sense.

My textbook (Principles of Mathematical Analysis, Third Edition, by Rudin) uses the word countable to mean countably infinite. On the one hand, this feels slightly misleading, since finite sets can obviously be counted. However, as I've been working with the concept, I think there are some good reasons for this, and I will use the same terminology to be consistent. A countable set is one which has a one-to-one, onto function mapping to the set of natural numbers. Since the natural numbers are infinite, countable sets are infinite. Infinity is deeply counter-intuitive, and the behavior of countable sets is therefore also deeply counter-intuitive. I plan to go into some detail on examples of countable sets, both to demonstrate that they defy expectations and in the hope that with enough examples, countable sets will start to make sense.

Finally, there are uncountable sets. These are sets which are infinite, but for which there does not exist a one-to-one, onto mapping to the natural numbers. Once countable sets start making sense, it may be reasonable to ask whether any sets are uncountable. We can demonstrate a way to contruct an uncountable set and prove that it's not countable, but we need to work on countable sets first.

0 comments

7:30 PM

Now that we can talk about functions of sets, and specifically whether the function is one-to-one, onto, both, or neither, we can compare the sizes of sets.

We can say that two sets have the same size, or that they have the same cardinality, if we can find a function that is both one-to-one and onto that maps from the first set to the second set. Symbolically, we can write the statement that X has the same cardinality as Y as X∼Y. Cardinality is an equivalence relation. That is, it obeys the reflexive, symmetric, and transitive properties.

The statement that cardinality is reflexive means that X∼X. This is one of those obvious statements that it's important to explicitly state, since sometimes obvious statements turn out to be wrong. We can prove it's true by defining the function f:X→X by f(x)=x for all x∈X. f is one-to-one and onto, so X has the same cardinality as itself for any set X.

Symmetry means that if X∼Y, then Y∼X. This is marginally less obvious that the previous statement. Since X∼Y, there exists a function f which maps X to Y and is one-to-one and onto. Since f is one-to-one and onto, there exists an inverse of f, f⁻¹, which maps Y to X and is also one-to-one and onto. Since f⁻¹ is one-to-one and onto, Y∼X.

Finally, the transitive property states that if X∼Y and Y∼Z, then X∼Z. If f maps X to Y and g maps Y to Z, then for any point x∈X, g(f(x)) is a point in Z. By following points back and forth through the functions, you can show that since both f and g are one-to-one and onto, g(f(x)) must also be one-to-one and onto. Therefore, g(f(x)) is a one-to-one and onto function that maps X to Z, so X and Z have the same cardinality.

0 comments

5:59 PM

Okay, now that we've looked at functions and inverse functions of sets and intersections, unions, and complements of sets, it makes sense to look at functions of intersections of sets (and the other combinations). The trick here is that functions of sets correspond to functions of points. To figure out what's going on with the sets, follow the individual points in the sets.

There are a pile of statements that look like identities involving functions of sets. It would be nice if the statements are true, but we would have to prove that first, and some statements that look like they "should be" true are not in fact true in general. For example, if f is a function that maps the set X to the set Y, and A is a subset of X and A^c is the complement of A, is it true that f(A^c)=[f(A)]^c? Unfortunately, no. If f is not onto, then f(X)= the range of f, which is a subset of Y but not equal to Y. So [f(X)]^c is every point in Y that is not in the range of f. But X^c=∅, so f(X^c)=f(∅)=∅. Therefore, they are not equal.

In addition, if f is not one-to-one, then the equality also doesn't hold. Choose a point y in Y such that for two points a and b in X, f(a)=f(b)=y, but a≠b. Then choose a subset A of X that includes the point a but not b. Then f(A) includes the point y, but f(A^c) also includes the point y, so f(A) cannot be the complement of f(A^c).

However, if f is both one-to-one and onto, then the equality does hold. Given a set A⊂X, choose any point y∈Y. Since f is onto, there exists a point x∈X such that f(x)=y. Since f is one-to-one, x is unique. If x∈A, then f(x)=y∈f(A). If x∉A, then f(x)=y∉f(A). If x∉A, then x∈A^c, and if y∉f(A), y∈[f(A)]^c, so f(A^c)=[f(A)]^c for any A⊂X.

But let's look at inverse functions. If x is a point in the set X, and A is a subset of X, and f is a function that maps X to the set Y, f(x) is a point in Y and f(A) is a subset of Y. If y is a point in Y and B is a subset of Y, f⁻¹(y) is only a function if f is one-to-one and onto, but f⁻¹(B) is always a function. So let's look at f⁻¹(B^c).

Choose any point x in X. Then there is one point, y, in Y such that f(x)=y. y is either a member of B, or it is a member of B^c. If y is a member of B, then x is a member of f⁻¹(B). If y is not a member of B, then x is not a member of f⁻¹(B), and is therefore a member of [f⁻¹(B)]^c. Also, since y is not a member of B, y is a member of B^c, so x is a member of f⁻¹(B^c). Therefore, [f⁻¹(B)]^c=f⁻¹(B^c).

I won't go through the details here, but the same types of reasoning apply for unions and intersections of sets in X and Y. Take λ as an index of a collection of sets. Then A_λ is a subset of X for each λ. (From the discussion of indexes last time, the possible values of λ do not have to be organized.) Then, using the same type of reasoning as with complements, we can prove that f(∪A_λ)=∪[f(A_λ)] and f⁻¹(∪B_λ)=∪[f⁻¹(B_λ)].

A couple of posts ago, I introduced some definitions that will be useful here, so as a reminder, if B=f(A), we can call B the image of A, and if A=f⁻¹(B), we can call A the preimage of B. Then in words (math jargon words, but words nonetheless), the first statement is that the image of a union of sets is equal to the union of the images of sets. The second statement is that preimage of a union of sets is equal to the union of the preimages of the sets.

Looking at intersections, we can show that f(∩A_λ)=∩[f(A_λ)] only if f is one-to-one. The image of an intersection of sets is only equal to the intersection of the images if f is one-to-one. You can verify this by taking a simple function f which is not one-to-one, so two different values in X map to the same value in Y, and defining some subsets of X where the equality does not hold. However, once again, f⁻¹(∩B_λ)=[∩f⁻¹(B_λ)] for any f. The preimage of an intersection of sets is always equal to the intersection of the preimages of the sets.

The conclusion here is that we can switch the order of operations for preimages and for complements, unions, or intersections, but we can only generally switch the order for images with unions. In this sense, preimages are more powerful than images.

0 comments