[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

PDF version

Recall from SetTheory the definition of an ordered pair (x,y) as { {x}, {x,y} }, with the interpretation that x is the first element and y is the second element. The Cartesian product A×B of two sets A and B is {(x,y)|x∈A,y∈B}. A relation R on A and B is any subset of A×B; it is interpreted as a two-argument predicate that holds for x and y if and only if (x,y)∈R. The set A is called the domain of R and B the codomain. A special kind of relation is a function; this is a relation f for which there is exactly one y for each x such that (x,y)∈f. We write f(x) for this unique y such that (x,y)∈f.

For more on relations and their properties, see Relations.

When the domain is finite, we can always write down a list of all the values of a function. For infinite domains (e.g. ℕ), almost all functions are impossible to write down, either as an explicit table (which would need to be infinitely long) or as a formula (there aren't enough formulas). Most of the time we will be interested in functions that have enough structure that we can describe them succinctly, for simple practical reasons. But in a sense these other, ineffable functions still exist, so we use a definition of a function that encompasses them.

Examples of functions

Sequences and generalized Cartesian products

Sequences, e.g. x=1,2,3,4,... or y=1,0,1,0,1,0,... are just thinly-disguised functions from an index set (often ℕ or ℕ-{0}) to some codomain. When we think of a function as a sequence, we usually write the argument as a subscript, e.g. x0 = 1 instead of x(0) = 1. Sequences also give us a way to define order tuples with more than two elements: (a,b,c) is the sequence represented by the function x from {1,2,3} to some codomain with x1 = a, x2 = b, x3 = c.

We can think of the Cartesian product of k sets (where k need not be 2) as a set of sequences indexed by the set {1..k} (or sometimes {0..k-1}). Technically this means that A×B×C (a set of functions) is not the same as (A×B)×C (the set of all ordered pairs whose first element is an ordered pair in A×B and whose second element is in C) or A×(B×C) (the set of ordered pairs whose first element is in A and whose second element is in B×C). This distinction has no practical effect and so we typically ignore it; the technical justification for this is that the three different representations are all isomorphic in the sense that a translation exists between each pair of them that preserves their structure.

A special case is the Cartesian product of no sets. This is just the set containing a single element, the empty sequence.

Cartesian products over indexed collections of sets can be written using product notation (see SummationNotation), e.g.

\prod_{i=1}^{n} A_n

or even

\prod_{x \in \mathbb{R}} A_x

Functions of more (or less) than one argument

If f:A×B→C, then we write f(a,b) for f((a,b)). In general we can have a function with any number of arguments (including 0); a function of k arguments is just a function from a domain of the form A₁×A₂×...Ak to some codomain B.

Composition of relations and functions

Given relations R:A→B and Q:B→C, their composition Q∘R is the relation given by {(x,y)|x∈A,y∈C,∃z (x,z)∈R /\ (z,y)∈Q}. As a special case, if f:A→B and g:B→C are functions, then g∘f is also a function, and (g∘f)(x) = g(f(x)).


Given a relation R:A→B, its inverse is a relation R-1:B→A given by R-1 = { (y,x) | (x,y) ∈ R }. All relations (and thus all functions) have inverses in this sense; however, the inverse of a function is itself a function only under certain special conditions—see the section on "one-to-one correspondences" below.

Properties of functions


A function is one-to-one or injective if x≠y implies f(x)≠f(y), for all x and y in its domain. The function f(x)=x² from ℕ to ℕ is injective. The function f(x) = x² from ℤ to ℤ is not (f(-1) = f(1) = 1). The function f(x) = x+1 from ℕ to ℕ is injective.

By contraposition, an equivalent definition is that f(x)=f(y) implies x=y for all x and y in the domain.


A function is onto or surjective if its range equals its codomain, where the range is the set { y | y = f(x) for some x }. A simpler definition is that f is onto if and only if there is at least one x with f(x)=y for each y. The function f(x)=x² from ℕ to ℕ is not surjective, because its range includes only perfect squares. The function f(x) = x+1 from ℕ to ℕ is not surjective because its range doesn't include 0. However, the function f(x) = x+1 from ℤ to ℤ is surjective, because for every y in ℤ there is some x in ℤ such that y = x+1.

One-to-one correspondence/bijective

A function is a one-to-one correspondence or is bijective if it is both one-to-one/injective and onto/surjective. Of the functions we have been using as examples, only f(x) = x+1 from ℤ to ℤ is bijective.

If there is a bijection from A to B, then A and B are said to have the same size or cardinality; see HowToCount.

One way to think about injections, surjections, and bijections is to count how many x in the domain get mapped to each y in the codomain. If it's at most 1, then you have an injection. If it's at least 1, you have a surjection. If it's both at most 1 and at least 1 (i.e., it's exactly 1), then you have a bijection. The nice thing about this last case is that bijections are invertible: their inverses are also functions. Functions that are not bijections are not thought of as invertible, because they don't have inverse functions (they do, however have inverse relations).


For functions between ordered sets, there are various monoticity properties. A function f is

For example:

Some functions are increasing over parts of their domain and decreasing over others; for example, f(x)=x² is decreasing for x < 0 and increasing for x > 0.

These sorts of monotonicity properties are useful for ProvingInequalities. Note that being increasing or non-decreasing is preserved by composition: e.g., if f and g are both increasing, then so is f∘g.

Properties of compositions of functions

Various properties of f∘g (e.g., being injective) are related to the properties of f and g individually. For example, each of the following holds:

We won't prove all of these, but here is an example of a what a proof of the third fact might look like: Suppose f is not surjective. Then there is some y in the codomain of f such that y≠f(x) for any x in the domain of f. So in particular y doesn't equal f(g(z)) for any g(z), and f∘g is not surjective either.


2014-06-17 11:58