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 $X$ and some statement $p$ that can be unambiguously determined true or false for each element of $X$ , there is a set containing exactly those elements of $X$ so that $p$ is true. We write this set as $\{x\in X|p(x)\}$ , read “the set of those elements $x$ of $X$ such that $p$ is true of $x$ “.
Intersection: This is actually a special case of specification. For our statement we use “ $x$ is an element of the set $Y$ “. This gives us the set of all elements in both $X$ and $Y$ , and we write this set $X\cap Y$ . 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 $X$ and $Y$ there is a set containing any element in either $X$ or $Y$ . We write this set as $X\cup Y$ . As for intersection, we will allow unions of any collection of sets.
Cartesian product: For any two sets $X$ and $Y$ there is the set of ordered pairs $(x,y)$ , where $x$ is an element of $X$ and $y$ is an element of $Y$ . We write this set $X\times Y$ . 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 $\varnothing$ .
Subset: If every element of $Y$ is also an element of $X$ we say $Y$ is a subset of $X$ — written $Y\subseteq X$ . Note that specification gives us a subset of $X$ .
Power set: For any set $X$ we have the set of all subsets of $X$ . We write this set ${\rm P}(X)$ .

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 $X$ and a “codomain” set $Y$ (the codomain is often called the “range”). For every element $x$ of the domain, there is a uniquely specified element $f(x)$ 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 $f:X\rightarrow Y$ to specify a function with domain $X$ and codomain $Y$ .

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: $A=\{{\rm a},{\rm b},{\rm c}\}$ , $M=\{{\rm foo},{\rm bar}\}$ , $N=\{1, 2, 3\}$ , $V=\{w,x,y,z\}$ . We use these to define a number of examples of functions.

$f:N\rightarrow M$ , with $f(1)={\rm foo}$ , $f(2)={\rm bar}$ , and $f(3)={\rm foo}$ . This function is surjective, but not injective.
$g:N\rightarrow V$ , with $g(1)=y$ , $g(2)=x$ , $g(3)=z$ . This function is injective, but not surjective.
$h:A\rightarrow N$ , with $h({\rm a})=2$ , $h({\rm b})=3$ , $h({\rm c})=3$ . This function is neither injective nor surjective.
$k:A\rightarrow A$ , with $k({\rm a})={\rm c}$ , $k({\rm b})={\rm b}$ , $k({\rm c})={\rm a}$ . This function is bijective.

February 8, 2007 - Posted by John Armstrong | Fundamentals

12 Comments »

I can’t say how many times I’ve read descriptions such as this. and i’d say you’ve done well. but i’m a bit confused by your layout in your final paragraph.

Would it not make more sense to the casual reader to put it like this:

” . . .Every function assigns a value in its codomain to every element in its domain. Every function assigns only one value to every element in the domain. If every element . . . etc.”

or even: ‘Every function assigns one and only one value in its codomain to every element of its domain’

but if there is a reason for stating it as you did, please share. i was puzzled about it all night.

it was a dull evening.

Comment by das | February 9, 2007 | Reply
I may have mangled the style a bit there. What I had in mind is this.

If we think of a function as setting up a correspondence between elements of the domain and elements of the codomain, like a tables of input and output values, we see that every element of the domain shows up as an input, and it shows up only once. A surjection is a function where every element of the codomain shows up at least once and an injection is one where every element shows up at most once.

These two properties — “shows up at least once” and “shows up at most once” — must hold for elements on the domain side of the table. They don’t need to hold on the codomain side, but if they do we have special names for those sorts of functions.

Comment by John Armstrong | February 10, 2007 | Reply
[…] of homomorphisms. For now, there are a few definitions we will find useful later. Recall from the discussion about functions that a surjection is a function between functions that hits every point in its codomain at least […]

Pingback by Group homomorphisms « The Unapologetic Mathematician | February 10, 2007 | Reply
You wrote:

the codomain is often called the “range”

In my experience, the codomain is called the `range’ only when the function is surjective (onto). In general, the range (also called the `image’) of the function is a subset of the codomain, consisting of those elements y satisfying the property (so we are using the Specification principle here!) that y is assigned to at least one element of the domain.

In other words: The codomain is the set of potential values of the function, while the range is the set of actual values of the function.

In the example g, the range is only {x, y, z}, not all of the codomain V. And in the example h, the range is only {2, 3}, not all of the codomain N. (The other two examples are onto; for them the range is all of the codomain.)

Comment by Toby Bartels | February 15, 2007 | Reply
Toby, that’s correct in current usage among most working mathematicians, but there are places where “range” shows up, notably many calculus texts.

I agree that “range” should mean “the values that actually show up”, but I don’t need that concept too often as yet, and I’d rather avoid collisions with other authors here than include the term.

Comment by John Armstrong | February 15, 2007 | Reply
[…] direct product says that we can take two groups, form the Cartesian product of their sets, and put the structure of a group on that. Given groups and we form the group as […]

Pingback by Direct Products of Groups « The Unapologetic Mathematician | February 27, 2007 | Reply
[…] on the left of exactly one pair in . In this case if is in the relation we write . Remember from our discussion of functions that I was saying every element of has to show up both at least once and at most once (that is, […]

Pingback by Relations « The Unapologetic Mathematician | March 2, 2007 | Reply
Peace people

We love you

Comment by HelloWorld | April 28, 2007 | Reply
[…] The standard example here (which will motivate much of our later definitions) is : the category of sets. This has as objects the class of all sets (which can’t itself be a set). The morphisms are […]

Pingback by Categories « The Unapologetic Mathematician | May 22, 2007 | Reply
I certainly once suffered from the ‘foundationalist fallacy’ (if you know how it’s built, you have a clue what it’s for), probably due to a combination of intellectual style defects and osmosis of misguided New Math principles. But, I think the axiom of extensionality for sets and especially functions is worth focussing on a bit, since the standard technique for proving two functions to be identical is proving that the do the same thing to their inputs.

& isn’t what you are calling specification the one that’s more usually called separation (I think ‘culling’ would be better, but I’ve never seen it called that).

Comment by MathOutsider | October 13, 2007 | Reply
MO, it’s really more a philosophical point. I tend to take the language of sets as being a very convenient one, but far from the only one that’s available. Compare this situation with that of the natural numbers. Both the Church and the von Neumann numerals provide models, but neither is inherently any better than the other.

And yes, specification, separation, comprehension, and so on are all different names for the same thing. “Separation” has the sense of taking a set and separating those elements which satisfy a predicate from those which don’t. “Specification” (which I prefer) has the sense of taking a set and specifying (by a predicate) which of its elements are in a subset. “Culling” would have the sense of taking a set and removing those of its elements which don’t satisfy a predicate. They’re all slightly different ways of thinking about the same thing.

Comment by John Armstrong | October 13, 2007 | Reply
[…] finite sums, but about infinite sums. As such, we consider all possible rearrangements — bijections — which make up the “infinity symmetric group . Now we might not be able to effect […]

Pingback by Commutativity in Series I « The Unapologetic Mathematician | May 8, 2008 | Reply

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects

Subjects
Archives

February 2007

M T W T F S S

1 2 3 4

5 6 7 8 9 10 11

12 13 14 15 16 17 18

19 20 21 22 23 24 25

26 27 28

« Jan Mar »
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider