• Advertisements

## Functions, Mappings, and Counting, Surjections, Injections, and Bijections

See more in Google Books’ scan of Norman Biggs’ Discrete Mathematics:

A few quick points to be expanded upon later, correct me in the comments if I make any mistatements:

• functions map from one set to another, from a domain to a codomain; the set of all output values is the range. The sets can be finite sets or infinite sets. Common language is such as “the function f maps from the set X to the set Y.” Often X and Y are infinite like N (natural numbers) and Z (all integers). X would be the range and Y would be the codomain.
• The input numbers from the domain are called arguments, and the input is usually placed into a placeholder called an independent variable–the independent variables inputted may in fact be dependent variables of another function as in the composition of functions.
• The output numbers from the range are called values, and are represented by a placeholder called the dependent variable.
• Function definitions specify the codomain, not the range, thus when function definitions say something like “a function from X to Y” or ” ƒ is a function on N into R” the Y and the R specify the codomain, not the range:

Formal description of a function typically involves the function’s name, its domain, its codomain, and a rule of correspondence.

• The range is a consequence of the function, the range consists of all the values mapped to/outputted by the function, but the range isn’t stated in the function definition, the codomain is.
• Each number in the domain can map to at most one value. The function may be undefined for certain input numbers. However, each value in the range can be mapped to by more than one argument in the domain. The codomain can have values which aren’t mapped to at all; the range is the set of all values that are mapped to.
• When each value is mapped to by at least one input number, that’s called a surjection. In a surjection, each value must be mapped to by at least one input number, and each value may be mapped to by more than one input number.
• When each input number maps to at most one value, that’s called an injection. In an injection, there can be values in the range set which are not mapped to at all, but no value can be mapped to by more than one input number.
• When there’s an injection, and some of the values aren’t mapped to, then that value set must be a codomain, and not a range of the function. Because according to Wikipedia “the range of a function is the set of all “output” values produced by that function”–if the range is the set of all output values, and in an injection some of the values might not be mapped to by the function, then that isn’t a range, but a codomain.
• “If f is a surjection then its range is equal to its codomain.” This is because in a surjection, each value in the target set is mapped to by a input value, there are no unmapped-to values as there could be in an injection. Thus I figure in an injection, where there are values that are not mapped-to, the codomain is larger than the range, but in a surjection, the range is equal to the codomain.
• When a function is both a surjection injection and an injection, i.e. each value is mapped to by one and only one input number, that’s called a bijection.  Think of bijections as being one-to-one mappings.

Here’s some interesting information on ranges and codomains from Wikipedia:

Mathematical functions are denoted frequently by letters, and the standard notation for the output of a function ƒ with the input x is ƒ(x). A function may be defined only for certain inputs, and the collection of all acceptable inputs of the function is called its domain. The set of all resulting outputs is called the range of the function. However, in many fields, it is also important to specify the codomain of a function, which contains the range, but need not be equal to it. The distinction between range and codomain lets us ask whether the two happen to be equal, which in particular cases may be a question of some mathematical interest.

For example, the expression ƒ(x) = x2 describes a function ƒ of a variable x, which, depending on the context, may be an integer, a real or complex number or even an element of a group. Let us specify that x is an integer; then this function relates each input, x, with a single output, x2, obtained from x by squaring. Thus, the input of 3 is related to the output of 9, the input of 1 to the output of 1, and the input of −2 to the output of 4, and we write ƒ(3) = 9, ƒ(1)=1, ƒ(−2)=4. Since every integer can be squared, the domain of this function consists of all integers, while its range is the set of perfect squares. If we choose integers as the codomain as well, we find that many numbers, such as 2, 3, and 6, are in the codomain but not the range.

….

In mathematics, the codomain, or target set, of a function, described symbolically as f : XY, is the set Y into which all of the output of the function is constrained to fall.

All the output that the function can possibly produce from its given domain, X, is the image. The function’s image will not necessarily fill the entire codomain Y, even though the output must all land inside of the codomain: there can be points in the codomain that are “not used.”

The codomain (or target) is part of the definition of a function. The image (or range) is a consequence of the definition of a function: the image is a subset of the codomain and depends upon (i.e. is a consequence of) how the definition of the function prescribes the domain, codomain, and map or formula.

(The domain of f is the set X.)

Internal tag: math

Advertisements

### One Response

1. What is the inverse operation for reciprocal?