Conformitybetween sets A and B is called a subset of their Cartesian product

In other words, pairs define a correspondence between the sets A \u003d () and B \u003d () if the rule R is specified, according to which an element from set B is selected for an element of the set A.

If an element is associated with some element, b is called way element a and is written as follows: b \u003d R (a). Then - prototype an element that has the properties of uniqueness and completeness:

1. A single image corresponds to each type;

2. The image must be complete, just as the prototype must be complete.

Example.If A is a set of parabolas, B is a set of points of the plane, and R is a correspondence “apex of a parabola”, then R (a) is a point that is a vertex of a parabola, and consists of all parabolas with a vertex at point b (Fig. 6)

The image of a set A under correspondence R is called many meanings of this correspondence and denoted by R (A) if R (A) consists of the images of all elements of the set A.

The inverse image of a set B for some correspondence R is called scope this correspondence is designated. In turn is reverse correspondence for R.

So, for the correspondence of R given by the points of the coordinate plane, the domain of definition is the set of points on the abscissa axis, and the set of values \u200b\u200bis the projection of points on the ordinate axis (Fig. 7). Therefore, for some point

M (x, y) y is an image, and x is a preimage under some correspondence R: Y \u003d R (x). The correspondence between the sets X is convenient in the form of a point on the plane using the method of Cartesian coordinates.

Let the correspondence R and Y \u003d R (X) be given. It corresponds to points M with coordinates (x; y) (Fig. 7). Then the set of points of the plane, distinguished by the mapping R, will be schedule.

To describe the correspondences between sets, the concept of mapping (functions) of one set to another is used.

To set the display, you must specify:

1. The set that is displayed (the scope of this mapping is often denoted);

2. The set in (on) which the given domain of definition is displayed (the set of values \u200b\u200bof this mapping is often denoted);

3. The law or correspondence between these sets, according to which elements (images) from the second set are selected for the elements of the first set (preimages, arguments).

Designations:.

Ways of setting mappings: analytical (in the form of formulas), tabular, graphic (diagrams or graphs).

There are two main types of single-valued mappings (functions). By power, they are divided into surjective and injective.

1. A correspondence in which a single element of the set B is indicated for each element of the set A, and at least one element of the set A can be indicated for each element of the set B, is called a mapping of the set A on the set B(surjection).

2. A correspondence in which each element of the set A corresponds to a single element of the set B, and to each element B there corresponds at most one preimage from A, is called a mapping of the set A in a multitude B (injection).

The mapping of the set A onto the set B, in which each element of the set B corresponds to a single element of the set A, is called one-to-one correspondence between two sets, or bijection.injection and surjection.

MAPPING OF SETS §1. Basic definitions

Definition. Let A and B be two sets. They say that a mapping f of a set A into B is given if a law is specified by which any element a from A is associated with a single element b from a set B:

Mappings are also called functions.

We will use the following notation:

ƒ: A → B. The mapping f maps the set A to B;

A f B. Set A is mapped to B in mapping f.

If element a is mapped to element b when displaying f, then they write f (a) \u003d b (left record) or af \u003d b (right record). The element b is called the image of the element a under the mapping f; element a is the preimage of b for

this display. The set (f (a) | a A) \u003d f (A) is the image of the set A under the mapping f. Note that

f (A) B.

A B

f f (A)

AND - domainmapping f; AT - rangemapping f (sometimes - for example, in school mathematics - f (A) is considered the range of values, but we will consider it B).

Note that we are considering only single-valued mappings.

Of all the mappings, the following types are especially distinguished:

1. Surjection (display "on")Is a mapping f: A → B such that f (A) \u003d B. Under surjection, each element from the set B has at least one preimage.

2. Injection - a display in which different elements go into different ones, ie. if a, a 1 A and a ≠ a 1, then f (a) ≠ f (a 1).

				f (a1)

3. Bijection, or one-to-one mappingIs a mapping that is both injection and surjection.

Examples of displays:

1. Let A be any set and B be a set consisting of one element, i.e. B \u003d (b).

AND . b

The mapping f (a) \u003d b, and A is a surjection, since f (A) \u003d B.

2. Let the set A be some segment on the plane, the set B a straight line. From each point of segment A, let us drop the perpendicular to line B and put the bases of these perpendiculars in correspondence with the points of segment A.

Ah

φ (a) B

We denote this mapping by φ. Obviously

ϕ (a) ≠ ϕ (a 1), a, a 1 A, a ≠ a 1.

Therefore, φ is an injection (but not a surjection).

3. Let the set A be the hypotenuse of a right-angled triangle, and B - its leg. Any point of the hypotenuse is associated with its projection onto the leg. We obtain a one-to-one mapping from A to B:

those. f - bijection.

Note that this is how mathematics proves that the "number" of points on the hypotenuse and leg is the same (more precisely, these sets have the same cardinality).

Comment. It is not difficult to think of a mapping that is neither surjection, nor injection, nor bijection.

4. If f is any function of a real variable, then f is a mapping from R to R.

§2. Multiplication of mappings

Let A, B, C be three sets and two maps f: A → B and ϕ: B → C are given.

Definition 1. The product of these mappings is a mapping that is obtained as a result of their sequential execution.

ϕ f

There are two options for recording.

1. Left entry.
ƒ (a) \u003d b, ϕ (b) \u003d c.		denote ϕ f:
Then the product of f and φ will be	translate a into c, it should
(ϕ f) (a) \u003d ϕ (f (a)) \u003d ϕ (b) \u003d c, ϕ f: A → C (see figure above).
By definition (ϕ f) (a) \u003d ϕ (f (a)),	those. product of mappings -	this is a complex function,
set to A.

2. Right entry.

aƒ \u003d b, bϕ \u003d c. Then a (f ϕ) \u003d (af) ϕ \u003d b ϕ \u003d c,

f ϕ: A → C.

We will use the left entry (note that the book uses the right one). Below we will denote the product of mappings by f ϕ.

Remark 1. It follows from the definition of multiplication of mappings that not any mappings can be multiplied, but only those whose “mean” sets are the same. For example, if f: A → B, ϕ: D → C, then for B \u003d D one can multiply the maps f and φ, but for B ≠ D it is impossible.

Multiplication Properties of Mappings

Definition 2. The mappings f and g are said to be equal if their domains of definition and range of values \u200b\u200bcoincide, i.e. f: A → B, g: A → B and the following condition holds: a A is true

equality f (a) \u003d g (a).

1. Multiplication of mappings is non-commutative. In other words, if fφ and φf exist, then they are not necessarily equal.

Let, for example, the sets A \u003d B \u003d C \u003d R, f (x) \u003d sin x, ϕ (x) Consider the products:

(ϕ f) (x) \u003d ϕ (f (x)) \u003d ϕ (sin x) \u003d e sin x,

(f ϕ) (x) \u003d f (ϕ (x)) \u003d f (e x) \u003d sin (e x).

Therefore, the functions fφ and φf are different.

2. Multiplication of mappings is associative.

Let f: A → B, ϕ: B → C, ψ: C → D. Let us prove that (ψϕ) f

E x, f: R → R, ϕ: R → R.

and ψ (ϕ f) exist and are equal, that is, (ψϕ) f \u003d

ψ (ϕ f). (1)

Obviously, (ψϕ) f: A → D, ψ (ϕ f): A → D.

To prove equality (1), due to the definition of equality of mappings, it is required to check that a A: ((ψϕ) f) (a) \u003d (ψ (ϕ f)) (a) (2). Using the definition of multiplication of maps (on the left)

((ψϕ) f) (a) \u003d (ψϕ) (f (a)) \u003d ψ (ϕ (f (a))),

(ψ (ϕ f)) (a) \u003d ψ ((ϕ f) (a)) \u003d ψ (ϕ (f (a))). (4)

Because in equalities (3) and (4) the right-hand sides are equal, then the left-hand sides are also equal, i.e. equality (2) is true, and then (1) also holds.

Remark 2. The associativity of multiplication makes it possible to uniquely determine the product of three, and then any finite number of factors.

there are several preimages in A, or there are no preimages at all. However, for a bijective mapping f, the converse can be defined.

Let f: A → B be a bijection, f (a) \u003d b, a A, b B. Then for any element b B, by the definition of bijection, there is a unique preimage under the map f - this is an element a. Now we can define f - 1: B → A by setting f - 1 (b) \u003d a (b B). It is easy to see that f - 1 is a bijection.

So, every bijective mapping has the opposite.

§3. Set transformations

Any mapping f: A → A is called transformation of the setA. In particular, any

a real variable function is a transformation of the set R.

Examples of transformations of a set of points on a plane are rotation of the plane, symmetry about an axis, etc.

Since transformations are a special case of mappings, everything said above about mappings is true for them. But the multiplication of transformations of the set A also has specific properties:

1. for any transformations f and φ of the set A, the products fφ and φf exist;

2. there is an identical transformation of the set Aε: ε (a) \u003d a, a A.

It is easy to see that for any transformation f of this set f ε \u003d ε f \u003d f, since, for example, (f ε) (a) \u003d f (ε (a)) \u003d f (a). Hence, the transformation ε plays the role of a unit element in the multiplication of transformations.

equalities are easy to check. Thus, the inverse transformation plays the role of the inverse element in the multiplication of transformations.

Surjection, injection and bijection

The rule that defines the mapping f: X (or the function /) can be conventionally depicted by arrows (Fig. 2.1). If the set Y contains at least one element) to which none of the arrows points, then this indicates that the range of values \u200b\u200bof the function f does not fill the entire set Y, i.e. f (X) S U.

If the range of values \u200b\u200bof / coincides with Y, i.e. f (X) \u003d Y, then such a function is called surjective) or, in short, surjection, and the function / is said to map the set X to the set Y (in contrast to the general case of the mapping from X to the set Y according to Definition 2.1). So, /: X is a surjection if Vy 6 Y 3x € X: / (x) \u003d y. In the figure, in this case, at least one arrow leads to each element of the set Y (Fig. 2.2). In this case, several arrows can lead to some elements from Y. If at most 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).

• Thus, a function f: X -Y Y is an injection if any two different elements of X have as their images under the mapping / two different elements of Y, or Vy e f (X) C Y 3xeX: f (x) \u003d y. Surjection, injection and bijection. Reverse mapping. Composition of mappings, product of sets. Display graph. A mapping /: X-\u003e Y is called bijective, or bi-injection, if each element of y 6 Y is the image of some and the prize of the only element from X, i.e. Vy € f (X) \u003d Y E! X € X: f (x) \u003d y.

In fact, the function / in this case establishes a one-to-one correspondence between the sets X and Y, and therefore it is often called a one-to-one function. Obviously, the function / is bijective if and only if it is simultaneously injective and surjective. In this case, arrows (Fig. 2.4) connect in pairs each element of X with each element of Y. Moreover, no two elements of X can be connected by an arrow with the same element of Y, since / is injective, and no two elements from Y cannot be connected by arrows with the same element from X due to the requirement of uniqueness of the image in Definition 2.1 of the map. Each element of X participates in pairwise connection, since X is the domain of the function /. Finally, each element of Y also participates in one of the pairs, for / is surjective. The roles of X and Y in this case are, as it were, exactly the same, and if we turn all the arrows backwards (Fig. 2.5), then we get a different mapping or a different function d), which is also injective, in surjective. Mappings (functions) that allow such an inversion will play an important role in the future.

In a particular case, the sets X and Y may coincide (X \u003d 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 some bijection and let y € Y. Let f _1 (y) be the only element x € X such that f (r) \u003d y. Thus, we define some mapping 9: Y Xy which is again a bijection. It is called inverse mapping, or inverse bijection to /. It is often also called simply the inverse function and is denoted by f "*. In Fig. 2.5, the function q is precisely the inverse of f, that is, q \u003d f" 1.

Examples of solutions in tasks

The mappings (functions) / and are mutually inverse. It is clear that\u003e if the function is not a bijection, then the function inverse to it does not exist. Indeed, if / is not injective, then some element y ∈ Y may correspond to several elements x from the set X, which contradicts the definition of the function. If / is not surjective, then there are elements in Y for which there are no preimages in X, that is, the inverse function is not defined for these elements. Example 2.1. and. Let X \u003d Y \u003d R be the community of real numbers. The function / defined by the formula y \u003d 3a - 2, i, y € R, is a bijection. The inverse function will be x \u003d (y + 2) / 3. b. The real function f (x) \u003d x2 of the real variable x is not surjective, since the negative numbers from Y \u003d R are not images of elements from X \u003d K for /: A -\u003e Y. Example 2.2. Let A "\u003d R, and Y \u003d R + be the set of positive real numbers. The function f (x) \u003d ax, a\u003e 0, af 1, is a bijection. The inverse function will be Z" 1 (Y) \u003d 1 ° 8a Y

• Surjection, injection and bijection. Reverse mapping. Composition of mappings, product of sets. Display graph. 2.4. Composition of mappings If f: X- * Y and g: Y- * Zy then the mapping (p: X - + Z, given for each a: 6 A "by the formula \u003d, is called the composition (superposition) of mappings (functions) / and q\u003e or a complex function, and denote ro / (Fig. 2.6).
• Thus, the complex function before f implements the rule: I apply first / and then di, i.e. in the composition of operations “before /, one must start with the operation / located on the right. Note that the composition Fig. 2.6 mappings is associative, i.e. if /: X - + Y, q: Y Z and h: Z- * H\u003e then (hog) of \u003d ho (gof) i, which is easier to write as ho to /. Let us check this as follows: On any wK "oaicecmee X, a mapping 1х -XX is defined, called the identity, often also denoted by idx and given by the formula Ix (x) \u003d x Vx € A". Its -action is that it leaves everything on their places.

So, if is the bijection inverse to the bijection /: X- + Y, then / "1o / \u003d / x, a / o / -1 \u003d / y, where u / y are the identical maps of the sets X and Y, respectively. Conversely, if the maps f: X -\u003e Y and p: Y A "are such that gof \u003d Ix and fog \u003d / y, then the function / is a bijection, and y is its inverse bijection. Obviously, if / is a bijection of A "on Y, and $ is a bijection of Y on Z, then gof is a bijection of X on Z, and will be an inverse bijection with respect to it. 2.5. Product of sets. Graph of a map Recall that two mutually perpendicular coordinate axes with the same scale for both axes, set on the plane a rectangular Cartesian coordinate system (Fig. 2.7). The point O of the intersection of the coordinate axes is called the origin * of coordinates.

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 My on the coordinate axis Oy. Points Mx and My 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 the point M (in the selected coordinate system), and x is called the abscissa of the point M, and y is the ordinate of this point. Obviously, each pair (a, b) of real numbers a, 6 6R corresponds on the plane to a point M, which has these numbers as its coordinates. And vice versa, 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 essential which of the two numbers a and b is in the first place in the designation of a 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 \u003d 6. Surjection, injection and bijection. Reverse mapping.

Composition of mappings, product of sets. Display graph. The set of all pairs of real numbers, as well as the set of points on the plane, denote R2. This designation is associated with an important concept in set theory of a direct (or decks of art) product of sets (they often speak simply of a product of sets). Definition 2.2. The product of sets A and B is called 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") determine conditions x \u003d x "and y \u003d y7. Pairs (x, y) and (y, x) are considered different if xφy. This is especially important to bear in mind when the sets A and B coincide. Therefore, in the general case A x B φ В х Л, ie the product of arbitrary sets is not commutative, but it is distributive with respect to 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 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 a new set and are objects of a different kind compared to the elements of the original sets. Similar to Definition 2.2

You 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) identify and denote simply A x B x C, so that. Works of Ah Ah Ah Ah Ah etc. denote, as a rule, through 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 on the plane as the product of two sets of points on the number line). The set of points of the geometric (three-dimensional) space corresponds to the product R x R x R of three copies of the set of points of the number line, denoted by 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 e R, and any point x * from Rn is such a set (xj, x, x *) of real numbers xn ∈ K *
• The product of n arbitrary sets is the set of ordered sets of n (in the general case, heterogeneous) elements. For such sets, the names tuple or n-ka (pronounced "enka") are used. Example 2.3 Let A \u003d (1, 2) and B \u003d (1, 2). Then, and the set A x B can be identified with four points of the plane R2, the coordinates of which are indicated when enumerating the elements of this set.If C \u003d (1,2) and D \u003d (3,4), then Example 2.4. Let Then the Geometric interpretation of the sets Е х F and F х Е is shown in Fig. 2.8 . # For the mapping f: X, one can compose the set of ordered pairs (z, y), which is a subset of the direct product X x Y.
• Such a set is called the graph of the display f (or the graph of the function i * "- Example 2.5. In the case of XCR and Y \u003d K, each ordered pair specifies the coordinates of a point on the plane R2. If, in this case, 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 for XCR2 and Y \u003d R the graph of the function is a set of points in R3, which can represent a certain surface (Fig. 2.10).

If X C R, and Y \u003d R2, then the graph of the function is also a set of points in R3, which can represent some line intersected by the plane x \u003d const only at one point M with three coordinates x) yi, y2 (Fig.2.11) ... # All mentioned examples of function graphs are the most important objects of mathematical analysis, and in the future they will be discussed in detail.

Let us consider one more important special case of the general concept of correspondence - set mapping. Upon compliance R between sets X and Y item image andX may be empty, or may contain several elements.

Relationship between elements of sets X and Y called mapping X atY if each element x of the multitude Xonly one element of the set matches Y... This element is called element imagex with this mapping: f (x).On the 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 be X - a lot of students in the classroom, and Y - lots of chairs in the same auditorium. Matching "student x sitting on a chair at»Sets display XatY. Student image x is the chair.

Let be X \u003d Y \u003d N - a set of natural numbers. Matching "decimal notation number x consists of atdigits "defines the display N at N... In this mapping, 39 corresponds to 2, and 45981 corresponds to 5 (39 is a two-digit number, 45981 is a five-digit number).

Let be X - a set of quadrangles, Y - many circles. The correspondence "quadrangle x inscribed in a circle at"Is not a display Xat Y, since there are quadrangles that cannot be inscribed in a circle. But in this case, they say that the resulting map is X in a lot Y.

If the display X at Y is such that each element y of the multitude
Y matches one or more elements x of the multitude X, then such a mapping is called mapping the set X manyY.

A bunch of Xis called the mapping domain f: XY,and a lot Y - the arrival area of \u200b\u200bthis display. The portion of the arrival area that contains all images y of the multitude Y, is called the set of display values f.

If y \u003d f (x), then x is called preimage of element y when displaying f... The set of all preimages of an element at they call it a full prototype: f(y).

Mappings are of the following types: injective, surjective and bijective.

If the full preimage of each element yY contains at most one element (it may be empty), then such mappings are called injective.

Mappings XY such that f (X) \u003d Yare called mappings X the whole set Yor surjective (from each point of the set Xan 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 mapping X the set is called bijectiveif each element xX matches a single element yY, and each element yYmatches only one element xX(fig. 32) .

Bijective mappings generate equally powerful (equivalent) sets : X ~ Y.

Example ... Let be - Xmany coats in the wardrobe, Y - a lot of hooks in the same place. Assign each coat to the hook on which it hangs. This correspondence is a mapping X inY. It is injective if there are no more than one coat hanging on any hook, or some hooks are free. This display is surjective if all the hooks are occupied or several coats are hanging on some. It will be bijective if there is only one coat hanging from each hook.

Display - one of the basic concepts of mathematics. Mapping is some kind of rule or law of correspondence of sets. Let and be arbitrary non-empty sets. They say that a set-to-set mapping (notation: or) is given if each element of the set (a correspondence is assigned to a unique, uniquely defined element of the set (.

The item is called way element when displayed, and the element is called prototype element in this display. The image of a set of elements during display is the set of all elements of a view that belong to the range of values. The set of all elements () whose images make up the range of values \u200b\u200bis called prototype set of elements (). The set is called scope display.

The mapping is called surjective m , when each element of the set (has at least one preimage 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., from follows.

The mapping is called bijectiveor one-to-onewhen it is simultaneously injective and surjective, i.e. each element of the set is the image of one and only one element of the set.

Equality of two mappings and means by definition that their corresponding regions coincide (and), and.

Composition two mappings and can be defined as a mapping that assigns an element of the set to each element of the set.

A set-to-set mapping is otherwise called a function on a set with values \u200b\u200bin a set. If the sets and coincide, then the bijective mapping of the set onto itself is called transformation sets. The simplest transformation of a set is identical - is defined as follows:. The identity mapping taking each element into itself is also called single transformation. If transformations and are given, then the transformation that is the result of sequential execution of the transformation first and then the transformation is called work transformations and:.

For transformations, and the same set, the following laws are valid:

In the general case, the commutative law for making transformations does not hold, i.e. ...

If between two sets one can set bijective mapping (establish a one-to-one correspondence between their elements), then such sets are called equivalent or equal... Finite sets are equal 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 you can indicate some rule according to which each element of one of the sets corresponds to one and only one element of the other set.

If such a mapping is impossible, then the sets have different cardinality; it turns out that in the latter case, no matter how we try to match the elements of both sets, there will always be extra elements and moreover always from the same set, to which a higher value of the cardinal number is attributed, or they say that this set has more power... An infinite set and some of its subset may be equivalent. A set equivalent to a 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. A countable subset can be distinguished from any infinite set. Any 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.