[1.1] (Functions) A function from one set to a second set relates objects in the first set to objects in the second set, always subject to the following condition: no object in the first set is related to more than one object in the second set. (This condition means that a function is single-valued)
Notation: if f is the name of a function then f(x) = y means that f relates x to y. This is called function notation.
The only way that a function can relate x to y and relate the same x to y' is that y = y'.
It is often said that f carries object x onto object y. Intuitively speaking, x is what is being carried.
y is called the image of x. Intuitively speaking, images are the recipients of the carrying process.
Example [1.1a]
On telephone buttons are some letters with numbers:
Example [1.1b]
Consider now the tripling relation which relates each natural number with its triple: x ~ 3x. This is a function because each natural number has one and only one triple. Let g be the name of this function. Then
This function notation allows the variable x to be replaced by specific values (or names):
Example [1.1c]
Using the division algorithm there is a "natural" function h from N0, the non-negative integers, to J10, the integers mod 10:
Example [1.1d]
Let U and V be any non-empty sets. Let c be a fixed object in V. Define f as
Example [1.1e]
Let U be any set. The identity function on U carries each object in U back onto itself.
There are always two sets directly involved with every function. (The two sets may be the same.)
The domain of a function is the set of all objects being carried by the function.
x is in the domain of a function f if and only if f carries x onto something: f(x) = some object in the second set.
Usually the domain is the whole first set. But sometimes it is convenient for the domain to be a proper subset of someuniverse.
The range of a function is the set of all images. y is in the range if and only if f(some object in first set) = y.
Usually the range is a proper subset of a second set, but it may be the whole second set
[2.2] (Technical definitions of domain and range) Let f be a function from U to V.
x is in the domain of f if and only if f(x) = some object in V
y is in the range of f if and only if for some x in U, f(x) = y.
In example [1.1a] domain of f = {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,R,S,T,U,V,W,X,Y}, range of f = {2,3,4,5,6,7,8,9}.
In example [1.1b] domain of g = N (all natural numbers), range of g = 2N (all even natural numbers)
In example [1.1c] domain of h = N0 (all non-negative integers), range of h = J10 = {0,1,2,3,4,5,6,7,8,9}
In example [1.1d] domain of f = U, range of f = {c}
In example [1.1e] domain of I = U, range of I = U.
Let f be a function from U to V. If all of the images of objects in U are in V, then f is a function from U into V. ("Into" is just another word for "to.")
If every object in V is an image, then f is said to be a function from U onto V.
The functions in examples [1.1a], [1.1c], [1.1e] are "onto". In example [1.1b] if g is considered a function from N to N then g is not "onto", only "into". If g is a function from N to 2N, then g is "onto". A function from a set to a second set is "onto" if and only if the range of the function is all of the second set.
It is important to understand that a function is allowed to carry two distinct objects in the first set onto the same object in the second set. The functions in examples [1.1a], [1.1c], [1.1d] do this. But the following function is different. f is a function from N3 = {1,2,3} to V = {a,b,c,d} (four balls) defined by
[2.3a] (One-to-one functions) A function from a first set to a second set is one-to-one if it carries distinct objects in the first set onto distinct objects in the second set.
Notation:f is 1-1 means if x1 is not equal to if x2 then f(x1) is not equal to f(x2).
The functions in examples [1.1b] and [1.1e] are one-to-one. They carry distinct objects onto distinct objects.
In examples [1.1a], [1.1c],[1.1d] (First set has more than one object) are not 1-1. They carry a pair of distinct objects onto a single object in the second set. in example [1.1a] the function carries distinct objects A,B,C onto a single number 2.
The contrapositive of the implication expressed in [2.3a] provides an equivalent definition:
[2.3b] (One-to-one functions) A function from set U to set V is one-to-one if images in the second set imply that what is carried onto them are equal.
Notation: f is 1-1 means f(x1) = f(x2) => x1 = x2.
Often it is easier to use [2.3b] to prove that a function is 1-1. For example, to prove that the tripling function g in example [1.1b] is 1-1 start with equal images: g(x1) = g(x2). Then use a chain of implications to arrive at x1 = x2:
A function being "onto" and a function being 1-1 are independent ideas. There are functions that are neither, there are functions are one but not the other. Finally there are functions that are both 1-1 and "onto."
[2.4] (One-to-one correspondences) A function from a first set to a second set is a one-to-one correspondence between the two sets if and only if the function satisfies the following two conditions:
(a) the function is one-to-one;
(b) the function carries the first set onto the second set.
Notation: If f carries U onto V and is one-to-one then f is a one-to-one correspondence.
Let f be a function from N5 = {1,2,3,4,5} to the set of balls V = {a,b,c,d,e}, defined by
Intuitively speaking, a one-to-one correspondence can be used to count objects in a (finite) set.:
[2.5]There are exactly n objects in a given set if and only if there is a one-to-one correspondence between Nn and the given set.
A father wants to give his to sons each a bag of many marbles. One bag contains red marbles, the other contains black marbles. There must be an equal number of marbles in each bag. Two methods can be used to prove this equality:
Method I The father counts the number of marbles in each bag to see if the numbers are equal.
Method II The boys who cannot count that big a number devise another method. They place all the red marbles in a straight line. Under each red marble a black marble is placed. There should be no more marbles of one color than marbles of the other color.
Method II is more interesting. It establishes a one-to-one correspondence between marbles of the two colors. From method II a generalization of [2.5] can be defined:
[2.6] (Same number of objects) Two sets have the same number of objects if and only if there is a one-to-one correspondence between them.
Clearly, for a set to have exactliy n objects, it must have the same number of objects as Nn. But using [2.6] it is possible to say that there are just as many natural numbers as negative integers. The one-to-one correspondence is the natural function f: