A **relation** from to is just a subset of . For example, is a relation from to that includes, say, , and so on. We generally write instead of $(a,b)\in R$. Except in very few circumstances, we actually only care about three kinds of relations.

The first kind is an **order** relation. A **partial order** is a relation from a set to itself with for all , with and only if , and with whenever and for some . We call these properties “reflexive,” “anti-symmetric,” and “transitive” respectively. Because this includes the case , it is called a “weak” partial order. There’s also a “strict” notion of a partial order: a relation < with for *no* , with and for *no* pair , and that is also transitive. The definitions are pretty much equivalent. Given a weak partial order , we get a strict partial order defined by when and . Likewise, we can get a weak partial order from a strict partial order by including the case of equality.

The reason that partial orders are “partial” is that it’s possible to have elements that aren’t comparable: that is, neither nor . If we have a partial order on where every pair of elements *is* comparable, we call it a **total order**. Total orders arrange sets in lines. Partial orders are more complex, but it’s good to think of them in terms of what’re called “Hasse diagrams.” These are just graphs with nodes for elements of and a line going upwards from to whenever

and there’s no element between and (so with ). You can then infer the rest of the relation by using transitivity: whenever there is some chain of lines going up from to . At right is an example for one of the most common partial orders, the subset relation, on the power set of . Another good example of a partial order is on : if $\latex a$ divides $\latex b$.

The second big kind of relation is the **equivalence relation**. Like partial orders, equivalence relations are reflexive and transitive. But instead of anti-symmetry, we require them to be symmetric: that is, if is an equivalence relation on , we must have whenever , for all . Equality is the ur-equivalence relation, and the most restrictive one. Another example is equivalence modulo on : if is divisible by . For example, for , we have , , , and so on.

Call the set of elements that is equivalent to under the **equivalence class** of , written sometimes as . The general idea is that an equivalence relation splits up its set into equivalence classes. In fact, this is our first important theorem. We call two sets **disjoint** if their intersection is the empty set, and we call a subset of a **partition** if its elements are all disjoint from each other and their union is itself. So every element of is in exactly one of the sets of the partition. Then we have

**THEOREM.** Every equivalence relation on defines a partition whose elements are its equivalence classes, and each partition on defines an equivalence relation by if there is an element of containing both of them.

If you haven’t proved many theorems, try proving this one. It’s easy! Both directions are very useful.

The third kind of relation can occur between any two sets, and should be the most familiar. A **function** or **map** from to is a relation that contains *exactly one* pair for each . We use letters like and for functions, and write or rather than . The element is called the **image** of , and the definition of a function ensures that each has an image, and just one image, in . (Oh, is the **preimage** of ). So a function can really be thought of as a machine that takes in and prints out its image.

Functions have a lot of terminology. The set is called the **domain** and the **codomain**, and we write to show this relationship. The set of elements is called the **range** of . If the range *is* the codomain, so “fills up” , we say that is **surjective** or **onto**. If hits each element of its range just once, so only if , then is **injective** or **one-to-one**. For any two functions , we can define their **composition**, a function defined by . Note the function is given by *first* applying , *then* . Confusing, but hard to stop using once you’re used to it.

Okay, so why do “surjective” and “injective” have such similar names? Because they obey an important duality property. Let $f:A\rightarrow B,g,h:B\rightarrow C,j,k:Z\rightarrow A$. If is *injective*, then implies , so you can cancel on the *left*. If is *surjective*, then , so you can cancel on the *right*. Prove these! (The best way to really get this is to look at examples where you can’t cancel . For example, if isn’t surjective, then and could disagree outside its range and still have .)

If is both surjective and injective, then it can be cancelled on both sides and we call it **bijective**. We can define an **inverse function** by . By surjectivity, every element of is for some , and by injectivity, this holds for just one , so the inverse function is well defined. It is also true that . So this is why cancellation works: if for a bijective , then we can just compose with to get . This is very basic category theory! Another way of looking at bijections is by observing that they pair off elements of their domain with elements of their codomain.

Functions on are always the best examples because they have graphs. So

- The function are bijective (every number has a cube root!)
- The function is injective but not surjective (every number has a log, but the log is always positive!)
- The function is surjective but not injective.
- The function is neither injective nor surjective.

Here’s the great thing about graphs. Remember the Horizontal Line Test? You can test injectivity by seeing if any horizontal line hits your graph more than once? Well, there’s a Horizontal Line Test for *surjectivity*, too: just see if any horizontal line hits your graph *less* than once! Which is obvious when you think about it, but it illustrates the duality between the concepts in a way they don’t teach at school.

One more concept is needed. Given a set , we can define . Likewise, given , we can define . The words **image** and **preimage** are also used to describe these operations. Note that is defined even if is not bijective, since . However, it is *not* the inverse of : just take a non-injective function like and look at .

Parting words: the set of functions from to is sometimes called . Can you see why? We will talk more about cardinality later. Tomorrow, I want to start topology.

**3 Comments so far**

Leave a comment

[…] a pairing off between a set and a set is really just a function from to . If you recall the post about relations, you’ll realize that it is actually a one-to-one and onto function, or bijection. As I […]

Pingback by Cardinality | Gracious Living and the Two Meat MealNovember 1, 2010 @ 04:45[…] of these sequences is also uncountable. But a sequence is just a function whose domain is . In my post about relations, I gave a common notation for the set of such functions: . So is uncountable. In fact (try this […]

Pingback by Countability | Gracious Living and the Two Meat MealNovember 2, 2010 @ 01:28[…] the definition of totally ordered set (toset). A convex subset of a toset is one that includes the interval whenever and are in the […]

Pingback by Connectedness « Gracious Living and the Two Meat MealNovember 9, 2010 @ 09:30