Order relation on the set of examples. Relation of strict and non-strict order

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. In a computer, the keyboard and some aids determine the alphabet of valid characters.

Word in the alphabetBUT - tuple of alphabet characters BUT. The word is written with alphabetic characters in a row, from left to right, without spaces A natural number is a word in the digital alphabet A formula is not always a word due to the non-linear arrangement of characters the presence of superscript (exponents) and subscript (indices of variables, bases of logarithms) symbols, fractional bar, signs radicals, 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.

Lexico-graphic (alphabetic) ordering - for various words in the alphabet with ordered

characters set ordering: if

possible presentation , 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 in a row on the left are different

characters, or - the last character in the word - tail

subwords.

Thus, the alphabetical ordering of words is determined by the first character that distinguishes them from the left (for example, the word KONUS precedes the word COSINUS, since they first differ in the third letter, and H precedes C in the Russian alphabet). It is also considered that the space character precedes any character of the alphabet - for the case when one of the words is a prefix of the other (for example, KOH and CONE)

The exercise. Check that the alphabetical ordering of natural numbers that have the same number of digits in decimal notation is the same as their ordering by magnitude.

Let be BUT - partially ordered set. The element is called maximum in BUT, if there is no element for which but< b. Element but called greatest in BUT, if for any other than but item completed b<а-

are defined symmetrically minimum and least elements. The concepts of the largest and maximum (respectively, the smallest and minimum) elements are different - see. example in Fig.14. The set in Fig. 14a 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, the set having two maximum elements / and j , there is no greatest, minimum, it is the smallest - one: T.

In general, if a set has a largest (respectively, smallest) element, then only one (there may be none).

There can be several maximum and minimum elements (may not be at all - in an infinite set; in the final case, there must be).

Let's look at two more examples. - relation on the set N:

"Y divides X", or "X is the divisor of the number Y"(for example,

) is reflexive and transitive. Consider it on a finite set of divisors of the number 30.

The relation is a relation of partial order (non-strict)

and is represented by the following matrix of order 8, containing 31 characters

The corresponding scheme with 8 vertices must contain 31 bundles. . However, it will be more convenient for viewing if we exclude 8

links-loops depicting the reflexivity of the relation (diagonal elements of the matrix) and transitive links, i.e. bundles

If there is an intermediate number Z such that

(for example, a bunch because ). Then in the schema

there will be 12 ligaments (Fig. 15); the missing links are implied "by transitivity". The number 1 is the smallest and the number 30

the largest elements in . If we exclude from the number 30 and

consider the same partial order on the set , then

there is no largest element, but there are 3 maximum elements: 6, 10, 15

Now let's build the same scheme for the Boolean relation

(set of all subsets) of a three-element set

Contains 8 elements:

Check that if you match the elements a, b, c, the numbers 2, 3, 5, respectively, and the operations of union of sets are the multiplication of the corresponding numbers (i.e., for example, a subset corresponds to

product 2 5 = 10), then the relation matrix will be exactly

same as for relation ; schemes of these two relations with the described

abbreviations of loops and transitive connectives coincide up to notation (see Fig. 16). The smallest element is

And the biggest -

binary relations R on the set BUT And S on the set IN called isomorphic if between A and B it is possible to establish a one-to-one correspondence Г, in which, if (i.e.

elements are related R), then (images

these elements are related S).

Thus, partially ordered sets and are isomorphic.

The considered example admits a generalization.

The Boolean relation is a partial order. If

Those. lots of E contains P elements , then each

subset corresponds P-dimensional vector with

components , where is the characteristic function

sets 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 the segment, the vertices of the square and the cube - hence the common name. For /7=4, a graphic representation of this relationship is in Fig.17. Near each vertex of the 4-dimensional cube, the corresponding

subset of a 4-element set and four-dimensional

a vector representing the characteristic function of this subset. The vertices are connected to each other, corresponding to subsets that differ in the presence of exactly one element.

In Fig. 17, a four-dimensional cube is depicted in such a way that on one

level there are pairwise incomparable elements 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 upwards (intentional deviation from the vertical so that the various edges of the cube do not merge):

while the 3-dimensional subcube corresponding to X= 0 is located below, and for X= 1 - higher. On fig. 186 same axle OH directed from inside the cube to the outside, the inner subcube corresponds to X= Oh, and external - X= 1.

IN
The material file shows an image of a 5-dimensional unit cube (p. 134).

The word "order" is often used in a variety of issues. The officer gives the command: “Calculate in the order of numbers”, arithmetic operations are performed in a certain order, athletes become in height, there is an order for performing operations in the manufacture of a part, word order in a sentence.

What is common in all cases when it comes to order? The fact that the word “order” has such a meaning: it means which element of this or that set follows which (or which element precedes which).

Attitude " X follows at» transitively: if « X follows at" And " at follows z", then " x follows z". In addition, this ratio must be antisymmetric: for two different X And at, if X follows at, then at does not follow X.

Definition. Attitude R on the set X called strict order relation, if it is transitive and antisymmetric.

Let us find out the features of the graph and the graph of strict order relations.

Consider an example. On the set X= (5, 7, 10, 15, 12) the relation R: « X < at". We define this relation by enumeration of pairs
R = {(5, 7), (5, 10), (5, 15), (5, 12), (7, 10), (7, 15), (7, 12), (10, 15), (10, 12), (12, 15)}.

Let's build its graph. We see that the graph of this relation has no loops. There are no double arrows on the graph. If from X the arrow goes to at, and from at- in z, then from X the arrow goes to z(Fig. 8).

The constructed graph allows you to arrange the elements of the set X in this order:

{5, 7, 10, 12, 15}.

In Fig. 6 (§ 6 of this chapter) columns VII, VIII are graphs of relations of a strict order.

Non-strict order relation

The relation "less than" in the set of real numbers is opposite to the relation "not less". It is no longer a strict order. The point is, at X = at, relations X ³ at And at ³ X, i.e. the relation "no less" is reflexive.

Definition. Attitude R on the set X called non-strict order relation, if it is reflexive, antisymmetric and transitive.

Such relations are unions of a strict order relation with an identity relation.

Consider the relation "no more" (£) for the set

X= (5, 7, 10, 15, 12). Let's build its graph (Fig. 9).

A non-strict order relation graph, unlike a strict order relation graph, has loops at each vertex.

On fig. 6 (§ 6 of this chapter) graphs V, VI are graphs of relations of non-strict order.

Ordered sets

A set may turn out to be ordered (they also say completely ordered) by some order relation, while another may be unordered or partially ordered by such a relation.

Definition. Lots of X called orderly some order relation R if for any two elements x, y from X:

(X, at) Î R or ( y, x) Î R.

If R is a strict order relation, then the set X ordered by this relation under the condition: if X, at any two unequal elements of a set X, then ( X, at) Î R or ( y, x) Î R, or any two elements x, y sets X are equal.

It is known from the school mathematics course that number sets N , Z , Q , R ordered by the ratio "less than" (<).

The set of subsets of a certain set is not ordered by the introduction of an inclusion relation (U), or a strict inclusion relation (T) in the above sense, because there are subsets none of which is included in the other. In this case, the given set is said to be partially ordered by the relation Í (or Ì).

Consider the set X= (1, 2, 3, 4, 5, 6) and it has two relations "less than" and "divisible by". It is easy to check that both of these relations are order relations. The less than relation graph can be represented as a ray.

The graph of the relation "is divided by" can be represented only on a plane.

In addition, there are vertices on the graph of the second relation that are not connected by an arrow. For example, there is no arrow connecting the numbers 4 and 5 (Fig. 10).

The first relation X < at' is called linear. In general, if the order relation R(strict and non-strict) on the set X has the property: for any X, atÎ X or xRy, or yRx, then it is called a linear order relation, and the set X is a linearly ordered set.

If the set X of course, and consists of n elements, then the linear ordering X reduces to enumeration of its elements by numbers 1,2,3, ..., n.

Linearly ordered sets have a number of properties:

1°. Let be a, b, c– set elements X, ordered by relation R. If it is known that aRv And vRc, then we say that the element in lies between the elements but And from.

2°. Lots of X, linearly ordered by the relation R, is called discrete if between any two of its elements lies only a finite set of elements of this set.

3°. A linearly ordered set is called dense if for any two distinct elements of this set there is an element of the set lying between them.

2) the relation on the set X is called the relation strictly order, if it is antisymmetric and transitive. The relation is called antisymmetric, if from the fact that a is in relation to c in it does not follow that in is in relation to a (a, in ∈ X, and R in → in R a) R - to be in relation. The relation 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, c, c ∈ X. For example: the relation "more, less". A set on which a strict order relation is given is called orderly many.

3) the relation on the set X is called the relation not in a strict order, if it is reflexive, asymmetric and transitive. For example: ratio ≥ ≤. If an order relation has the property of being connected, then it is said to be a relation linear order. The relation is called related on the set X, if for any elements x and y the 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 need to measure the lengths of segments, areas, etc. led to the expansion of the set of rational numbers. Any measurement is based on the same principle: the measured object is compared with the standard (object or phenomenon), the value of which has a numerical value equal to 1, but not always a single segment is embedded in the measured object. Therefore, when measuring, 2 assumptions are made, which in mathematics were defined as axioms: 1) A single standard can be divided into any number of equal shares or parts. 2) The chosen standard can be used to measure any arbitrarily large object. For segments, these axioms were formulated by Archimedes: No matter how small the segment AB and no matter how large the segment CD, there is such a natural number N that N*AB>CD, if an equal number of segments AB fit in the measured segment CD, then the length of the segment CD is expressed as a natural number. If in the measured segment CD the segment AB fits an unequal number of times, then we divide AB into 10 identical segments, called the tenth of the standards. If necessary, the tenth share can be divided into 10 equal parts, etc. If an equal number of 10, 100, etc. fits into the segment CD. fractions of segments AB, then the length of the segment CD is expressed as a rational number. However, not always the length of the segment can 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-recurring fractions are called irrational numbers. 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. one). The set of points of the numerical axis is equivalent to the set of real numbers.

0 M 1 Take any point M on the segment from 0 to 1,

Draw a semicircle centered at

The middle of this segment and the radius

K O C equal to half of it. Draw a perpendicular from M to the intersection with the semicircle. We get D. This point is unique, since the semicircle and the straight line intersect at only one point. From the middle of this segment through D we draw a straight line to the intersection with the real axis. We obtain K, which is uniquely determined, since the lines intersect at only one point. Choosing another arbitrary point on a given segment and repeating the whole process, we get that any point on the segment from 0 to 1 corresponds to a single point on the real line. Arguing backwards, 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 only one line can be drawn through the points M and E that intersects the semicircle. From a semicircle, you can drop a perpendicular to a given segment. Thus, between the points of the segment from 0 to 1 and the points of the number line, a mutually identical mapping is established, i.e. they are equal.

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. Splitting the set into classes. Classification examples. Equivalence relation, its properties. The relationship of the equivalence relation with the division of the set into classes. Let's look at an example. Let the set M be given (a set of convex polygons), we form all subsets of this set: A 1 - a set of triangles; A2 is a set of quadrilaterals; А3 – set of pentagons; Ak is the set of k-gons. The set M is considered to be divided into classes if the following conditions are met:

1. each subset A is not empty
2. the intersection of any two subsets is the empty set
3. the union of all subsets is the given set M

The division of a set into classes is called classification.

Attitude on the set X is called equivalent , if it is reflexive, symmetric and transitive. The relation is called reflective, if any element from the set X is in relation with itself a ∈ X, and R a (R is in relation). The relation is called symmetrical, if for any two elements of the set X (a and c) from the fact that a is in relation to c it follows that c is in relation to a (a, c ∈ X, and R c → c R a). The relation 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, c, c ∈ X. There are loops, mutually inverse arrows and triangular arrows on the graph of the equivalence relation. The equivalence relation, and only it, is connected with the division of a set into classes. This statement can be formulated as theorems: If an equivalence relation is specified on the 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 relation be given - to live in the same house. Let us show that the set of tenants in the house will be divided into classes. And each class is a separate apartment. For this division, all the necessary conditions for dividing the set into classes will be satisfied: a) each class is not empty, since each apartment has at least 1 person, but 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. tenants of each apartment, and makes up the set of tenants of the house.

18 . Set-theoretic approach to the construction of the theory of non-negative integers. Relations of equality, more (less). Two sets A and B are called equivalent or equivalent if a one-to-one correspondence can be established between them, i.e., if each element of the set A is associated with a single element of the set B and vice versa. Power or cardinal number is a property that is inherent in any set B, which is equal in power to set A, and is not inherent in any other set, which is not equal in power to set A. A~B n (A)=a is power. Equivalence relation is an equivalence relation, i.e. it satisfies the properties of reflexivity, symmetry, and transitivity. The equivalence relation divides the set of all sets into equivalence classes. To define the concept of a natural number and zero, consider a partition of all finite sets.

Let M be the set of all finite sets. M=K 0 Ka Kv, where Ko is a class of empty sets, Ka is a set containing equal sets a 1, a 2, a 3, etc., Kv is a set. Containing equal sets in 1 , in 2 , in 3 , etc. The set M may also contain other subsets K of different nature, 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 a class of finite equal sets. A natural number is a general property of the class of non-empty finite equipotent sets. Each class is assigned a cardinal number (power). The class empty set is assigned the coordinate number 0. The class consisting of sets with 1 element is assigned the number 1. The 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. Integer non-negative numbers a and b are called equal if the sets A and B, the number of which they express, are equivalent (A; n(A)=a, n(B)=b, A ~ B n(A)=n(B) a=c).

Theorem: the equality relation in the set of non-negative integers is an equivalence relation. Proof. Let us prove that the relation of equality has the properties of symmetry, transitivity and reflexivity.

Because properties of reflexivity, symmetry, transitivity are satisfied, then the equality relation is an equivalence relation.

Ratio less. A non-negative integer a<в, если множество А равномощно собственному подмножеству В 1 множества В. а<в; n(А)=а; n(В)=в; В 1 В n(В 1)

Theorem: the ratio less than in the set of non-negative integers is a relation of strict order. Proof: Let us prove that the relation less than has the properties of antisymmetry and transitivity.

C 2 C 1 C 2 ~ B 1 C 2 ~ A n (A) \u003d n (C 2) n (C 2)

A B C 1 C

B 1 C 2

19 . Addition and subtraction in the quantitative theory of integer non-negative numbers. Their properties. sum two non-negative integers a and b is called a non-negative integer c, which is the cardinality of the union of two non-intersecting sets A and B, whose cardinalities are respectively equal to a and c. a+b=c, n(C)=n(AUB), n(AUB)=n(A)+n(B).

Addition properties. 1. Addition in the set of non-negative integers always exists and is uniquely defined. 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 c. we find the union of A and B. Since the union of two disjoint sets always exists, and hence the sum exists, and from the definition of the sum it follows that addition always exists.

Let us prove that the sum is uniquely determined. There are C 1 and C 2 - non-negative integers. C 1 \u003d a + b and C 2 \u003d a + c. The sum of numbers a and b does not depend on which sets A and B we have chosen from the class of equivalent sets, and therefore the union of A and B taken from the class of equivalent sets does not depend on the choice of sets A and B, because the power in each class are the same, then C 1 \u003d C 2.

2. Commutativity of addition. For any non-negative integers a and b, the property a+b=b+a is fulfilled. We know from set theory that for AUB = BUA. If the sets are equal, their numerical values ​​are equal. n(AUB)=n(BUA). We know from set theory that the cardinality of a union is equal to the sum of the cardinalities. 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. It is known from the theory of sets that the associativity property is fulfilled for the union of sets: АU(ВУС)=(АУВ)UС, if the sets are equal, then their numerical values ​​are equal, n(AU(ВУС))=n((АУВ)UC). It is known from set theory that the cardinality of the union is equal to the sum of the cardinalities of these sets, n(A) + n (BUC) \u003d n (AUB) + n (C) n (A) + (n (B) + n (C)) \u003d (n (A) + n (B)) + n (C) a + (b + c) \u003d (a + c) + c.

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)=c.

Difference Properties. 1. For a 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 the difference, it follows that there is a complement of set B to set A, and this complement has a cardinality that can be found from an equality known from set theory.

n () \u003d 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) in; B enters A; n(V)

2). Necessary condition. Given a. prove the existence of the 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. Compose the difference between A and A 1. This difference always exists (A-A 1 \u003d 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 \u003d 1A The power of C is the power of the complement of A 1 to A. n (C) \u003d n ( 1A) \u003d n (A) -n (A 1) , since A 1 ~ B, then n (A 1) \u003d n (B), therefore n (C) \u003d n (A) -n (B), therefore c \u003d a-c.

2. The difference of non-negative integers is found in a unique way, since the difference is the cardinality of the complement of subsets to a set, and the complement is defined in a unique way, then the difference of non-negative integers is defined in a unique way.

3. For subtraction, the properties of commutativity and associativity are not satisfied.

4. Subtraction of the sum from the number. a-(b+c)=(a-c)-c. From set theory we know A\(BUC)=(A\B)\C, and B Ì A; C Ì A; VUSÌA.

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 \u003d (a-c)-c. The proof is based on the set difference property (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 sets (AUB)\C=(A\C)UB.

Disable adBlock!
very necessary