PineWikiRecall from SetTheory the definition of an ordered pair (x,y) as , 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. We can't talk about what we can't talk about, or as Wittgenstein put it: Wovon man nicht sprechen kann, darüber muß man schweigen. But in a sense these other, ineffable functions still exist, so we use a definition of a function that encompasses them.
1. Examples of functions
- f(x) = x². Note: this single rule gives several different functions, e.g. f:ℝ→ℝ, f:ℤ→ℤ, f:ℕ→ℕ, f:ℤ→ℕ. Changing the domain or codomain changes the function.
- f(x) = x+1.
- Floor and ceiling functions: when x is a real number, floor(x) (usually written ⌊x⌋) is the largest integer less than or equal to x and ceiling(x) (usually written ⌈x⌉) is the smallest integer greater than or equal to x. E.g. ⌊2⌋=⌈2⌉=2, ⌊2.337⌋=2, ⌈2.337⌉=3.
- The function from { 0, 1, 2, 3, 4 } to { a, b, c } given by the following table:
0
a
1
c
2
b
3
a
4
b
1.1. Functions of more than one argument
If f:A×B→C, then we write f(a,b) for f((a,b)). Functions on more than two arguments are defined similarly.
1.2. Sequences
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 with x1 = a, x2 = b, x3 = c.
2. 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)).
3. Inverses
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.
4. Properties of functions
4.1. One-to-one/injective
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.
4.2. Onto/surjective
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.
4.3. 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).
4.4. Monotonicity
For functions between ordered sets, there are various monoticity properties. A function f is
increasing if f(x) < f(y) when x < y,
non-decreasing if f(x) ≤ f(y) when x < y,
non-increasing if f(x) ≥ f(y) when x < y, and
decreasing if f(x) > f(y) when x < y.
For example:
- f(x) = x+1 is increasing.
- f(x) = ⌊x⌋ is non-decreasing.
- f(x) = -⌊x⌋ is non-increasing.
f(x) = 2-x is decreasing.
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.
4.5. 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:
- If f and g are both injective, so is f∘g.
- If f and g are both surjective, so is f∘g.
- If f∘g is surjective, so is f (but not necessarily g).
- If f∘g is injective, so is g (but not necessarily f).
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.