Seminar on Set Theory Basics

This seminar was held in #mathematics on Freenode (with a relay set up to EFnet) on 27th of August 2005 at 15:00 EDT by Kit.

It covered basic undergraduate set theory.

Seminar Log

15:03 <@DRMacIver> Today I'll be introducing the basics of set theory. I'll start by giving some basic definitions, and then go on to develop some of the basic theory of cardinality of infinite sets.
15:03 <@DRMacIver> This is by no means a comprehensive introduction to set theory - it's a big subject, and there's a lot in it. This is just what I think one of the neatest bits of elementary set theory is.
15:04 <@DRMacIver> So, lets start by telling you what a set is.
15:04 <sven> !
15:04 <@DRMacIver> sven: Yes?
15:04 <sven> could you introduce yourself, or refer us to a web page of yours?
15:05 <@DRMacIver> I suppose so. :)
15:05 < South-Park> !can we also have ur mail id so that we can mail our doubts while reffering to the logs later ??
15:05 < DrChemicalX> ! i would be happy if you introduced yourself also sir
15:05 <@DRMacIver> Briefly, I'm a recent graduate of Cambridge university. I've been in EFNet's #math channel for the past few years and have given a number of online talks there.
15:06 <@DRMacIver> My website is
15:06 <@DRMacIver> Some of you probably know me as Kit. I'm using a different name because someone else has already taken that on freenode.
15:07 <@DRMacIver> Now, if anyone has any more non-mathematical questions can you leave them to the end of the talk? It'll take forever if we keep getting sidetracked. :)
15:08 <@DRMacIver> Ok. Briefly, a set is a collection of objects - usually these are of some mathematical significance. For example sets of numbers.
15:08 <@DRMacIver> We use the notation {1, 2, 3} to mean the set containing precisely the numbers 1, 2 and 3.
15:09 <@DRMacIver> Important features of sets: Firstly, they have no inherent order to them.
15:09 <@DRMacIver> So {2, 3, 1} is the same as {1, 2, 3}
15:09 <@DRMacIver> Also, repetitions are ignored - {1, 2, 2, 3} is again the same as {1, 2, 3}.
15:10 <@DRMacIver> Finally, sets don't have any special 'names'. A set is determined entirely by what it contains - it doesn't matter if the definitions and names are completely different, if they contain the same things then they are the same set.
15:11 <@DRMacIver> Another notation we might use is defining a set by a formula. For example we could write { p : p is a prime } for the set of all prime numbers.
15:12 <@DRMacIver> Now I'm going to teach you how to count. :)
15:13 <@DRMacIver> Suppose we have a set such as {1, 2, 3} or {2, 7, 9}. It's obvious that these contain three elements, but what does that actually mean?
15:13 <@DRMacIver> Now, first of all, it essentially must be true by definition that {1, 2, 3} has three elements.
15:14 <@DRMacIver> There are always going to be n numbers between 1 and n. This is just inherent in the process of counting.
15:15 <@DRMacIver> Now, we can pair up the numbers in these two sets. (1, 2), (2, 7) and (3, 9).
15:15 <@DRMacIver> For each element of the first set we've given you a unique element of the second set.
15:15 <@DRMacIver> And every element is hit this way.
15:15 <@DRMacIver> So intuitively speaking these must have the same number of elements: Any way of counting the first set gives you a way of counting the second set.
15:16 <@DRMacIver> So really the numbers themself aren't important with counting (Yes, you can quote me as saying that numbers aren't important for counting. :) ). What's important is the notion of two sets having the same number of elements.
15:17 <@DRMacIver> Oh, sorry. I should say - an element of a set is just something that's contained in that set.
15:17 <@DRMacIver> We use the notation \in which is written as a little E, or an epsilon. For example 1 \in {1, 2, 3}
15:18 <@DRMacIver> For a finite set X we use the notation |X| to mean the number of elements of X.
15:18 <@DRMacIver> So |{1, 2, 3}| = |{2, 7, 9}| = 3
15:19 <@DRMacIver> Now, the above discussion is basically saying that if we have a set X and a set Y, then |X| = |Y| if we can pair up the elements of X and Y like that.
15:19 <@DRMacIver> I haven't actually proved that - what I'm really giving you here is a definition.
15:20 <@DRMacIver> This leads us onto the idea of a function, which will allow us to make the notion of that pairing up slightly more precise.
15:20 <@DRMacIver> Suppose we have a set X and a set Y. A function from X to Y is a rule that takes an element of X and gives you an element of Y.
15:21 <@DRMacIver> So if we have the sets {1, 2, 3} and {2, 3, 7} we might have the function that sends 1 to 2, 2 to 3 and 3 to 7. This is the pairing we had above.
15:21 <@DRMacIver> We often give these functions names. For example we might (imaginatively) call this function f.
15:21 <@DRMacIver> We would write f : X -> Y for a function from X to Y.
15:21 <@DRMacIver> And f(x) for the value that x is sent to.
15:22 <@DRMacIver> So in the above we have f : {1, 2, 3} -> {2, 3, 7} with f(1) = 2, f(2) = 3, f(3) = 7.
15:23 <@DRMacIver> Now, a function is called injective (or an injection) if it sends distinct things to distinct things.
15:23 <@DRMacIver> So f is injective.
15:23 <@DRMacIver> But if we defined g by g(1) = 2, g(2) = 2, g(3) = 7, this wouldn't be.
15:23 <@DRMacIver> Because 1 and 2 are different, but g(1) = g(2)
15:24 <@DRMacIver> We call a function surjective (or a surjection) if it hits every element.
15:24 <@DRMacIver> Oh, sorry. I forgot to tell you. If f : X -> Y then we call X the domain and Y the codomain.
15:24 <@DRMacIver> So in that definition I really want to say if it hits every element of the codomain.
15:25 <@DRMacIver> So f is surjective, but g isn't because it doesn't hit 3.
15:25 <@DRMacIver> Similarly if we defined f : {1, 2, 3} -> {1, 2, 3, 4} by just setting f(x) = x, then this is injective but not surjective.
15:26 <@DRMacIver> Finally, a function is bijective (or a bijection) if it is both injective and surjective.
15:26 <@DRMacIver> So what we are saying is that |X| = |Y| if and only if there is a bijection between X and Y.
15:26 <@DRMacIver> Phew. Sounds a bit heavy handed, but it really isn't once you're used to it. :)
15:26 <@DRMacIver> Any questions so far?
15:27 <@DRMacIver> ok. Guess not. :)
15:27 <@DRMacIver> Oh, we can also make sense of |X| <= |Y|, just by saying this means that there is an injection from X to Y.
15:28 <@DRMacIver> Now, if we have a function f : X -> Y and a function g : Y -> Z then we can define a new function gf : X -> Z by saying gf (x) = g(f(x))
15:29 <@DRMacIver> Exercise: If g and f are both bijections then so is gf.
15:29 <@DRMacIver> This is called composing g and f, or composition of functions.
15:30 <@DRMacIver> This lets us prove something that the notation has already suggested, which is that if |X| = |Y| and |Y| = |Z| then we have |X| = |Z|. Just take a bijection from X to Y and a bijection from Y to Z and compose them, giving a bijection from X to Z.
15:30 <@DRMacIver> Now, the clever part of all this is that our definitions don't assume the sets to be finite!
15:30 <@DRMacIver> So this will allow us to make sense of the notion of how many elements of an infinite set has.
15:30 <@DRMacIver> Other than 'lots' :)
15:31 <@DRMacIver> Our basic example of an infinite set is the set of natural numbers. That is numbers of the form 1, 2, 3, 4, ...
15:31 <@DRMacIver> We call this set N.
15:31 <@DRMacIver> We now encounter something slightly surprising - if you take away some elements from an infinite set then you still have the same number of elements left.
15:32 <@DRMacIver> For example |N| = | {2, 3, 4, ... } |
15:32 <@DRMacIver> Proof: Define f : N -> {2, 3, 4,...} by f(n) = n + 1
15:32 <@DRMacIver> Exercise: This is a bijection.
15:32 <@DRMacIver> You can even take away infinitely many elements (although of course if you take away *all* the elements, or even all but finitely many, this doesn't work).
15:32 <@DRMacIver> |N| = |{2, 4, 6, ...}|
15:33 <@DRMacIver> Proof: Define f(n) = 2n
15:33 <@DRMacIver> Same exercise.
15:33 <@DRMacIver> So there are as many even numbers as there are numbers.
15:33 <@DRMacIver> In fact, if A is any infinite subset of N then |A| = |N|
15:34 <@DRMacIver> How we prove this is as follows. Strictly speaking this is a definition by induction, but you don't really need to know what that means. :)
15:34 <Reloaded> !
15:34 <@DRMacIver> Reloaded: Yes?
15:35 <Reloaded> What is Aleph, Aleph_0 and the difference between these two notations?
15:35 <@DRMacIver> I'm not going to use that notation in this talk, so I won't answer that now.
15:35 <Reloaded> Oh, that's to bad. :)
15:36 <@DRMacIver> Anyway, back to proving this.
15:36 <Reloaded> Those are some really interesting parts of set theory.
15:36 <@DRMacIver> Reloaded: Shush. :)
15:36 <@DRMacIver> What we do is define f : N -> A as follows.
15:36 <@DRMacIver> f(1) is the smallest element.
15:36 <@DRMacIver> f(2) is the next smallest element.
15:36 <@DRMacIver> ...
15:37 <@DRMacIver> f(n) is the smallest element greater than the ones we've previously defined.
15:37 <@DRMacIver> And there are always going to be more elements, because A is infinite, so we can keep defining it this way.
15:37 <@DRMacIver> This is injective because if m < n then we've chosen f(n) to be strictly greater than f(m).
15:38 <@DRMacIver> This is surjective because you can easily check that f(n) >= n, and because of the way we've constructed it, if something is in the image then all smaller numbers in A are also in the image.
15:38 <@DRMacIver> Sorry. Going to introduce another random definition. :)
15:38 <@DRMacIver> The image is the set of points in the codomain which get hit.
15:39 <@DRMacIver> So if f : X -> Y then the image, which we write f(X), is { f(x) : x \in X }
15:39 <@DRMacIver> So saying f is surjective is just saying that f(X) = Y
15:39 <@DRMacIver> Anyway, so f is a bijection.
15:39 <@DRMacIver> Thus |N| = |A|
15:40 <@DRMacIver> This should suggest to you that |N| is the 'smallest infinity'. In fact this is true.
15:41 <@DRMacIver> Suppose X is any infinite set. We can define an injective function f : N -> X in a very similar way. The only thing is that we need something called the axiom of choice to do this, because we dont' have any sensible way of picking elements of X.
15:41 <@DRMacIver> So we pick something for f(1), then having picked f(1), ... ,f(n-1) we pick something differet for f(n) (which we can do because A is infinite).
15:41 <@DRMacIver> I'm not going to get into the details of choice. I'm just going to occasionally mention it in this talk. :)
15:42 <@DRMacIver> i.e. for any infinite set X we have |N| <= |X|
15:42 <@DRMacIver> If |X| <= |N| then we say that X is countable. I'm now going to spend a little time showing that various sets are countable.
15:43 <@DRMacIver> First of all I'm going to give you another definition. :)
15:43 <@DRMacIver> If we have a set X then X^2 is the set of ordere dpairs of elements of X.
15:44 <@DRMacIver> i.e. { (x, y) : x, y \in X }
15:44 <@DRMacIver> X^3 is then the set of ordered triplets, etc.
15:44 <@DRMacIver> I'm now going to show that N^2 is countable.
15:45 <@DRMacIver> There's a nice explicit bijection between N and N^2, but it really needs a diagram so I'm not going to give it. :)
15:45 <@DRMacIver> Instead I'll do something slightly different.
15:45 <@DRMacIver> Define f : N^2 -> N by f(m, n) = 2^m 3^n
15:46 <@DRMacIver> This is then injective because things have unique prime factorisation (don't worry if you can't prove this. :) )
15:46 <@DRMacIver> So we've got that |N^2| <= |N|
15:46 <@DRMacIver> And then because this means we have a bijection between N^2 and f(N^2), which is an infinite subset of N, we have that |N^2| = |N|
15:47 <@DRMacIver> So there are as many pairs of numbers as there are numbers.
15:47 <@DRMacIver> Another thing. If we have a surjective map f : N -> X then X must be countable.
15:48 <@DRMacIver> Proof: Define g : X -> N by letting g(x) be the least n such that f(n) = x.
15:48 <@DRMacIver> Exercise: This is injective.
15:48 <@DRMacIver> Now, this will work if we replace N with any other countable set.
15:49 <@DRMacIver> So for example there are countably many positive rationals, because we can define f : N^2 -> {positive rationals} by f(m, n) = m / n
15:49 <@DRMacIver> And this is obviously a surjection (but not injective).
15:50 <@DRMacIver> Now I'm going to introduce another notion.
15:50 <@DRMacIver> First of all I want to note that it's ok for sets to contain other sets.
15:50 <@DRMacIver> So for example we could have { {1, 2}, {1, 2, 3} } - the set whose elements are precisely {1, 2} and {1, 2, 3}
15:51 <@DRMacIver> This leads us to the notion of a power set. If X is a set then we define P(X) = { subsets of X }
15:51 <@DRMacIver> Oh, sorry. I don't think I've defined a subset.
15:52 <@DRMacIver> But it's probably what you'd have expected. A is a subset of B if every element of A is also contained in B.
15:52 <@DRMacIver> So {1, 2, 3} is a subset of {1, 2, 3, 4}, but {1, 2, 5} is not because 5 is not in {1, 2, 3, 4}.
15:53 <@DRMacIver> Exercise: |P({1, ..., n})| = 2^n
15:53 <@DRMacIver> Because of this we often use the notation |P(X)| = 2^|X|
15:53 <@DRMacIver> This isn't really important though.
15:53 <@DRMacIver> First as a warmup we'll show that N has countably many finite subsets.
15:54 <@DRMacIver> What we do is we take n and write it as a prime factorisation. Say n = 2^1 5^7 11^1
15:54 <@DRMacIver> We now send this to the set of numbers which appear in the powers. So that number goes to {1, 7, 1} = {1, 7}
15:54 <@DRMacIver> Exercise: This is a surjective map.
15:55 <@DRMacIver> So, we've seen lots of infinite sets are countable. You're probably getting a bit bored of this by now. :)
15:55 <@DRMacIver> So as a punchline I'm finally going to give you an uncountable set.
15:55 <@DRMacIver> This is called Cantor's theorem: It says that for any set X there is no bijection between X and P(X).
15:56 <@DRMacIver> The proof is clever. Don't blink or you'll miss it. :)
15:56 <@DRMacIver> Suppose f : X -> P(X) was a bijection.
15:56 <@DRMacIver> Define the set A = { x \in X : x is not a member of f(x) }
15:57 <@DRMacIver> Now, f is surjective so we must have f(x) = A for some x
15:57 <@DRMacIver> As A is a subset of X.
15:57 <@DRMacIver> Now, x is an element of A if and only if it is not an element of A!
15:57 <@DRMacIver> Because we've defined A to be the set all x which are not contained in f(x)
15:58 <@DRMacIver> Err. Say y which are not contained in f(y)
15:58 <@DRMacIver> So, this is a contradiction. Thus our initial assumption can't have been correct.
15:58 <@DRMacIver> (This is called a proof by contradiction if you haven't seen it before. It's very useful, but occasionally feels like a bit of a rabbit out of a hat).
15:59 <@DRMacIver> So we've concluded that P(N), the set of all subsets of N, must be uncountable.
15:59 <@DRMacIver> And thus there are different sizes of infinity.
15:59 <@DRMacIver> I was going to use this to show that there are uncountably many real numbers, but I'm running behind so I'll leave it there.
15:59 <@DRMacIver> You basically just construct an injection from P(N) into the real numbers using the decimal expansion.
16:00 <@DRMacIver> Anyway, this is one of the basic ideas which got the subject started, and leads on to a lot of other useful and cool ideas.
16:00 <@DRMacIver> Hope it was interesting. :)
16:01 <@DRMacIver> Oh good. I've put everyone to sleep. :)
16:02 <Teirdes> Thank you.
16:02 <@Chandra> I will be publishing the lecture on site, would you mind?
16:02 <@Chandra> *odd site*
16:02 <@DRMacIver> Chandra: Go right ahead. We'll probably stick a copy on the EFNet #math one as well.