The word “order” is often used in a wide variety of issues. The officer gives the command: “Calculate in numerical order,” arithmetic operations are performed in a certain order, athletes are ranked according to height, all leading chess players are arranged in a certain order according to the so-called Elo coefficients (American professor who developed the system coefficients, allowing you to take into account all the successes and failures of the players), after the championship, all football teams are located in a certain order, etc. There is an order of operations when manufacturing a part, the order of words in a sentence (try to understand what the sentence “on he old man” means I didn’t plant the donkey!”
By arranging the elements of a certain set one after another, we thereby order them or establish some relationship between them in order. The simplest example is the natural order of the natural numbers. Its naturalness lies in the fact that for any two natural numbers we know which one follows the other or which one is greater than the other, so we can arrange the natural numbers in a sequence such that the larger number is located, for example, to the right of the smaller one: 1, 2, 3, ... . Of course, the sequence of elements can be written in any direction, not just from left to right. The very concept of natural numbers already contains the idea of order. By establishing some relative arrangement of the elements of any set, we thereby define on it some binary order relation, which in each specific case may have its own name, for example, “to be less,” “to be older,” “to be contained in ", "follow", etc. Symbolic designations of order can also be varied, for example, Í, etc.
Main hallmark order relation is the presence of the property of transitivity. So, if we are dealing with a sequence of some objects x 1, x 2, ..., x n,..., ordered, for example, by relation, then from what is being performed x 1x 2... x p..., it should follow that for any pair x i, x j elements of this sequence is also fulfilled x ix j:
For a pair of elements x ij in the relation graph we draw an arrow from the vertex x i to the top x j, i.e. from the smaller element to the larger one.
The order relation graph can be simplified by using the so-called method Hasse diagrams. The Hasse diagram is constructed as follows. Smaller elements are placed lower, and larger ones are placed higher. Since such a rule alone is not enough for depiction, lines are drawn showing which of the two elements is larger and which is smaller than the other. In this case, it is enough to draw only lines for the elements immediately following each other. Examples of Hasse diagrams are shown in the figure:
You don't have to include arrows in a Hasse diagram. The Hasse diagram can be rotated in a plane, but not arbitrarily. When turning, it is necessary to maintain the relative position (above - below) of the vertices of the diagram:
Attitude R in abundance X called attitude of strict order, if it is transitive and asymmetrical.
A set in which a strict order relation is defined is called ordered. For example, the set of natural numbers is ordered by the relation “less than”. But this same set is also ordered by another relation - “divided into” and “more”.
The graph of the “less than” relation in the set of natural numbers can be depicted as a ray:
Attitude R V X called relation non-strict (partial) order, if it is transitive and antisymmetric. Any relation of non-strict order is reflexive.
The epithet "partial" expresses the fact that perhaps not all elements of a set are comparable in a given respect.
Typical examples of partial order relations are the relations “not greater than,” “not less than,” and “not greater than.” The particle “not” in the names of relationships serves to express their reflexivity. The relation “not more than” coincides with the relation “less than or equal”, and the relation “not less” is the same as “greater than or equal”. In this regard, partial order is also called not strict in order. Often a partial (non-strict) order relation is denoted by the symbol "".
The inclusion relation Í between subsets of a certain set is also a partial order. Obviously, not every two subsets are comparable in this respect. The figure below shows the partial inclusion order on the set of all subsets of the set (1,2,3). The arrows on the graph that should be pointing upward are not shown.
Sets on which partial order is given are called partially ordered, or simply ordered sets.
Elements X And at partially ordered set is called compare with us If Xat or atX. IN otherwise they are not comparable.
An ordered set in which any two elements are comparable is called linearly ordered, and the order is linear order. Linear order is also called perfect order.
For example, the set of all real numbers with the natural order, as well as all its subsets, are linearly ordered.
Objects of the most varied nature can be ordered hierarchically. Here are some examples.
Example 1: The parts of a book are organized so that a book contains chapters, chapters contain sections, and sections contain subsections.
Example 2. Folders in the computer file system are nested inside each other, forming a branching structure.
Example 3. The relationship between parents and children can be depicted as the so-called family tree, which shows who is whose ancestor (or offspring).
Let on the set A partial order is given. Element X called maximum (minimum) element of set A, if from the fact that Xat(atX), equality follows X= u. In other words, the element X is maximum (minimum) if for any element at or is it not true that Xat(atX), or is executed X=u. Thus, the maximum (minimum) element is greater (smaller) than all elements distinct from it with which it is in relation.
Element X called largest (smallest), if for anyone atÎ A performed at< х (х< у).
A partially ordered set can have several minimum and/or maximum elements, but there cannot be more than one minimum and maximum element. The smallest (largest) element is also the minimum (maximum), but the converse is not true. The figure on the left shows a partial order with two minimum and two maximum elements, and on the right a partial order with the smallest and largest elements:
In a finite partially ordered set there are always minimum and maximum elements.
An ordered set that has the largest and smallest elements is called limited. The figure shows an example of an infinite bounded set. Of course, it is impossible to depict an infinite set on a finite page, but you can show the principle of its construction. Here the loops near the vertices are not shown to simplify the drawing. For the same reason, the arcs that provide the display of the transitivity property are not shown. In other words, the figure shows the Hasse diagram of the order relation.
Infinite sets may not have maximum or minimum elements, or both. For example, the set of natural numbers (1,2, 3, ...) has a smallest element of 1, but no maximum. The set of all real numbers with natural order has neither a smallest nor a largest element. However, its subset consisting of all numbers X< 5, has the largest element (the number 5), but does not have the smallest.
Let R be a binary relation on the set A.
DEFINITION. A binary relation R on a set A is called an order relation on A or an order on A if it is transitive and antisymmetric.
DEFINITION. A relation of order R on a set A is called nonstrict if it is reflexive on A, that is, for each of A.
An order relation R is called strict (on A) if it is anti-reflexive on A, that is, for any of A. However, from the anti-reflexivity of the transitive relation R, it follows that it is antisymmetric. Therefore, the following equivalent definition can be given.
DEFINITION. A binary relation R on a set A is called a strict order on A if it is transitive and anti-reflexive on A.
Examples. 1. Let be the set of all subsets of the set M. The inclusion relation on a set is a relation of non-strict order.
2. Relations on the set of real numbers are, respectively, relations of strict and non-strict order.
3. The divisibility relation in the set of natural numbers is a relation of non-strict order.
DEFINITION. A binary relation R on a set A is called a preorder relation or preorder on A if it is reflexive on and transitive.
Examples. 1. The divisibility relation in the set of integers is not an order. However, it is reflexive and transitive, which means it is a preorder.
2. The relation of logical implication is a preorder on the set of propositional logic formulas.
Linear order. An important special case of order is linear order.
DEFINITION. An order relation on a set is called a linear order relation or linear order on if it is connected on , i.e. for any x, y from A
An order relation that is not linear is usually called a partial order relation or partial order.
Examples. 1. The relation “less than” on the set of real numbers is a relation of linear order.
2. The order relation adopted in Russian language dictionaries is called lexicographic. The lexicographic order on the set of words in the Russian language is a linear order.
Properties of relationships:
1) reflexivity;
2) symmetry;
3)transitivity.
4) connectedness.
Attitude R on a set X called reflective, if about each element of the set X we can say that he is in a relationship R With myself: XRx. If the relation is reflexive, then there is a loop at each vertex of the graph. Conversely, a graph whose every vertex contains a loop is a reflexive relation graph.
Examples of reflexive relations are the relation “multiple” on the set of natural numbers (each number is a multiple of itself), and the relation of similarity of triangles (each triangle is similar to itself), and the relation of “equality” (each number is equal to itself), etc.
There are relations that do not have the property of reflexivity, for example, the relation of perpendicularity of segments: ab, ba(there is not a single segment that can be said to be perpendicular to itself) . Therefore, there is not a single loop in the graph of this relationship.
The relation “longer” for segments, “more by 2” for natural numbers, etc. does not have the property of reflexivity.
Attitude R on a set X called anti-reflective, if for any element from the set X always false XRx: .
There are relationships that are neither reflexive nor anti-reflexive. An example of such a relationship is the relationship “point X symmetrical to the point at relatively straight l", defined on a set of points on the plane. Indeed, all points of a straight line l are symmetrical to themselves, and points that do not lie on a straight line l, themselves are not symmetrical.
Attitude R on a set X called symmetrical, if the condition is met: from the fact that the element X is in relation to the element y, it follows that the element y is in relation R with element X:xRyyRx.
The symmetric relation graph has the following feature: along with each arrow coming from X To y, the graph contains an arrow going from y To X(Fig. 35).
Examples of symmetrical relations can be the following: the relation of “parallelism” of segments, the relation of “perpendicularity” of segments, the relation of “equality” of segments, the relation of similarity of triangles, the relation of “equality” of fractions, etc.
There are relationships that do not have the property of symmetry.
Indeed, if the segment X longer than the segment at, then the segment at cannot be longer than the segment X. The graph of this relationship has a peculiarity: the arrow connecting the vertices is directed only in one direction.
Attitude R called antisymmetric, if for any elements X And y from truth xRy should be false yRx: : xRyyRx.
In addition to the “longer” relation, there are other antisymmetric relations on many segments. For example, the "greater than" relation for numbers (if X more at, That at there can't be more X), the “more on” attitude, etc.
There are relations that have neither the property of symmetry nor the property of antisymmetry.
Relation R on a set X called transitive, if from that element X is in relation R with element y, and element y is in relation R with element z, it follows that the element X is in relation R with element z: xRy And yRzxRz.
Transitive relation graph with each pair of arrows coming from X To y and from y To z, contains an arrow going from X To z.
The relation “longer” on a set of segments also has the transitivity property: if the segment A longer than the segment b, line segment b longer than the segment With, then the segment A longer than the segment With. The relation of “equality” on a set of segments also has the property of transitivity: (a=b, b=c)(a=c).
There are relations that do not have the property of transitivity. Such a relation is, for example, the perpendicularity relation: if a segment A perpendicular to the segment b, and the segment b perpendicular to the segment With, then the segments A And With not perpendicular!
There is another property of relations, which is called the property of connectedness, and a relation that has it is called connected.
Attitude R on a set X called connected, if for any elements X And y from this set the following condition is satisfied: if X And y are different, then either X is in relation R with element y, or element y is in relation R with element X. Using symbols this can be written like this: xyxRy or yRx.
For example, the relation “greater than” for natural numbers has the property of connectedness: for any distinct numbers x and y one can state, either x>y, or y>x.
On the graph related relationship any two vertices are connected by an arrow. The opposite statement is also true.
There are relationships that do not have the property of connectedness. Such a relation, for example, is the relation of divisibility on the set of natural numbers: we can name such numbers x and y whatever the number X is not a divisor of a number y, nor number y is not a divisor of a number X(numbers 17 And 11 , 3 And 10 etc.) .
Let's look at a few examples. On set X=(1, 2, 4, 8, 12) the relation “number” is given X multiple of the number y" Let's construct a graph of this relationship and formulate its properties.
The relation of equality of fractions is said to be an equivalence relation.
Attitude R on a set X called equivalence relation, if it simultaneously has the properties of reflexivity, symmetry and transitivity.
Examples of equivalence relations include: equality relations geometric shapes, the relation of parallelism of lines (provided that coinciding lines are considered parallel).
In the relation of “equality of fractions” discussed above, the set X split into three subsets: ( ; ; }, {; } , (). These subsets do not intersect, and their union coincides with the set X, i.e. we have a partition of the set into classes.
So, if an equivalence relation is given on a set X, then it generates a partition of this set into pairwise disjoint subsets - equivalence classes.
Thus, we have established that the equality relation on the set
X=( ;; ; ; ; ) corresponds to the partition of this set into equivalence classes, each of which consists of fractions equal to each other.
The principle of partitioning a set into classes using some equivalence relation is important principle mathematics. Why?
Firstly, equivalent means equivalent, interchangeable. Therefore, elements of the same equivalence class are interchangeable. Thus, fractions that are in the same equivalence class (; ; ), are indistinguishable from the point of view of the relation of equality, and the fraction can be replaced by another, for example . And this replacement will not change the result of the calculations.
Secondly, since the equivalence class contains elements that are indistinguishable from the point of view of some relation, it is believed that the equivalence class is determined by any of its representatives, i.e. an arbitrary element of the class. Thus, any class of equal fractions can be specified by specifying any fraction belonging to this class. equivalence class by one representative allows you to study a set of representatives from equivalence classes instead of all elements of the set. For example, the equivalence relation “to have the same number of vertices,” defined on a set of polygons, generates a partition of this set into classes of triangles, quadrangles, pentagons, etc. properties inherent in a certain class are considered on one of its representatives.
Thirdly, partitioning a set into classes using an equivalence relation is used to introduce new concepts. For example, the concept of a “bundle of lines” can be defined as what parallel lines have in common with each other.
Another important type of relationship is the order relationship. Let's consider the problem. On the set X={3, 4, 5, 6, 7, 8, 9, 10 ) the relation “have the same remainder when divided by 3 " This relation generates a partition of the set X into classes: all numbers will fall into one, when divided by 3 it turns out to be the remainder 0 (these are numbers 3, 6, 9 ). In the second - numbers, when divided by 3 the remainder is 1 (these are numbers 4, 7, 10 ). The third will contain all the numbers that, when divided by 3 the remainder is 2 (these are numbers 5, 8 ). Indeed, the resulting sets do not intersect and their union coincides with the set X. Therefore, the relation “have the same remainder when divided by 3 ", defined on the set X, is an equivalence relation.
To take another example, the many students in a class can be sorted by height or age. Note that this relation has the properties of antisymmetry and transitivity. Or everyone knows the order of letters in the alphabet. It is provided by the “should” attitude.
Attitude R on a set X called relation of a strict order, if it simultaneously has the properties of antisymmetry and transitivity. For example, the relation " X< y».
If the relation has the properties of reflexivity, antisymmetry and transitivity, then such it will be non-strict relation. For example, the relation " Xy».
Examples of order relations include: the “less than” relation on a set of natural numbers, the “shorter” relation on a set of segments. If an order relation also has the property of connectedness, then it is said to be linear order relation. For example, the relation “less than” on the set of natural numbers.
A bunch of X called orderly, if an order relation is specified on it.
For example, many X={2, 8, 12, 32 ) can be ordered using the “less than” relation (Fig. 41), or this can be done using the “multiple” relation (Fig. 42). But, being order relations, the relations “less than” and “multiple” order the set of natural numbers in different ways. The “less than” relation allows you to compare any two numbers from a set X, but the relation “multiple” does not have this property. Okay, a couple of numbers. 8 And 12 is not related to the relation “multiple”: it cannot be said that 8 multiple 12 or 12 multiple 8.
One should not think that all relations are divided into relations of equivalence and relations of order. There are a huge number of relations that are neither equivalence relations nor order relations.
Important type binary relations- relations of order. Strict order relation - a binary relation that is anti-reflexive, antisymmetric and transitive:
designation - (A preceded b). Examples include
relations “more”, “less”, “older”, etc. For numbers, the usual notation is the signs "<", ">".
Non-strict order relation - binary reflexive, antisymmetric and transitive relation. Along with natural examples of non-strict inequalities for numbers, an example can be the relation between points of a plane or space “to be closer to the origin of coordinates.” Non-strict inequality, for integers and real numbers, can also be considered as a disjunction of the relations of equality and strict order.
If a sports tournament does not provide for the division of places (i.e., each participant receives a certain, only eat/awarded place), then this is an example of a strict order; otherwise, it is not strict.
Order relations are established on a set when for some or all pairs of its elements the relation
precedence . The task - for a set of some order relation is called its "arranging, and the "set itself" as a result of this becomes ordered. Order relations can be introduced in different ways. For a finite set, any permutation of its elements “specifies some strict order. An infinite set can be ordered in an infinite number of ways. Only those orderings that have meaningful meaning are of interest.
If for the order relation R on a set .M and some different elements hold at least one of the relations
aRb or bRa, then the elements A And b are called comparable, otherwise - incomparable.
A fully (or linearly) ordered set M -
a set on which an order relation is specified, and any two elements of the set M comparable; partially ordered set- the same, but pairs of incomparable elements are allowed.
Linearly ordered is the set of points on a line with the relation “more to the right”, the set of integers, rational numbers, real numbers with the relation “greater than”, etc.
An example of a partially ordered set would be three-dimensional vectors, if the order is given as follows, if
That is, if the precedence is carried out along all three coordinates, the vectors (2, 8, 5) and (6, 9, 10) are comparable, but the vectors (2, 8, 5) and (12, 7, 40) are not comparable. This ordering method can be extended to vectors of any dimension: vector
precedes the yector if
And done
We can consider other examples of ordering on the set of vectors.
1) partial order: 
, If
Those. by vector length; vectors of the same length are incomparable.
2) linear order: 
, If a
The last example introduces the concept of alphabetical order.
Alphabet is a tuple of pairwise distinct characters called letters of the alphabet. An example is the alphabet of any European language, as well as the alphabet of 10 Arabic numerals. On a computer, the keyboard and some supporting tools determine the alphabet of valid characters.
Word in the alphabetA - tuple of alphabet characters A. The word is written in alphabetical characters in a row, from left to right, without spaces Natural number is a word in the digital alphabet The formula is not always a word due to the nonlinear arrangement of symbols, the presence of superscript (exponents) and subscripts (indices of variables, bases of logarithms) symbols, fractional bar, radical signs, etc.; however, by some conventions it can be written into a string, which is used, for example, in computer programming (for example, the exponentiation sign is written as 2 multiplication signs in a row: 5**3 means the third power of the number 5.
Lexicographical (alphabetical) ordering - for different words in the alphabet with ordered
symbols set the ordering: , if
possible introduction 
, at which either
(subword can be empty), or - empty subword
In this definition - a prefix (initial subword) that is the same for both words - or the first ones on the left are different
characters, either - the last character in the word - tail
subwords.
Thus, the alphabetical ordering of words is determined by the first symbol on the left that distinguishes them (for example, the word KONUS precedes the word COSINE because they first differ in the third letter, and N precedes S in the Russian alphabet). The space character is also considered to precede any character of the alphabet - for the case when one of the words is a prefix of another (for example, CON and CONE)
Exercise. Check that the alphabetical ordering of natural numbers that have the same number of decimal places coincides with their ordering by magnitude.
Let A - partially ordered set. The element is called maximum V A, if there is no element for which A< b. Element A called the largest V A, if for everyone different from A element completed b<а-
Determined symmetrically minimal and smallest elements. The concepts of largest and maximum (respectively, smallest and minimal) elements are different - see. example in Fig. 14. The set in Fig. 14,a has the largest element R, it is also the maximum, there are two minimum elements: s and t, there is no smallest. In Fig. 14b, on the contrary, there is a set having two maximal elements / and j, there is no greatest, minimal, aka the smallest - one: T.
In general, if a set has the largest (respectively, smallest) element, then there is only one (there may be none).
There can be several maximum and minimum elements (there may not be any at all - in an infinite set; in the final case - there must be).
Let's look at two more examples. - relation on a set N:
"Y divides X", or "X is a divisor of a number Y"(For example,
) is reflexive and transitive. Let's consider it on a finite set of divisors of the number 30.
The relation is a partial order relation (non-strict)
and is represented by the following matrix of order 8, containing 31 characters
The corresponding circuit with 8 vertices must contain 31 links. . However, it will be more convenient for viewing if we exclude 8
connectives-loops depicting the reflexivity of the relationship (diagonal elements of the matrix) and transitive connectives, i.e. ligaments
If there is an intermediate number Z such that
(for example, the connective since). Then in the scheme
12 ligaments will remain (Fig. 15); missing links are implied "by transitivity". The number 1 is the smallest, and the number 30
largest elements in . If we exclude from the number 30 and
consider the same partial order on the set, then
there is no maximum element, but there are 3 maximum elements: 6, 10, 15
Now let's build the same circuit for a relation on a Boolean
(the set of all subsets) of a three-element set
Contains 8 elements:
Check that if you match the elements a, b, c, respectively, the numbers 2, 3, 5, and the operations of combining sets are multiplication of the corresponding numbers (i.e., for example, a subset corresponds
product 2 5 = 10), then the relation matrix will be exactly like this
same as for relation ; diagrams of these two relationships with those described
abbreviations of loops and transitive connectives coincide up to notation (see Fig. 16). The smallest element is
And the greatest -
Binary relationships R on a set A And S on a set IN are called isomorphic, if between A and B it is possible to establish a one-to-one correspondence Г, in which, if (i.e.
elements are in relation R), then (images
these elements are in relation S).
Thus, partially ordered sets are isomorphic.
The considered example allows for generalization.
A Boolean relation is a partial order. If
Those. a bunch of E contains P elements, then each
corresponds to the subset P-dimensional vector with
components , where is the characteristic function
set A/ . The set of all such vectors can be considered as a set of points P-dimensional arithmetic space with coordinates 0 or 1, or, in other words, as vertices P-dimensional
unit cube, denoted by , i.e. cube with edges of unit length. For n = 1, 2, 3 indicated points represent, respectively, the ends of a segment, the vertices of a square and a cube - hence the common name. For /7=4, a graphical representation of this relationship is in Fig. 17. Near each vertex of a 4-dimensional cube the corresponding
subset of 4-element set and four-dimensional
a vector representing the characteristic function of this subset. The vertices corresponding to subsets that differ in the presence of exactly one element are connected to each other.
In Fig. 17, a four-dimensional cube is depicted in such a way that on one
level, incomparable elements are located in pairs, containing the same number of units in the record (from 0 to 4), or, in other words, the same number of elements in the represented subsets.
In Fig. 18a, b - other visual representations of a 4-dimensional cube;
in Fig. 18a the axis of the first variable OH directed upward (intentional deviation from the vertical so that different edges of the cube do not merge):
in this case the 3-dimensional subcube corresponding to X= 0 is located below, and for X= 1 - higher. In Fig. 186 same axis OH directed from the inside of the cube to the outside; the inner subcube corresponds to X= Oh, and the external one is X = 1.
IN 
The materials file shows an image of a 5-dimensional unit cube (p. 134).
2) a relation on the set X is called a relation strictly in order, if it is antisymmetric and transitive. The relationship is called antisymmetric, if from the fact that a is in relation to c in it does not follow that b is in relation to a (a, in ∈ X, and R in → in R a) R – to be in relation. The relationship is called transitive, if for any elements a, b, c from the fact that a R in and in R c → that a R c, a, b, c ∈ X. For example: the relation “more, less”. A set on which a strict order relation is defined is called ordered many.
3) a relation on the set X is called a relation not in strict order, if it is reflexive, asymmetric and transitive. For example: relation ≥ ≤. If an order relation has the property of connectedness, then it is said to be a relation linear order. The relationship is called related on the set X, if for any elements x and y the following condition is satisfied: from the fact that x ≠ y it follows that x R y or y R x. If a linear order relation is given on a set, then it linearly orders the given set.
5. The set of real numbers. Its properties. The expansion of the set of rational numbers was led by the need to measure the lengths of segments, areas, etc. The basis of any measurement is the same principle: the measured object is compared with a standard (object or phenomenon), the value of which has a numerical value equal to 1, but the unit segment is not always embedded in the measured object. Therefore, when measuring, two assumptions are made, which in mathematics are defined as axioms: 1) A single standard can be divided into any number of equal shares or parts. 2) The selected standard can be used to measure any object as large as desired. For segments, these axioms were formulated by Archimedes: No matter how small the segment AB is and no matter how large the segment CD is, there is a natural number N such that N*AB>CD, if the measured segment CD contains an equal number of segments AB, then the length of the segment CD is expressed as a natural number. If in the measured segment CD the segment AB is placed an unequal number of times, then AB is divided into 10 identical segments, called tenths of standards. If necessary, a tenth can be divided into 10 equal parts, etc. If the equal number 10, 100, etc. fits into the segment CD. fractions of segments AB, then the length of the segment CD is expressed by a rational number. However, the length of a segment cannot always be expressed as a natural or rational number. There are incommensurable segments, i.e. segments whose length is not expressed by a rational number. (theorems see question 32)
Numbers that can be represented as infinite decimal non-periodic fractions are called irrational. The union of the set of rational numbers and the set of irrational numbers is the set of real numbers ().
Properties of the set of real numbers. 1). The set of points on the number line is equal to the set of real numbers.
0 M 1 Take any point M on the segment from 0 to 1,
D draw a semicircle with center at
The midpoint of this segment and the radius
K O S equal to half of it. Let's draw a perpendicular from M until it intersects with the semicircle. We get D. This point is unique, since the semicircle and the straight line intersect only at one point. From the middle of this segment, draw a straight line through D until it intersects with the number axis. We obtain K, which is determined in a unique way, since the lines intersect only at one point. By choosing another arbitrary point on a given segment and repeating the entire process, we obtain that any point on the segment from 0 to 1 corresponds to a single point on the number line. Reasoning in reverse order, we can show that any point on the number line also corresponds to a single point from 0 to 1. If an arbitrary point E belongs to the number line, then through the points M and E only one line can be drawn that intersects the semicircle. From a semicircle you can lower a perpendicular to a given segment. Thus, a mutually identical mapping is established between the points of the segment from 0 to 1 and the points of the number line, i.e. they are equally powerful.
2) the set of real numbers is not countable, i.e. it is not equal to the set of natural numbers.
3). The set of real numbers is a continuous set. The continuity of the set of real numbers is that between any two real numbers there is an infinite set of only real numbers
6. Partitioning a set into classes. Examples of classification. Equivalence relation, its properties. The relationship between the equivalence relation and the partition of a set into classes.
- Let's look at an example. Let a set M be given (a set of convex polygons), we form all the subsets of this set: A 1 – a set of triangles; A2 – set of quadrangles; A3 – set of pentagons; Ak is a set of k-gons. A set M is considered to be divided into classes if the following conditions are met:
- every subset A is not empty
- the intersection of any two subsets is the empty set
the union of all subsets is the given set M Partitioning a set into classes is called.
classification Attitude on the set X is called equivalent , if it is reflexive, symmetrical and transitive. The relationship is called reflective symmetrical, if for any two elements of the set X (a and b) from the fact that a is in a relationship with b, it will follow that b is in a relationship with a (a, b ∈ X, and R b → in R a). The relationship is called transitive, if for any elements a, b, c from the fact that a R in and in R c → that a R c, a, b, c ∈ X. On the graph of equivalence relations there are loops, mutually inverse arrows and triangular arrows. The equivalence relation, and only it, is associated with the partition of a set into classes. This statement can be formulated as theorems: If an equivalence relation is specified on a set X, then this relation divides the set X into classes, and vice versa, if the set X is divided into classes, then the equivalence relation is satisfied on the given set. For example. Let the attitude be given - to live in the same house. Let us show that the set of residents in the house will be divided into classes. And each class is a separate apartment. For this division, all will be performed the necessary conditions partitioning a set into classes: a) each class is not empty, because in each apartment at least 1 person is registered, b) the classes do not overlap (1 person is not registered in two different apartments), c) the union of all classes, i.e. residents of each apartment, and constitutes the set of residents of the house.
18 . A set-theoretic approach to constructing the theory of non-negative integers. Relations of equality, more (less). Two sets A and B are called equivalent or equally powerful if a one-to-one correspondence can be established between them, that is, if each element of set A is associated with a single element of set B and vice versa. Power or cardinal number is a property that is inherent in any set B that is equivalent to set A and is not inherent in any other set that is not equal to set A. A~B n (A) = a is power. The relation of equal power is an equivalence relation, i.e. the properties of reflexivity, symmetry and transitivity are satisfied for it. The equivalence relation divides the set of all sets into equivalence classes. To define the concept of a natural number and zero, consider the partition of all finite sets.
Let M be the set of all finite sets. M = K 0 Ka Kv, where Ko is the class of empty sets, Ka is a set containing equal sets a 1, a 2, a 3, etc., Kv is a set. Containing sets of equal cardinality in 1, in 2, in 3, etc. The set M may also contain other subsets K of different natures, which consist of sets of equal power. Each equivalence class K has in common that they consist of the same number of elements; there are no other common properties. A non-negative integer, from a set-theoretic point of view, is a general property of the class of finite sets of equal power. A natural number is a general property of the class of non-empty finite sets of equal cardinality. Each class is assigned a cardinal number (cardinality). The class empty set is assigned the coordinate number 0. The class consisting of sets that have 1 element is assigned the number 1. A class consisting of sets with 2 elements is assigned the number 2. (n(K 0)=0, n(K 1)=1, n(K 2)=2, n(Ka)=a).
Equality relation. Non-negative integers a and b are said to be equal if the sets A and B, the number of which they express, are equal (A; n(A)=a, n(B)=b, A ~ B n(A)=n(B) a=c).
Theorem: the relation of equality in the set of non-negative integers is an equivalence relation. Proof. Let us prove that the equality relation has the properties of symmetry, transitivity and reflexivity.
Because the properties of reflexivity, symmetry, and transitivity are satisfied, then the equality relation is an equivalence relation.
The ratio is less. Non-negative integer a<в, если множество А равномощно собственному подмножеству В 1 множества В. а<в; n(А)=а; n(В)=в; В 1 В n(В 1) Theorem: the relation less than in the set of non-negative integers is a relation of strictly order. Proof: Let us prove that the relation less has the properties of antisymmetry and transitivity. C 2 C 1 C 2 ~B 1 C 2 ~A n(A)=n(C 2) n(C 2) A B C 1 C B 1 C 2 19
. Addition and subtraction in the quantitative theory of non-negative integers. Their properties. Amount two non-negative integers a and b is called a non-negative integer c, which is the cardinality of the union of two disjoint sets A and B, whose cardinalities are respectively equal to a and b. a+b=c, n(C)=n(АУВ), n(АУВ)=n(А)+n(В). Properties of addition. 1. Addition in a set of non-negative integers always exists and is defined in a unique way. Let us prove that the sum always exists. Consider A and B, such that their intersection is the empty set and the number of elements of A is a, and the cardinality of B is b. let's find the union of A and B. Since the union of two disjoint sets always exists, this means that the sum also exists, and from the definition of the sum it follows that addition always exists. Let us prove that the sum is determined in a unique way. There are C 1 and C 2 – non-negative integers. C 1 = a + b and C 2 = a + b. The sum of the numbers a and b does not depend on which sets A and B we chose from the class of equal power sets, and therefore the union of A and B taken from the class of equal power sets does not depend on the choice of sets A and B, since the power in each class are the same, then C 1 = C 2. 2. Commutative addition. For any non-negative integers a and b, the property a+b=b+a holds. From set theory we know that for АУВ = ВУА. If sets are equal, their numerical values are equal. n(АУВ)=n(ВУА). From set theory we know that the power of a union is equal to the sum of the powers. N(A)+n(B)=n(B)+n(A). 3. Property of associativity. For any numbers a, b, c, the following property holds: a+(b+c)=(a+b)+c. From set theory it is known that to unite sets the associativity property is satisfied: АU(ВУС)=(АУВ)UC, if sets are equal, then their numerical values are equal, n(АU(ВУС))=n((АУВ)UC). From set theory it is known that the power of a union is equal to the sum of the powers of these sets, n(A)+n(BUC)=n(AUB)+n(C) n(A)+(n(B)+n(C))= (n(A)+n(B))+n(C) a+(b+c)=(a+b)+c. By difference non-negative integers a and b is called a non-negative integer c, which is the power of the complement of the set B to the set A, such that B belongs to A, n(A)=a, n(B)=b. Difference Properties. 1. In order for the difference of non-negative integers to exist, it is necessary and sufficient that a be greater than or equal to b. Let's prove: 1) a sufficient condition for the existence of a difference. Given: a - b = c, prove: a c. By the definition of difference it follows that there is a complement of set B to set A, and this complement has power, which can be found from the equality known from set theory. n() = n(A)-n(B). From the fact that B is a subset of A it follows that the number of elements in B is less than the number of elements of A. n (B) 2). Necessary condition. Given a c. prove the existence of difference (a-c). If a>b, by the definition of the “less than” relation, there is a set A 1 such that A 1 is included in A and A 1 ~B. Let's make the difference between A and A 1. This difference always exists (A - A 1 = C), and therefore there exists C, which is this difference. From these conditions it follows that C is the complement of A 1 to A. C = 1A The power of C is the power of the complement of A 1 to A. n (C)=n( 1A)=n(A)-n(A 1), since A 1 ~ B, then n(A 1)=n(B), therefore n(C)=n(A)-n(B), therefore c=a-b. 2. The difference of non-negative integers is found in a unique way, since the difference is the power of the complement of subsets to a set, and the complement is determined in a unique way, then the difference of non-negative integers is determined in a unique way. 3. The properties of commutativity and associativity are not satisfied for subtraction. 4. Subtracting an amount from a number. a-(b+c)=(a-c)-c. From set theory it is known A\(BUC)=(A\B)\C, and B Ì A; S Ì A; BUSCA. n (A\(BUC))=n((A\B)\C) n(A)-n(BUC)=n(A\B)-n(C) n(A)-(n(B)+n(C))=(n(A)-n(B))-n(C) a-(b+c)=(a-c)-c. 5. Subtracting a number from the difference (a-c)-c=(a-c)-c. The proof is based on the property of the difference of sets (A\B)\C=(A\C)\B. 6. Subtracting a number from the sum (a+b)-c=(a-c)+c. The proof is based on the property of the sets (АУВ)\С=(А\С) УВ. Properties of numerical functions. 1. Each function has a domain of definition and a set of values. 2. The function can be increasing or decreasing. A function is said to be increasing on the interval a b if for any x1 and x2 x1 > x2 it follows f (x1) > f (x2). A function is called decreasing on the interval a b if for any x1 and x2 from this interval, from the fact that x1 > x2 it follows f (x1) Even not even< f (x0). In practice, we often encounter functions that are neither even nor odd. 7. a function may have breakpoints, i.e. those values of the variable x in which y does not exist (functions of inverse proportionality). y = , if x = 0 Search on the site: Disable adBlock!
7. The concept of a tuple of an ordered pair. Cartesian product of sets and its properties. The number of elements in a decrete product of sets. To introduce the concept of a Cartesian product of sets, consider the concept motorcade. This concept, like the concept of set, is a basic indefinite concept. For a tuple, the order of the elements is important. Elements in a tuple can be repeated. The number of elements in a given tuple is called its length. A tuple of length 2 is called an ordered pair. The card is designated by () or< >. × is a designation for the Cartesian product of sets. (a,b,a); (a,b,c) ≠ (b,a,c); (a,e,c)=(a,e,c). Cartesian product of sets A and B is a set consisting of all ordered pairs in which the first component is an element of the first set, and the second component is an element of the second set. A=(a,b,c) B=(1,2) A×B=((a,1),(a,2), (c,1),(c,2),(c,1) ,(с,2)) Property of the Cartesian product of sets (DPM). The DPM does not have the property of commutativity and associativity: A×B≠B×A. The distributive properties of the DPM are satisfied: 1) with respect to the union of sets A×(B⋃C)=(A×B)⋃(A×C); 2) regarding the intersection of sets A×(B∩C)=(A×B)∩(A×C). To find the number of elements in a DP in two or more sets, you need to know the number of elements in each set. If the number of elements is n. If n(A)=n, and n(B)=m, then n(A×B)=n*m. Let A=(a1,a2,a3,...an) B=(b1,b2,b3,...bm). Let's compose the DPM A and B: (a1,b1) (a1,b2) (a1,b3) ...(a1, bm) (a2,b1) (a2,b2) (a2,b3) ...(a2, bm) (a3 ,в1) (а3,в2) (а3,в3) …(а3,вm) ___________________________ (аn, в1) (аn, в2) (аn, в3) …(аn, вm) In each line there are em-pairs, such lines en, it means that the total number of items listed is em on en pairs, therefore the number of elements in the DPM A and B is equal to the product of the number of elements in set A and the number of elements in set B. 8. The concept of correspondence between sets. Methods for specifying compliance. Types of correspondences. The correspondence ef between the elements of the sets X and Y is called a triple of sets (X;U; G f (ji from ef), ji from ef is a subset of the DP (Cartesian product). The set X is called the departure region, the set Y is called the arrival region ji from ef - is called the graph of this correspondence. The domain of determination of the correspondence ef is the set of those elements of the first set (i.e., the departure region) to which the elements of the second set correspond (i.e., the set of the value of the correspondence ef is the set of elements of the arrival region, which are assigned). in accordance with some elements of the departure area. Methods for specifying correspondences: listing its elements, using a graph, using a graph, using a table, verbally, algebraically, i.e. equation, inequality. Types of correspondences. The correspondences are called everywhere defined , if the sending area coincides with the definition area. In the graph of such a correspondence, at least one arrow departs from each element of the first set. Compliance is called, if its set of values coincides with the arrival region. In a graph of such correspondence, at least 1 arrow matches each element of the 2nd set. Compliance is called injective, if no different elements of the 1st set correspond to the same element of the 2nd set. In a graph of such correspondence, no element of the 2nd set is matched by more than 1 arrow. Compliance is called functional, if each element of the 1st set corresponds to no more than 1 element of the 2nd set. On a graph of such a correspondence, if there is only 1 arrow departing from each element of the 1st set. Functional correspondence is called function. Among all functional correspondences, there are universally defining correspondences, which are called display. Compliance is called one-to-one, if the following conditions are met: 1) any two different elements of the set X correspond to different elements of the set Y, 2) any element of the set Y corresponds to at least one element of the set X. Two correspondences between the sets X and Y are called opposite, if their graphs complement each other the Cartesian product of X and Y. The correspondence is called reverse to a given correspondence if a given correspondence holds if and only if the converse holds. If a given correspondence is a subset of the Cartesian product of the sets X and Y, then the inverse correspondence is a subset of the Cartesian product of the sets X and Y. To obtain the inverse correspondence to the given one. On its graph it is necessary to change the direction of the arrows.
9.Functional compliance. Properties of numerical functions. Compliance is called functional, if each element of the 1st set corresponds to no more than 1 element of the 2nd set. On a graph of such a correspondence, if there is only 1 arrow departing from each element of the 1st set. A functional correspondence defined on a numerical set is called numerical is called function.< f (x2).
3. функции могут быть четными или не четными. Функция называется четной, если она задана на симметричной области определения и выполняется условие f(-x)=f(x). Функция называется не четной, если на симметричной области определения выполняется условие f(-x)=-f(x). График четной функции симметричен относительно оси ОУ, не четной – симметричен относительно начала координат.
у = х 2 у = х 3
2015-2020 website - Contacts - Latest addition
very necessary
