Now that we know all about sets (enough, in fact, to derive the paradox of lesson 5), there is a very natural question to ask: What happens when we have two of them? In other words, what types of relationships can exist between sets?
We’ll formalize this in a second, but let me comment first about the generality of this procedure. Perhaps the most pervasive idea studied in mathematics is the concept of “relationships between structures”. A mathematician first defines some new object (in our case the object that we’ve defined is a set) and then studies the behavior of “relationships” between two such objects. As we’ll see, there is always a remarkably subtle interaction between the mathematical object itself, and the relationships that can be established between two such objects. One of the most general types of mathematical object is the set, and therefore the relationships that can be established between sets are some of the most general as well. Let us therefore quit the philosophizing and move on to studying these relationships.
The most basic and fundamental relationship between two sets that mathematicians study is known as a function. We’ll make a somewhat precise definition shortly, but intuitively a function from one set to another set (these two sets can be arbitrary—they could even be the same!) is something which “sends” every element of one set to some element of the other. Of course, “out there” in the world of mathematics there is nothing that literally picks up elements in one set and carries them over to some other set, so let us try to formalize this idea as much as we can. By “sends”, I really mean “associates”. Thus, a function takes each individual element in one set and associates to it some element of the other set. In other words, a function “assigns” some element of one set to some element in the other.
There is more to a function than just this “assigning” of elements, however. In particular, a function always “goes” from one set to another (I use scare quotes because there isn’t really anything moving “out there”, but the dynamical nature of a function is a good analogy to keep in one’s head). Whichever set the function “starts at” must have every one of its elements assigned to some element of the set it’s going to. Let us see an example to make all of this concrete.
Consider the set and the set . Then a function from A to B is an assignment of every element in A to some element in B. Thus I could assign and , and this would be a perfectly good function because I’ve given a “value” to every element in A. I use scare quotes on “value” here because the “value” of an element in A is some element in B. Normally we like to think of “values” as being numerical, but we really can generalize the notion of “value” to any set. If A is given as above and , and we have the function , then the “value” of 1 is horse, and the “value” of 3 is cow.
There are a couple of things that we need to note about these examples that will in fact be crucial for when we actually define a set rigorously. The first thing to note is that although every element in A is given a value in B, it is not the case that every element in B has some element in A assigned to it. For example, donkey never got an element in A assigned to it. That’s fine, because the function is defined to be from A to B, and not the other way around. Whenever a function is from one set, it must assign some “value” to every element in that set. We could, for example, assign chicken to every element in A, and that would be a perfectly fine function. I.e., the function is perfectly fine because nowhere in our “definition” of a function (scare quotes because we haven’t rigorously defined a function yet) did we say anything about whether or not we could assign the same value to every element in the “from” set. The last thing to note is that we are only assigning one element (i.e., one “value”) to every element in A. In other words, the function is not a function because 3 was “sent to” both cow and donkey, which is not okay. We simply define a function to be something which assigns only one value to each element in the “from” set.
This reminds me of something important, and something very “mathematical” in a general sense. We could, of course, have defined a function to be otherwise. We could have defined a function to be something that always assigns two elements to each element in its “from” set. We could have defined a function so that it did not have to assign a value to every element in its “from” set. We’re simply choosing to define a function in this way, because it appears to be one of the most interesting definitions to study. Remember, once we define some object (in this case, a function), the logical deductions that can be made about that object are completely out of our control. We can choose the definition, but we can’t choose the deductions because the deductions are firmly rooted in the world of mathematics, which is already “out there”, beyond us. It just so happens that this definition of a function is much more interesting than other definitions, which means that we’ve stumbled across the definition that is somehow “right”. Let us therefore just go ahead and make this definition and then we’ll study its consequences in coming lessons.
Definition 6.1: Let A and B be two arbitrary sets. A function from A to B is an assignment to every element in A exactly one element in B. //
That’s it. There are no requirements for how many elements of B we end up using, or which elements go where. Thus, this is an extremely general definition, since all we need to remember is that every element of A needs to go somewhere (in B), and each element in A only goes to one place (in B).
Let us now set up some notation (remember, notation isn’t scary, we just need to learn what it is). If we have two sets A and B and a function from A to B, and if we denote this function by f (short for “function”, perhaps), then we denote the entire phrase “f is a function from A to B” simply by . Thus, in that small amount of writing, we know that A and B are sets, we know that f is a function between them, and we know that f goes from A to B (i.e., that every element in A has one and only one element in B associated with it). We sometimes also call A the domain of f, and B the codomain of f. In this sense, then, A is the “domain of influence” of the function f (since f sends every element of A somewhere), and the word codomain is used just to remember “where f sends things to”. Accordingly, if g were a function from C to D, we would write . Here, C would be the domain, and D would be the codomain.
The last bit of notation that we’ll set up is a succinct way to describe where a function f sends individual elements. In other words, we’ll set up notation that not only encapsulates where a function starts and finishes (i.e. f starts at A and finishes at B), but also where the individual elements go. Suppose , and (read aloud as “f is a function from A to B”, so that this sentence is in fact grammatically correct). Moreover, suppose f is the function which assigns . Then we simply denote this by . I.e., the notation is simply shorthand notation for the phrase “f is a function which sends 1 to cat”.
Just as sets may have seemed trivial until we were able to derive a highly non-trivial result from them, functions may at first sight seem like a rather trivial concept. Nonetheless, they form a cornerstone of mathematics and are absolutely pivotal in understanding virtually all of the field. In fact, in only a few lessons we’ll use functions to make precise the notion that there are, in fact, some infinities which are in a clear sense “more infinite” than others. For now, let’s be patient and simply internalize the idea of a function, and the corresponding vocabulary and notation (of which there is very little).