Infinity is a topic which is generally rather hard to grasp. Our world does not readily provide anything infinite for us to study in the Sciences. Indeed, if some structure was infinite, we would not be able to study it fully; indeed, we would not be able to find all its edges. It would have no shape, no measurable volume, no mass, energy or velocity which we would be in any way able to comprehend. And yet, in mathematics, the idea of infinity can actually have meaning, which shows that our imagination is not solely confined to the extent of our experiences. More than that, infinity can actually help us understand the finite physical, chemical, biological etc. structures with which scientists deal all the time. Infinity helps us understand sequences, which in turn helps in the understanding of limits, giving rise to the ideas of calculus, on which most contemporary Science and Engineering methods rely.
So, what is infinity? In general, we often treat it as a number. We may put it in the limits of a sum, a product or an integral, we may even give it as the result of these things. However, infinity is not, in fact a number. (This assertion is true in the reals. There are formal systems, like the hyperreal numbers, where infinity is a number. These systems are not what I am talking about here.)
Probably the most important work on infinity was done by Georg Cantor, when he formalised the ideas of infinite sets. Indeed, the best way to think of infinity is as a measure of the elements of an infinite set. As for finding such an infinite set, this is simple. We can simply take the positive integers (also known as the natural numbers), 1, 2, 3... and so on. We call this set N and consider the number of elements it contains. Obviously, it cannot be empty, as it contains the number 1. It cannot have only 1 element, as it contains the numbers 1 and 2. Similarly, it cannot contain only 100 elements, as every number from 1 to 101 is in N. For any positive integer we think of, we can find that many elements in N, and more. This is the very idea of infinity: something that is not bounded, which is larger than any number.
As we can see, this set of the natural numbers is infinite, in that it has infinitely many elements. Naturally, this means that any set which contains the natural numbers and others as well (a "superset" of N, as it is called) would also be of infinite size. We can take, for example, the set of all integers, Z. This includes the natural numbers (since they are the positive integers), as well as the negative integers and zero. Intuitively we can see that this must be a bigger set than N. Unfortunately, our intuition is wrong. When it comes to infinite sets, the only way to decide if Z is larger than N is to examine whether a bijection (one-to-one and onto function) exists between the two sets. If such a function can be found, then automatically the sets must have the same "size". Note that the natural numbers are essentially the numbers we count with, 1, 2, 3 and so on. So, finding a bijection between Z and N is the same as finding some way of listing all the elements of Z, without missing any, in a certain order. If such a sequence exists for Z, then Z and N have the same "size". This sequence is extremely easy to come up with: 0, 1, -1, 2, -2... and so on. Obviously this ordering will go through every single integer, much in the same way that 1, 2, 3... goes through every natural number.
The above shows us that Z has, in a sense, the same number of elements as N. Except that, as they both have infinitely many elements, we are not really talking about a number of elements. Because of this, the idea of cardinality was formulated. Cardinality can be thought of as the size of infinite sets, like the naturals or the integers. so, our example above shows that in fact both N and Z have the same cardinality, even if one is a subset of the other. This is a very important concept; infinity does not behave in the same way that other numbers do. Cutting infinity in half or doubling it does not actually change its size at all.
At this point one might think that all infinite sets must have the same cardinality as the natural numbers. After all, it should be easy to find a sequence that lists all the elements in a set. This is often the case; sets like the rational numbers, the algebraic numbers, the set of polynomials with integer coefficients and so on are certainly all countable (i.e. have the same cardinality as N). But there are sets which are actually much larger. The set of real numbers is actually uncountable. Any attempt to make a comprehensive list of all the reals, will result in failure. Indeed any such list can be shown to be missing some real numbers (in fact, an infinite amount of them). The proof for this uses a rather elegant method devised by Cantor, known as Cantor's diagonal argument.. I do not propose to present it here, as it is readily available online in other places. However, it should be clear from all this that the subject of cardinalities and the nature of infinity is one with a lot of substance.
Saturday, July 28, 2012
Wednesday, July 25, 2012
Group Theory
This post will assume some fundamental knowledge of Set Theory, as well as Functional Analysis. Only the basic ideas, e.g. what a set is, what functions are, what a bijection is, and so on are required.
Ideally, I should have titled this post "Algebra", however I hesitate to do this, as there are many misconceptions about what algebra actually is. In middle-school people learn it informally as equations with letters replacing some of the numbers. In fact, algebra is the study of relations between mathematical objects.
A group G is a set which has a built-in binary function, F(x, y). This function takes two elements from the set and returns one element from the set. This property is known as closure and is one of the requirements for a group. The other properties a group must have, with respect to its binary function are:
1) An identity element. This is an element e for which F(e, x) = F(x, e) = x. Think of this as the number 0, when we add integers. 0 + x = x + 0 = x, for any integer x. Note that the identity element is unique.
2) Inverses. Every element of the set must also have an inverse in the set. Two elements a and b are inverses of each other if F(a, b) = F(b, a) = e, where e is the identity. This is similar to the negative of a number. When adding integers, x + (-x) = (-x) + x = 0. Note that each element has a unique inverse. This includes the identity, which is its own inverse.
3) Associativity. Using the addition example, this means that (a + b) + c = a + (b + c). That is, the order in which the additions are carried out does not matter; whereas the order of the elements added does.
The last part may seem strange, in light of the addition example. After all, 2 + 3 = 3 + 2 = 5. The order is irrelevant! This is, in fact, not the case, with more general groups. For example, if we take the set of 2x2 matrices with non-zero determinant, under normal matrix multiplication, they form a group. But in this group AB is not equal to BA. The order of the elements added (or multiplied) matters in many groups. The groups for which a + b = b + a are known as abelian groups; the integers under addition are such a group.
Having read all these rather abstract notions which define a group, one may ask what the point of Group Theory is. Why should it be a field of study, when it seems so disconnected from anything which can relate to the experience of our senses? In fact, the same question could be asked of most high-level fields of Mathematics, and the answer will roughly be the same. There are in fact three reasons to study Group Theory, or indeed any sort of Mathematics. The first is because of the applications they have. With Group Theory these may not be readily apparent, however modern Physics, Chemistry and Cryptography rely on the study of Group Theory. The second reason is that we humans have a natural curiosity and a tendency to look for patterns. In many ways, the study of Mathematics in general and Algebra in particular is the study of patterns. The third reason is that mathematical study helps one develop a rational way of thinking. Abstracting problems into mathematical models is the only way which has been discovered so far, which is consistently successful in solving said problems.
Ideally, I should have titled this post "Algebra", however I hesitate to do this, as there are many misconceptions about what algebra actually is. In middle-school people learn it informally as equations with letters replacing some of the numbers. In fact, algebra is the study of relations between mathematical objects.
A group G is a set which has a built-in binary function, F(x, y). This function takes two elements from the set and returns one element from the set. This property is known as closure and is one of the requirements for a group. The other properties a group must have, with respect to its binary function are:
1) An identity element. This is an element e for which F(e, x) = F(x, e) = x. Think of this as the number 0, when we add integers. 0 + x = x + 0 = x, for any integer x. Note that the identity element is unique.
2) Inverses. Every element of the set must also have an inverse in the set. Two elements a and b are inverses of each other if F(a, b) = F(b, a) = e, where e is the identity. This is similar to the negative of a number. When adding integers, x + (-x) = (-x) + x = 0. Note that each element has a unique inverse. This includes the identity, which is its own inverse.
3) Associativity. Using the addition example, this means that (a + b) + c = a + (b + c). That is, the order in which the additions are carried out does not matter; whereas the order of the elements added does.
The last part may seem strange, in light of the addition example. After all, 2 + 3 = 3 + 2 = 5. The order is irrelevant! This is, in fact, not the case, with more general groups. For example, if we take the set of 2x2 matrices with non-zero determinant, under normal matrix multiplication, they form a group. But in this group AB is not equal to BA. The order of the elements added (or multiplied) matters in many groups. The groups for which a + b = b + a are known as abelian groups; the integers under addition are such a group.
Having read all these rather abstract notions which define a group, one may ask what the point of Group Theory is. Why should it be a field of study, when it seems so disconnected from anything which can relate to the experience of our senses? In fact, the same question could be asked of most high-level fields of Mathematics, and the answer will roughly be the same. There are in fact three reasons to study Group Theory, or indeed any sort of Mathematics. The first is because of the applications they have. With Group Theory these may not be readily apparent, however modern Physics, Chemistry and Cryptography rely on the study of Group Theory. The second reason is that we humans have a natural curiosity and a tendency to look for patterns. In many ways, the study of Mathematics in general and Algebra in particular is the study of patterns. The third reason is that mathematical study helps one develop a rational way of thinking. Abstracting problems into mathematical models is the only way which has been discovered so far, which is consistently successful in solving said problems.