Lesson 22: Giving Life to Sets

If you think what we’ve done so far is cool, then just wait—it gets better.  If you don’t think what we’ve done so far is cool, then you’re probably not reading this anyway, so it won’t really matter.

This lesson marks the beginning of our departure from what I’d like to call “dead set” theory, and our journey into essentially the rest of math.  In short, we’ll take the “dead sets” that we’ve been dealing with until now (I’ll describe that terminology shortly) and give them “life”. As we go on, we’ll find that virtually all of mathematics—and certainly all of the mathematics that one learns until maybe an advanced undergraduate or even early graduate school course—is nothing but the study of sets with “life”.

Now, what do I mean by “living” and “dead” sets?  I’ll explain the latter, and leave the description of the former to the reader, who will develop a sense of what I mean as she goes on through the lessons and witnesses living sets for herself.

A “dead” set is simply a set without anything extra “added” to it.  All of the sets that we’ve been dealing with so far have been dead.  Now, this is not to say that we can’t infuse them with life (and we most certainly will do so with some of the sets that we’ve already seen).  What it is to say, however, is that we haven’t dealt with sets in any way other than them being simply “a collection of objects”.  I.e., we have no way of describing what makes the set \{1, 2, 3, 4,...\} different from the set

\{\mathrm{Donkey}, \mathrm{rainbow}, 6.45, \mathrm{Cheesy\ Gordita\ Crunch}\},

despite the fact that we’d really like to say, and most certainly believe, that one set is somehow “more mathematical” or has “more structure” than the other.

To put it yet another way, when I write down the set \mathbb{Z} of integers, so that \mathbb{Z}=\{...,-3,-2,-1,0,1,2,3,...\}, we have no way of really “accessing” the oh-so-familiar fact that we can add these elements together.  All our terminology has allowed us to do so far is acknowledge that each member of this set is an element, but we have no terminology for describing the obvious “specialness” of the element 0, or the obvious “special relationship” between 1\mathrm{\ and\ } -1 (or 2 and -2, and so on).  So far, all of these elements are “on the same footing”, so to speak, despite our intuitive feeling that they have some “extra structure”.

So what do we do about this?  We simply define this extra structure, and in doing so breathe life into \mathbb{Z}.  But keep in mind that, being mathematicians, we want to make our definitions as abstract as possible, so as to be as powerful as possible (see this note on abstract thought for more on the relationship between abstraction, generality, and the power that comes with it).  There are lots of sets that have this obvious notion of “extra structure”, and sometimes the various types of “extra structure” are different.  As we’ll eventually see, the set \{1, 2, 3, ...\} has a somewhat different “extra structure” than that of \mathbb{Z}.  For now, however, let us take \mathbb{Z} and use it as motivation to define sets with extra structure in such a way that \mathbb{Z} ends up being a special case.  It turns out that the definition we’ll make is one of the most profound definitions ever made in the history of mathematics.

Let us begin this process of abstraction as we usually do, by asking the following question: what are we “really” doing when we add 5 and 3 and get 8, or when we add 4 and -4 and get 0 (recall that adding a negative number is the same as subtracting the positive version of that number).  I use this question as motivation because we are after that elusive “extra structure” that we so obviously see to exist in \mathbb{Z}, namely, the “add-ability” of its elements.  So, what’s “really” going on when we add 5 to 3 and declare it to be 8?

Well, for one thing, we’re taking two elements of \mathbb{Z} (in this case 5 and 3), we’re doing something to them (in this case adding them), and then we’re declaring the result of that “doing something” to be another element in \mathbb{Z} (in this case 8).  Using more foreshadowing language, we’re taking a “pair of elements” (5 and 3) and “associating” to that pair another element.  Moreover, this element that we’re associating with the pair of elements is itself an element of the set that each element in the pair came from (tough wording there, sorry).  Now, do we have the machinery to deal with this?  It turns out, we have the perfect machinery for it!

Take a look at the phrases in scare quotes above, and think about what we’ve done so far and how it might be applicable here.  We’re taking a “pair of elements” and doing something with them.  Where have we dealt with “pairs of elements” before?  The Cartesian product!  Thus, what we’re doing is dealing with a single element in the set \mathbb{Z}\times \mathbb{Z}.  But then what?  We’re “associating” to it some other element in \mathbb{Z}.  Where have we seen associations like this before?  In functions!  Thus, addition is nothing but a function from \mathbb{Z}\times \mathbb{Z} to \mathbb{Z}.  If we write the addition map as “g”, then we can write g:\mathbb{Z}\times\mathbb{Z}\rightarrow \mathbb{Z}, where each element (a,b)\in \mathbb{Z}\times \mathbb{Z} is mapped to the element a+b\in \mathbb{Z}.  Note that the element (a,b) here is a “pair of elements”, and that “a+b” is a single element in \mathbb{Z}—namely, the element that is the result of adding “a” to “b”.  Explicitly, we have g((5, 3))=5+3=8.  (Nested parentheses here because we usually put the element inside parentheses g(), but the element itself has its own parentheses “(5, 3)” due to the notation that we’ve adopted for Cartesian products).

Now, it just so happens that in this case, g(3,5)=g(5,3) because 3+5=5+3, but that’s fine.  We’ll see later that this is an example of even more structure that we can add to sets, although we won’t add it here.

So let’s recap.  We’ve found that “addition of integers” is nothing but a very special (!!) function from \mathbb{Z}\times \mathbb{Z} to \mathbb{Z} (we certainly could define other functions with the same domain and codomain, but the addition function is the special one that we want to consider).  But there’s even more structure in \mathbb{Z} that we want to encapsulate.  Namely, we want the machinery to describe the “specialness” of the element 0, and we want the machinery to describe the special relationship between a number and its negative.  Let’s start with the former.

What is so special about 0?  The bit of specialness that I’ll focus on here is the fact that we can add it to anything, and the “anything” doesn’t get changed:

5+0=5,

0+5=5,

-4+0=-4,

0+0=0,

and so on.  How do we express that in our more abstract terminology?  We can say that there is a special element, denoted here by 0, such that for any a\in \mathbb{Z}, it is the case that g(0,a)=a \mathrm{\ and\ } g(a,0)=a.  The existence of such an element is part of what gives \mathbb{Z} its extra structure.

Now that we have this special element, we can more fully understand the relationship between numbers and their negatives.  Namely, this relationship is that one added to the other gives us the special element back.  I.e.,

(-4)+4=0,

5+(-5)=0

and 13267+(-13267)=0.

Thus, any number plus its negative gives us the special element.  We say that negative five is the “inverse” of positive five, because negative five plus its inverse gives us the special element.  Similarly, positive five is the “inverse” of negative five for the exact same reason.

There is one more special property of \mathbb{Z} that we have yet to mention, but which will be important in the general definition that we’ll be giving soon.  The property I am talking about is the seemingly trivial fact that we can consider the sum 5+3+7 without worrying about which two numbers we add together first.  I.e., we could add 5 to 3, then add 7, which would be denoted by (5+3)+7or we could add 3 and 7 first, then add 5, which would be denoted 5+(3+7), and we’d clearly get the same result in both cases.  In our abstract language, this comes down to the fact that we can take any three elements in \mathbb{Z} and apply “g” to them in any order we like, and get the same answer.  I.e., it is the case that for all a,b,c\in \mathbb{Z}, \ g(g(a,b),c)=g(a,g(b,c)).

Don’t be scared of that equation.  Remember that the domain of “g” is \mathbb{Z}\times \mathbb{Z}, so whatever goes in the parentheses g() must be a pair of integers (I’ve dropped the nested parentheses just because they’d make those expressions too messy, and the meaning should be clear without them).  Well, in the above equation, g(g(a,b),c) means take the integer which is given by g(a,b) and put it in the first slot of g(\cdot, c), so those expressions with nested g’s actually make perfectly good sense, and it gives us a completely abstract way of saying “it doesn’t matter which order we add things”.  This means that addition is what we call an associative operation, which is simply a fancy word for “it doesn’t matter the order in which we apply the operation”.

Let’s summarize these results.  We’ve found that in order to encapsulate the “additivity” specialness of \mathbb{Z}, the specialness of 0, the special relationships between numbers and their negatives, and the fact that addition is “order insensitive”, we have to say the following:

\mathbb{Z} is a set that comes equipped with a special associative function g:\mathbb{Z}\times \mathbb{Z}\rightarrow \mathbb{Z}, where g(g(a,b),c)=g(a,g(b,c)) for any a,b,c\in \mathbb{Z}.  It also has a special element, which we denote by “0”, which is such that for any a\in \mathbb{Z}, g((0,a))=a \mathrm{\ and\ } g((a,0))=a.  Lastly, it happens to be the case that for any a\in \mathbb{Z}, there exists another element in \mathbb{Z} which we denote as “-a”, such that g((a,-a))=0 and g((-a, a))=0.

Now, we can see immediately how to generalize this.  All we need to do is let \mathbb{Z} be any set.  The fact that we use \mathbb{Z} above is, after all, completely irrelevant.  All of the abstraction that we set up (special functions, associativity, a special element, and elements having inverses with respect to the special function and special element) can be phrased without reference to \mathbb{Z}.  Let us therefore go ahead and make the definition that this lesson has been building up to, and that happens to be one of the most important definitions in the history of mathematics.

Definition: Let G be a set and let g:G\times G\rightarrow G be an associative function (also called an associative map).  Also let G have a special element, which we denote by 0, where g(0,a)=a \mathrm{\ and \ } g(a,0)=a for each a\in G.  Let it also be the case that for each a\in G, there exists an element b\in G such that g(a,b)=0 and g(b, a)=0.  In this case, we call “b” the inverse of “a” and can choose to denote it by “-a” or “a^{-1}” depending on the situation at hand (it’s just notation, after all).  When all of these conditions hold, G is called a group.//

There you have it.  The definition of a group is supremely important and will come up over and over again, so let me make some comments.  Note that the “special element” in this definition is only denoted by 0, and will often have nothing to do with the element 0 that is in \mathbb{Z}.  We simply use this notation as a reminder that this special element plays an analogous role in the group G as 0 does in \mathbb{Z}.  The same holds for the inverse of some element a\in G being denoted by -a.  Namely, the “negative sign” often has nothing to do with same negative sign in \mathbb{Z}, but rather is just a reminder that the element -a plays a similar role in relation to a \in G as, say, -4 does with 4\in \mathbb{Z} (note also that in \mathbb{Z}, the inverse of -4 is 4 and that -(-4)=4, as usual).  Note also that the “order insensitivity”—or associativity—part of the definition does not necessarily mean that g(a,b)=g(b,a).  Although this is true for the integers (i.e., the 5+3=3+5), we’ll see that several interesting groups do not have this property.  Finally, note that a group is nothing but a set “with life”—it’s a set with certain added properties (a special function, etc.) and these properties give the set “structure” and in some way brings it to life.

We’ll spend the next several lessons studying groups, but for now let’s look at some examples so that we can get used to the definition.  Obviously \mathbb{Z} is a group with the special function being addition (taking in a pair of elements and spitting back out their sum), and this better be the case since it was the example that motivated the definition in the first place! Moreover, the set of fractions is a group with their special function being addition (special element being 0, and inverses being negatives), and the real numbers are also a group with the special function again being addition (with the same special element and inverses).

Are the integers a group when we consider their special function to be multiplication?  I.e., the function now takes in a pair of integers and spits out their product under multiplication.  The special element will have to be 1, now, since it’s this element which, when multiplied to anything, leaves that “anything” alone.  However, with the integers, we don’t have inverses because there’s nothing in the integers which, when multiplied by 2 (or 3 or -4) takes you back to 1 (the special element).  Thus, we might be able to consider the set of fractions as a group under multiplication (where we use the word “under” to mean “whose special function is”) since the fractions have the special element 1 as well as inverses for 2, 3, 4, and their negatives.  Namely, the inverse of 2 is \frac{1}{2} because 2\times \frac{1}{2}=1, and the inverse of -4 is \frac{-1}{4} because -4\times \frac{-1}{4}=1 (a negative times a negative is a positive).   However, there is no inverse for 0 because zero times anything is again zero, and thus there’s nothing that, when multiplied to zero, gives us back 1 (which is the requirement for an inverse).  Since the definition of a group requires every element in the set to have an inverse, and since 0 does not have a multiplicative inverse (an inverse under the operation of multiplication), the set of fractions can’t be a group.  They can, however, form a group if we exclude the element 0.  Thus, the set of fraction minus the element 0, which we denote as \mathbb{Q}\setminus \{0\}, is a group under multiplication with special element 1 and with inverses being “1 over” the given fraction (so that the inverse of \frac{5}{4} is \frac{4}{5} and the inverse of \frac{1}{5} is 5, for example).

We’ll see much more of the power and flexibility of groups in the coming lessons, and for now I’ll leave some important and fun examples for the exercise.  Even though there’s only one, and even though it seems “fluffy”, it’s an important one.  If you’re stumped, check out my own solutions and use them as motivation to find other answers yourself.

Exercise:

1)  Can you think of some other groups?  Remember, you need to specify the set, the function, the special elements, and the inverses, and then make sure that all of the axioms in the definition of a group hold (i.e., check that the function is “order insensitive”, and so on).

Solution to Exercise

On to Lesson 23

Back to Lesson 21

Advertisements

3 Responses to Lesson 22: Giving Life to Sets

  1. vivekkumar1 says:

    This is one of most intutitive and clear explanations that I have ever read anywhere. The steps underlying the development of the definition of a group in this article appears to be the following – (1) We have the object (a set) with a intuitive feeling about its “extra structure”. (2) We then define this extra structure (3) To define I need to abstract, and finally (4) we define the object with extra structure.

    While carrying out step (3) in the above article you found a function underlying the process of addition. Although addition is a function but is not a function that has an inverse. For example, g((5,3)) = 8 but f(8) is not is not unique. So addition is a function that does not have an inverse.

    Why did you stop at the general notion of function and not considered the extra bit of information that addition was a function that did not have inverse?

    I am really confused about it.

    • vivekkumar1 says:

      In addition to the above question, the set of integers also have other properties like order. And I think order would also be a function from a pair of integers to a True or False.

      So in the hindsight it appears that you choose your abstractions (for example addition here).

      How did you come to know which abstractions to select and which ones to leave?

      I would be very thankful if you could explain with elementary examples/counterexamples.

      • I’m glad you like the explanation 🙂 and your analysis of what the steps in the process are is pretty spot on. I’m a bit confused by the first question: namely, addition does have an inverse. Adding by -3 “undoes” adding by 3, and indeed the whole reason why the integers form a group is that 0 is the identity element and any number has a partner number (its negative) such that, when they’re added to each other, they give 0. So perhaps I don’t understand what you mean by “addition doesn’t have an inverse”.

        And indeed you’re totally right that the integers have an order too, and that the definition of a group in no way reflects this. Indeed, the integers are a group but they’re ALSO a “partially ordered set” (indeed, they’re also a “totally ordered set”), which is a mathematically precise definition. The reason we choose to care about certain abstractions and not others at any given time is rather arbitrary. If we want to see what is similar between, say, the integers and a group of reflections of a napkin, then we want to consider them both as groups. However, if we want to see what is similar between, say, the integers and the non-negative integers, then we want to consider them both partially ordered sets (namely, because the non-negative integers do NOT form a group). It just so happens that the integers are BOTH a group as well as a partially (and totally) ordered set, but there are lots of groups that aren’t partially ordered sets and lots of partially ordered sets that aren’t groups. So choosing which (collection of) abstractions to concern ourselves with at any given time is a matter of taste, intuition, and utility—–this is what makes math into an art form.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s