In this thread, we are going to construct some numbers. We all have some practical experience counting and measuring things, so we'll want our formal construction to match this experience in such a way that using the numbers we construct abstractly to do the same counting and measuring we've done will give us the same experience.
We'll count before we try to measure. Let's begin by assuming we're comfortable with the idea of a single, physical object in our hands; I've just taken a cigarette from the packet next to me, and I am holding it. In a way that, for the moment, we will take to be deeply intuitive, I understand that I am holding a single cigarette. Perhaps you're becoming uneasy about my deeply held intuitions; you probably have the same intuitions, but you wanted to construct numbers mathematically, and you may be feeling slightly, although probably not very, cheated at the moment. This is a good thing.
In a display of blatant disregard for personal space hygienics, I have started removing cigarettes from the packet and placing them on my desk. I do this in such a way that I place each one on the desk before retrieving another from the packet, so that sometimes I am not holding cigarettes, and sometimes I have the deeply felt intuition about oneness, but I never have any other number-experience. Each time I put a cigarette on the desk, though, I say one of the number-words I learnt as a child, which I learnt in a special order: "One, two, three, four, five, six, seven, eight".
At this point, there are no cigarettes left for me to take, and each cigarette on my desk corresponds to a unique word in my number-language, so I make a bit of a leap and conclude that the final word I uttered measures, in some way, "how many" cigarettes I have: I have exactly enough cigarettes to repeat the oneness intuition for each of the words "one, two, three, four, five, six, seven, eight". According to an ancient convention, this situation is called having eight cigarettes.
In the above counting process, I paired the objects to be counted with members of a set of concepts in my mind. This part of the counting process is not especially troubling; it's equivalent to, say, placing each cigarette on my desk next to a different penny. The conclusion of my counting is a bit more troublesome; what I've really done is defined the idea of "how many" by noticing how far I can go in my number-language with this pairing before I run out of cigarettes. To see why this is troublesome, suppose I had paired my cigarettes with pennies rather than number-words. I'd know I had a penny for each cigarette and vice versa, but I'd then wonder "how many" pennies I had.
Counting seems like a promising approach to numbers, but we're going to need to get rid of the "how many" ambiguity, and we're going to do this by transporting the ambiguity elsewhere, to somewhere were it is more palatable.
It's time for a small digression on sets. A full discussion of set theory is not really necessary here, but we'll need a few ideas. It's hard to find sources on sets which don't draw most of their examples from other maths, which doesn't seem to be what you're looking for, but I've stuck a few links on the bottom of this post.
One of the first people to consider sets sensibly was Georg Cantor, and he defined a set to be:
"any collection M of definite, distinct objects m of our perception or of our thought (which will be called the elements of M) into a whole."
Thus the totality of my cigarettes in the previous post constitutes a set, and the individual cigarettes are elements of the set. Likewise, the pennies are elements of the set of pennies on my desk. Any penny or any cigarette on my desk is an element of the set of pennies and cigarettes which are on my desk, and also of the set of pennies and cigarettes on Earth, and also of the set of things which are harmful if inhaled, etc.
The above examples suggest a powerful way of defining sets, which we'll introduce using a little notation. First, let the symbol ":" mean "such that". The symbol "{}" with some things inside it means "the set of". Putting these together, we can write sets as:
{x : some statement about x}
In words, the above means "the set of all objects x such that the statement about x is true". We might write {x : x is on my desk} for the set of things on my desk, and this unambiguously determines this set; a set is defined exactly by what its elements are. It would be instructive to construct a few more examples of sets in this way, to see how it works and what sort of statements are able to unambiguously define sets.
Tomorrow, I'll post about subsets and functions, after which we'll be able to construct (DUN DUN DER!) the natural numbers, with which we can count. I'll also talk about where the ambiguity mentioned before has been banished to.
I'm sure this is not a very well-written exposition so far, so ask for clarification wherever required.
Originally posted by ChronicLeakyYou need to get out more!!
It's time for a small digression on sets. A full discussion of set theory is not really necessary here, but we'll need a few ideas. It's hard to find sources on sets which don't draw most of their examples from other maths, which doesn't seem to be what you're looking for, but I've stuck a few links on the bottom of this post.
One of the first peop ...[text shortened]... l-written exposition so far, so ask for clarification wherever required.
Originally posted by ChronicLeakyIt's all good so far. Comprehensible and amusing. The set notation is satisfying. I might have learnt it before, but to all intents and perhapseses my mind is a shaved slab.
I'm sure this is not a very well-written exposition so far, so ask for clarification wherever required.
Originally posted by Bosse de NageExcellent.
It's all good so far. Comprehensible and amusing. The set notation is satisfying. I might have learnt it before, but to all intents and perhapseses my mind is a shaved slab.
(@ Noodles: True. Hopefully I'll rectify this in a bit.
@ mancityboy: Your knuckles are dragging again. If you use your hands to wipe the drool off your chin, you'll solve both problems.)
Anyway, subsets and functions. Given a set, we can sometimes come up with a statement that defines another set, all of whose elements are elements of the first set. In this case, we say the second set is a subset of the first one.
Next, given two sets called X and Y, we can form the so called "Cartesian product" of them, which is denoted XxY and is defined by:
XxY = {(x, y) : x is an element of X and y is an element of Y}
By "(x, y)" we mean a pair of elements, in the specified order. The Cartesian product is just the set of all such ordered pairs*.
A function, called F, "from a set X (which is called the domain of the function) to a set Y" is a subset of the Cartesian product XxY with the requirement that if x is an element of X and (x, y) and (x, w) are elements of F, then y = w. A little reflection shows that we can think of F as being a way of choosing, for each x in X, a unique element of Y. Notice that nothing says we can't have two elements of X which associate with the same element Y, but we can't have a single element of X associated with more than one element of Y. If F is a function from X to Y, we write F:X-->Y, and if y is the element of Y associated with some element x of X, we write F(x) = y. Now, not every element of Y need be the result of applying F to elements of X. In general, if we took every element x of X and looked at which element of Y it associates with, we'd get a subset of Y, which is called the "image" of X and is denoted F(X).
Finally, three words. If a function F:X --> Y is such that F(X) = Y, ie every element of Y is the result of applying F to some element of X, we say F is "surjective".
If every element in the image of X is the result of applying F to a single element of X, we say F is "injective".
If F is both surjective and injective, we say F is "bijective". This is the one of our three words we'll use most, and it simply means that F associates each element of X with a different element of Y, and every element of Y is the result of applying F to some element of X -- a bijective function puts X and Y in one-to-one correspondence.
That's a lot of unmotivated jargon, but it's the last such litany of jargon we'll need for now, and once you've acquired some familiarity with it, things will be a lot more like cigarette-counting from now on. Any later litanies of jargon will be formalisations of things you'll have already thought of by having the discussion.
As always, if anything's unclear, fire away.
*If you're uncomfortable with the notion of the elements x and y being in a specified order, there is an alternative definition. If we let {x} be the set (a subset of X) whose only element is x, and {x, y} be the set whose only elements are x and y, we can define the pair (x, y) to be a set of sets, namely (x, y) = {{x}, {x,y}}. We then say "x is the first element in the ordered pair" if and only if x is an element of every set in the pair. We say "y is the second element in the ordered pair" if not. If you weren't unhappy with the idea of the order to begin with, ignore this.
Originally posted by Bosse de NageFirst of all, stocken, cheers for reading and for the kind words. You're welcome to chime in anytime.
All right. I am having fun so far. Serve up some more, please.
Next serving:
We're going to build a set in a funny recursive way. First of all, suppose we have a set, which we'll call N. Let's also stipulate that N has, at minimum, an element, which we'll call x.
The real step is to suppose that we have a function, say f, whose domain is N and whose image consists of every element of N except x (we denote this set N\{x} and it is {y : y is in N and y is not x}). Furthermore, we are going to stipulate that f:N --> N\{x} is a bijection.
Now we're going to construct a set called N' whose elements are certain subsets of N. Start with x. Put the set {x} (not the element x) into the set N'.
Since f(x) is, by definition, an element of N\{x}, f(x) is not equal to x.
[Insert digression from the bottom of the post here.] Thus we can safely conclude that {x} and {x, f(x)} are two distinct sets. Put {x, f(x)} into N'.
Now consider f(f(x)). Since f maps everything in N to something in N\{x}, which does not contain x, it cannot be that f(f(x)) = x. Also, if f(f(x)) = f(x), then since f is an injective function, x = f(x). We just saw that that's impossible, so f(f(x)) must be different from f(x) as well. Thus the set {x, f(x), f(f(x))} contains none of the redundancies mentioned in the digression at the bottom of the post, so it's different from everything else we've already put into N'. Thus we put it in, too.
At this point, we have two things. We have a set, N', which contains {x}, {x, f(x)} and {x, f(x), f(f(x))}. We also have an instance of an element of N\{x}, namely f(x), which is not equal to its image, f(f(x)). This last fact is the central feature of what we're doing. The first fact is part of our filing system for keeping track of this mess.
Suppose we have some instance of the second fact, ie some y in N\{x} such that f(y) is different from y. We know that this can be done in at least one case (the case we just dealt with), so we're not making any silly suppositions. Then, since f is injective, f(f(y)) = f(y) would imply that f(y) = y, a contradiction. Thus, we know that given a situation where f(y) and y are different, f(f(y)) and f(y) must be different.
On the other hand, we know that everything in N\{x} is the image of something under f.
If we continue the process we started above, considering f(f(f(x))), f(f(f(f(x)))), etc, we will therefore enumerate all of N. Remember that as we performed this iteration before, we made a set and put it into N'. As a shorthand, given any y in N, we'll call the set we put into N' when dealing with f(y) "fy".
For example, {x, f(x)} is called fx, {x, f(x), f(f(x))} is called ff(x). The considerations above show that when we come to consider any f(y), ff(y) will be a set not already in N'. ff(y) consists of all elements of fy, together with {x, f(x), f(f(x), f(f(f(x))), ... f(y), f(f(y))}.
The elements of N' are the set {x} and the sets fy, for each y in N\{x}.
Now we will define a way of relating the elements of N'. If fy and fz are elements of N' (remember fy and fz are sets), then we say "fy < fz" is we can find a bijection between some subset of fz and the whole of fy. We say "fy > fz" if fz < fy. If fz < fy and fz > fy, we say fz = fy. Notice that since, for all y, fy is a subset of ffy, which is a subset of fffy, and so on, we can always say, given any two elements of N', which of these relationships holds. In other words, N' is a set in a specified order...
(technically, we say '' < '' is a "total ordering relation" on the set N', although a little reflection shows us that it's just set inclusion -- subsetness -- in fancy dress).
We call N' the set of "natural numbers". For convenience, we call {x} "1", and {{x}, {x, f(x)}} "2" and so forth. If we've used our number language to call some element fy of N' "n", we call ffy "n+1".
If we have some random set S (of cigarettes, say), we "count" the elements of S by finding the unique element fy of N' such that there exists a bijection between S and fy. If we succeed, we take whatever number-word we associated with fy and use it to tell how many elements S has.
For example, is S = {cigarettes on my desk the other day}, I could say "I have four cigarettes on my desk" and mean "there is a bijection from S to the set {{x}, {x, f(x)}, {x, f(x), f(f(x))}, {x, f(x), f(f(x)), f(f(f(x)))}, which is an element of N'".
If we can't find an fy in N' for which there is a bijection from fy to S, we say S is "infinite". This is a situation of unspeakable bliss if S is still defined as in the previous paragraph. If, however, we can find a bijection from S to the whole set N', we say S is "countably infinite". If we can't even do that, we say S is "uncountable" (I can't conceive of an uncountable set of cigarettes).
You may wonder why we've used N' at all. Why didn't we just say "x is 1, f(x) is 2, f(f(x)) is 3, f(f(f(x))) is 4, etc.". This would have captured the spirit of the situation well enough. We would have to think of a new way to define ordering (which would be easy enough). More problematically, while this would have kept the idea that the natural numbers are objects in an order, it would give us no feel for cardinality -- "how many". By defining numbers to be sets, as we did, they have both the ordinal qualities of the system suggested at the beginning of this paragraph and the ability to measure the cardinality of other finite sets, ie they can count and measure, in a rudimentary way.
In the next serving, we're going to try and do a little arithmetic with the natural numbers. We're going to meet some basic algebraic considerations, which will motivate us to construct the whole set of integers. Zero will also make its first appearance.
It's worth pointing out that all of the above is a modification of what was taught me as the standard formal construction of the natural numbers. The standard formal construction puts the empty set -- the set with no elements -- into N', and then uses a process nearly identical to the above one the construct N'. This is all fine, except that in the present discussion, we were motivated by the desire to be able to measure cardinalities and to count, and 1 is a more intuitive starting point. I think it's more sensible for zero to arise later, as an algebraic necessity. This is also what happened historically, but if you'd like to see the standard construction, a good presentation is to be found in Robert Stohl's "Set Theory and Logic", although I'll try and find something better on the internets.
Finally, you may like to think about where this all has put the ambiguity alluded to in earlier posts.
----------------------------------------------------
Digression from the bottom of the post:
I forgot to say that since a set is defined solely by its elements, a set written with one element repeated is the same as a set written with that element only once, eg {x, x, x} = {x}.