Counting Arguments

In discrete mathematics, people often use counting arguments, which are based on deducing things from sizes of sets.

For example, suppose we have a function from a set with n elements to another set with n elements. This function is 1-to-1 iff it’s onto (1-to-1, or injective, means that f(x) != f(y) when x != y; onto, or surjective, means that every element in the range can be written as f(x) for some x; invertible, or bijective, means 1-to-1 and onto).

To see why, let’s say that the function f from X to Y is not onto. There is some y in Y that isn’t of the form f(x) for some x in X. So the image of f has at most n-1 elements. But X has n elements, so the function can’t be 1-to-1. This is called the pigeonhole principle: if there are more pigeons than pigeonholes, at least two pigeons must share a pigeonhole. Similarly, if the function is not 1-to-1, we must have f(x1) = f(x2) for some distinct x1 and x2 in X. But then the image has at most n-1 elements, whereas Y has n.

In algebra, it’s relevant because it implies that in a finite ring, every element that isn’t a zero divisor is a unit. If a satisfies the condition that ab = 0 implies a = 0, then the function from R to itself that sends x to ax is 1-to-1. This is because ax = ay implies a(xy) = 0, so xy = 0, i.e. x = y. Then the function is onto, and we can find some b with ab = 1. In particular, if R is a finite integral domain, it’s a field. I should add that this requires no additional assumptions; the existence of a implies that R has 1, and even if R is not commutative, the condition implies that ab = ba = 1 for some b.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: