Surjection, injection and bijection
The rule defining the mapping f: X (or the function /) can be conventionally represented by arrows (Fig. 2.1). If there is at least one element in the set Y that none of the arrows points to, then this indicates that the range of values of the function f does not fill the entire set Y, i.e. f(X) C Y.
If the range of values / coincides with Y, i.e. f(X) = Y, then such a function is called surjective) or, in short, surjection, and the function / is said to map the set X onto the set Y (in contrast to the general case of mapping the set X into the set Y according to Definition 2.1). So, / : X is a surjection if Vy 6 Y 3x € X: /(x) = y. In this case, in the figure, at least one arrow leads to each element of the set Y (Fig. 2.2). In this case, several arrows may lead to some elements from Y. If no more than one arrow leads to any element y € Y, then / is called an injective function, or injection. This function is not necessarily surjective, i.e. the arrows do not lead to all elements of the set Y (Fig. 2.3).
- So, the function /: X -Y Y is an injection if any two different elements from X have as their images when mapping / two different elements from Y, or Vy £ f(X) C Y 3xeX: f(x) = y. Surjection, injection and bijection. Reverse mapping. Composition of mappings is a product of sets. Display schedule. The mapping /: X->Y is called bijective, or bi-jection, if each element of y 6 Y is the image of some and the only element from X, i.e. Vy € f(X) = Y E!x € X: f(x) = y.
In a particular case, the sets X and Y may coincide (X = Y). Then the bijective function will map the set X onto itself. The bijection of a set onto itself is also called a transformation. 2.3. Inverse mapping Let /: X -? Y is a certain bijection and let y € Y. Let us denote by /_1(y) the only element x € X such that /(r) = y. Thus we define some mapping 9: Y Xу which is again a bijection. It is called the inverse mapping, or inverse bijection to /. Often it is also simply called the inverse function and is denoted /"*. In Fig. 2.5, the function d is precisely the inverse of /, i.e. d = f"1.
Examples of solutions in problems
The mappings (functions) / and are mutually inverse. It is clear that if a function is not a bijection, then its inverse function does not exist. Indeed, if / is not injective, then some element y € Y can correspond to several elements x from the set X, which contradicts the definition of a function. If / is not surjective, then there are elements in Y for which there are no preimages in X, i.e. for these elements the inverse function is not defined. Example 2.1. A. Let X = Y = R - a set of real numbers. The function /, defined by the formula y = For - 2, i,y € R, is a bijection. The inverse function is x = (y + 2)/3. b. The real function f(x) = x2 of a real variable x is not surjective, since negative numbers from Y = R are not images of elements from X = K as /: Γ -> Y. Example 2.2. Let A" = R, and Y = R+ be the set of positive real numbers. The function f(x) = ax, a > 0, af 1, is a bijection. The inverse function will be Z"1 (Y) = 1°8a Y
- Surjection, injection and bijection. Reverse mapping. Composition of mappings is a product of sets. Display schedule. 2.4. Composition of mappings If f:X-*Y and g:Y-*Zy then the mapping (p:X -+Z, defined for each a: 6 A" by the formula =, is called a composition (superposition) of mappings (functions) / and d> or a complex function, and is designated rho/ (Fig. 2.6).
- Thus, a complex function before f implements the rule: i Apply / first, and then di, i.e. in the composition of operations “before / you must start with the operation / located on the right. Note that the composition Fig. 2.6 mappings are associative, i.e. if /: X -+Y, d: Y Z and h: Z-*H> then (hog)of = = ho(gof)i which is easier to write in the form ho to /. Let's check this as follows: On any wK "oaicecmee X there is defined a mapping 1x -X X, called identical, often also denoted by idx and given by the formula Ix(x) = x Vx € A". Its -action is that it leaves everything to in their places.
Each point M can be associated with a pair (i, y) of real numbers where x is the coordinate of the point Mx on the coordinate axis Ox, and y is the coordinate of the point Mu on the coordinate axis Oy. Points Mx and Mu are the bases of perpendiculars dropped from point M on the Ox and Oy axes, respectively. The numbers x and y are called the coordinates of point M (in the selected coordinate system), and x is called the abscissa of point M, and y is the ordinate of this point. It is obvious that each pair (a, b) of real numbers a, 6 6R corresponds to a point M on the plane, which has these numbers as its coordinates. And conversely, each point M of the plane corresponds to a pair (a, 6) of real numbers a and 6. In the general case, pairs (a, b) and (6, a) define different points, i.e. It is important which of the two numbers a and b comes first in the designation of the pair. Thus, we are talking about an ordered pair. In this regard, the pairs (a, 6) and (6, a) are considered equal to each other, and they define the same point on the plane, if only a = 6. Surjection, injection and bijection. Reverse mapping.
Composition of mappings is a product of sets. Display schedule. The set of all pairs of real numbers, as well as the set of points in the plane, is denoted by R2. This designation is associated with the important concept in set theory of a direct (or dek-artov) product of sets (often they simply speak of a product of sets). Definition 2.2. The product of the sets A and B is the set Ax B of possible ordered pairs (x, y), where the first element is taken from A and the second from B, so that the equality of two pairs (x, y) and (&", y") is determined conditions x = x" and y = y7. Pairs (i, y) and (y, x) are considered different if xy. This is especially important to keep in mind when the sets A and B coincide. Therefore, in the general case A x B f B x A, i.e. the product of arbitrary sets is not commutative, but it is distributive with respect to the union, intersection and difference of sets: where denotes one of the three named operations. The product of sets differs significantly from the indicated operations on two sets. The result of performing these operations is a set whose elements (if it is not empty) belong to one or both of the original sets. The elements of the product of sets belong to the new set and represent objects of a different kind compared to the elements of the original sets. Similar to Definition 2.2
We can introduce the concept of a product of more than two sets. The sets (A x B) x C and A*x (B x C) are identified and simply denoted A x B x C, so. Works Ah Au Ah Ah Ah Ah, etc. denoted, as a rule, by A2, A3, etc. Obviously, the plane R2 can be considered as the product R x R of two copies of the set of real numbers (hence the designation of the set of points of the plane as the product of two sets of points on the number line). The set of points in geometric (three-dimensional) space corresponds to the product R x R x R of three copies of the set of points on the number line, denoted R3.
- The product of n sets of real numbers is denoted by Rn. This set represents all possible collections (xj, X2, xn) of n real numbers X2) xn £ R, and any point x* from Rn is such a collection (xj, x, x*) of real numbers xn £ K*
- The product of n arbitrary sets is a set of ordered collections of n (generally heterogeneous) elements. For such sets, the names tuple or n-ka are used (pronounced “enka”). Example 2.3. Let A = (1, 2) and B = (1, 2). Then the set A x B can be identified with four points of the plane R2, the coordinates of which are indicated when listing the elements of this set. If C = ( 1,2) and D = (3,4), then Example 2.4 Let Then The geometric interpretation of the sets E x F and F x E is presented in Fig. 2.8 . # For the mapping /: X, we can create a set of ordered pairs (r, y), which is a subset of the direct product X x Y.
- Such a set is called the graph of the mapping f (or the graph of the function i*" - Example 2.5. In the case of XCR and Y = K, each ordered pair specifies the coordinates of a point on the plane R2. If X is an interval of the number line R, then the graph of the function can represent some line (Fig. 2.9) Example 2.6 It is clear that with XCR2 and Y = R the graph of the function is a certain set of points in R3, which can represent a certain surface (Fig. 2.10).
Let's consider another important special case of the general concept of correspondence - mapping of sets. If compliant R between sets X And Y element image AX may be empty, or may contain several elements.
Relationship between elements of sets X And Y called display X VY , if each element X from many X only one element of the set matches Y. This element is called element imageX with this display: f(x). On a graph of such a mapping from each point of the set X Only one arrow will come out (Fig. 29).
Consider the following example . Let X- many students in the audience, and Y- many chairs in the same auditorium. Match "student" X sitting on a chair at» sets display X VY. Student image X is a chair.
Let X = Y = N- a set of natural numbers. Matching "decimal notation of a number" X comprises at digits" determines the display N V N. With this display, the number 39 corresponds to the number 2, and the number 45981 corresponds to the number 5 (39 is a two-digit number, 45981 is a five-digit number).
Let X- many quadrilaterals, Y- many circles. Matching "quadrangle" X inscribed in a circle at» is not a display X V Y, since there are quadrilaterals that cannot be inscribed in a circle. But in this case they say that the result is a mapping from the set X into the multitude Y.
If display X V Y such that each element y from many
Y matches one or more elements X from many X, then such a mapping is called display of the set X for manyY.
A bunch of X is called the domain of definition of the mapping f: XY, and a lot Y- the arrival region of this mapping. Part of the arrival area consisting of all images y from many Y, called the mapping value set f.
If y=f(x), then x is called prototype of element y when displayed f. The set of all preimages of an element at they call it a complete prototype: f(y).
Displays are of the following types: injective, surjective and bijective.
If the complete prototype of each element yY contains at most one element (may be empty), then such mappings are called injective.
Displays XY such that f(X)=Y, are called mappings X for the whole multitude Y or surjective(from each point of the set X an arrow comes out, and after changing direction at each point of the set X ends) (Fig. 31).
If a mapping is injective and surjective, then it is called one-to-one or bijective.
Set display X is called a set bijective, if each element XX matches a single element yY, and each element yY matches only one element XX(Fig. 32) .
Bijective mappings generate equal sets : X~Y.
Example . Let - X many coats in the wardrobe, Y- a lot of hooks there. Let's match each coat with the hook on which it hangs. This correspondence is a mapping X inY. It is injective if no hook has more than one coat hanging on it or some hooks are free. This mapping is surjective if all the hooks are occupied or some have several coats hanging on them. It will be bijective if there is only one coat hanging on each hook.
An important role in mathematics is played by the establishment of connections between two sets and associated with the consideration of pairs of objects formed from elements of the first set and the corresponding elements of the second set. The mapping of sets is of particular importance.
Let be arbitrary sets. Display sets X to set Y every rule is called f, according to which each element of the set is associated with a completely specific (single) element of the set.
The fact that f there is a mapping, briefly written in the form: .
The designation is also used. Most often, displays are denoted by letters f, q, F.
So, to set the display of the set X in a set, each element must be associated with one and only one element.
If the element X from X matched element from Y, then they call way elements , A X – prototype of the element when displayed, which is written as .
From the definition of a mapping it follows that each element from X the image is unique, but for an element there may be many prototypes, or there may not be any at all. The set of all preimages of an element is called its a complete prototype and is denoted by . Thus, .
The image of a subset of A and the inverse image of a subset of IN when displayed:
For example, let and be a mapping A V A, matching each element A from A remainder of the division A by the number 4. Then we have:
Depending on the properties, images and prototypes, mappings are distinguished: surjective, injective and bijective.
The mapping is called surjective , if those. each element from displays at least one element from X, or for any .
The mapping is called injective , if different elements of the set X are mapped to different elements of the set i.e. , or is either empty or a singleton set for any . Injective mappings are also called investments .
The mapping is called bijective , or one-to-one a mapping onto if it is surjective and injective, i.e. if there is a singleton set for any . In this case, we can define mappings by putting for any: . It's called reverse k and is denoted as .
Let us illustrate the types of mappings for clarity.
Surjective Injective Bijective
Figure 12
Set display A called into oneself transformation of the set A. Bijective set transformation A called set substitution A.
An example of substitution of a set of integers is the mapping defined by equality.
Note also that the mapping of the set A V IN also called function , defined on the set A with values in the set IN. In this case, the element is called meaning functions point A. The multitude itself A called region definitions functions, and the set is the range of values of the function.
A function is often treated as a variable that takes values from IN and so depending on the variable X, taking values from A, that to each value A variable size X corresponds to a very specific value of . At the same time, they write and instead of “function” they say “function”.
Let's consider various mappings and define their types.
1) Let X– a set of circles on a plane. By associating each circle with its center, we obtain the mapping X on . This mapping is not injective, since the same point can be the center of an infinite number of circles. But it is surjective, since any point is the center of some circle. Therefore, the inverse correspondence is everywhere defined, surjective, but not functional.
2) The correspondence is a numerical function defined on the entire set of real numbers. The set of values of this function is a set of non-negative numbers. Since , the function is not surjective. It is not injective, since . Therefore it does not have an inverse function.
3) The mapping is surjective and injective: for any there is one and only one number such that . This number is .
4) The mapping ( - the set of non-negative numbers) of a set into itself is defined everywhere, injective, but not surjective. Indeed, for the fraction , it is satisfied.
Therefore, the set of values of this function is the interval. The inverse function is defined on this interval and takes non-negative values.
5) The mapping defined by the rule is an injective mapping. It is not bijective because . However, if we define the mapping in in the same way, we obtain a bijective mapping. . ; from surjectivity only surjectivity follows, and from injectivity follows only injectivity.
3. If and are set transformations A, then their composition is also a transformation of the set A.
Introduction to set theory and combinatorics
Practical work No. 8. Mappings. Types of displays
Questions for work
- What is a “set-to-set mapping”?
- What is an “image”, what is a “prototype” in this mapping?
- What is full f - image, what is complete f - prototype, when displayed f?
- Name the types of mappings, give their definitions and give examples.
- Which two sets are said to be equivalent? Give examples.
- Which set is called countable? Give examples.
Examples of task solutions
Example 1. Let A = {1; 2; 3; 4; 5; 6; 7; 8; 9} N and B =(0; 1) Z Let's match each number x A its remainder when divided by 2.
Is this matching a mapping? What type is this display? Which element is the image of element 6, 7? Let's find the complete inverse image of element 1.
Solution. Let's represent the given correspondence using a graph:
We see that:
1) each element of the set A , is the starting point;
2) for each origin point, there is only one arrival point. (This means that the indicated correspondence is a mapping of the set A to set B);
3) Each element of the set IN is the arrival point. (So this is a mapping "to").
Since there are many IN there is an element (for example, 0) for which the prototype is no element from A , then this mapping is not one-to-one.
The image of the number 6 is the number 0 IN , the image of the number 7 is the number 1 IN . Full prototype of the number 1 IN there is a set of numbers (1; 3; 5; 7; 9) A .
Example 2. Let X be set of plane triangles, Y = R. Let's choose a unit of measurement for lengths and assign a number to each triangle - the perimeter of this triangle. Will this match be a mapping? What type is the given display? What is the complete prototype of the number at R?
Solution. Every triangle on a plane has a uniquely defined perimeter. Therefore, each triangle from the set X matches a single number from R , i.e. this correspondence is a mapping X to R . In this case, two different triangles can have the same perimeter. In other words, the mapping is not one-to-one. In addition, there is no triangle whose perimeter is equal to a negative number, i.e. the mapping is not a "to" mapping. Let at R. Then:
- at > 0, the complete image is the set of all triangles in the plane whose perimeter is equal to the number at , this set is infinite.
- at ≤ 0, the complete image is an empty set.
Example 3. X = (0; 1; 2; 3; 4) N, Y = Z. Mapping f of the set X to the set Y given as follows:
Let's determine the type of this mapping and build its graph.
Solution. For each x X let's find the image y Y. We write the corresponding results in the table:
|
y=f(x) |
–2 |
Multiple display values f is a set
A = (–2; 1; 4; 7; 10) Y and B ≠ Y . Each element y B in X there is only one prototype. We therefore have a one-to-one mapping of the set X to set Y.
Value pairs (x; y ) from the table forms a graph of this mapping f: X→Y . In a rectangular coordinate system, this graph looks like:
Example 4. Given two sets of words: X = (red; blue; green; yellow) and Y = (tie; light; scarf; sheet). Are these sets equivalent?
Solution. These sets are equivalent, because for them it is possible to establish a one-to-one mapping “to”.
For example:
Example 5. Given sets: A = ( x | x = 2 n , n N ) and
B = ( x | x = , n N ). Are these sets equivalent?
Solution. These sets are equivalent, since it is possible to select a one-to-one mapping of the set A to set B.
For example: f: A B
x = 2 n y = .
Exercises
1. Between the set of names X = (Andrey; Boris; Mikhail; Alexey; Konstantin; Vasily; Valentina; Clara; Semyon; Maria; Sophia; Oleg; Trofim4 Yuri; Yakov) and a set Y (letters of the Russian alphabet) a correspondence has been established in which each name is associated with its first letter. Will this match display X to Y ? If yes, what type? Find the image of the set X . Find complete prototypes of letters A, B, K, L. Construct a graph of the indicated correspondence.
2. Each point M of the segment AB Let's match its projection M to this line L . Will this match be a mapping? Which one? Describe the domain of definition, the range of values of this mapping.
3. Set X consists of all the squares on the plane, and the set Y from all circles on the same plane. Let us associate each square with a circle inscribed in it. Is this mapping mapping X to Y?
4. Is it possible to set the display as follows: set And from segments, on Y – from triangles; is each segment associated with a triangle for which this segment is the midline?
5. Is it true that compliance f: Z Z
X y = –5 x + 2
is there a mapping "to"?
6. Let X – set of real numbers. Each number x X Let's match its square. Can this correspondence be called a reversible mapping?
7. Show that the following sets are countable:
a) the set of odd natural numbers;
b) the set of non-negative integers;
c) the set of squares of natural numbers;
d) the set of natural numbers that are multiples of 5;
e) the set of cubes of natural numbers.
8. Given two sets: A = (Paris; Moscow; Warsaw; Krakow; London; Saransk; Vladimir; Marseille) and B = (France; Russia; England; Poland; Sweden; Austria). Let us set the correspondence between them: “city x A located in the country" Let's build graphs of this correspondence. Will this match be a mapping? What type?
9. Are the sets A equivalent to images of settlements on the map and the set B populated areas of the area shown on the map?
Individual task
- Select a display from the specified matches. Indicate their type, build a graph.
2. Draw graphs of the following relations in a rectangular Cartesian coordinate system Z . For each relation, find out whether it is a mapping Z to Z, mapping Z to Z , one-to-one mapping, overlay:
1) x + y = 3; 7) at< х + 2;
2) x – y ≤ 5; 8) y ≤ x + 2;
3) x + y = 4, x > 0; 9) y = 4;
4) x = y, – 4 ≤ x ≤ 6; 10) xy = 24, –6 ≤ x ≤ 6.
5) = y, – 4 ≤ x ≤ 6;
6) x > y ;
Self-control tasks
Join the following pairs of sets with an “=” sign if they are equal and a “~” sign if they are equivalent:
1) A - the set of sides of a triangle,
IN - set of angles of a triangle;
2) A - many letters in the word “ear”,
B = (o; k; s; l);
3) A – many rings on a tree stump,
IN – many years lived by the tree;
4) many continents on Earth and many states
Display - one of the basic concepts of mathematics. A mapping is any rule or law of correspondence between sets. Let and be arbitrary non-empty sets. They say that a mapping of a set to a set is given (notation: or) if each element of the set (is assigned a correspondence to a single, uniquely defined element of the set (.
The element is called way element when displayed, and the element is called prototype element in this display. The image of a set of elements when displayed is the set of all elements of the type that belong to the range of values. The set of all elements (), the images of which make up the range of values is called prototype set of elements (). The set is called domain of definition display.
The mapping is called surjective m , when each element of the set (has at least one inverse image of the set (, i.e. , or.
The mapping is called injective, when each element of the set (is the image of only one element of the set (, i.e. the images of any two different elements of the set are different, i.e. it follows.
The mapping is called bijective or one-to-one, when it is both injective and surjective, i.e. Each element of the set is the image of one and only one element of the set.
Equality two mappings and means by definition that their corresponding areas coincide (and), and.
Work two mappings and can be defined as a mapping that associates each element of the set with an element of the set.
A mapping from a set to a set is otherwise called a function on a set with values in the set. If the sets coincide, then the bijective mapping of the set onto itself is called transformation multitudes. The simplest set transformation is identical- is defined as follows: . An identity mapping that takes each element to itself is also called single transformation. If transformations and are given, then the transformation resulting from the sequential execution of first the transformation and then the transformation is called work transformations And: .
For transformations of the same set, the following laws apply:
The commutative law for carrying out transformations is not satisfied in the general case, i.e. .
If between two sets we can set bijective mapping (to establish a one-to-one correspondence between their elements), then such sets are called equivalent or equally powerful. Finite sets are equivalent only if the number of their elements is the same.
Infinite sets can also be compared with each other.
Two sets have the same cardinality or are called equivalent (notation) if a one-to-one correspondence can be established between their elements, i.e. if it is possible to specify some rule according to which each element of one of the sets is associated with one and only one element of the other set.
If such a mapping is impossible, then the sets have different cardinalities; it turns out that in the latter case, no matter how we try to bring the elements of both sets into correspondence, there will always be extra elements left and, moreover, always from the same set, to which a higher value of the cardinal number is assigned or they say that this set has more power. An infinite set and some subset of it can be equivalent. A set equivalent to the set of natural numbers is called a countable set. In order for a set to be countable, it is necessary and sufficient that each element of the set be associated with its ordinal number. From any infinite set it is possible to select a countable subset. Every subset of a countable set is countable or finite. A countable set is the most primitively organized infinite set. The Cartesian product of two countable sets is countable. The union of a finite or infinite number of finite or countable sets is a finite or countable set.
