Sets and functions
I’m soon going to need to really use the notion of a function, and I want to make sure that I lay the groundwork properly. This is also a good place to mention a few things about sets.
For most of my purposes, a naïve concept of sets will suffice. A set is a collection of objects, called the elements of the set. In formal treatments of set theory, the elements are themselves sets. In fact, everything in sight is “really” a set. This sort of foundationalist approach, though, tends to obscure the real structure of mathematical theories, so I’ll avoid talking about formal set theory unless it’s absolutely necessary. What we’ll need from set theory are a few operations on sets.
- Specification: If we have a set and some statement that can be unambiguously determined true or false for each element of , there is a set containing exactly those elements of so that is true. We write this set as , read “the set of those elements of such that is true of “.
- Intersection: This is actually a special case of specification. For our statement we use “ is an element of the set “. This gives us the set of all elements in both and , and we write this set . In practice, we will allow intersections not just of two sets, but of any number of sets — even infinitely many.
- Union: For any two sets and there is a set containing any element in either or . We write this set as . As for intersection, we will allow unions of any collection of sets.
- Cartesian product: For any two sets and there is the set of ordered pairs , where is an element of and is an element of . We write this set . Again, we allow Cartesian products of any number of sets, though only a finite number at a time here.
- Empty set: While not a “construction”, per se, the empty set is something important to pay attention to. This is, predictably enough, the set containing no elements at all. We write it .
- Subset: If every element of is also an element of we say is a subset of — written . Note that specification gives us a subset of .
- Power set: For any set we have the set of all subsets of. We write this set .
I may have forgotten some, but I will mention those (and add them here) if I realize it later.
Anyhow, a function is basically a rule that assigns to each element of one set an element of another. Formally, we need to specify a “domain” set and a “codomain” set (the codomain is often called the “range”). For every element of the domain, there is a uniquely specified element in the codomain. Often there is some sort of calculational method to determine the value of the function, but a simple lookup table will suffice. We write to specify a function with domain and codomain .
There are a few properties a function may have that are worth mentioning here. Every function assigns a value in its codomain to every element in its domain. If every element in the codomain is the value of the function at some element of the domain we say that the function is “onto” or a “surjection”. Every function assigns only one value to every element in the domain. If no element in the codomain is the value of the function at more than one element of the domain, we say that the function is “one-to-one” or an “injection”. If both of these properties hold, we say the function is a “bijection”.
Let’s consider four sets: , , , . We use these to define a number of examples of functions.
- , with , , and . This function is surjective, but not injective.
- , with , , . This function is injective, but not surjective.
- , with , , . This function is neither injective nor surjective.
- , with , , . This function is bijective.