Thread: Some Superficial Set theory

And I do mean superficial; all you will learn here is a few definitions, what the set-theoretic symbols mean, and some very basic concepts.

So, a set is simply a collection of objects for which I can find a suitable unifying property which will allow me to make the following assertion:

A set is well-defined iff, for any object whatever in the universe of objects, an object is either in the definitely in this set or definitely not in this set.

We will see that this assertion neatly side-steps a famous paradox.

Obviously, the objects we shall be dealing with here are mathematical objects. Let's now look at the "algebra" of sets (it's not, of course, really an algebra!), so we will need some notation.

One says that S is a set, and that if one wants to assert that "x is a member of (an element in) S". In like fashion, it is sometimes syntactically convenient to write to mean "S is the set that has x as a member".

(Caveat: militant set theorists will insist these two forms are subtly different - let them go hang!).

Conversely, one would write to mean that x is not an element in S.

More notation: when talking about a set, one has two choices; one can give the entire set a label, like X or Y or whatever, or one might want to be more specific. Write, say, X = {x, y, z} to mean that "X is the set whose elements are x, y and z".

Note that this formulation is very rarely useful when x, y and z are not fully defined. The exceptions include, say, Y = {2, 4, 6, 8, 10, ...}, where one may may assume that Y is the set of even numbers.

This brings us full circle for now, and to some useful notation which, unexpectedly, reveals something slightly profound. Recall we agreed that a set is a collection which has a strict membership criterion. In other words, a set is really a collection together with that criterion. We write it like this:

X = {x : membership criterion}. Here's a concrete example. 3Z = {x : x is integer exactly divisible by 3}. Read the colon ( the pipe | is also used) to mean "such that", or "with the property that".

Here is the slight profundity; sets are pretty dumb creature, as we shall see - they know nothing about, say, division (as in the example above). But we are not dumb - we can establish the qualification for set membership in any way we choose, but once "inside the set" the members are not allowed (in general) to use that qualification.

Like, throw a party for footballers only, but stipulate that no football is allowed inside your house.

You'll be tired of reading this drivel, no doubt, and I have barely scratched the surface.

Later, but ask questions, make corrections, put me on ignore, whatever.....

Count me in! I am encouraged by being able to understand what you are saying :wink:

Guitarist, how far are you going to take this thread? I know a little set theory, but it only really goes so far as to talk about subsets/supersets, and also injective/bijective/surjective functions (which I'm not sure are really a central idea in set theory anyway, but just use set notation?). Anyways, could you please outline what you plan to do, since I'd like to know what is beyond my current knowledge of it. To me, it seems like a subject that isn't very extensive, but I'm sure you'll tell me there's alot to it.

bit4bit: As far as you want, so long as it is in the within the range of my understanding/interest.

Wait for more!

Ok, thanks.

Originally Posted by Guitarist

Here is the slight profundity; sets are pretty dumb creature, as we shall see - they know nothing about, say, division (as in the example above). But we are not dumb - we can establish the qualification for set membership in any way we choose, but once "inside the set" the members are not allowed (in general) to use that qualification.

Like, throw a party for footballers only, but stipulate that no football is allowed inside your house.

I'm fine with everything but could you give a mathematical example in some way of the first paragraph above? I understand it, but if you can give an example in some way it would be cool. I'm enjoying it so far, thanks for doing this.

The point I was trying make was this; a set may have as members real numbers, or it may be complex numbers or it may be polynomials, or it may be chocolate brownies. Set theory is completely agnostic, and treats these sets all in exactly the same way. This should become clear shortly.

So, I said "set theory treats....". What does this mean?

By stretching a point ever so slightly, we may say that the only thing set theory knows about is what we may call "inclusion". Now inclusion can be passive or it can be active; in the former case we will call this a "set relation", in the latter a "set operation"

We have seen an example of a relation already: ; x is included in S.

But not only can we talk about the inclusion of elements in sets, we can talk about the inclusion of sets in sets. In this circumstance, one says that the included set is a subset of the including set.

Let's have a proper definition: if every element of the set A is also an element of the set B, one says that A is a subset of B. Now look at that a minute - notice I haven't said that "not every element of B is an element of A" (though I will shortly..)

This has the curious (but useful) consequence that every set is a subset of itself. One writes to denote this. Read it as "subset or equal". This relation is reciprocal, so that in the case above we have that B is a superset of A; .

So we should know what we mean by equality. Obvious really; two sets are said to be equal if every member of one is also a member of the other and vice versa.

So there is rather stricter inclusion relation; if it is the case that A is a subset of B such that one says that A is a "proper"subset of B; . This is also reciprocal.

I shall give just 2 examples of the above. The set of real numbers is a subset of the complex numbers; (since, when every , every )

The set of integers is a proper subset of the set of rational numbers; (since every for some ).

PS; although now might seem the obvious place to introduce the complement, there's a couple other things it will be useful to know first. So I shall defer it.

Next we want to talk about "active" inclusions, the set operations. Later for that.

OK, before pressing on, let me alert you to one boo-boo, an one abuse of terminology.

Boo-boo: it can never be true, as I seemed to be asserting, that , since R never equals C. I should have written proper subset.

Abuse: the terms "passive inclusion" and "active inclusion" are entirely my own pedagogic inventions. They are never used in practice.

So let's now look at the set operations. Given sets A and B, one is always free to "amalgamate" them. This is called "set union", and is written . One is free to write , but this is rarely useful, rather it is generally helpful to have a notational device to remind ourselves of the following;

and .

We have the following far from pedestrian result;

If , then .

This can only mean that no element in any set can be counted more than once - it's fundamental to the theory.

Another operation allows us to recover the set of elements shared by both A and B. This is called "set intersection", and is written . Here it is useful to give the set of shared elements a name

We then have the result that, if , then .

Compare this with the above - they are almost "dual" notions.

Now, here's a piece of fun. We are always free to take the intersection of sets that have no elements in common. Let X and Y be such sets. Rhe notion that they share no elements in common is succinctly expressed by saying that their intersection is "empty".

In fact we define a set called the "empty set", and write it , hence This is not as crazy as in might seem, because of the following;

For any set S, we have that

and

Again a pleasing duality. In fact it's more than that. Comparing this duality with the one above, one might be tempted to conclude that this implies that . And one would be right!!

The empty set is a subset of any and all sets.

Now let us suppose that A is a proper subset of B; . We say that every element in B that is not in A is in the "complement of A in B" and is written . Obviously .

Notice by our original definition of a set (i.e. the well-definedness condition) this can only mean that and have no elements in common, hence .

This is called a "partition" of B. Obviously we also have that .

Cheers still with you so far.

Originally Posted by Guitarist

Now let us suppose that A is a proper subset of B; A ⊂ B. We say that every element in B that is not in A is in the "complement of A in B" and is written A^c. Obviously A^c ⊂ B.

Two points:

(1) There is no need for A to be a proper subset for A^c to exist. If A = B, then A^c = Ø.

(2) A can be a subset of many sets, not just B. The complement notation ^c should only be used when there is no ambiguity as to which set A is a subset of. I don’t like the complement notation myself; instead I always write B\A to mean the complement of A relative to B.

Of couse the complement notation can be useful when it’s properly used. For example, if you are considering subsets of a fixed topological space, then complement notation certainly makes the statement “A is open if and only if A^c is closed� look very elegant on paper – which is a great help to those rely a lot on intuition.

Originally Posted by JaneBennet

(1) There is no need for A to be a proper subset for A^c to exist. If A = B, then A^c = Ø.

Yes, you are right. Let's just say I was trying to keep it as simple and as intuitive as possible. Thanks for the correction

(2) A can be a subset of many sets, not just B. The complement notation ^c should only be used when there is no ambiguity as to which set A is a subset of. I don’t like the complement notation myself; instead I always write B\A to mean the complement of A relative to B.

Well I was leaving it like that, in order to use precisely this ambiguity to introduce the notion of "set difference".

So let's do that now.

As Jane points out, there may be a certain ambiguity in the notation for the complement of . Complement wrt what?. One may, I suppose, use to emphasize, where there may be ambiguity, that this is the complement of A in B.

No-one ever does. however.

More useful (sometimes) is the notion of "set difference". This is the set-theoretic analogue of the arithmetic "minus". One writes to denote all those elements in B that are not in A.

As expected from our analogy, we have that .

OK, what next? Well this perhaps.....

Notice first that we may define the set {x} as the "singleton set" (since {x, y, z} is a set, and {x, y} is a set, then logic dictates {x} is a set). Then if , so , and and so on

Now suppose that S = {a, b, c}. I will define the set of all the subsets of S to be the "powerset on S", whose elements are of the form {a}, {b}, {a, b} etc.

Then the powerset on S is written , where I include the empty set since this, from an earlier post, is always a subset of S,

Notice that S here is a 3-element set, is an - element set.

Now, using all available fingers and toes, those of your boyfriend/girlfriend, you should be able to convince yourself that, if S has n elements, then it seems possible that, in general, has elements.

this turns out to be true.

For even more fun, we need to define the "cardinality" of a set, but right now I have an urgent appointment with a pint of beer.

OK, I promised some fun.

The "cardinality" of a set is nothing more that its number of elements. This is sometimes written card(S), more usually |S|, in spite of this being an over-used notation.

It might appear that it goes without saying that the cardinality of a set is always a natural ("counting") number. Aha!

From our last discussion of the powerset, we may write . It should be fairly obvious that, for any . (here I am not including 0 in N).

So the question now arises; when , what is . I invite you to brood on that a bit, it's a lot of fun. Hint1: note my "Aha!" above, Hint2: recall the guy who went off his head thinking about "different kinds of infinity"

OK, some more set operations. One of the most useful and all-pervading set operations is called "the Cartesian product" of sets (in fact it is so pervasive, one frequently fails to mention it - I'll give an example in a mo.)

Let A and B be sets, . The Cartesian product of A and B is written . Note that is is a brand, spanking new set, whose elements are written (a, b).

(a, b) is called an "ordered pair" so as to emphasize the fact that, in general, .

Here is an example in use. When we learned in school that 1 + 2 = 3, what we should really have been told is something like this. Let be the set of real numbers, and let + denote a commutative binary operation on R.

Then define by

We would have freaked!!

I'm following everything well, but about the only symbol you've used that isn't a little box to me (in other words I can't see the real symbol), is the one for an intersection. Anything I can do about this?

Well this is a very serious problem for you. In fact I am astounded you followed this thread at all.

If I get bored, I'll go back and reformat in LaTex.

Cheers.

P.S. 'Tis done!

OK, so there is another sort of set operation called "disjoint union", but it is rather specialized, so I shan't bother with it (unless requested).

I now want to show you the Law of de Morgan, principally for its extreme beauty.

We will start with some simple assertions; "today is not a wet Sunday" means "today it isn't raining" OR "today is not Sunday"

Likewise "today is neither wet nor Sunday" means "today is not Sunday" AND "today it is not raining".

Logicians put it like this; let P and Q be propositions. Then,

not(P AND Q) = notP OR notQ

not(P OR Q) = notP AND notQ.

This has been stolen by set theorists as follows. Let A and B be sets, and let the complement of be etc (I don't think it matters what the complement is with respect to, but some-one is free to set me straight on that).

Then de Mogan as applied here is





This is nice; it succinctly illustrates that

a) the complement of a set is it's "negation" which follows from (assuming the Law of Excluded Middle)

b) set union is analogous to the Boolean AND

c) set intersection is analogous to the Boolean OR

Next we will discuss the Axiom of Choice, and try to raise a few hackles in the process!

Originally Posted by Guitarist

b) set union is analogous to the Boolean AND

c) set intersection is analogous to the Boolean OR

You mean the other way around.

*Blush*

Yes; OR , and

AND .

Indeed Boole's notation gives the game away; A AND B and

A OR B

Sorry folks

So, guys, we're about done. There remains this, though;

So far, we have not axiomatized our theory, by which I mean, build our theory from ground-level using only assertions which, although not provable, no reasonable person would dispute.

Neither are we going to do so, in general; this has been done, but it makes the theory (it's called ZF axiomatic set theory, by the way) highly technical and extremely arid. Note only that there are some clever dudes out there who spend their lives thinking about this stuff.

But there is one axiom we need to discuss, and that is the Axiom of Choice.

It goes like this; let be a collection of non-empty sets. Then, from each I can always choose exactly one element and use these to form the set , say.

Now, where each has a finite cardinality, this presents us with no real difficulty. For example, if , then I can tell you that the sets and so on.

In short, for finite sets, I can always give explicit instructions on how to form any particular "choice set".

But where we are dealing with infinite sets, we have a problem. The choices from each set is, let us assume, countably infinite. The choices from a countably infinite number of countably infinite sets is uncountably infinite (This, btw, is the content of the powerset puzzle I posed a coupla posts back)

But, by the definition of "uncountable", this means I can never, ever, write down explicit instructions on how to construct my "choice set". All I can do is assert its existence, by analogy with the finite case.

There is/was a fringe of mathematicians who totally rejected this axiom (They are/were by no means a "lunatic fringe" - they included Kronecker, Brouwer and others). This gave rise to a school of thought called "constructivism" - if you can't tell me explicitly how to construct a mathematical object, I am under no obligation to accept its existence.

So let's see what acceptance of the Axiom of Choice implies.

Some pretty nasty stuff, actually. First we have, among many, the Well-Ordering Theorem: any set can be well-ordered, that is, any subset of a set has a least element. Try and apply this to the real line . The theorem asserts that there is an element in (0, 1) for which there is no smaller element.

Can we write it down? No, but the theorem, which is equivalent to the Axiom of choice, simply asserts that it exists.

Take the Zariski-Banach paradox, that any ball of radius r can be subdivided and reassembled into 2 balls, each also of radius r. Do they tell us how to do this? No, they simply use the Axiom of Choice.

Now, let's hear for the Axiom of Choice..........

Originally Posted by Guitarist

First we have, among many, the Well-Ordering Theorem: any set can be well-ordered, that is, any subset of a set has a least element. Try and apply this to the real line . The theorem asserts that there is an element in (0, 1) for which there is no smaller element.

Careful there. The theorem implies any set can be well-ordered, not that any order is a well order. So you can define an order on, say, under which every subset has a least element. However, many orders that are not well-orders exist--for example, the usual order on . has no least element under this, as given any element , and .

Perhaps a better way of thinking of the well-ordering theorem is that, given any cardinal, there is a ordinal of cardinality equal to that cardinal.

Fair enough, but if we regard as a totally ordered set (we may, may we not?) then the Thm surely states that there is a total well-order to be had on the set , n'est-ce-pas?

This your bag, man, not mine at all - I cede to your love of numbers (Ugh!!)

Originally Posted by Guitarist

Fair enough, but if we regard as a totally ordered set (we may, may we not?) then the Thm surely states that there is a total well-order to be had on the set , n'est-ce-pas?

The theorem doesn't even require that you start with a set which has an order. It just says, "Give me a set, I'll put a well-order on it." The theorem says nothing about orders in general.

This your bag, man, not mine at all - I cede to your love of numbers (Ugh!!)

This is not my bag, actually. In my bag there is only one total order on the real numbers that's worth considering.

There is another statement which is equivalent to the axiom of choice (and the well-ordering principle), namely Zorn’s lemma: “A partially ordered set in which every totally ordered subset has an upper bound has a maximal element.”� (This is used in the proof that every vector space (finite- or infinite-dimensional) has a basis.)

Of the three statements, the axiom of choice is possibly the most intuitive, the well-ordering principle the most counterintuitive, and Zorn’s lemma the most confusing. This is summed up a by the mathematician Jerry Bona when he said: “The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?”�

Originally Posted by Guitarist

Well this is a very serious problem for you. In fact I am astounded you followed this thread at all.

If I get bored, I'll go back and reformat in LaTex.

Cheers.

P.S. 'Tis done!

I've seen all of what's been done so far to some extent, so I've been able to follow it ok. I've had an idea of what the symbols have been supposed to be. Always helps to actually see them though. I was hoping the TeX would take care of things, which thankfully it has.

OK, good. I am about at the limit of my expertise now; anything you want to ask? If I can't answer, it is certain that either Jane or serpicojr can

I feel like this is all of the set theory that you need to know before jumping into abstract algebra or topology. Anything that isn't covered here can be developed as needed.

The most difficult thing covered here is the Axiom of Choice and its two other forms. These only show up in a couple of places in algebra and topology anyway--existence of bases of vector spaces, algebraic closures of fields, and maximal ideals of rings in algebra, Tychonoff's theorem in topology.

Originally Posted by Guitarist

OK, good. I am about at the limit of my expertise now; anything you want to ask? If I can't answer, it is certain that either Jane or serpicojr can

I feel like I'm pretty well set, but I'll certainly ask questions if I think of anything. Thank you very much for doing this thread, and thanks to Jane and serpicojr for their contributions as well.

Where shall we go from here? Group theory, perhaps...?

Edit: you said in the 'Lessons' thread that we could do set theory, group theory, vector spaces, tensor spaces, topological spaces, manifolds, etc. This seems like a good progression to me, if you'd like to continue in that direction.

Originally Posted by Chemboy

. Where shall we go from here? Group theory, perhaps...?

Aah, one of my all time faves.

Hold tight.........

I'm sure we'll all have a field day with some group theory.

I followed most of that pretty well....it's alot like boolean logic, which I know form digital circuit design. Still haven't quite grasped the cardinality of infinite sets thing though. I'm doing some reading on Aleph numbers, and thinking it over.

One thing I'd like to ask, is about open and closed sets. I've seen this mentioned before when looking at things like topology (The first excercise in Janes thread for example mentions closed subsets of a topological space). Would you mind covering a little on these?

Originally Posted by bit4bit

I followed most of that pretty well....it's alot like boolean logic, which I know form digital circuit design. Still haven't quite grasped the cardinality of infinite sets thing though. I'm doing some reading on Aleph numbers, and thinking it over.

Yes, I believe we can develop the coverage here to infinite sets and cardinality next.

Originally Posted by bit4bit

One thing I'd like to ask, is about open and closed sets. I've seen this mentioned before when looking at things like topology (The first excercise in Janes thread for example mentions closed subsets of a topological space). Would you mind covering a little on these?

Open and closed sets are the objects of study in topology. My thread on algebraic topology is at the deep end of the area of mathematics, sorry about that. Then again serpicojr’s thread on algebraic-number theory is pretty advanced as well, definitely not for the faint-hearted either. :P But I can do something on elementary point-set topology if you like.

bit4bit: The concept of open and closed sets is an entirely topological one - it is no part of set theory.

If you ask nicely, Jane might oblige, but I warn you, it is deep at times. (I did try it earlier on this board, but found that my friend river_rat was running rings round me).

However, there is a logical connection between set theory and the theory of topological spaces, so you may have a point

Well, I was probably being a bit too ambitious jumping into it I'd love to see some more elementary stuff on topology, though, if you're up for doing some? Chemboy seems up for some topology too.


Guitarist: I suspected that it probably wasn't a primarily set theoretic idea, since it is always mentioned in topology and never in set theory texts...from the little I've read of those things.

Ya know what, the more I think about it, the more sense it makes sense to do point set topology next - we have most of the necessary tools at our disposal now.

Unless Jane jumps in, I may start up........

Originally Posted by Guitarist

Unless Jane jumps in, I may start up........

You go ahead, start up. :-D

Meanwhile, in this thread, let’s say something about infinite sets and cardinality, as bit4bit suggested. First, a word about functions.

Let A and B be sets, and f be a function with domain A and codomain B, which we write . In other words, f associates every element x in A with a unique image y in B, written as . (In rigorous mathematics, the definition of a function is in terms of the Cartesian product A×B, but we don’t need that for our purpose now; just think of a function f as an association of elements from the set A to the set B.)

Now for some definitions:

(i) injective: The function f is injective iff different elements of A have different images in B. Equivalently, if two elements of A have the same image in B, then the elements are equal. That is to say, for any , if , then .

Examples: The function where is injective. For any real numbers , if , i.e. , it always follows that . On the other hand, if , then f is not injective. We have, e.g., but .

(i) surjective: The function f is surjective iff every element in B is the image of some element in A. That is to say, given any element there is an element such that . A surjective function is also called “onto”.

Examples: The function where is surjective. For any real number , . On the ohter hand, if , then f is not surjective. Why? Well, e.g. −1 is a real number, but there is no real number r such that .

(iii) bijective: The function f is bijective iff it is both injective and surjective. A bijective function is called a bijection. Thus the function given by is a bijection from to .

Now we can go on to finite and infinite sets.

Given a set A, suppose we try and list all the elements of A one by one. If the process eventually terminates, then A is finite, otherwise A is said to be an infinite. Here is a formal definition:

Let be the set of natural numbers. We say that that a set A is finite iff either (the empty set) or there is a bijection from the set to A for some natural number n. If A is not finite, then we say that it is infinite.

Theorem: A set A is infinite if and only if there is a bijection between A and a proper subset of A.

I’ll maybe prove the theorem next time – if I can remember how to do it. :P Note that some mathematicians (myself included) prefer to use the theorem as the definition of an infinite set. However I’ve used the other result as the definition here because I feel it’s perhaps more intuitive and easier to follow for some people.

Next up: countable and uncountable sets, and the idea of cardinality.

Originally Posted by Guitarist

Ya know what, the more I think about it, the more sense it makes sense to do point set topology next - we have most of the necessary tools at our disposal now.

Unless Jane jumps in, I may start up........

If you feel that's a nice logical progression to make, then go for it.

Originally Posted by JaneBennet

Now for some definitions:

(i) injective: The function f is injective iff different elements of A have different images in B. Equivalently, if two elements of A have the same image in B, then the elements are equal. That is to say, for any , if , then .

Examples: The function where is injective. For any real numbers , if , i.e. , it always follows that . On the other hand, if , then f is not injective. We have, e.g., but .

If a function is injective when different elements of A have different images in B, then it is still injective when different elements of A, map to the the same image in B? Isn't that surjective?

Originally Posted by bit4bit

If a function is injective when different elements of A have different images in B, then it is still injective when different elements of A, map to the the same image in B? Isn't that surjective?

No to both. Different elements of A having different images in B means, given r and s in A, . This is logically equivalent to the statement . In most cases, the latter form is much easier to use. Thus, when different elements in A have the same image in B, the function is not injective.

Surjective means that every element in B (the codomain) is the image of at least one element in A (the domain).

Thanks. Understanding it now. What's next?

Definition: A set A is said to be countable iff there is a bijection from to A.

NB: Since the set of all natural numbers is infinite, a countable set is infinite according to the definition. However, some authors include finite sets as countable, defining a countable set as either finite or countably infinite. I prefer to exclude finite sets from the definition of “countable” because (as we shall see) countably infinite sets have properties that are markedly different from finite sets; when we explore the properties of countable sets, we more often than not exclude finite sets and concentrate on just the infinite ones. It is therefore more convenient to exclude finite sets from the definition altogether, so we don’t have keep using the cumbersome phrase “countably infinite”.

A set that is either finite or countable can be described as “at most countable”.

Theorem: The set of all integers is countable.

Proof: Define ,

Then f is a bijection. Can you see why? f has the following output:









… etc.

It may come as a surprise to you to learn that the set of all natural numbers is of the same “size”, so to speak, as the set of all integers. Since there appear to be more integers than natural numbers, you might at first be led into thinking than is a bigger set than . This is not the case. Remember: we are dealing with infinite sets here, and infinite sets have properties that are very different from finite ones. We must therefore avoid ascribing to infinite sets properties which we are familiar with from finite sets.

If the above result is a surprise, the following may come as a mild shock:

Theorem: The set of all rationals is countable.

Think about it. If you’re still baffled, I’ll come back and sort things out in the next post.

Originally Posted by JaneBennet

Theorem: The set of all rationals is countable.

Think about it. If you’re still baffled, I’ll come back and sort things out in the next post. :lol:

This is actually a sweet proof - let's say I am baffled.....

There is actually a very intuitive proof that the rationals are countable. Consider the points (x,y) in the xy-plane where x and y are integers; assume that all the points on the x- or y-axis represent the number 0 and that all other points (x,y) represent the rational number x/y. (Different points can represent the same rational number; for example (1,2) and (2,4) both represent the number 1/2.) Then all you do is start at (0,0) and move in an outward-spiral path like this:



This way you will eventually put all the rationals in a one-to-one correspondence with the natural numbers. (It doesn't matter if you reach a point representing a rational number that's already counted; just skip it and move on to the next point.)

It may be a headache to write a formal algebraic description of this procedure but certainly you can't get more intuitive than this for a proof of the countability of the rationals.

Originally Posted by Guitarist

Originally Posted by JaneBennet

Theorem: The set of all rationals is countable.

Think about it. If you’re still baffled, I’ll come back and sort things out in the next post.

This is actually a sweet proof - let's say I am baffled.....

Yes. Please call me baffled too - I want to see how Cantor's strike-out or whatever method works. Please?

Originally Posted by JaneBennet

Here is a formal definition:

Let be the set of natural numbers. We say that that a set A is finite iff either (the empty set) or there is a bijection from the set to A for some natural number n. If A is not finite, then we say that it is infinite.

Theorem: A set A is infinite if and only if there is a bijection between A and a proper subset of A.

Do you mind giving an example of using this definition to prove whether or not a particular set is finite or not? For example if there is a bijection, then how do you know what the function, f, is? For example A might not even be a set of numbers. I kind of get what the expression is saying, that since is finite, then a bijection to A means that A must also be finite, but how do you show this for an arbitrary set, A, where it may not be obvious whether it is finite or not?

Cheers

Originally Posted by bit4bit

For example if there is a bijection, then how do you know what the function, f, is?

You don’t always know. The definition doesn’t say that you have to know what that function is. As long as such a function exists, that’s good enough; you don’t have to know what it is.

Joke:

An engineer, a physicist, and a mathematician spend the night at a hotel. In the middle of the night, a fire breaks out and the three of them are woken up by the fire alarm. The engineer just grabs a bucket of water and tries to put out the fire. The physicist stands at the fire hydrant outside the hotel, calculating the distance to the fire and velocity of the water and estimating the angle at which the hose needs to be aimed in order to reach the fire. The mathematician sits on his bed and thinks about the problem. Finally he says, “A solution exists!”� and goes back to sleep.

Okay, back to the question of why is countable. Faldo_Elrith has demonstrated intuitively how you can “count� each and every rational number, even though they are densely spread over the real line. But, as Faldo also pointed out, writing down the exact formula for this spiral counting method is anything but straightforward.

There are other ways of proving the countability of the rationals – less intuitive than the spiral counting method but more expressible in terms of a formula. The method I wish to show depends on two simple results about bijections:

1. If and are bijections, then the function , where for each , is a bijection. ( is called the composite of f and g. Note the order! means apply f to x first, then apply g to .)

2. If there is a bijection from A to B and there is a bijection from C to D, then there is bijection from to . (Recall that the Cartesian product of the sets X and Y is .)

The proof of the first result is easy. For the second, if is a bijection and is another, then , is your required bijection between the Cartesian products.

And the procedure to establishing the countability of the rationals is as follows. First, we estabish a bijection from to . Now we already know that there is a bijection fron to (check back a few posts). Hence, by lemma 2 above, there is a bijection from to . And by lemma 1, there will be a bijection from to .

Now each rational number can be written uniquely as where a and b are integers with b > 0 and . Then the mapping , is a bijection from to a subset of . If is countable, then any infinite subset of will be countable – this will imply that .

So, what might this mysterious bijection from to be? Well, it’s not that mysterious, actually. I’ll reveal it all in my next post, but I’ll leave you with the following sets to think about:















Figured out what to do with these yet?

Thanks Jane, and nice joke. I can see now, how if there is a one-to-one correspondance between A and a finite set, , then A must also be finite. I think it's quite an anal way of saying it, but no doubt this is the proper language of mathematicians.

Would you mind proving the theorem about A being infinite when there is a bijection between A and a proper subset of A?

p.s. For some reason all the aposthrophes and quotation marks in your posts are showing as unicode characters such as the euro sign, and 'a' with a hat on it, plus a couple more. All other posts (Chemboy, Faldo,...) are ok.

Originally Posted by bit4bit

p.s. For some reason all the aposthrophes and quotation marks in your posts are showing as unicode characters such as the euro sign, and 'a' with a hat on it, plus a couple more. All other posts (Chemboy, Faldo,...) are ok.

That would be because when the forum was switched to the new server, the default encoding for pages on the forum was swtiched from Unicode to Western European. :| I’ve edited some of my posts to fix that.

Originally Posted by bit4bit

Would you mind proving the theorem about A being infinite when there is a bijection between A and a proper subset of A?

I can prove that result, certainly. Once I remember how it’s done, I’ll do it. :P

In the meantime, I’ll just briefly finish off the result about the countability of the rational numbers.

Lemma: For every natural number n, there exist unique natural numbers k and r such that and .

And you can then satisfy yourself that the function , is a bijection. The first ten values of this function are:

The science forum changed servers? I didn't know

Anyway, I'll just carry on reading through the rest in the mean time.

Okay, let’s try and tackle this result: A set S is infinite if and only if there is a bijection from S to a proper subset of itself.

This is logically equivalent to the following: A set S is finite if and only if there is no bijection from S to a proper subset of itself.

From now on, when we talk of finite sets, we can limit ourselves to sets of the form . This is because of three facts:

(i) the identity function from a set A to itself is a bijection
(ii) if is a bijection, then the inverse function is also a bijection
(iii) if and are bijections, then the composite function is a bijection

These three facts imply that the relation ~ defined by there exists a bijection from A to B is an equivalence relation on any set of sets. For the set of all finite sets, in particular, each equivalence class contains all those sets with a given number of elements. Hence, for a finite set with n elements, we may select as a “representative” of such a set.

To be continued.

Originally Posted by JaneBennet

Originally Posted by bit4bit

p.s. For some reason all the aposthrophes and quotation marks in your posts are showing as unicode characters such as the euro sign, and 'a' with a hat on it, plus a couple more. All other posts (Chemboy, Faldo,...) are ok.

That would be because when the forum was switched to the new server, the default encoding for pages on the forum was swtiched from Unicode to Western European. :| I’ve edited some of my posts to fix that.

Why does it only affect your posts though? My posts don't seem to be affected, and neither do anybody else's.

I normally use Word-formatted punctuation marks – for example ’ instead of ' for an apostrophe. These Word-formatted symbols look different in different encodings. :x

Okay, where were we …

Lemma: Let be a function between two finite sets. If f is injective, then

Proof: If f is injective, then the numbers are all distinct, i.e. whenever . Thus must contain at least m distinct elements, i.e. .

Now we are ready to see why there is no bijection from the finite set to a proper subset of itself. If A is a proper subset of , then there would be a bijection where . If there were a bijection , then the composite function would be a bijection; in particular, it would be injective function and so, by the lemma above, we would have , a contradiction.

So we have proved that if a set is finite, there is no bijection from that set to itself. Equivalently, if there is a bijection from a set to itself, that set must be infinite. The converse remains to be proved.

I'm understanding everthing up to finite/infinite sets, and countable sets, but am struggling a little with the idea of cartesian product, ordered pairs, the well-ordering theorem etc, and because of that, I can't follow janes algebraic approach to proving why the rationals are countable (Though I did understand Faldo's proof very well). I also can't follow Guitarists' definition of addition a few posts back, and won't be able to follow the strict definition of the function in terms of cartesian product (As Jane mentioned somewhere).

Anyway, it's this idea of 'order' on a set that is confucing me. If a set can be any collection of objects - bananas, elephants, whatever - then what is the actual rule that determines the order of a set. Is this something that only applies to sets of numbers, in which case you list them out from lowest to highest? but then you seem to have the ordered pair, (4,1) mentioned which is from highest to lowest.

I also don't get 'least element' (although that will probably be very clear when I understand the idea of ordering), and 'identity element', which I seem to understand as being tied to additive and multiplicative inverses. e.g. has symettry about 0, so for all the additive inverse is -n, and n+(-n)=0, so 0 is the identity element?

Anyway, one of you mind eleborating a little bit on this? If it is tied to the axiom of choice, then I think I missed something.

Originally Posted by bit4bit

I'm understanding everthing up to finite/infinite sets, and countable sets, but am struggling a little with the idea of cartesian product, ordered pairs, the well-ordering theorem etc, and because of that, I can't follow janes algebraic approach to proving why the rationals are countable (Though I did understand Faldo's proof very well). I also can't follow Guitarists' definition of addition a few posts back, and won't be able to follow the strict definition of the function in terms of cartesian product (As Jane mentioned somewhere).

Well, as long as you can understand Faldo’s intuitive proof, then I think that’s good enough. I’m sorry you didn’t understand the more formal proof I gave but I don’t think it matters too much.

I’m not sure what it is you want elaborating though. :?

Originally Posted by bit4bit

Anyway, it's this idea of 'order' on a set that is confucing me. If a set can be any collection of objects - bananas, elephants, whatever - then what is the actual rule that determines the order of a set. Is this something that only applies to sets of numbers, in which case you list them out from lowest to highest? but then you seem to have the ordered pair, (4,1) mentioned which is from highest to lowest.

I think you're confused by the word "ordered" in the terms "ordered set" and "ordered pair". The same word is with slighly different meanings in the two terms. An ordered set is a set with an order relation. For example, the integers with the relation "is less than or equal to" form an ordered set. An ordered pair is the 2-tuple (a,b), where the order of a and b matters (so (a,b) ≠ (b,a) in general).

Originally Posted by bit4bit

I'm understanding everthing up to finite/infinite sets, and countable sets, but am struggling a little with the idea of cartesian product, ordered pairs, the well-ordering theorem etc, and because of that, I can't follow janes algebraic approach to proving why the rationals are countable (Though I did understand Faldo's proof very well). I also can't follow Guitarists' definition of addition a few posts back, and won't be able to follow the strict definition of the function in terms of cartesian product (As Jane mentioned somewhere).

Anyway, it's this idea of 'order' on a set that is confucing me. If a set can be any collection of objects - bananas, elephants, whatever - then what is the actual rule that determines the order of a set. Is this something that only applies to sets of numbers, in which case you list them out from lowest to highest? but then you seem to have the ordered pair, (4,1) mentioned which is from highest to lowest.

I also don't get 'least element' (although that will probably be very clear when I understand the idea of ordering), and 'identity element', which I seem to understand as being tied to additive and multiplicative inverses. e.g. has symettry about 0, so for all the additive inverse is -n, and n+(-n)=0, so 0 is the identity element?

Anyway, one of you mind eleborating a little bit on this? If it is tied to the axiom of choice, then I think I missed something.

The notion of ordering is useful and relatively easy once you see it as an abstract notion. An ordering is just a relation, usually denoted by > with the property that any two elements are always comparable, i.e. given distinct A and B either A>B or B>A but not both. And transitivity A>B and B>C implies A>C. So basically it says that with respect to > there are no "apples and oranges" and that > makes sense if you interpret it as "bigger" in the usual sense of the English language. Not all sets are ordered. and not all orderings are "natural". The real numbers are ordered in the usual manner. The complelx numbers are not.

So elephants or bananas need not be ordered. You can order them arbitrarily and you can do that in any number of ways. But unless there is some "naturality" to the ordering it is not likely to do much good.

A well ordered set is one in which any non-=empty subset whatever always contains a least element. The natural numbers are well ordered. The integers, rationals, reals, etc are not. Well-ordering of the natural numbers is equivalent to the principle of induction. In induction what you are really doing is proving that if an assertion is true for n then it is true for n+1 and then based on truth for n=1 concluding that it is true for all natural numbers. Now in terms of well ordering what you are doing is considering the set of numbers for which an assertion is true. First you show that 1 belongs to that set. Now consider the set K of natural numbers for which it is not true. If that set is non-empty it has a least element, so call it m. But m cannot be 1 so m-1 is a number for which it is true. But then you show that if the assertion is true for n it is true for n+1. So taking n = m-1 you find the assertion to be true for m, a contradiction unless the set K is empty. So K is empty and the assertion is true for all natural numbers.

Originally Posted by bit4bit

...and because of that, I can't follow janes algebraic approach to proving why the rationals are countable ....

Jane's proof is actually remarkably similar to Faldo's. Think of Faldo's dots as a grid geometrically representing the pairs of natural numbers, via rows and columns. We'll count them off, but using a scheme a bit different from Faldo's spiral.

Label the columns 1.2.3.4.5.... from left to right and the columns in the same way from top down. Now count then off by counting from top to botton and right to left along 45 degree lines. That process is called Cantor diagonalization.

Jane's algebraic formula is simply Cantor diagonalization written out explicitly.

Originally Posted by DrRocket

An ordering is just a relation, usually denoted by > with the property that any two elements are always comparable, i.e. given distinct A and B either A>B or B>A but not both.

That would be a total ordering. Does every order need to be a total? I mean, sometimes a partial order (like the relation “is a subset of” on a collection of sets) may do just as well.

Originally Posted by JaneBennet

Originally Posted by DrRocket

An ordering is just a relation, usually denoted by > with the property that any two elements are always comparable, i.e. given distinct A and B either A>B or B>A but not both.

That would be a total ordering. Does every order need to be a total? I mean, sometimes a partial order (like the relation “is a subset of” on a collection of sets) may do just as well.

In the terminology that I am used to an ordering and a total ordering are the same thing. When you want to deal with a partial order you say partial order. I guess you can adopt a different convention though. I prefer not to, but all that is important is that everyone understand what the other person is saying.

The notion of being a subset is a partial ordering, a particularly useful one. Partial orderings are all the more useful when combined with the Zorn's Lemma or the Hausdorff maximality principle -- one of the more common routes to transfinite induction.

There is a book that I will recommend, and it follows your suggestion in which order may mean partial order and total order is spelled out explicitly. That book is Naive Set Theory by Paul Halmos. It is a short little book and very readable. Anyone with a serious interest in mathematics ought to read this book at least once. It won't take much time and it gets you through all the elementary stuff on cardinality, order, etc. It only about 100 pages. Halmos has a wonderful expository style.

Originally Posted by JaneBennet

Originally Posted by DrRocket

An ordering is just a relation, usually denoted by > with the property that any two elements are always comparable, i.e. given distinct A and B either A>B or B>A but not both.

That would be a total ordering. Does every order need to be a total? I mean, sometimes a partial order (like the relation “is a subset of” on a collection of sets) may do just as well.

Your question brings up a point that might be worth making here. I addressed the question literally above, but on thinking about it I feel that some further caution may be warranted.

Mathematics is very precise. But the terminology can vary a bit with useage and among specialties. So you need to be careful and make sure that when you see a term you understand what the author really means.

Some examples.

In typical U.S. useage a compact topological space is one in which every open cover admits a finite subcover. But in some European useage, particularly with the French, it also means that the space is Hausdorff.

The term ring can mean ring with a multiplicative identity or sometimes without that assumption.

The term "manifold" in most useage makes the assumption that the topology is paracompact and Hausdorff. If you don't make this assumption you can get pathalogical examples.

The term "metric" shows up in a couple of ways. One is as a distance function in topology. Another is as a quadratic form in the theory of manifolds, and there you need to be careful if the quadratic form is not positive-definite.

Anytime you see the prefix pseudo-, quasi-, or semi- find out what specifically the author means.

Be very careful with the term basis when used in conjunction with infinite-dimensional vector spaces. To an algebraist it probably means a Hamel basis. To an analyst it probably means a complete orthornormal set in a Hilbert space.

Be very careful with mathematical terms when used by physicists. They might mean something quite different that what you are used to. The term might not even be sufficiently well-defined to be acceptable in mathematical circles.

Originally Posted by DrRocket

Mathematics is very precise. But the terminology can vary a bit with useage and among specialties. So you need to be careful and make sure that when you see a term you understand what the author really means.

Some examples.

In typical U.S. useage a compact topological space is one in which every open cover admits a finite subcover. But in some European useage, particularly with the French, it also means that the space is Hausdorff.

The term ring can mean ring with a multiplicative identity or sometimes without that assumption.

The term "manifold" in most useage makes the assumption that the topology is paracompact and Hausdorff. If you don't make this assumption you can get pathalogical examples.

The term "metric" shows up in a couple of ways. One is as a distance function in topology. Another is as a quadratic form in the theory of manifolds, and there you need to be careful if the quadratic form is not positive-definite.

Anytime you see the prefix pseudo-, quasi-, or semi- find out what specifically the author means.

Be very careful with the term basis when used in conjunction with infinite-dimensional vector spaces. To an algebraist it probably means a Hamel basis. To an analyst it probably means a complete orthornormal set in a Hilbert space.

Be very careful with mathematical terms when used by physicists. They might mean something quite different that what you are used to. The term might not even be sufficiently well-defined to be acceptable in mathematical circles.

Excellent advice, DrRocket! Thanks for sharing. :-D

Thanks for the replies. I'm still not sure I get it after all that though. So an ordered set is any set that has some kind of condition applied to it? But by itself has no condition/relation tied to it, whereas has the condtition, tied to it, so I would expect the former to be an un-ordered set, and the latter to be an ordered set. Also, instead of , we could have used any number of operations here, just to show that there is a relation tied to the elements of the set?

DrRocket, what do you mean by 'a natural ordering', and when you use the symbol >, (A>B..etc) are you taking this to mean 'is greater than' or something more?

Originally Posted by bit4bit

Thanks for the replies. I'm still not sure I get it after all that though. So an ordered set is any set that has some kind of condition applied to it? But by itself has no condition/relation tied to it, whereas has the condtition, tied to it, so I would expect the former to be an un-ordered set, and the latter to be an ordered set. Also, instead of , we could have used any number of operations here, just to show that there is a relation tied to the elements of the set?

DrRocket, what do you mean by 'a natural ordering', and when you use the symbol >, (A>B..etc) are you taking this to mean 'is greater than' or something more?

No. An ordering is an abstract idea. along with the usual notion of is ordered. It has nothing to do with whether a set is described using the ordering, only with the fact that a particular ordering exists. An ordered set is actually a pair, a set plus an ordering.

By a natural ordering I mean an ordering that is somehow related to other structure of the set, a positive class in the case of the natural numbers. Naturalness is a somewhat subjective concept in this context.

Here is an unnatural ordering: Let my set set be (Bill, baseball, orange). Define an ordering, <, by Bill<orange<baseball. Then I have an ordered set, but I can't really do much more with the ordering. The order topology here is discrete, and that is not very interesting, particularly on a set with three elements.

I'm understanding the cartesian product now, and ordered pairs. It helped to look at the examples of , where the ordered pairs (in ) or n-tuples in are co-ordinates, so obviously e.g. (3,4) does not equal (4,3). I also looked at the definition for on the wiki:



...and was glad to be able to understand it! not long ago that would have looked completely foreign to me, so I'm glad I'm familiar with some of the set notation and ideas now.

As for the ordered sets, I'm still not really getting it, but I've printed off various wikis as reading material for when I go away. (I won't be here for 2 weeks) Cheers.

Originally Posted by bit4bit

I'm understanding the cartesian product now, and ordered pairs. It helped to look at the examples of , where the ordered pairs (in ) or n-tuples in are co-ordinates, so obviously e.g. (3,4) does not equal (4,3). I also looked at the definition for on the wiki:



...and was glad to be able to understand it! not long ago that would have looked completely foreign to me, so I'm glad I'm familiar with some of the set notation and ideas now.

As for the ordered sets, I'm still not really getting it, but I've printed off various wikis as reading material for when I go away. (I won't be here for 2 weeks) Cheers.

If you can handle the abstract definition for a Cartesian product, then you will have no trouble with the notion of an ordering once you think about it a bit. I suggest that you get your hands on a copy of the little book by Paul Halmos called Naive Set Theory. It is very short, very easy to read, and I think will help you a lot. It provides a nice introduction to the things related to simple set theory that every mathematician ought to know but that are not collected anywhere else. Halmos is, or was, basically an operator theory guy, so this is written for the "working mathematician", at an undergraduate level, and not for a logician or set theory specialist. It has no prerequisites except for a desire to learn the material. It is a great book.