Orderliness of the set of natural numbers. inequalities on the set of natural numbers in the discipline “Abstract Algebra”
Ordered sets
Definition 1. A bunch of M called ordered, if some relationship is established between its elements a b(" a preceded b"), having the following properties: 1) between any two elements a And b there is one and only one of three relationships: a = b, a b, b a; 2) for any three elements a, b And c from a b, b c follows a c.
An empty set is considered ordered.
Comment. We always understand the = sign in the sense of identity, coincidence of elements. Record a = b simply means that in letters a And b denotes the same element of the set M. Therefore, from property 1) it follows that between two different elements one and only one of the two relations holds a b or b a.
If a preceded b, then they say that b follows a and write: b > a.
Attitude a > b It has, as can be easily verified, properties similar to 1) and 2). It can be taken as the main one, then defining through it the relation a b.
If in an ordered set M change the roles of the relationship, i.e. instead a b write a > b, and vice versa, we get a new ordered set M", the order of which is said to be inverse to the order M. For example, for the above order in the set of natural numbers, the order will be reversed:
Two ordered sets composed of the same elements, but arranged in different orders, are considered different. Therefore, when defining an ordered set through its elements, it is necessary to indicate their order. We will assume that the notation from left to right corresponds to the order of elements, and we will retain the previous notation with curly braces. The same set can be ordered in different ways (if it contains at least two elements). Thus, the set of natural numbers can be ordered in the usual way or in the reverse order; odd numbers can be placed in front of even numbers or vice versa, arranging both in ascending or descending order. We obtain ordered sets
We will say that the natural number and more than a natural number b(and designate a > b), if there is a natural number k such that a = b + k.
Theorem 1. One is not greater than any natural number.
Indeed, the condition 1 > a entails 1 = a + k, which is impossible: for k = 1 we obtain 1 = a /, which contradicts the first axiom of natural numbers; for k ¹ 1 we find its predecessor and again come to the same contradiction.
This “more” relation is anti-reflective(it is not true that a > a) and transitive(a > b /\ b > c => a > c), that is, is relation of a strict order. Moreover, this relation is a relation of linear order, that is, for the set of natural numbers the trichotomy theorem is valid:
Trichotomy theorem: For any two natural numbers, one and only one of the following three statements is true:
Proof: First we show that no two of the three conditions are satisfied simultaneously. Let us assume that conditions 1 and 2 are met. Then
a = b + k, b = a + n => a = a + (n + k) => a > a,
which contradicts the anti-reflexivity of the “more” attitude. Similarly, the incompatibility of conditions 2 and 3 and conditions 1 and 3 is established.
Now we will prove that one of the three conditions necessarily holds for any numbers a and b. We use mathematical induction on b. For b = 1, depending on a: either a = 1 = b, or for a there is a predecessor, then
a = c / = c + 1 = 1 + c = b + c => a > b.
Thus, for b = 1 the theorem is true. Let us make an induction assumption that the theorem is valid for some x, namely, that x is comparable to the number a, that is, three options are possible: either a > x, or x > a, or x = a. Then we prove that x/ is also comparable to a. In the first case, a > x, that is, a = x + k. Depending on whether the given k is equal to 1 or not, we get
a) a = x + 1 = x / (the theorem is true)
b) a = x + c / = x + c + 1 = x + 1 + c = x / + c => a > x / .
In the second case x > a, but then
x / = (a + m) +1 = a + (m + 1),
that is, x / > a. Similarly, for x = a, x / = x + 1 = a + 1, that is, again x / > a. The theorem is completely proven.
Now you can introduce the concepts<, £, ³.
a< b ó b >a;
a £ b ó a< b \/ a = b
a ³ b ó a > b \/ a = b.
Properties of monotonicity:
For the addition operation:
1) a > b => a + c > b + c;
2) a + c > b + c => a > b;
3) a > b /\ c > d=> a + c > b + d.
<, £, ³.
For the multiplication operation:
4) a > b => a×c > b×c;
5) Law of contraction: ac = bc => a = b
6) ac > bc => a > b;
7) a > b /\ c > d=> ac > bd.
The same properties occur for other signs<, £, ³.
Let us give as an example the proof of properties 4 and 5. Since a > b, by definition a = b + k, then a×c = (b + k)×c = b×c + k×c, which means that a ×c > b×c, and property 4 is proven. We prove Property 5 by contradiction. Let ac = bc, but suppose that a ≠ b, but then, by the trichotomy theorem, either a > b, or b > a, but this means, according to property 4, that either ac > bc, or bc > ac, which contradicts the condition (ac = bc).
Discreteness theorem. You cannot insert a natural number between two adjacent natural numbers:
(" a, x О N) it is not true that a< x < a /
Proof(by contradiction method). Let a< x < a / . Тогда х = а + k,
a / = x + n = a + k + n => a + 1 = a + k + n => 1 = k + n.
The last equality is impossible, since it contradicts the theorem that one is not greater than any natural number.
Tower of Archimedes. For any natural numbers a and b, there is a natural number n such that a< bn.
We carry out the proof by induction on b. For b = 1, n = a / . Let us make an inductive assumption that for b = k the required n exists, that is, a< kn. Но тогда тем более a < k / n = kn + k. Теорема доказана.
The smallest element of the set M we will call an element with О М such that for any elements m О M the following inequality holds: с ≤ m.
Least Element Theorem. Any non-empty subset of the set of natural numbers has a smallest element.
Proof: If M is a subset of N containing 1, then 1 will be the desired smallest element. If 1 is not included in the set M, then consider the auxiliary set A, consisting of all natural numbers smaller than all natural numbers from the set M:
A = (a О N| (" m О M) a< m}.
From this construction, in particular, it follows that the sets A and M do not have common elements. In addition, A is not empty, since 1 Î A. In A there is also an element b, such that b / Ï A. Indeed, if there were no such element, then by the axiom of induction it would be possible to prove that A = N, but then M would be empty, which does not correspond to the conditions of the theorem. The element b / = c will be precisely the smallest element in the set M. Indeed, c £ m for any m ОМ (if this were not so, then the inequality c > m would hold true for at least one natural m, but b О A , so b< m < c = b / , что противоречит теореме о дискретности). Кроме того, с не может быть строго меньше всех элементов множества М, иначе с Î А, что противоречит его выбору. Таким образом, с равен хотя бы одному элементу из М, а значит с Î М, то есть действительно с – наименьший элемент множества М. Теорема доказана.
Note that not every subset of the set of natural numbers has a greatest element, but if this subset is finite, then it also has a greatest element. The opposite is also true. If a subset of the set of natural numbers has the largest element, then this subset is finite. One can prove an even more general statement: a non-empty subset of the set of natural numbers is bounded from above if and only if it is finite (has the largest element).
Tasks for independent solution
No. 1.8. Prove that the relation “more than” is anti-reflexive and transitive on the set of natural numbers.
No. 1.9. Prove monotonicity properties 1, 2, 3, 6, 7 from this section.
No. 1.10. Prove inequalities for all natural numbers n
a) 5 n > 7n – 3;
b) 2n +2 > 2n + 5;
Valid (real) numbers are well known from school mathematics courses. Let us briefly dwell on their properties, which are quite easily perceived by each of us. Real numbers form a set of elements that have the following properties.
Order property
For any two numbers %%a%% and %%b%% the order relation is defined, i.e. Any two real numbers %%a%% and %%b%% satisfy one of the following relations: %%a< b, a = b%% или %%a >b%%; Moreover, if %%a< b%% и %%b < c%%, то %%a < c%%.
Properties of the addition operation
amount and denoted by %%a + b%%, that the following properties are satisfied.
- Commutativity: %%a + b = b + a %%.
- Associativity: %%a + (b + c) = (a + b) + c%% for any numbers %%a, b%% and %%c%%.
- zero and denoted by %%0%% , which means %%a + 0 = a%% for any number %%a%%.
- For any number %%a%% there is a number called opposite%%a%% and denoted %%-a%%, which is %%a + (-a) = 0%%.
- If %%a< b%%, то %%a + c < b + c%% для любого числа %%c%%. Нуль единственен, и для каждого числа единственно противоположное ему число. Для любой пары чисел %%a%% и %%b%% число %%a + (-b) %% называют difference numbers %%a%% and %%b%% and denote %%a - b%%.
Properties of the multiplication operation
For any pair of numbers %%a%% and %%b%% there is a unique number called their work and denoted by %%ab%% (or %%a \cdot b%%) that the following properties are satisfied.
- Commutativity: %%ab = ba%%.
- Associativity: %%a(bc) = (ab)c%% for any numbers %%a, b%% and %%c%%.
- There is a number called unit and denoted by %%1%%, that %%a \cdot 1 = a%% for any number %%a%%.
- For any number %%a%% not equal to zero, there is a number called reverse to this and denoted by %%1 / a%%, which is %%a \cdot (1 / a) = 1%%.
- If either %%a%% or %%b%%, or both %%a%% and %%b%% are zero, then %%ab = 0%%.
- If %%a< b%% и %%c >0%%, then %%ac< bc%%. Единица единственна, и для каждого ненулевого числа существует единственное обратное к нему. Для любой пары чисел %%a%% и %%b (b \neq 0)%% число %%a \cdot (1/b)%% называют private from dividing %%a%% by %%b%% and denoted %%a/b%%.
Distributivity property
For any triple of numbers %%a, b%% and %%c%% the equality %%(a + b)c = ac + bc%% holds.
Archimedean property
Whatever the number %%a%%, there is an integer %%n \in \mathbb(N)%% such that %%n > a%%.
Rice. 1. Number line
Before formulating the next property of real numbers, recall that the line is given frame of reference, if two different points are fixed on this line (points %%O%% and %%e%% in Fig. 1). The left one (point %%O%%) is called the origin, and the length of the segment %%Oe%% specifies the scale unit. A straight line with a given reference system is called coordinate axis. It is usually denoted %%Ox%%. The point %%O%% divides the coordinate axis into two parts: the positive semi-axis, where the point %%e%% lies, and the negative semi-axis.
Coordinate points %%M%% on the axis %%Ox%% are the length of the segment %%OM%%, taken with the sign %%+%%, if the point %%M%% lies on the positive semi-axis, and with the sign %%-% %, if point %%M%% lies on the negative semi-axis.
Obviously, each point %%M%% on the %%Ox%% axis corresponds to a real number %%x%%, namely its coordinate. And conversely, each real number on the %%Ox%% axis corresponds to a point for which this real number is its coordinate. Whenever this is required, we will assume that this kind of correspondence has been established between the real numbers and the points of a certain line, with %%e = 1%%, %%O = 0%%.
Thus, the set of all real numbers can be considered as number line. Sometimes, instead of the number line, the term “real line” is also used. Identifying real numbers with points on the number line will be extremely useful in the future, as it serves as an aid to understanding and motivates the introduction of new concepts.
The subset %%X%% of the set of real numbers is called in between, if, together with any two numbers %%x_1, x_2%%, this subset contains any %%x%% enclosed between them. The following types of gaps are used:
- %%(a, b) = \(x: a< x < b\}%% - interval, or open span;
- %% = \(x: a \leq x \leq b\)%% - line segment, or closed gap(sometimes the term “segment” is used);
- %%(a, b] = \(x: a< x \leq b\}%% и %% \supseteq %%, то отрезок %%%% называют nested into the segment %%%%.
Continuity property
For any system of nested segments $$ \supseteq \supseteq \supseteq \ldots \supseteq \supseteq \ldots $$ there is at least one point belonging to all segments of this system. This property is also called the principle of nested segments (Cantor's principle).
From the listed properties of real numbers one can obtain that 1 > 0, as well as the rules for operations with rational fractions; rules of signs for multiplying and dividing real numbers; rules for transforming equalities and inequalities; properties of the absolute value of a real number.
Absolute value
Absolute value(or module) %%|a|%% of any real number %%a%% is a real number that satisfies the conditions: $$ |a| = \begin(cases) a, \text( if ) a \geq 0 \\ -a, \text( if ) a< 0 \end{cases} ~~~~~~~~~~(1) $$
It follows that the absolute value of any real number is non-negative %%(|a| \geq 0)%%, as well as $$ \begin(array)(l) |a| = |-a|, \\ |a| \geq a, \\ |a| \geq -a, \\ -|a| \leq a \leq |a|. \end(array)~~~~~~~~~~(2) $$
Geometrically, %%|a|%% corresponds to the distance between the points on the number line representing the numbers %%0%% and %%a%%.
Let the inequality %%|a|< \varepsilon%%, где %%\varepsilon%% - некоторое положительное число (%%\varepsilon >0%%) . Then this inequality is equivalent to the double inequality $$ -\varepsilon< a < \varepsilon. $$ Равносильность рассмотренных неравенств будет сохранена, если строгие неравенства (%%<%%) заменить на нестрогие (%%\leq%%): %%|a| \leq \varepsilon%% равносильно %%-\varepsilon \leq a \leq \varepsilon%%.
For any real numbers %%a%% and %%b%% the equality $$ |ab| = |a||b| ~~~~~~~~~~(3) $$ and the following inequalities hold: $$ \begin(array)(lr) |a + b| \leq |a| + |b| &~~~~~~~~~~(4),\\ |a - b| \geq \big||a| - |b|\big|&~~~~~~~~~~(5). \end(array) $$
Using (1) and (2), we prove inequality (4): if %%a + b \geq 0%%, then $$ |a + b| = a + b \leq |a| + |b| $$ and if %%a + b< 0%%, то $$ |a + b| = -(a + b) = (-a) + (-b) < |a| + |b| $$
The above properties completely describe the set of all real numbers.
The set of all real numbers, as well as the set of points on the number line, is usually denoted as %%\mathbb R%%.
Completed set of real numbers
Replenished(or expanded) the set of real numbers is the set formed from all real numbers %%x \in \mathbb R%% with the addition of two elements, denoted %%+\infty%% (“plus infinity”) and %%-\infty%% ( "minus infinity") It is believed that %%-\infty< +\infty%% и для всех чисел %%x \in \mathbb R%% справедливо %%-\infty < x < +\infty%%. Пополненное множество обозначают %%\overline{\mathbb R}%%. Ему соответствует extended(or replenished) number line. The elements %%-\infty%% and %%+\infty%% are called infinite points of such a line.
Subsets of the set %%\mathbb R%% of real numbers
- Set of integers$$ \mathbb Z = \(\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots \) $$ is a proper subset of the set %%\mathbb R%% (%%\mathbb Z\subset\mathbb R%%).
- Set of natural numbers$$ \mathbb N = \(1, 2, 3, \ldots \) $$ is a proper subset of both the set %%\mathbb Z %% and the set %%\mathbb R%% %%(\mathbb N \ subset \mathbb Z \subset \mathbb R)%%.
The set of all real numbers that can be represented as the quotient of the integer %%m \in \mathbb Z%% divided by the natural number %%n \in \mathbb N%% is called the set rational numbers and denote %%\mathbb Q%%, i.e. $$ \mathbb Q = \left\(\frac(m)(n): m \in \mathbb Z, n \in \mathbb N\right\) $$
The ratios %%\frac(m)(n)%% and %%\frac(m"))(n")%% are considered equal (representing the same rational number %%r \in \mathbb Q%%), if %%mn" = nm"%%. Thus, each rational number %%r = \frac(m)(n)%% can have infinitely many images %%r = \frac(p m)(p n), p \in \mathbb N%%.
It is obvious that %%\mathbb N \subset \mathbb Z \subset \mathbb Q \subset \mathbb R%%.
Endless intervals
On the completed number line there are infinite intervals $$ (b, +\infty) = \(x: x > b\), (-\infty, a) = \(x: x< a\} $$ и бесконечные полуинтервалы $$ = \{x: x \leq a\} $$ По аналогии с бесконечными интервалами множество всех точек на числовой прямой R обозначают часто %%(-\infty, +\infty)%% или просто %%(-\infty, \infty)%%.
Rice. 2. Neighborhood of a point
Any interval %%(a, b)%% containing some point %%x_0%% is called surroundings this point and denote %%\text(U)(x_0)%%, i.e. %%\text(U)(x_0) = (a, b)%% if %%x_0 \in (a, b)%%. The point %%x_0%%, located in the middle of its neighborhood %%(a, b)%%, in this case is called the center of the neighborhood, and the distance %%\varepsilon = \frac((b - a))(2)%% is the radius of the neighborhood. Then the set %%\(x: |x - x_0|< \varepsilon\}%% называют %%\varepsilon%%-окрестностъю точки %%x_0%% и обозначают %%\text{U}(x_0, \varepsilon)%% или %%\text{U}_\varepsilon(x_0)%% (рис. 2).
On the extended number line, the concept of neighborhood is introduced for the infinite points %%+\infty%% and %%-\infty%%, thereby equating these points with finite ones when considering many issues. Let %%M%% be some positive number. Then %%\text(U)(+\infty) = \(x \in \mathbb(R): x > M\)%% and %%\text(U)(-\infty) = \(x \ in\mathbb(R): x< -M\}%%, а для объединения бесконечных точек %%\text{U}(\infty) = \{x \in \mathbb{R}: |x| >M\)%%. It is clear that for any of the infinite points, the neighborhood with a smaller value of %%M%% includes a neighborhood with a larger value of %%M%%.
Ministry of Education and Science of the Russian Federation
Federal Agency for Education
NIZHNEKAMSK MUNICIPAL INSTITUTE
Department of Informatics, Mathematics and Natural Sciences -
scientific disciplines
Group 561
ABSTRACT
in the discipline "Abstract Algebra"
Level of education specialist
Topic: Ordered sets
Head ___________________ R.M. Munipov
Student ___________________ A.V. Glazunov
Nizhnekamsk 2007
INTRODUCTION………………………………………………………………………………..3
1. Partially ordered sets……………………………5
2. Well-ordered sets…………………………………..20
3. Partial groupoids and their properties……………………………..23
CONCLUSION………………………………………………………..35
REFERENCES………………………………………………………….36
Introduction
Currently, algebra is understood mainly as the general theory of algebraic operations and relations. It is characterized by a great internal naturalness of the initial ideas and tasks, unity of methods, and a far-reaching breadth of basic concepts. Its area is delineated clearly and clearly. And yet the existing boundaries of the theory cannot be considered firmly and definitively established. The desire to go beyond its limits begins to emerge more and more often. There is a need to consider operations not only complete, but also partial.
The theory of partial actions must naturally continue the theory of complete actions. This latter is currently extremely extensive, rich and is in its heyday. Naturally, the thought arises of transferring the concepts and results developed there to a new area. This is, of course, necessary and in many cases fruitful. However, already from the first steps in the development of the theory of partial actions, the significant specificity of this direction makes itself felt. Often the direct transfer of the results of the theory of complete actions turns out to be difficult or even impossible. The usual algebraic material has to be subjected to significant processing or rethinking; in addition, completely new concepts and problems arise that are specific to the new direction. They require their own research methodology.
There has not yet been a sufficiently complete and coherent presentation of the theory of partial algebraic actions. There is inconsistency in the initial concepts and even in notations and terminology. There are not enough connections between individual works. The inadequacy of the development of individual questions necessary for the construction of a general theory makes itself felt.
1 . Hastically ordered sets
Binary relation on a set A called antisymmetric If:
(a,c A) A? V V? A
A called reflective If:
( a A) a a
Binary relation on a set A called transitive If:
(a,V,c A) a V V c>a With
Example 1.
Divisibility relation (entirely) on the set of natural numbers N antisymmetric. In fact, if A V, V A, then there are natural q1 ,q N, such that a=bq1 , в=аq where a=aq1 q , that is q1 q = 1. But,
q1 ,q N,hence q1 = q = 1, from which it follows that a = b.
Reflexive antisymmetric transitive binary relation on a set A called order relation (partial order) on the set A.
A bunch of A with a partial order relation given on it? they call partially ordered set and denote< A; ? >.
In what follows, for convenience, we will use the abbreviation PLAGUE , denoting a partially ordered set.
Example 2.
< N, ? > ? ordinary non-strict inequality of numbers (in the school sense). Is it necessary to prove the transitivity, reflexivity and antisymmetry of this relationship?
a)a? a,(2 ? 2) - reflexivity,
b) if A? V , V? With, That a ? c, (3 ? 4, 4 ? 5 > 3 ? 5) - transitivity,
c) if a ? V , V?a, That a=in,(3 ? 3, 3 ? 3 > 3=3) - antisymmetry.
It follows that < N, ? > - CHUM.
Example 3.
< N, > .
a) Divisibility relation on the set of natural numbers N reflexive, because every number is a multiple of itself, i.e. because for anyone A N Always a = a 1 (1 N), this, in the sense of the relation, we have A A. Therefore, it is reflexive.
b) If the first number is divisible by the second (i.e., a multiple of the second), and the second is a multiple of the third, then the first is a multiple of the third, which means the relation is transitive, i.e. If A V, V With, a,V,c N. So there are such q ,q N, What
a= inq ,
in =c q ,
a = c (q q ).
Let's denote: q = q q N. We have
Where q N, i.e. A With- a-priory . Therefore, the relation is transitive.
c) The antisymmetry of the relation follows from the fact that two natural numbers that are multiples of each other are equal to each other, i.e. If A V, V A, then there are such q1 ,q N, What
a=bq1 ,
в=аq ,
a=aq1 q ,
that is q1 q = 1. But, q1 ,q N,hence q1 = q = 1, from which it follows that a = b. Therefore antisymmetric.
Therefore there is a partial order and, therefore, < N, > - CHUM (partially ordered set).
Elements a,V Plague A are called incomparable are written down
A|| V, If a? V And V? A.
Elements a,V Plague A are called comparable If a? V or V? A.
Partial order? on A called linear, but the plague itself linearly - ordered or chain, if any two elements from A comparable, i.e. for any a,V A, or a ? V, or V? a.
Example 4 .
< N, ? >, < R, ? > - are a chain. However<В(M) ; > ,where B( M) - the set of all subsets of the set M or in( M) is called Boolean on a set M, is not a chain, because not for any two subsets the set M one is a subset of the other.
Let < A, ? > - arbitrary plague.
Element m A called minimal, if for any x A from what x ? m should x = m.
The meaning of this concept is that A does not contain elements strictly smaller than this element m. They say that X strictly less m and write down X< m, If x ? m, but at the same time x ? m. The maximum element of this plague is determined in a similar way. It is clear that if m , m - different minimum (maximum) elements of the plague, then m || m .
In the theory of partially ordered sets the condition a ? V sometimes read like this: elementA contained in the elementV or elementV contains an elementA .
Lemma.
Each element of a finite Plague contains a minimum element and is contained in a maximum element of this Plague.
Proof:
Let A- arbitrary element of the final plague S. If A - minimal element, then, due to reflexivity, the lemma is proven. If A is not minimal, then there is an element A such that
A < A(1)
If A is minimal, then everything is proven. If the element A is not
minimal, then for some A we get
A < а (2)
If A is minimal, then from (1), (2), thanks to transitivity, we conclude that A contains the minimum element A . If A is not minimal, then
A < A (3)
for some A S. And so on. This process cannot be infinite due to the finiteness of the set itself S.
Thus, for some time n- at the th step of reasoning the process ends, which is equivalent to the fact that the element A minimal. Wherein
A < а < < а < а < а
Due to transitivity, it follows that the element A contains the minimum element A . Likewise, element A contained in the maximum element. The lemma is proven.
Consequence.
The final plague contains at least one minimal element.
Now we introduce the concept that is important for further presentation diagrams the ultimate plague S.
First we take all the minimal elements m , m , m V S. According to the investigation, there will be such people. Then in the partially ordered set
S = S \ {m , m , m },
which, like S, is finite, we take the minimal elements,
, , and consider the set
= S \ {, , }
Elements of the “first row” m , m , m depicted by dots. A little higher we mark the elements of the “second row” with dots, , and connect the points with segments in that and only that case if m <
Next, we find the minimal elements of the Plague, depict them with points of the “third row” and connect them with points of the “second row” in the manner indicated above. We continue the process until all the elements of this Plague are exhausted S. The process is finite due to the finiteness of the set S. The resulting set of points and segments is called diagram PLAGUE S. At the same time a < в if and only if from the “point” A you can go to “points” V along some “ascending” broken line. Due to this circumstance, any finite plague can be identified with its diagram.
Example 5 .
Here given by the CHUM diagram S = {m , m , , ),wherein m < , m < , m < m < , m < m < , m < .
Element m called the smallest element of the PLAGUE, if for anyone x A Always m ? x.
It is clear that the smallest element is minimal, but the converse is not true: not every minimal element is the smallest. There is only one smallest element (if any). The largest element is determined similarly.
Example 6.
· · · ·
This is a plague, the elements of which are incomparable in pairs. These are partially
ordered sets are called antichains.
Example 7 .
This is the chain with the smallest and largest element. Where 0 is the smallest element, and 1 is the largest element.
Let M- subset of a partial ordered set A. Element A A called bottom edge sets M, If A? X for anyone x M.
The largest of all the infimums of the set M, if it exists, is called exact bottom edge sets M and denote inf M.
Let < A, ? > - arbitrary plague. Element With A called exact bottom edge elements a,V A, If With= inf( a,V}.
Note 1.
Not in every plague there is an exact infimum for any two elements.
Let's show this with an example.
Example 8 .
For ( a;c},{d;e) there is no bottom edge,
inf( a;V}=d, inf( V;c}=e.
Example 9 .
Let us give an example of a plague, which has an exact infimum for any elements.
inf( a;V}=d, inf( a;d}=d, inf( a;0 }=0 , inf( a;c}=0 , inf( a;e}=0 ,
inf( V;c}=e, inf( V;e}=e, inf( V;d}=d,
inf( c;e}=c, inf( c;0 }=0 , inf( c;d}=0 ,
inf( d;e}=0 , inf( d;0 }=0 ,
inf( e;0 }=0 .
Definition: A partially ordered set in which for any two elements there is an infimum is called semi-lattice.
Example 10 .
Let us give an example of a plague, which is not a semilattice.
Let < N, ? > - linearly ordered set of natural numbers and e ,e N. On set N = N { e ,e ) define a binary relation? , assuming that x ? y, If x, y N, Where x ? y, or if x N, y { e ,e ). We also consider by definition: e ? e ,e ? e .
The diagram of this plague is as follows:
Any natural number n ? e and n? e , but in N there is no greatest element, therefore, N - CHUM, but not a half-lattice.
So, by its very definition, a semilattice is a model (like a set with a relation?). As we will now see, another approach to the concept of a semilattice is possible, namely, a semilattice can be defined as a certain algebra.
To do this, we introduce some additional algebraic concepts. As is known, semigroup is a non-empty set with an associative binary algebraic operation defined on it.
An arbitrary semigroup is usually denoted S(semigroup).
Definition. Element eS called idempotent, If
e = e, that is e · e = e.
Example 11 .
Semigroup< N; · > ? has only one idempotent 1.
Semigroup< Z; + > ? has a single idempotent 0.
Semigroup< N; + > ? does not have idempotent, because 0 N.
For any non-empty set X, as usual, denotes the set of all subsets of the set X - the Boolean of the set X.
Semigroup<В;>- is such that each of its elements is idempotent.
A IN, A = A A.
The semigroup is called idempotent semigroup or bunch, if each of its elements is idempotent. Thus, an example of a connective is any Boolean relative to a union.
Example 12 .
Let X- an arbitrary set.
B- the set of all subsets of the set X.
B- is called a Boolean on the set X.
If X= (1,2,3) , then
B = (O,(1),(2),(3),(1,2),(2,3),(1,3),(1,2,3)).
Since the intersection of two subsets of the set X is again a subset of X, then we have a groupoid< В;>, moreover, it is a semigroup and even a connective, since A In and A = A A=A.
In exactly the same way, we have the connection<; В > .
The commutative connective is called semi-lattice.
Example 13 .
Let X= (1,2,3), let's build a diagram< В ; >.
Let us give examples of plagues, but not semilattices.
Example 14 .
CHUM with two lower faces e And d , which are not comparable to each other: e|| d. Therefore inf( a;With) does not exist.
Example 15.
CHUM with two lower faces With And d, which are incomparable: With|| d. Therefore inf( a;V) does not exist.
Let us give examples of semilattices.
Example 16 .
Diagram:
A
inf( a;V}=V, inf( a;With}=With, inf( a;d}=d,
inf( V;c}=d, inf( V;d}=d,
inf( c;d}=d.
Example 17 .
It is a semilattice, because for any two elements there is an infimum, i.e.
inf( a;V}=V, inf( a;With}=With, inf( V;c}=With.
Theorem 1.
Let<S ; ? > - semilattice. Then<S ; > commutative connective, where
a V=inf( a,V} (*).
Proof:
It is necessary to prove that in<S ; > the following identities hold:
(1) x y = y x
(2) (x y) z = x (y z)
(3) x x = x
1) According to equality(*)
x y= inf( x,y) = inf ( y,x) = y x
2) Let us denote A = (x y) z, in =x ( y z)
Let's prove that A = V.
To do this it is enough to prove that
A ? V (4)
V ? A(5) (due to antisymmetry)
Let's denote
With = x y , d = y z
Within the meaning of, A the exact lower bound between With And z
A? With , A ? z , c ? x, therefore, due to transitivity a ? x.
Likewise, A? y, i.e. A- common lower bound for y And z. A d- their exact lower bound.
Hence, a ? d, But V=inf( x, d}.
From inequality a ? x , a ? d follows that A X And d, A V is their exact infimum, therefore,
A? V(4) proven.
(5) is proved in a similar way.
From (4) and (5), in view of antisymmetry, we conclude that
a = b.
With this we proved the associativity of the operation ().
3) We have x X=inf( x,x} = x.
Equality is achieved through reflexivity: X? X.
That. constructed algebra<S ; > will be a commutative idempotent semi-group, i.e. commutative link.
Theorem 2.
Let<S ; · > is a commutative idempotent semigroup, then a binary relation? on S, defined by equality
? = a·в = а,
is a partial order. At the same time, PLAGUE<S ; ? > is a semilattice.
Proof:
1) reflexivity?.
By condition<S ; · > satisfies three identities:
(1) X = X
(2) x y = y x
(3) (x y)· z = x(y· z)
Then x x = x = x - by virtue of (1). That's why X? X.
2) antisymmetry? .
Let X? at And y? X, then by definition,
(4) x y = x
hence, thanks to commutativity, we have x = y.
3) transitivity?.
Let X? at And y?z then, by definition,
(6) x y = x
(7) y z= y
We have x· z = (x· y)· z x· (y· z) xy X
So, x· z = x, that is X?z.
Thus, we have CHUM<S ; ? >. It remains to show that for any ( A,V)S exists inf( a,c}.
We take arbitrary A,V S and prove that the element c = a b is inf( a,c), i.e. With= inf( a,c}.
Indeed,
c a =(a·c)·A A·(a·c) (a·a)· V a·b = c,
That. With? A.
Likewise, с·в =(a·c)·V A·(in) a·b = c,
those. With? V.
So, With- common lower bound ( a,c}.
Let's prove its accuracy.
Let d- some common lower bound for A And V:
(8) d? a
(9)d? V
(10) d a = d
(11)d in =d
d· c = d· (a·c) (d·A)· V d·V d,
d· c = d, hence, d ? c.
Conclusion: c = inf( a,V}.
Theorems 1 and 2 proved allow us to look at semilattices from two points of view: as CUMs, and as in algebra (idempotent commutative semigroups).
2. Well-ordered sets
The theory of ordered sets was created by G. Cantor . Shatunovsky . Hausdorff (1914).
Well-ordered sets - An ordered set is called well-ordered if each of its subsets has a first element (that is, an element followed by all others). All finite ordered sets are completely ordered. The natural series, ordered in ascending order (as well as in some other ways), forms a completely ordered set. The importance of completely ordered sets is determined mainly by the fact that the principle of transfinite induction is valid for them.
Ordered sets that have the same ordinal type also have the same cardinality, so we can talk about the cardinality of a given ordinal type. On the other hand, finite ordered sets of the same cardinality have the same ordinal type, so that each finite cardinality corresponds to a certain finite ordinal type. The situation changes when moving to infinite sets. Two infinite ordered sets can have the same cardinality but different order types.
3. Partial groupoids and their properties
As is known, a binary algebraic operation on a set S is a mapping from a Cartesian square S?S. In this case, the action is said to be set to S. In this paragraph we will call it full effect.
Any mapping from a subset S?S V S called partial effect on S. In other words, partial action on S is some function from S?S > S.
It can be said that on S a partial action (partial multiplication) is specified if for any elements a,c S work a·c either undefined or unambiguously defined. Simply put, not all elements are multiplied here.
A bunch of S with a partial multiplication specified in it is called partial groupoid and is denoted by ( S ; · ) in contrast to a complete groupoid< S ; · >.
If for a complete groupoid we can talk about a Cayley table, then for a partial groupoid we can talk about some analogue of the Cayley table, namely a table where some cells are empty - this is the case when the product of elements is indefinite.
Example 1.
a
A· in = in, But V· A not defined, i.e. V· A= O. Symbol " O" do not belong S, i.e. is not an element of S.
Example 2.
Consider the plague ( S ; ? ).
S = {a,V,c, d), Where A? A, V? V, With? With, d ? d, With? A, With? V, d? A, d? V.
In an arbitrary plague ( S ; ? ) we agree to denote:
A V= inf( a,V}.
Then the plague indicated in the example with respect to this partial action is a partial groupoid ( S;), the Cayley table of which is the following
d
a
d
c
-
In this section we will look at three types of associativity: strong associativity, medium associativity, weak associativity.
Definition 1.
Partial groupoid ( S ; · ) is called weakly associative , If
(X,y,z S) (x· y)· z O x·( y· z) > (x· y)· z= x·( y· z) (*)
Definition 2.
Partial groupoid ( S ; · ) is called moderately associative , If
(X,y,z S) (x· y)· z O y· z > (x· y)· z= x·( y· z)
Definition 3.
Partial groupoid ( S ; · ) is called strongly associative , If
(X,y,z S) [(x· y)· z O x·( y· z) O> (x· y)· z= x·( y· z)] (*)
A strongly associative partial groupoid satisfies the properties of moderate and weak associativity. However, the opposite is by no means necessary.
Example 3.
Given A = {a, in, with). Let's set it to A partial operation of multiplication by “partial Cayley table”.
We obtain some partial groupoid. Let's check whether the groupoid is strongly associative.
Let ( x· y)· z O because X A, then either x = c x = b
1) let x = c, Then y = in y = c
a) let y = in, Then z = a
(With· V)· A O With·( V· A) defined
(With· V)· a = c·( V· A) equality is satisfied
b) let y = c, Then z= in z= c
and if z= in, Then
(With· With)· V O With·( With· V) defined
(With· With)· in = c·( With· V) equality is satisfied
b") if z= c, Then
(With· With)· With O With·( With· With) defined
(With· With)· c = c·( With· With) equality is satisfied
2) let x = b, Then y = a, A z= in z = c
and if y = a And z= in
(V· A)· V O= in·( A· V) undefined
(V· A)· V V·( A· V) equality is not satisfied
b) let y = a And z= c
(V· A)· With O= in·( A· With) undefined
(V· A)· With V·( A· With) equality is not satisfied
So, by definition, a partial groupoid is not strongly associative. But this does not mean that ( S ; · ) is not weakly associative.
Let's find out.
Let (x· y)· z O x·( y· z) O .
At X A, at A, namely, when
x = b x = c
y = in y = c
this partial groupoid is weakly associative.
Example 4.
Let A ={a, in, with), can be set to A the following Cayley table. We obtain some partial groupoid. Let's check whether this groupoid is moderately associative.
Let ( x· y)· z O because X V, Then x = a x = c
1) let x = a, Then y = a y = in
a) let y = a, Then z = a, z= in
and if z= a, Then
(A· A)· A O A· a defined
(A· A)· A A·( A· a) equality is not satisfied
b") if z= in, Then
(A· A)· V O A· V defined
(A· A)· V A·( A· V) equality is not satisfied
Hence, we see that the groupoid is not mean associative. Find out whether it is weakly associative.
Let ( x· y)· z O x·( y· z) O, because X V, Then x = a x = c
1) let x = a, Then y = a y = in
a) let y = a, Then z = a, z= in
and if z= a, Then
(A· A)· A O= a·( A· a) undefined
(A· A)· A A·( A· a)
b") if z= in, Then
(A· A)· V O A·( A· V) defined
(A· A)· in = a·( A· V) equality is satisfied
b) let y = in, Then z = a, z= in
and if z= a, Then
(A· V)· A O= a·( V· a) undefined
(A· V)· A A·( V· a)
b") if z= in, Then
(A· V)· V O A·( V· V) undefined
(A· V)· V A·( V· V) equality is not satisfied
2) let x = c, Then y = a,y = in
a) let y = a, Then z = a, z= in
and if z= a, Then
(With· A)· A O= c·( A· a) undefined
(With· A)· A With·( A· a) equality is not satisfied
b") if z= in, Then
(With· A)· V O With·( A· V) defined
(With· A)· in = c·( A· V) equality is satisfied
So, we see that a partial groupoid is weakly associative for x = a And z= in or when x = c If y = a And z= in.
Definition 4.
Partial groupoid ( S ; · ) is called commutative , If
(X,y S) x· y = y· X
Definition 5.
Partial groupoid ( S ; · ) is called catenary , If
(X,y,z S) (x· y O y· z) > [(x· y)· z O x·( y· z)]
Definition 6.
Partial groupoid ( S ; · ) is called idempotent , If
(X S) X = X
Let us give an example of a non-catenary partial groupoid.
Example 5.
d
a
d
c
-
We have With a = c O, A d = d O. However, ( With A) d = c d O. Therefore, the given CG is not catenary.
It is clear what we mean by the term “common upper bound” of elements A And V some plague.
Definition 7.
It's called a plague categorical , if any two of its elements that have an upper bound have an exact lower bound.
Example 6.
Example 7.
A partially ordered set defined by a Cayley table:
Example 8.
Partially ordered set
having the following Cayley table:
-
-
-
It is clear that every semilattice is a categorical plague (but not vice versa), because any two elements have an exact infimum. In other words, the class of all categorical plagues contains the class of all semilattices, but does not coincide with it. That. any proposition proven for categorical plagues entails as an obvious consequence a certain theorem regarding semilattices.
Let us give examples of semilattices.
Example 9.
Diagram:
called diamond
d
a
d
c
Example 10.
Diagram:
called Pentagon, and is defined by a semilattice having the following Cayley table:
Example 11.
The semilattice defined by the Cayley table:
has a diagram:
Theorem 1.
Let ( S ; ? ) - categorical plague, then ( S;) - catenary idempotent commutative weakly associative partial groupoid.
Proof:
For anyone A S Always
A A= inf( a, a} = a therefore partial groupoid S idempotent.
We have A V= inf( a,V) = inf( V,a} = V A, and therefore S commutative
Let's check weak associativity.
Let ( A V) With O A (V With) , denote
A V = d, V With = e, (A V) With= d With = f, A (V With) = A e= g
Let's prove that f = g.
By definition we have f ? d ? a f ? a,
f ? d? V f? V (1)
f ? c (2)
Because e= inf( in, with), then from (1), (2) it follows that f ? e. That. f - some common lower bound for A And e, A g is their exact infimum, so
f ? g (3)
Likewise,
g ? f (4)
Inequality (3), (4) and antisymmetry of the relation? provide f = g. Weak associativity has been proven.
Let's check the catenary S.
Let A V O V With, denote A b = x, V With = y, from here X? V, y? V, i.e.
V- common upper bound X And at. Because PLAGUE S categorically, then there exists inf( x,y), i.e. exists in S X at. Let's denote X y = z, we will show that
A (V With) = X With= z. We have z ? x, z ? y (because z = inf( x,y}), y ? z z ? x, z ? c,
z - bottom edge for X And With.
We will ensure accuracy.
Let t ? x , t ? c (t- any lower bound), because t ? x , That t ? a, t? V, by condition t? With, i.e. t- common lower bound for V And With. It follows by definition at, t ? y.
So, t ? x, t? at hence t ? z (a-priory z).
Catenary has been proven.
Theorem 2.
If ( S ; · ) is a catenary idempotent commutative weakly associative partial groupoid, then the relation
? = (a,c) S?S (2)
Is an order relation. At the same time, PLAGUE<S ; ? > - is catenary.
Proof:
Let's prove the reflexivity of the relationship? . Because partial groupoid S idempo-tenten, then a· a = a hence, by definition (2) A? A.
Let's check the antisymmetry.
If A? in, in? A, That а·в = а, в·а = в, the left sides are equal due to commutativity, which means the right sides are equal, therefore a = b.
It remains to prove transitivity.
Let A? V, V? With, Then a·b = a, v s = in, а·с =(a·c)· With. Due to catenary we have ( A· V)· With O , A·( V· With) O, hence due to weak associativity
(a·c)·c = a·(v s), and therefore, a·c = a·(v s) = a·b = a.
So, a·c = a, i.e. A? With.
That. we have a plague<S ; ? > .
Let z- common upper bound for X And at. Hence, X?z, y ? z, from here X·z = x, y· z = y, Then z· y = y. Due to catenary ( x· y)· z O x· y O.
Let's denote x y =s, let's prove that s exact bottom edge.
We have s· x = (x· y)· x = x· (x· y) = (x· x)· y = x· y = s (due to catenary and weak associativity), therefore, s ? x, i.e. s- common lower bound.
Two corollaries well known in the theory of semilattices follow from these theorems.
Corollary 1.
If<S ; · > is an idempotent commutative semigroup, then the relation? , defined by equality (2), is a partial order. Moreover, for any two elements in S there is an exact lower bound.
Corollary 2.
If<S ; · > is a partially ordered set in which there is an infimum of any two elements, then with respect to the operation
A V= inf( a,V} (3)
a bunch of S is an idempotent commutative semigroup.
CONCLUSION
In conclusion, it can be noted that the theory of ordered sets was created by G. Cantor . In 1883 he introduced the concept of a completely ordered set and an ordinal number, and in 1895 - the concept of an ordered set and an ordinal type. In 1906-07 S.O. Shatunovsky formulated the definitions of a directed set (in Shatunovsky - a located complex) and the limit over a directed set (by American mathematicians E . G. Moore and G. L. Smith considered these same concepts independently of Shatunovsky, but much later - in 1922). The general concept of a partially ordered set belongs to F. Hausdorff (1914).
Thus, the theory of partial algebraic actions, being a continuation of the theory of complete actions, taking advantage of its achievements, associated with it ideas and experience of applications outside of algebra, should still take shape as an independent direction in the vast field of modern algebra.
To date, hundreds of works have been published specifically devoted to the study of partial actions. As for the works in which certain partial actions occur during the course of the study, their number cannot be estimated. Partial actions are also discussed in some general algebraic works, but always very briefly.
Bibliography
A.K. Clifford, G. Preston. Algebraic theory of semigroups. 1972.
Greitzer. General theory of lattices. Moscow.-284 p.
Kozhevnikov O.B. Partially ordered sets of partial groupoids. Moscow, 1998. - 680s.
E.S. Lyapin. Semigroups. Moscow: Fizmat, 1960.- 354 p.
Lyapin E.S. Algebra and number theory. Moscow, 1980.-589 p.
When introducing operations with supersets, we did not take into account that the sets themselves can have their own internal structure, that is, we assumed that all elements of the set were equal. However, in mathematics such “pure” sets are of little interest, and much more often sets are studied, between the elements of which there are certain relationship . One of the most important relationships between the elements of a set is order relation .
Order relation is nothing more than, as a rule, establishing the order of “sequence” of the elements of the set.
Let A- some set, set A called ordered set , if for any two of its elements a, b one of the following is installed order relations :
or a ≤ b (A does not exceed b),
or b ≤ a (b does not exceed A),
having the following properties:
1) reflexivity:
no element is superior to itself;
2) antisymmetry:
If A does not exceed b, A b does not exceed A, then the elements A And b match up;
3) transitivity:
If A does not exceed b,a b does not exceed With, That A does not exceed With.
The empty set was agreed to be considered ordered. In the above definition of an ordered set, the elements of which can be objects of any nature, the sign ≤ reads “does not exceed.” This sign (as the sign “less than or equal”) acquires its usual reading and meaning in the case when the elements of the set A- numbers.
Two sets composed of the same elements, but with different order relations, are considered different ordered sets.
The same set can be ordered in different ways, thereby obtaining different ordered sets.
Example
Consider a set whose elements are various convex polygons: triangle, quadrilateral, pentagon, hexagon, etc. One way of forming an ordered set from a given unordered set might, for example, be to take a triangle as the first element of the ordered set, the second is a quadrangle, the third is a pentagon, etc., i.e., we arrange the set in increasing order of the number of internal angles of polygons. The set of polygons can be ordered in another way, for example, by listing the polygons in increasing order of area, when the polygon with the smallest area is selected as the first, the polygon with an area not exceeding the area of all others except the one already selected is selected as the second, etc. .
Ordered (finite or countable) sets are often written by arranging their elements in a given order in parentheses.
Example
The notations (1; 2; 3) and (2; 1; 3) represent different finite ordered sets that can be obtained from the same set (1; 2; 3) by ordering it in two different ways.
To write a countable ordered set, you need to indicate the first element of the ordered set and indicate the order (rule) of the arrangement of subsequent elements.