Relation of strict and non-strict order. Their properties, examples. Order relations Strict order relations

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 symbols 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 symbols; 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.

Lexicographical (alphabetical) ordering - for different words in the alphabet with ordered

symbols set the ordering: , if

presentation possible , 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 minimum) 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, the 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).

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.

The main distinguishing feature of an order relation is that it has 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 n..., 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. 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 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 arranged 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.

A bunch of X (\displaystyle X), on which the partial order relation is introduced, is called partially ordered. A non-strict partial order relation is often denoted by ≼ (\displaystyle \preccurlyeq ).

Options

Partial order relation R (\displaystyle R) called linear order, if the condition is met

A bunch of X (\displaystyle X), on which a linear order relation is introduced, is called linearly ordered, or chain.

Attitude R (\displaystyle R), satisfying only the conditions of reflexivity and transitivity is called pre-order, or quasi-order.

Strict order

If the condition of reflexivity is replaced by the condition of anti-reflexivity:

then we get the definition strict, or anti-reflexive partial order(usually indicated by the symbol ≺ (\displaystyle \prec )).

Comment. The simultaneous anti-reflexivity and transitivity of a relation entails antisymmetry. Therefore the relation is relation of a strict order if and only if it is anti-reflexive and transitive.

In general, if R (\displaystyle R) is a transitive, antisymmetric relation, then

Examples

• On the set of real numbers, the relations “more than” and “less than” are relations of strict order, and “more than or equal to” and “less than or equal to” are non-strict.
• The divisibility relation on a set of integers is a relation of non-strict order.

Dushnik-Miller dimension

Story

Signs < {\displaystyle <} And > (\displaystyle >) invented

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 of 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 “greater than” relation for natural numbers has the property of connectedness: for any distinct numbers x and y one can state, either x>y, or y>x.

In a connected relation graph, 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, no 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: relations of equality of geometric figures, relations 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 an important principle of 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.

Equivalence relation. The connection between the equivalence relation and the partition of a set into classes

Definition. Attitude R on a set X is called an equivalence relation if it is reflexive, symmetric and transitive.

Example. Consider the relation " X classmate at"on many students of the Faculty of Education. It has the following properties:

1) reflexivity, because every student is his own classmate;

2) symmetry, because if a student X at, then the student at is a classmate of the student X;

3) transitivity, because if a student X- classmate at, and the student at– classmate z, then the student X will be the student's classmate z.

Thus, this relation has the properties of reflexivity, symmetry and transitivity, and therefore is an equivalence relation. At the same time, many students of the Faculty of Education can be divided into subsets consisting of students studying in the same course. We get 5 subsets.

Equivalence relations are also, for example, the relation of parallelism of lines, the relation of equality of figures. Each such relationship is associated with partitioning the set into classes.

Theorem. If on set X given an equivalence relation, then it splits this set into pairwise disjoint subsets (equivalence classes).

The converse statement is also true: if any relation defined on the set X, generates a partition of this set into classes, then it is an equivalence relation.

Example. On set X= (1; 2; 3; 4; 5; 6; 7; 8) the relation “have the same remainder when divided by 3” is specified. Is it an equivalence relation?

Let's build a graph of this relationship: (independently)

This relation has the properties of reflexivity, symmetry and transitivity, therefore, it is an equivalence relation and splits the set X to equivalence classes. In each equivalence class there will be numbers that, when divided by 3, give the same remainder: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

It is believed that the equivalence class is determined by any of its representatives, i.e. an arbitrary element of this class. Thus, a class of equal fractions can be specified by specifying any fraction belonging to this class.

In the initial course of mathematics, equivalence relations are also encountered, for example, “expressions X And at have the same numerical values", "figure X equal to the figure at».

Definition. Attitude R on a set X is called an order relation if it is transitive and asymmetric or antisymmetric.

Definition. Attitude R on a set X is called a strict order relation if it is transitive and asymmetric.

Examples relations of a strict order: “more” on the set of natural numbers, “higher” on the set of people, etc.

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

Examples relations of a non-strict order: “no more” on the set of real numbers, “be a divisor” on the set of natural numbers, etc.

Definition. A bunch of X is called ordered if an order relation is specified on it.

Example. On set X= (1; 2; 3; 4; 5) two relations are given: “ X £ at" And " X- divider at».

Both of these relations have the properties of reflexivity, antisymmetry and transitivity (construct graphs and check the properties yourself), i.e. are relations of non-strict order. But the first relation has the property of connectedness, while the second does not.

Definition. Order relation R on a set X is called a linear order relation if it has the property of connectedness.

In elementary school, many order relations are studied. Already in the first grade there are relations “less”, “more” on the set of natural numbers, “shorter”, “longer” on the set of segments, etc.

Control questions

1. Define a binary relation on a set X.

2. How to write a statement that the elements X And at are in a relationship R?

3. List ways to define relationships.

4. Formulate the properties that relationships can have. How are these properties reflected in the graph?

5. What properties must a relation have in order for it to be an equivalence relation?

6. How is the equivalence relation related to the partition of a set into classes?

7. What properties must a relation have in order for it to be a relation of order?