Fundamentals « The Unapologetic Mathematician

The uniqueness of the integers

It’s actually not too difficult to see that the integers are the only ordered integral domain with unit whose non-negative elements are well-ordered. So let’s go ahead and do it.

In fact, let’s try to build from the ground up. We can start with the additive identity ${}0$ and the unit $1$ . Since we’ve got an ordered ring we have to have $0\leq 1$ , otherwise the multiplication can’t preserve the order.

Now we can also tell that $1$ is the smallest element larger than ${}0$ . Let’s say there were some element in between: $0<r<1$ . Then $r^2<r$ , and $r^3<r^2$ , and so on. The collection of all powers of $r$ has no lowest element, so the positive elements can’t be well-ordered in this case.

We can add up an arbitrary number of copies of $1$ to get $n$ , and we know there’s nothing between $n$ and $n+1$ , or else there would have to be something between ${}0$ and $1$ . We also get all the negative numbers since we have to have them. Multiplication also comes for free since it has to be defined by the distributive property, and every element around is the sum of a bunch of copies of $1$ .

Finally, the fact that we’re looking for an integral domain means we can’t introduce any relations saying two different elements like these are really the same in our ring without making a zero-divisor or collapsing the whole structure. I’ll let you play with that one.

April 4, 2007 Posted by John Armstrong | Fundamentals, Numbers | Leave a Comment

The characterization of the integers

Okay, so we’ve seen that the integers form an ordered ring with unit, and that the non-negative elements are well-ordered. It turns out that the integers are an integral domain (thus the name).

Let’s assume we have two integers (still using the definition by pairs of natural numbers) whose product is zero: $(a,b)(c,d)=(ac+bd,ad+bc)=(0,0)$ . Since each of $a$ , $b$ , $c$ , and $d$ is a natural number, the order structure of $\mathbb{N}$ says that for $ac+bd=0$ we must have either $a$ or $c$ be zero and either $b$ or $d$ as well. Similarly, either $a$ or $d$ and either $b$ or $c$ must be zero. If $a$ is not zero then this means both $c$ and $d$ , making $(c,d)=0$ . If $b$ is not zero again both $c$ and $d$ are zero. If both $a$ and $b$ are zero, then $(a,b)=0$ . That is, if the product of two integers is zero, one or the other must be zero.

So the integers are an ordered integral domain with unit whose non-negative elements are well-ordered. It turns out that $\mathbb{Z}$ is the only such ring. Any two rings satisfying all these conditions are isomorphic, justifying our use of “the” integers. In fact, now we can turn around and define the integers to be any of the isomorphic rings satisfying these properties. What we’ve really been showing in all these posts is that if we have any model of the axioms of the natural numbers, we can use it to build a model of the axioms of the integers. Once we know (or assume) that some model of the natural numbers exists we know that a model of the integers exists.

Of course, just like we don’t care which model of the natural numbers we use, we don’t really care which model of the integers we use. All we care about is the axioms: those of an ordered integral domain with unit whose non-negative elements are well-ordered. Everything else we say about the integers will follow from those axioms and not from the incidentals of the pairs-of-natural-numbers construction, just like everything we say about the natural numbers follows from the Peano axioms and not from incidental properties of the Von Neumann or Zermelo or Church numeral models.

April 3, 2007 Posted by John Armstrong | Fundamentals, Numbers | 2 Comments

Well-Ordering

A well-ordering on a set is a special kind of total order: one in which every non-empty subset contains a least element.

The two best examples of ordered sets we have handy are the natural numbers $\mathbb{N}$ and the integers $\mathbb{Z}$ . For now, forget all the other algebraic structure we’ve talked about. The natural numbers are well-ordered, but the integers are not.

Seeing that the integers are not well-ordered is pretty easy: just take the subset of negative integers. There’s no negative number that’s less than all the others. Seeing that the natural numbers are well-ordered is a little more difficult. Given a set $X$ , either ${}0$ is in $X$ or it isn’t. If it is, it’s the least element — nothing could be less than it. If it isn’t, then we move to $S(0)$ . As we keep going, either we eventually hit an element of $X$ or we don’t. If we do, the first one is the least element of $X$ . If not, then by induction the set of natural numbers not in $X$ is all of them, and $X$ must be empty!

It turns out that in the standard logical framework I’m using, any set can be equipped with a well-order. For instance, we could well-order the integers by saying $x\preceq y$ if either $|x|\leq|y|$ or $|x|=|y|$ and $x\leq y$ . We can list the integers in this order: $0,-1,1,-2,2,...,-n,n,...$ . The problem is that this doesn’t mesh with the algebraic structure very well.

Now as we’ll see when we get to them, the natural order on the real numbers is even further from being well-ordered, and there doesn’t seem to be any sensible way to well-order them. Still, we’ll see eventually that though the well-ordering principle is “plainly false” — very counterintuitive — it turns out to be logically equivalent to another tool that’s so incredibly useful we really should accept this unexpected fact.

April 2, 2007 Posted by John Armstrong | Fundamentals, Orders | Leave a Comment

The ring of integers

As I mentioned before, the primal example of a ring is the integers $\mathbb{Z}$ . So far we’ve got an ordered abelian group structure on the set of (equivalence classes of) pairs of natural numbers. Now we need to add a multiplication that distributes over the addition.

First we’ll figure out how to multiply natural numbers. This is pretty much as we expect. Remember that a natural number is either ${}0$ or $S(b)$ for some number $b$ . We define
$a\cdot0=0$
$a\cdot S(b)=(a\cdot b)+a$
where we’ve already defined addition of natural numbers.

Firstly, this is commutative. This takes a few inductions. First show by induction that ${}0$ commutes with everything, then show by another induction that if $a$ commutes with everything then so does $S(a)$ . Then by induction, every number commutes with every other. I’ll leave the details to you.

Similarly, we can use a number of inductions to show that this multiplication is associative — $(a\cdot b)\cdot c=a\cdot(b\cdot c)$ — and distributes over addition of natural numbers — $a\cdot(b+c)=a\cdot b+a\cdot c$ . This is extremely tedious and would vastly increase the length of this post without really adding anything to the exposition, so I’ll again leave you the details. I’m reminded of something Jeff Adams said (honest, I’m not trying to throw these references in gratuitously) in his class on the classical groups. He told us to verify that the commutator in an associative algebra satisfies the Jacobi identity because, “It’s long and tedious and doesn’t add much, but I had to do it when I was a grad student, so now you’re grad students and it’s your turn.”

So now these operations — addition and multiplication — of natural numbers make $\mathbb{N}$ into what some call a “semiring”. I prefer (following John Baez) to call it a “rig”, though: a “ring without negatives”. We use this to build up the ring structure on the integers.

Recall that the integers are (for us) pairs of natural numbers considered as “differences”. We thus define the product
$(a,b)\cdot(c,d)=(a\cdot c+b\cdot d,a\cdot d+b\cdot c)$

Our life now is vastly easier than it was above: since we know addition and multiplication of natural numbers is commutative, the above expression is manifestly commutative. No work needs to be done! Associativity is also easy: just set up both triple products and expand out, checking that each term is the same by the rig structure of the natural numbers. Similarly, we can check distributivity, that $(1,0)$ acts as an identity, and that the product of two integers is independent of the representing pair of natural numbers.

Lastly, multiplication by a positive integer preserves order. If $a<b$ and $0<c$ then $ac<bc$ . Together all these properties make the integers as we’ve defined them into a commutative ordered ring with unit. The proofs of all these things have been incredibly dull (I actually did them all today just to be sure how they worked), but it’s going to get a lot easier soon.

March 29, 2007 Posted by John Armstrong | Fundamentals, Numbers, Ring theory | 1 Comment

Integers

I’m back from Ohio at the College Perk again. The place looks a lot different in daylight. Anyhow, since the last few days have been a little short on the exposition, I thought I’d cover integers.

Okay, we’ve covered that the natural numbers are a commutative ordered monoid. We can add numbers, but we’re used to subtracting numbers too. The problem is that we can’t subtract with just the natural numbers — they aren’t a group. What could we do with $2-3$ ?

Well, let’s just throw it in. In fact, let’s just throw in a new element for every possible subtraction of natural numbers. And since we can get back any natural number by subtracting zero from it, let’s just throw out all the original numbers and just work with these differences. We’re looking at the set of all pairs $(a,b)$ of natural numbers.

Oops, now we’ve overdone it. Clearly some of these differences should be the same. In particular, $(S(a),S(b))$ should be the same as $(a,b)$ . If we repeat this relation we can see that $(a+c,b+c)$ should be the same as $(a,b)$ where we’re using the definition of addition of natural numbers from last time. We can clean this up and write all of these in one fell swoop by defining the equivalence relation: $(a,b)\sim(a',b')\Leftrightarrow a+b'=b+a'$ . After checking that this is indeed an equivalence relation, we can pass to the set of equivalence classes and call these the integers $\mathbb{Z}$ .

Now we have to add structure to this set. We define an order on the integers by $(a,b)\leq(c,d)\Leftrightarrow a+d\leq b+c$ . The caveat here is that we have to check that if we replace a pair with an equivalent pair we get the same answer. Let’s say $(a,b)\sim(a',b')$ , $(c,d)\sim(c',d')$ , and $(a,b)\leq(c,d)$ . Then
$a'+b+c+d'=a+b'+c'+d\leq b+b'+c'+c$
so $a'+d'\leq b'+c'$ . The first equality uses the equivalences we assumed and the second uses the inequality. Throughout we’re using the associativity and commutativity. That the first inequality implies the second follows because addition of natural numbers preserves order.

We get an addition as well. We define $(a,b)+(c,d)=(a+c,b+d)$ . It’s important to note here that the addition on the left is how we’re defining the sum of two pairs, and those on the right are additions of natural numbers we already know how to do. Now if $(a,b)\sim(a',b')$ and $(c,d)\sim(c',d')$ we see
$(a+c)+(b'+d')=(a+b')+(c+d')=(b+a')+(d+c')=(a'+c')+(b+d)$
so $(a+c,b+d)\sim(a'+c',b'+d')$ . Addition of integers doesn’t depend on which representative pairs we use. It’s easy now to check that this addition is associative and commutative, that $(0,0)$ is an additive identity, that $(b,a)+(a,b)\sim(0,0)$ (giving additive inverses), and that addition preserves the order structure. All this together makes $\mathbb{Z}$ into an ordered abelian group.

Now we can relate the integers back to the natural numbers. Since the integers are a group, they’re also a monoid. We can give a monoid homomorphism embedding $\mathbb{N}\rightarrow\mathbb{Z}$ . Send the natural number $a$ to the integer represented by $(a,0)$ . We call the nonzero integers of this form “positive”, and their inverses of the form $(0,a)$ “negative”. We can verify that $(a,0)\geq(0,0)$ and $(0,a)\leq(0,0)$ . Check that every integer has a unique representative pair with ${}0$ on one side or the other, so each is either positive, negative, or zero. From now on we’ll just write $a$ for the integer represented by $(a,0)$ and $-a$ for the one represented by $(0,a)$ , as we’re used to.

March 18, 2007 Posted by John Armstrong | Fundamentals, Numbers | Leave a Comment

More structure of the Natural Numbers

Now we know what the natural numbers are, but there seems to be a lot less to them than we’re used to. We don’t just take successors of natural numbers — we add them and we put them in order. Today I’ll show that if you have a model of the natural numbers it immediately has the structure of a commutative ordered monoid.

The major tool for working with the natural numbers is “induction”. This uses the property that every natural number is either ${}0$ or the successor of some other natural number, as can be verified from the universal property. Think of it like a ladder: proving a statement to be true for ${}0$ lets you get on the bottom of the ladder. Proving that the truth of a statement is preserved when we take a successor lets you climb up a rung. If you can get on the ladder and you can always climb up a rung, you can climb as far as you want.

First let’s define the order. We say the natural number $a$ is less than or equal to the natural number $b$ (and write $a\leq b$ ) if either $a$ and $b$ are the same number, or if $b$ is the successor of some number $c$ and $a\leq c$ . This seems circular, but it’s really not. As we step down from $b$ to $c$ (maybe many times), eventually either $c$ will be equal to $a$ and we stop, or $c$ becomes ${}0$ and we can’t step down any more. A more colloquial way of putting this relation is that we can build a chain of successors from $a$ to $b$ .

The relation $\leq$ is reflexive right away. It’s also transitive, since if we have three numbers $a$ , $b$ , and $c$ with $a\leq b$ and $b\leq c$ then we have a chain of successors from $a$ to $b$ and one from $b$ to $c$ , and we can put them together to get one from $a$ to $c$ . Finally, the relation is antisymmetric, since if we have two different numbers $a$ and $b$ with both $a\leq b$ and $b\leq a$ , then we can build a chain of successors from $a$ back to itself. That would make the successor function fail to be injective which can’t happen. This makes $\leq$ into a partial order. I’ll leave it to you to show that it’s total.

The monoid structure of the natual numbers is a bit easier. Remember that a number $b$ is either ${}0$ or $S(c)$ for some number $c$ . We define the sum of $a$ and $b$ using this fact: $a+0$ is $a$ , and $a+S(c)$ is $S(a+c)$ .

That ${}0$ behaves as an additive identity is clear. We need to show that the sum is associative: given three numbers $a$ , $b$ , and $c$ , we have $(a+b)+c=a+(b+c)$ . If $c=0$ , then $a+(b+0)=a+b=(a+b)+0$ . If $c=S(d)$ , then $a+(b+S(d))=a+S(b+d)=S(a+(b+d))$ and $(a+b)+S(d)=S((a+b)+d)$ . So if we have associativity when the third number is $d$ we’ll get it for $S(d)$ , and we have it for ${}0$ . By induction it’s true no matter what the third number is.

There are two more properties here that you should be able to verify using these same techniques. Addition is commutative — $a+b=b+a$ — and addition preserves order — if $a\leq b$ then $a+c\leq b+c$ .

Notice in particular that I’m not using any properties of how we model the natural numbers. The von Neumann numerals preferred by Bourbaki have the nice property that $a\leq b$ if $a\subseteq b$ as sets. But the Church numerals don’t. The specifics of the order structure really come from the Peano axioms. They shouldn’t depend at all on such accidents as what sort of model you pick, any more than they should depend on whether or not $3$ is Julius Cæsar. No matter what model you start with that satisfies the Peano axioms you get the commutative ordered monoid structure for free.

March 12, 2007 Posted by John Armstrong | Fundamentals, Numbers | 4 Comments

Orders

As a bonus today, I want to define a few more kinds of relations.

A preorder is a relation on a set which is reflexive and transitive. We often write a general preorder as $x\preceq y$ and say that $x$ precedes $y$ or that $y$ succeeds $x$ . A set equipped with a preorder is called a preordered set. If we also have that for any two elements $x$ and $y$ there is some element $z$ (possibly the same as $x$ or $y$ ) that succeeds both of them we call the structure a directed set.

A partial order is a preorder which is also antisymmetric: the only way to have both $x\preceq y$ and $y\preceq x$ is for $x$ and $y$ to be the same element. We call a set with a partial order a partially-ordered set or a “poset”.

Any set gives a partial order on its set of subsets, given by inclusion: if $A$ and $B$ are subsets of a set $X$ , then $A$ precedes $B$ if $A$ is contained in $B$ . This has the further nice property that it has a top element, $X$ itself, that succeeds every element. It also has a bottom element, the empty subset, that precedes everything. The same sort of construction applies to give the poset of subgroups of any given group. These kinds of partially-ordered sets are very important in logic and set theory, and they’ll come up in more detail later.

Finally, a partial order where for any two elements $x$ and $y$ we either have $x\preceq y$ or $y\preceq x$ is called a total order. Total orders show up over and over, and they’re nice things to have around. I must admit, though, that as far as I’m concerned they’re pretty boring in and of themselves.

March 11, 2007 Posted by John Armstrong | Fundamentals, Orders | 8 Comments

Natural Numbers

UPDATE: added paragraph explaining the meaning of the commutative diagram more thoroughly.

I think I’ll start in on some more fundamentals. Today: natural numbers.

The natural numbers are such a common thing that everyone has an intuitive idea what they are. Still, we need to write down specific rules in order to work with them. Back at the end of the 19th century Giuseppe Peano did just that. For our purposes I’ll streamline them a bit.

There is a natural number ${}0$ .
There is a function $S$ from the natural numbers to themselves, called the “successor”.
If $a$ and $b$ are natural numbers, then $S(a)=S(b)$ implies $a=b$ .
If $a$ is a natural number, then $S(a)\neq0$ .
For every set $K$ , if ${}0$ is in $K$ and the successor of each natural number in $K$ is also in $K$ , then every natural number is in $K$ .

This is the most common list to be found in most texts. It gives a list of basic properties for manipulating logical statements about the natural numbers. However, I find that this list tends to obscure the real meaning and structure of the natural number system. Here’s what the axioms really mean.

The natural numbers form a set $\mathbb N$ . The first axiom picks out a special element of $\mathbb N$ , called ${}0$ . Now, think of a set containing exactly one element: $\{*\}$ . A function from this set to any other set $S$ picks out an element of that set: the image of $*$ . So the first axiom really says that there is a function $0:\{*\}\rightarrow\mathbb N$ .

The second axiom plainly states that there is a function $S:\mathbb N\rightarrow\mathbb N$ . The third axiom says that this function is injective: any two distinct natural numbers have distinct successors. The fourth says that the image of the successor function doesn’t contain the image of the zero function.

The fifth axiom is where things get really interesting. So far we have a diagram $\{*\}\rightarrow\mathbb N\rightarrow\mathbb N$ . What the fifth axiom is really saying is that this is the universal such diagram of sets! That is, we have the following diagram:
Universal Property of Natural Numbers
with the property that if $K$ is any set and $z$ and $s$ are any functions as in the diagram, then there exists a unique function $f:\mathbb N\rightarrow K$ making the whole diagram commute. In fact, at this point the third and fourth Peano axioms are extraneous, since they follow from the universal property!

Remember, all a commutative diagram means is that if you have any two paths between vertices of the diagram, they give the same function. The triangle on the left here says that $f(0(*))=z(*)$ . That is, since $K$ has a special element, $f$ has to send ${}0$ to that element. The square on the right says that $f(S(n))=s(f(n))$ . If I know where $f$ sends one natural number $n$ and I know the function $s$ , then I know where $f$ sends the successor of $n$ . The universal property means just that $\mathbb N$ has nothing in it but what we need: ${}0$ and all its successors, and ${}0$ is not the successor of any of them.

Of course, by the exact same sort of argument I gave when discussing direct products of groups, once we have a universal property any two things satisfying that property are isomorphic. This is what justifies talking about “the” natural number system, since any two models of the system are essentially the same.

This is a point that bears stressing: there is no one correct version of the natural numbers. Anything satisfying the axioms will do, and they all behave the same way.

The Bourbaki school like to say that the natural numbers are the following system: The empty set $\emptyset$ is zero, and the successor function is $S(n)=n\cup\{n\}$ . But this just provides one model of the system. We could just as well replace the successor function by $S(n)=\{n\}$ , and get another perfectly valid model of the natural numbers.

In the video of Serre that I linked to, he asks at one point “What is the cardinality of 3?” This betrays his membership in Bourbaki, since he clearly is thinking of 3 as some particular set or another, when it’s really just a slot in the system of natural numbers. The Peano axioms don’t talk about “cardinality”, and we can’t build a definition of such a purely set-theoretical concept out of what properties it does discuss. The answer to the question is “無!” (“mu”). The Bourbaki definition doesn’t define the natural numbers, but merely shows that within the confines of set theory one can construct a model satisfying the given abstract axioms.

This is how mathematics works at its core. We define a system, including basic pieces and relations between them. We can use those pieces to build more complicated relations, but we can only make sense of those properties inside the system itself. We can build models of systems inside of other systems, but we should never confuse the model with the structure — the map is not the territory.

This point of view seems to fetishize abstraction at first, but it’s really very freeing. I don’t need to know — or even care — what particular set and functions define a given model of the natural numbers. Anything I can say about one model works for any other model. As long as I use the properties as I’ve defined them everything will work out fine, and $1+2=3$ whether I use Bourbaki’s model or not.

March 5, 2007 Posted by John Armstrong | Fundamentals, Numbers | 11 Comments

Relations

Sooner or later I’ll have to use relations, so I may as well get the basics nailed down now.

A relation between two sets $X$ and $Y$ is just a subset $R$ of their Cartesian product $X\times Y$ . That is, it’s a collection of pairs $(x,y)$ . Often we’ll write $xRy$ when $(x,y)$ is in the relation.

A function $f$ is a special kind of relation where each element of $X$ shows up on the left of exactly one pair in $f$ . In this case if $(x,y)$ is in the relation we write $f(x)=y$ . Remember from our discussion of functions that I was saying every element of $X$ has to show up both at least once and at most once (that is, exactly once). A surjection is when every element of $Y$ shows up on the right side of a pair in $f$ at least once, and an injection is when each element in $Y$ shows up at most once.

Also interesting are the following properties a relation $R$ between a set $X$ and itself might have:

A relation is “reflexive” if $xRx$ for every $x$ in $X$ .
A relation is “irreflexive” if $xRx$ is never true.
A relation is “symmetric” if whenever $xRy$ then also $yRx$ .
A relation is “antisymmetric” if whenever $xRy$ and $yRx$ then $x$ and $y$ are the same.
A relation is “asymmetric” if whenever $xRy$ then $yRx$ is not true.
A relation is “transitive” if whenever $xRy$ and $yRz$ then also $xRz$ .

A very important kind of relation is an “equivalence relation”, which is reflexive, symmetric, and transitive. We’ve already used these a bunch of times, actually. When a group $G$ acts on a set $X$ , we can define a relation $\sim$ by saying $x\sim y$ whenever there is a group element $g$ so that $gx=y$ . Since the identity of $G$ sends every element of $X$ to itself, this is reflexive. If there is a $g$ so that $gx=y$ , then $g^{-1}y=x$ , so this is symmetric. Finally, if we have $g$ and $h$ so that $gx=y$ and $hy=z$ , then $(hg)x=z$ , so the relation is transitive.

When we have an equivalence relation $\sim$ on a set $X$ , we can break $X$ up into its “equivalence classes”. Any two elements $x$ and $y$ of $X$ are in the same equivalence class if and only if $x\sim y$ . We write the set of equivalence classes as $X/\sim$ . For group actions, these are the orbits of $G$ .

Show for yourself that in our discussion of cosets that there’s an equivalence relation going on, and that the cosets of $H$ in $G$ are the equivalence classes of elements of $G$ under this relation.

March 2, 2007 Posted by John Armstrong | Fundamentals | 2 Comments

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

Next Entries »

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
Archives

May 2013

M T W T F S S

« Sep

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 29 30 31
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider

The uniqueness of the integers

The characterization of the integers

Well-Ordering

The ring of integers

Integers

More structure of the Natural Numbers

Orders

Natural Numbers

Relations

Sets and functions

About this weblog

Recent Posts

Blogroll

Art

Astronomy

Computer Science

Education

Mathematics

Me

Philosophy

Physics

Politics

Science

RSS Feeds

Feedback

Subjects

Archives

Site info

Follow “The Unapologetic Mathematician”

May 2013
M	T	W	T	F	S	S
« Sep
		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	29	30	31