Saturday, March 03, 2007

Maths part 5- sets and counting

So, let's recap. We have our numbers- the naturals, the rationals, the reals, and the complex numbers, and we have our functions. To reiterate functions, they just tell you what to do to a number. Give me a number x (which can be 1, 4, pi... whatever you like), and I'll look at my function, do something to it, and give it back to you.

So next we need to look at sets. A set is simply a collection of objects. For example, the collection of all star signs is a set, as is the collection of people you'd rather jump off a bridge than sleep with. When I am talking about sets though, I will generally be talking about a collection of numbers. This set can be infinite- the natural numbers compose of a set... the set of all natural numbers. Note here that the notion of a set is just a conceptually useful concept, theres nothing particularly special about it, although it is worth noting that sets don't have repitition- it won't have 1 twice, for example.

Generally sets are written with these curly brackets {N}, for example, or {1,2,4,7,9}. They can also be empty too- we call such a thing the empty set, it's a useful concept to have.

See, sets aren't too scary (although I have skipped various notions for clarity).

Now I get to talk about counting. Counting is vital to an understanding of infinity. That is, an understanding of counting anyway. Suppose I have a deck of cards, and want to see if it has the requisite 52 cards in it. How do I count it? Well I can do it the usual way, but I am a fallible creature after all, and might miss count at some point. Another way to do it would be to get a deck we know has 52 cards (perhaps we went through and numbered each card). Now all we have to do is make sure there is a card to match with each of the cards from our original deck. If they all match up, we know our original deck has 52 cards. This is actually what you are doing when you are counting- you are attempting to assign all 52 numbers to an individual card.

We can translate to the concept of a "bijection". A bijection between two sets exists if we can find a function between those two sets that is both injective and surjective.

Those are some scary words, but conceptually all we are doing is what I described above. An injection says that for every element in our first set (call it A), we can assign it to a unique element in our second set (B). So in our pack of card examples, if we only had 51 cards, we would have one number left over- it would have nowhere to go to, so we would have to assign it to the same card as another number. Notice that if we had 53 cards we would be able to assign each number to it's own card... there would be one card left over, but it wouldn't matter- we would have created an injection.

So an injection by itself is not a strong enough concept to describe counting. We have a surjection, which says that for every single element of B, there exists an element of A assigned to it. In our card example, if we have 53 cards, then we only have a number available for the first 52 cards... one card is left over, so we do not have a surjection. However, if we have 51 cards, there will certainly be a number for each card, so we will have a surjection.

So you see that if we have an injection, we know we have at least as many cards as we have numbers, and if we have a surjection, we have at least as many numbers as we have cards. This traps us to saying we have exactly as many numbers as cards.

Now the mathematical versions of an injection and a surjection are a bit more... well mathsy, for example we have an injection if f(x)=f(y) implies x=y, but it describes exactly what we were saying.

Well, now we have a tool to see if two sets have the same amount of elements. Thats kind of useful, but in finite sets it's not terribly exciting. The beauty of the way we have set up our definitions is that there is nothing to stop us using them on infinite sets. So finally we can talk about infinity! Next time anyway......


Post a Comment

<< Home