Lesson 17: More Constructions pt. 1

Having seen in lesson 16 that we can “build” new sets from old ones—namely, we can take two sets and form their union or their intersection—the next natural question to ask is whether or not there is anything else we can do.  Namely, are there other ways that we can build new sets from old ones.  Well, obviously, there are lots of things that we can do, but it just so happens that there are a few constructions that are particularly useful and important.  Unions and intersections are two important constructions, and in the next two lessons we’ll introduce two more: the Cartesian product and the disjoint union.  Both of these constructions, however, are different from the constructions of unions and intersections in important ways.  Let us first see what these differences are.

Recall that when forming the union and intersection of two sets we never altered the individual elements themselves.  Namely, we simply constructed a new set from the elements that were in the two old sets, while never making any changes to the actual elements.  In the two constructions that we’ll study in this and the next lesson (Cartesian products here and disjoint unions in the next), we will be altering the elements themselves, but we’ll be doing so in an extremely natural and obvious way.

We’ll use this lesson to study the Cartesian products of two sets.  As usual, let’s call our initial two sets A and B.  A and/or B can be infinite sets, finite sets, sets of numbers, sets of animals, sets of fruit, or whatever.  Let us further suppose that “a” is an element in A (recall from lesson 16 that this is written ), and that (“a” and “b” simply stand for an arbitrary element in whatever sets A and B are, respectively).  Then we can define a new element, , that we simply define to be the pair of elements “a” and “b”.   This is completely abstract.  If and , then the pair of elements 1 and chicken is simply defined to be .

Now to define the Cartesian product of two sets A and B, we simply consider the set of all pairs of elements with one element in A and one element in B.  In fact, this is simply the definition of the Cartesian product:

Definition 17.1: Let A and B be sets.  The Cartesian product of A and B is the set of pairs such that and .  If we denote the Cartesian product of A and B as , then we have .//

Note that I used the symbol “” in the last line of the above definition because this is how we’re defining the set, and this symbol is read “is defined to be”, as discussed in lesson 16 (which is also where you’ll find an explanation of the rest of the notation used in the definition if you’ve forgotten).  This definition will make more sense if we see an example.  As usual I’ll take a very easy example.  Let’s let and .  Then .  It might already be clear from this example that if A and B are both finite sets, and if A has N elements and B has M elements, then the Cartesian product of A and B has elements.  This can be seen simply by realizing that for every element in A, we get M elements in , since if then there are exactly M elements of the form where the “” cycles through the M elements in B.  Since there are N elements in A, and each of them gives M elements, we therefore have the desired result.

But don’t let this fool you into thinking that we can only take Cartesian products of finite sets, because this is most certainly not the case.  We can easily take the Cartesian product of infinite sets (or of an infinite set with a finite set), we’d just have infinitely many elements in the product set.  But that’s fine!

There are some important things to note about the construction of a Cartesian product, which will be important for us much farther down the road when we introduce and study categories (which is a precise, extremely gorgeous, and wildly abstract mathematical structure).  The first thing to note is that the elements in the Cartesian product are completely abstract—even more abstract than the elements of the original set.  One good way to think of the Cartesian product of two sets is to consider the product as “the set of ways to pick one element from one set and one element from the other”.  This is a very abstract element, though, because it’s not a “thing” like an apple or an orange or a number, but rather a “way”.  This way of viewing things will make the next note more digestible.

The next thing to note is that is that there is a certain amount of arbitrariness to this definition.  Namely, why didn’t we define the Cartesian product to be the set of elements written with and ?  Or why not the set of elements with and ?  Or why not reverse the order so that the elements of B are on the left and those of A on the right?  Well, there is in some clear sense the notion that all of these sets would somehow be “the same”.  Namely, they somehow all contain the same information and we’re just finding different ways to write that information down.  Clearly, mathematics should not be dependent on how we choose to write things down, so how do we reconcile all of this?  Well, in short, we won’t.  At least, not until we have the structure of categories to work with, but that won’t be for a while.  The important thing to keep in mind is that while all of these alternatives are possible, we’re simply defining one of them to actually be the Cartesian product, and remembering that if the enemy hands us one of these other sets then we can very naturally identify it with the Cartesian product itself.

So what’s the take-away?  In short, the Cartesian product of two sets is the set obtained by taking all pairs of elements, one from A and one from B.  There are several ways to write these pairs down, but at the end of the day the mathematical content in each of these various ways is identical.  Take a look at the exercises for some more fun with Cartesian products.

P.s. We call this the “Cartesian” product because it is named after the mathematician/philosopher Rene Descartes, and because when you’re a great mathematician you get stuff named after you.

Exercises:

1) Let , and .  Then the Cartesian product of A and B is a perfectly good set, and so we can take its Cartesian product with C, denoted by .  How many elements are in ?.

2)  Let .  How many elements are in ?

Solutions to Exercices

Next Lesson

Previous Lesson