Как найти наибольший элемент множества

Упорядоченные множества

Множество вместе с заданным на нем отношением порядка называют упорядоченным множеством.

Отношение порядка будем, как правило, обозначать (или значками и т.п., похожими на ). При этом следует понимать, что даже на некотором множестве рассматриваться может любое отношение порядка, а не только естественный числовой порядок. Множество с заданным на нем отношением порядка будем записывать как пару . Записывая , мы будем говорить, что элемент не больше элемента .

Каждому отношению порядка на множестве можно сопоставить следующие отношения.

1. Отношение, которое будем обозначать , получается из исходного отношения порядка выбрасыванием всех элементов диагонали , т.е. для любых тогда и только тогда, когда и . Записывая , мы будем говорить, что элемент строго меньше элемента . Из определения следует, что отношение есть иррефлексивное, антисимметричное и транзитивное бинарное отношение на множестве , т.е. оно является отношением строгого порядка.

Двойственный порядок

2. Двойственный порядок. Это бинарное отношение на множестве , называемое также и отношением, двойственным к отношению порядка , определяется как бинарное отношение на множестве , обратное к отношению . Его обозначают . Тогда для любых условие равносильно тому, что . Можно без труда доказать, что отношение тоже является отношением порядка.

Записывая , мы будем говорить, что элемент не меньше элемента . Отношение строгого порядка, ассоциированное с , договоримся обозначать , говоря при этом, что элемент строго больше элемента , если и .

Отношение доминирования

3. Отношение доминирования. Для двух элементов и , по определению, тогда и только тогда, когда строго меньше и не существует такого элемента , что . Отношение называют отношением доминирования (или просто доминированием), ассоциированным с отношением порядка . Если имеет место , то говорят, что элемент доминирует над элементом .

Из определения следует, что отношение доминирования иррефлексивно, антисимметрично, но не транзитивно. Оно может быть и пусто. Например, легко видеть, что пустым будет отношение доминирования, если исходный порядок является плотным бинарным отношением на соответствующем множестве.

---

Пример 1.15. а. Рассмотрим множество действительных чисел с естественным числовым порядком. Пусть . Известно, что для любых и найдется такое , что , т.е. это отношение порядка на множестве действительных чисел является плотным. Поэтому отношение доминирования будет пустым.

По той же причине будет пустым отношение доминирования, ассоциированное с естественным числовым порядком на множестве рациональных чисел. Но на множестве целых чисел (опять-таки с естественным числовым порядком) отношение доминирования не пусто. Так, , но, конечно, неверно, что , поскольку между единицей и тройкой существует «промежуточный» элемент — двойка.

б. На множестве всех подмножеств трехэлементного множества , где в качестве отношения порядка взято отношение теоретико-множественного включения , подмножество доминирует над подмножествами и , но не доминирует над пустым множеством. В свою очередь, все множество доминирует над любым своим двухэлементным подмножеством, но не доминирует над одноэлементным и над пустым.

в. По отношению делимости на множестве натуральных чисел 15 доминирует над 3 и 5, но 20 не доминирует над 5, так как существует „промежуточный» элемент — 10, делитель 20, который делится на 5, но не равен ни 20, ни 5.

---

Упорядоченное подмножество

Рассмотрим упорядоченное множество и его произвольное непустое подмножество . Упорядоченное множество , где — ограничение отношения на подмножество , называют упорядоченным подмножеством упорядоченного множества .

Таким образом, можно переносить отношения порядка на непустые подмножества исходного упорядоченного множества. Как правило, вместо будем писать просто (если ясно, о каком подмножестве идет речь). Порядок на подмножестве называют также порядком, индуцированным исходным порядком на всем множестве . Часто прибегают к такому выражению: «рассмотрим подмножество упорядоченного множества с индуцированным порядком», понимая под этим порядок .

Элементы и упорядоченного множества называют сравнимыми по отношению порядка , если или . В противном случае элементы и называются несравнимыми.

Упорядоченное множество, все элементы которого попарно сравнимы, называют линейно упорядоченным, а соответствующее отношение — отношением линейного порядка (или просто линейным порядком). Бели индуцированный порядок на подмножестве упорядоченного множества является линейным, то это линейно упорядоченное подмножество называют цепью. Любое подмножество попарно не сравнимых элементов данного упорядоченного множества называют антицепью.

Замечание 1.5. Обратим внимание на то, что термину «упорядоченное множество» (в смысле приведенного определения) отвечает термин «частично упорядоченное множество», а то, что мы называем линейно упорядоченным множеством, называется просто упорядоченным множеством. Терминология этого выпуска более принята в алгебраической литературе и литературе по дискретной математике. Употребление термина «частично упорядоченное множество» мотивировано желанием подчеркнуть, что в общем случае в упорядоченном множестве существуют не сравнимые элементы.

Пример 1.16. а. Отношение естественного числового порядка на множестве действительных чисел является отношением линейного порядка, поскольку для любых двух чисел имеет место или неравенство , или неравенство .

б. Отношение делимости (см. пример 1.13.г) на множестве и отношение включения на (см. пример 1.13,д) не являются линейными порядками, за исключением случая, когда — одноэлементное множество.

---

Наибольший, наименьший и максимальный, минимальный элементы множества

Пусть — упорядоченное множество. Элемент называют наибольшим элементом множества , если для всех выполняется неравенство .

Элемент называют максимальным элементом множества , если для всякого имеет место одно из двух: или , или и не сравнимы.

Аналогично определяются наименьший и минимальный элементы упорядоченного множества, а именно: наименьший элемент упорядоченного множества — это такой его элемент , что для каждого , а минимальный элемент — это такой элемент , что для любого элементы и не сравнимы или .

Покажем, что наибольший (наименьший) элемент множества, если он существует, является единственным. Действительно, полагая, что и — наибольшие элементы по отношению порядка , получаем, что для всякого выполняется и . В частности, и , откуда ввиду антисимметричности любого отношения порядка следует, что . Аналогично доказывается единственность наименьшего элемента.

Замечание 1.6. Поскольку на одном и том же множестве могут быть определены разные отношения порядка (например, на множестве натуральных чисел — естественный числовой порядок и отношение делимости), то, когда это необходимо, мы будем говорить о наибольших, наименьших (соответственно максимальных и минимальных) элементах по данному отношению порядка, уточняя тем самым, о каком отношении порядка идет речь.

Следующие примеры показывают, что максимальных (минимальных) элементов может быть сколько угодно. Но заметим, что если у множества есть наибольший (соответственно наименьший) элемент, то он является единственным максимальным (соответственно минимальным) элементом данного множества.

Пример 1.17. Рассмотрим множество точек плоскости с некоторой фиксированной прямоугольной декартовой системой координат. Координаты каждой точки плоскости задаются упорядоченной парой действительных чисел. Отношение порядка на множестве точек плоскости определим следующим образом: , если и только если и . Рассмотрим множество точек треугольника (рис. 1.11, а). Точка с координатами является наименьшим элементом этого множества. Максимальными элементами являются все точки, лежащие на стороне . Наибольшего элемента нет.

---

Верхняя и нижняя грань множества

Пусть — упорядоченное множество и . Элемент называется верхней (соответственно нижней) гранью множества , если для всех элементов имеет место (соответственно ).

Наименьший элемент множества всех верхних граней (соответственно наибольший элемент множества всех нижних граней) множества называют точной верхней гранью (соответственно точной нижней гранью ) и обозначают .

Множество всех верхних (нижних) граней множества называют верхним (нижним) конусом и обозначают (соответственно ).

В отличие от наибольшего и наименьшего элементов множества элементы и не обязаны принадлежать множеству . Точная верхняя (нижняя) грань множества существует не всегда.

Пример 1.18. а. Рассмотрим множество точек прямоугольника (рис. 1.11, б) с заданным в примере 1.17 отношением порядка. Точка является точной нижней гранью, а точка — точной верхней гранью этого множества. Обе точки принадлежат множеству.

Если рассмотреть множество (рис. 1.11, в) с тем же отношением порядка, то увидим, что точная нижняя грань (точка ) и точная верхняя грань (точка ) множества существуют, но не принадлежат множеству.

б. На числовой прямой с «выколотой» точкой для полуинтервала множество верхних граней есть , но точной верхней грани нет.

---

Вполне упорядоченные множества

Упорядоченное множество называют вполне упорядоченным, если его любое непустое подмножество имеет наименьший элемент.

Множество натуральных чисел с отношением естественного числового порядка вполне упорядоченное. Множество целых чисел не вполне упорядоченное, поскольку оно не имеет наименьшего элемента. Аналогично множества рациональных и действительных чисел не являются вполне упорядоченными.

Можно показать, что справедлив принцип двойственности для упорядоченных множеств. Пусть — произвольное упорядоченное множество. Тогда любое утверждение, доказанное для порядка , останется справедливым для двойственного порядка , если в нем:

1) порядок заменить на порядок и наоборот;
2) наименьший (минимальный) элемент заменить наибольшим (максимальным) элементом и наоборот;
3) заменить на и наоборот.

Например, если для некоторого и для мы доказали, что при заданном отношении порядка, то для двойственного порядка .

Говорят также и о взаимно двойственных определениях: если в любом определении, связанном с упорядоченным множеством, произвести взаимные замены согласно принципу двойственности, то получится новое определение, называемое двойственным к исходному. Так, определение наибольшего (максимального) элемента множества двойственно к определению наименьшего (минимального) элемента, и наоборот. Часто употребляют оборот речи: «двойственным образом…» (или «двойственно…»), понимая под этим переход к утверждению или определению, которое двойственно к исходному.

---

Способы наглядного представления упорядоченных множеств

Рассмотрим теперь некоторые способы наглядного представления упорядоченных множеств.

Конечное упорядоченное множество можно графически изобразить в виде так называемой диаграммы Хассе. На этой Диаграмме элементы множества изображаются кружочками. При этом если элемент доминирует над элементом , то кружочек, изображающий элемент , располагается выше кружочка, изображающего элемент , и соединяется с ним прямой линией. Иногда для большей наглядности из в ведут стрелку. На рис. 1.12 изображены диаграммы Хассе для упорядоченных множеств делителей чисел 2, 6, 30 и 36 по рассмотренному выше отношению делимости (см. пример 1.13,г).

На рис. 1.13 приведена диаграмма Хассе для упорядоченного множества всех подмножеств трехэлементного множества по отношению включения (см. пример 1.13.д).

Последовательность элементов упорядоченного множества называют неубывающей, если для каждого справедливо неравенство .

Элемент а упорядоченного множества называют точной верхней гранью последовательности если он есть точная верхняя грань множества всех членов последовательности. Другими словами, точная верхняя грань последовательности есть точная верхняя грань области ее значений как функции натурального аргумента.

---

Точная нижняя грань последовательности

Двойственно определяется точная нижняя грань последовательности.

Упорядоченное множество называют индуктивным, если:

1) оно содержит наименьший элемент;
2) всякая неубывающая последовательность элементов этого множества имеет точную верхнюю грань.

Например, множество всех подмножеств некоторого множества по отношению включения будет индуктивным. Наименьший элемент — пустое множество, а точной верхней гранью произвольной неубывающей последовательности множеств будет объединение всех членов этой последовательности (наименьшее по включению множество, содержащее в качестве подмножества любой член последовательности).

Определение 1.5. Пусть и — индуктивные упорядоченные множества. Отображение одного индуктивного упорядоченного множества в другое называют непрерывным, если для любой неубывающей последовательности элементов множества образ ее точной верхней грани равен точной верхней грани последовательности образов , т.е. справедливо равенство

Определение 1.6. Отображение упорядоченных множеств и называют монотонным, если для любых из следует .

Теорема 1.6. Всякое непрерывное отображение одного индуктивного упорядоченного множества в другое монотонно.

Пусть — непрерывное отображение индуктивного упорядоченного множества в индуктивное упорядоченное множество . Пусть и . Образуем последовательность , где , а . Эта последовательность неубывающая. Для нее . В силу непрерывности отображения

откуда следует, что .

---

Заметим, что функция , непрерывная в смысле определений математического анализа, не обязана быть монотонным отображением упорядоченных множеств с естественным числовым порядком, т.е. приведенное выше определение 1.5 непрерывности не вполне аналогично определению непрерывности в анализе . Например, рассмотрим непрерывное в смысле определений математического анализа отображение числовой прямой с естественным числовым порядком на себя. Это отображение не является монотонным в смысле данного выше определения 1.6, поскольку, например, , однако неравенство не выполняется.

В общем случае монотонное в смысле определения 1.6 отображение не является непрерывным в смысле определения 1.5. Приведем пример, показывающий, что утверждение, обратное теореме 1.6, неверно.

Пример 1.19. Рассмотрим множество всех точек отрезка числовой прямой с порядком, индуцированным естественным числовым порядком. Это множество индуктивно: его наименьший элемент — 0, а любая неубывающая последовательность элементов ограничена сверху и по признаку Вейерштрасса имеет предел, который и будет ее точной верхней гранью. Любая кусочно-непрерывная (но не непрерывная!) и монотонная в смысле обычных определений из курса математического анализа функция, отображающая этот отрезок на любой отрезок с порядком, индуцированным естественным числовым порядком, дает пример монотонного в смысле определения 1.6, но не непрерывного в смысле определения 1.5 отображения между индуктивными частично упорядоченными множествами. Например, пусть функция имеет вид

Это отображение монотонно. Для последовательности , точная верхняя грань равна . Точная верхняя грань последовательности равна , a . Следовательно, отображение не является непрерывным в смысле определения 1.5.

---

Не следует путать отображение, монотонное в смысле определения 1.6, с монотонными функциями из курса математического анализа. Функция будет монотонной в смысле определения 1.6 тогда и только тогда, когда она является неубывающей.

Для приложений особенно важны непрерывные отображения индуктивного упорядоченного множества в себя.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

From Wikipedia, the free encyclopedia

In mathematics, especially in order theory, the greatest element of a subset of a partially ordered set (poset) is an element of that is greater than every other element of . The term least element is defined dually, that is, it is an element of that is smaller than every other element of

Definitions[edit]

Let be a preordered set and let
An element is said to be a greatest element of if and if it also satisfies:

for all

By using instead of in the above definition, the definition of a least element of is obtained. Explicitly, an element is said to be a least element of if and if it also satisfies:

for all

If is even a partially ordered set then can have at most one greatest element and it can have at most one least element. Whenever a greatest element of exists and is unique then this element is called the greatest element of . The terminology the least element of is defined similarly.

If has a greatest element (resp. a least element) then this element is also called a top (resp. a bottom) of

Relationship to upper/lower bounds[edit]

Greatest elements are closely related to upper bounds.

Let be a preordered set and let
An upper bound of in is an element such that and for all Importantly, an upper bound of in is not required to be an element of

If then is a greatest element of if and only if is an upper bound of in and In particular, any greatest element of is also an upper bound of (in ) but an upper bound of in is a greatest element of if and only if it belongs to
In the particular case where the definition of « is an upper bound of in » becomes: is an element such that and for all which is completely identical to the definition of a greatest element given before.
Thus is a greatest element of if and only if is an upper bound of in .

If is an upper bound of in that is not an upper bound of in (which can happen if and only if ) then can not be a greatest element of (however, it may be possible that some other element is a greatest element of ).
In particular, it is possible for to simultaneously not have a greatest element and for there to exist some upper bound of in .

Even if a set has some upper bounds, it need not have a greatest element, as shown by the example of the negative real numbers.
This example also demonstrates that the existence of a least upper bound (the number 0 in this case) does not imply the existence of a greatest element either.

Contrast to maximal elements and local/absolute maximums[edit]

A greatest element of a subset of a preordered set should not be confused with a maximal element of the set, which are elements that are not strictly smaller than any other element in the set.

Let be a preordered set and let
An element is said to be a maximal element of if the following condition is satisfied:

whenever satisfies then necessarily

If is a partially ordered set then is a maximal element of if and only if there does not exist any such that and
A maximal element of is defined to mean a maximal element of the subset

A set can have several maximal elements without having a greatest element.
Like upper bounds and maximal elements, greatest elements may fail to exist.

In a totally ordered set the maximal element and the greatest element coincide; and it is also called maximum; in the case of function values it is also called the absolute maximum, to avoid confusion with a local maximum.^[1]
The dual terms are minimum and absolute minimum.
Together they are called the absolute extrema.
Similar conclusions hold for least elements.

Role of (in)comparability in distinguishing greatest vs. maximal elements

One of the most important differences between a greatest element and a maximal element of a preordered set has to do with what elements they are comparable to.
Two elements are said to be comparable if or ; they are called incomparable if they are not comparable.
Because preorders are reflexive (which means that is true for all elements ), every element is always comparable to itself.
Consequently, the only pairs of elements that could possibly be incomparable are distinct pairs.
In general, however, preordered sets (and even directed partially ordered sets) may have elements that are incomparable.

By definition, an element is a greatest element of if for every ; so by its very definition, a greatest element of must, in particular, be comparable to every element in
This is not required of maximal elements.
Maximal elements of are not required to be comparable to every element in
This is because unlike the definition of «greatest element», the definition of «maximal element» includes an important if statement.
The defining condition for to be a maximal element of can be reworded as:

For all IF (so elements that are incomparable to are ignored) then

Example where all elements are maximal but none are greatest

Suppose that is a set containing at least two (distinct) elements and define a partial order on by declaring that if and only if
If belong to then neither nor holds, which shows that all pairs of distinct (i.e. non-equal) elements in are incomparable.
Consequently, can not possibly have a greatest element (because a greatest element of would, in particular, have to be comparable to every element of but has no such element).
However, every element is a maximal element of because there is exactly one element in that is both comparable to and that element being itself (which of course, is ).^{[note 1]}

In contrast, if a preordered set does happen to have a greatest element then will necessarily be a maximal element of and moreover, as a consequence of the greatest element being comparable to every element of if is also partially ordered then it is possible to conclude that is the only maximal element of
However, the uniqueness conclusion is no longer guaranteed if the preordered set is not also partially ordered.
For example, suppose that is a non-empty set and define a preorder on by declaring that always holds for all The directed preordered set is partially ordered if and only if has exactly one element. All pairs of elements from are comparable and every element of is a greatest element (and thus also a maximal element) of So in particular, if has at least two elements then has multiple distinct greatest elements.

Properties[edit]

Throughout, let be a partially ordered set and let

• A set can have at most one greatest element.^{[note 2]} Thus if a set has a greatest element then it is necessarily unique.
• If it exists, then the greatest element of is an upper bound of that is also contained in
• If is the greatest element of then is also a maximal element of ^{[note 3]} and moreover, any other maximal element of will necessarily be equal to ^{[note 4]}
  • Thus if a set has several maximal elements then it cannot have a greatest element.
• If satisfies the ascending chain condition, a subset of has a greatest element if, and only if, it has one maximal element.^{[note 5]}
• When the restriction of to is a total order ( in the topmost picture is an example), then the notions of maximal element and greatest element coincide.^{[note 6]}
  • However, this is not a necessary condition for whenever has a greatest element, the notions coincide, too, as stated above.
• If the notions of maximal element and greatest element coincide on every two-element subset of then is a total order on ^{[note 7]}

Sufficient conditions[edit]

• A finite chain always has a greatest and a least element.

Top and bottom[edit]

The least and greatest element of the whole partially ordered set play a special role and are also called bottom (⊥) and top (⊤), or zero (0) and unit (1), respectively.
If both exist, the poset is called a bounded poset.
The notation of 0 and 1 is used preferably when the poset is a complemented lattice, and when no confusion is likely, i.e. when one is not talking about partial orders of numbers that already contain elements 0 and 1 different from bottom and top.
The existence of least and greatest elements is a special completeness property of a partial order.

Further introductory information is found in the article on order theory.

Examples[edit]

See also[edit]

• Essential supremum and essential infimum
• Initial and terminal objects
• Maximal and minimal elements
• Limit superior and limit inferior (infimum limit)
• Upper and lower bounds

Notes[edit]

References[edit]

• Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. ISBN 978-0-521-78451-1.

Наименьший
элемент, минимальный элемент

Пусть
на множестве А дан частичный порядок.
Элемент у ∈
А называется
наименьшим
элементом
множества А, если для любого элемента
х
∈
А верно у ≤ х.

Элемент
у ∈
А называется минимальным
относительно
заданного порядка А, если не существует
таких элементов х ∈
А, что х < у.

Вопрос № 21. Наибольший и максимальный элементы множества относительно порядка

Наибольший
элемент, максимальный элемент

Пусть
на множестве А дан частичный порядок.
Элемент у ∈
А называется
наибольшим
элементом
множества А, если для любого элемента
х
∈
А верно у ≥ х.

Элемент
у ∈
А называется максимальным
относительно
заданного порядка А, если не существует
таких элементов х ∈
А, что х > у.

В
диаграмме Хассе вершина а ∈
V_а
соответствует
максимальному элементу, если из нее не
выходит ни одна дуга.

1. Наибольший
   элемент является и максимальным
   элементом.

2. Наибольший
   элемент, если он есть, всегда единственный.

3. Максимальных
   элементов у множества может быть
   несколько.

Вопрос № 22. Вполне упорядоченное множество

Определение:

Частично
упорядоченное множество X
называется вполне упорядоченным, если
любое его непустое подмножество имеет
минимальный элемент.

Теорема:

Всякое
вполне упорядоченное множество является
линейно упорядоченным.

Доказательство:

Пусть
А – вполне упорядоченное множество:

Тогда:

Примеры:

1.
Пустое множество является вполне
упорядоченным.

2. Простейший пример
бесконечного вполне упорядоченного
множества — множество натуральных
чисел с естественным упорядочением.

Вопрос
№23.
Верхняя граница множества Х, syp(X)=?

Пусть
А — частично упорядоченное множество.
Пусть х

А. х

А верхняя граница Х, если

Верхние
и нижние границы не обязаны существовать
для любого множества и если существуют,
то не всегда единственны. Если существует
наименьшая верхняя граница, то она
называется супремумом
и обозначается syp(X).

Вопрос
№24. Нижняя граница множества Х, inf
X=?

Элемент
x∈A
называется нижней границей
множества X,
если для любого y∈X
(x≤y)

Элемент
x∈A
называется наибольшей нижней гранью,
если это наибольшая из нижних границ
множества X
(inf)

Вопрос №25. Определение графа ориентированного, неориентированного, смешанного, пустого

Граф,
неориентированный граф, НГ, ориентированный
граф, оргаф, ОГ, смешанный граф, пустой
граф.

Вопрос №26. Степень вершины, псевдограф, мультиграф

Степенью
вершины
называется число ребер, которым
принадлежит эта вершина. Если это
количество четно, то вершина называется
четной, в противном случае вершина
называется нечетной.

Мультиграф

Определение.
Неориентированный
граф с кратными ребрами без петель
называется мультиграфом. Несколько
ребер, соединяющих одну и ту же пару
вершин, называются кратными.

Для
ориентированного графа имеем два
случая: дуги, имеющие одно направление,
называются кратными, разное направление
– параллельными.

Ориентированный
мультиграф — граф,
соединяющий кратные дуги без петель.

Псевдограф

Определение.
Граф,
содержащий петли и кратные ребра,
называется псевдографом.

Петлей
называется ребро, соединяющее вершину
саму с собой.

При
подсчете степени вершины петля
учитывается дважды.

Для
некоторых авторов, термины псевдограф
и мультиграф являются синонимами. Для
других, псевдограф является мультиграфом,
которому разрешено иметь петли.

Синие
линии – петли

Красные
линии – кратные ребра

Вопрос
№27.
Изоморфные
графы. Примеры. Гомеоморфизм графов.

Графы
G1
= (V1,
E1)
и G2
= (V2,
E2)
называются изоморфными, если существует
биекция φ
между
множеством вершин V1
и V2,
сохраняющая смежность.

{L1,
L2}
∈
E1
=> {φ(L1),
φ(L2)}
∈
E2.

Для
орграфа:

(L1,
L2)
∈
E1
=> (φ(L1),
φ(L2))
∈
E2.

Для
доказательства того, что графы изоморфны,
достаточно указать отображения,
удовлетворяющие условию, описанному
в определении.

Чтобы
доказать, что графы неизоморфны,
достаточно найти какое-нибудь свойство,
которым обладает один граф и не обладает
другой, и которое у изоморфных графов
должно быть общим.

Определения

Упорядоченная пара

Определение:

Упорядоченная пара — двухэлементное семейство, где множеством индексов является .

Декартово произведение

Определение:

Декартовым или прямым произведением множеств и называется множество всех упорядоченных пар, таких, что первый элемент пары принадлежит , а второй — :

Операции над множествами

Определение:

Пусть — семейство множеств. Объединением семейства называется множество всех элементов, которые принадлежат хотя бы одному из множеств :

Определение:

Пусть — семейство множеств. Пересечением семейства называется множество всех элементов, которые принадлежат каждому из множеств :

Определение:

Разностью множеств и называется множество всех элементов, которые принадлежат , но не принадлежат :

Пополненное множество вещественных чисел, операции и порядок в нем

Определение:

Множество называется расширенной числовой прямой.

Для :

Для :

Подмножество в R, ограниченное сверху

Определение:

Множество называется ограниченным сверху, если существует такое число , что для всех . Число называется верхней границей множества.

Определение:

Множество называется ограниченным снизу, если существует такое число , что для всех . Число называется нижней границей множества.

Определение:

Множество называется ограниченным, если оно ограничено и сверху, и снизу.

Максимальный элемент множества

Определение:

Число называется максимумом или наибольшим элементом множества , если и для всех . Обозначается .

Определение:

Число называется минимумом или наименьшим элементом множества , если и для всех . Обозначается .

Последовательность

Определение:

Отображение множества натуральных чисел в множество называется последовательностью в Обозначается как .

Образ и прообраз множества при отображении

Определение:

Пусть . Множество называется образом множества при отображении .

Определение:

Пусть . Множество называется прообразом множества при отображении .

Инъекция, сюръекция, биекция

Определение:

Пусть . Если , то отображение называется сюръективным, или сюръекцией, или отображением «на».

Иными словами: имеет хотя бы одно решение в .

Определение:

Пусть . Если для любых различных элементов их образы различны, то отображение называется инъективным, или инъекцией, или обратимым отображением.

Иными словами: имеет не более одного решения в .

Определение:

Пусть . Если отображение одновременно инъективно и суръективно, то оно называется биективным, или биекцией, или взаимно-однозначным отображением (соответствием).

Иными словами: имеет ровно одно решение в .

Целая часть числа

Пусть . Наибольшее целое число, не превосходящее , называется целой частью и обозначается .

Векторнозначаная функция

Определение:

Векторозначная функция (вектор-функция) — отображение из в или .

Координатная функция

Определение:

Отображение из в или , которое каждому элементу сопоставляет число , называют k-ой координатной функцией отображения и пишут .

График отображения

Определение:

Пусть . Графиком отображения называется множество

Композиция отображений

Определение:

Пусть , , . Отображение , действующее по правилу называется композицией или суперпозицией отображений и , а также сложным отображением и обозначается . При этом называется внешним, а — внутренним отображением.

Сужение и продолжение отображений

Определение:

Пусть , . Отображение, которое каждому сопоставляет , называется сужением отображения на множество и обозначается . Если отображение есть сужение отображения , то называется продолжением, распространением или расширением .

Предел последовательности (эпсилон-дельта определение)

Определение:

Пусть — последовательность вещественных чисел. Число называют пределом последовательности и пишут , если для любого положительного числа существует такой положительный номер , что для всех номеров , больших , выполняется равенство :

Определение:

Пусть — метрическое пространство, — последовательность в . Точку называют пределом последовательности и пишут , если для любого положительного числа существует такой номер , что для всех номеров , больших , выполняется равенство :

Предел последовательности (определение на языке окрестностей)

Определение:

Интервал называется —окрестностью точки и обозначается или , если значение несущественно.

Определение:

Число называется пределом последовательности , если для любой окрестности точки все члены последовательности, начиная с некоторого номера, принадлежат этой окрестности.

Метрика, метрическое пространство, подпространство

Определение:

Функция называется метрикой или расстоянием в множестве , если она удовлетворяет следующим условиям:

Определение:

Пара — множество с метрикой в нём — называется метрическим пространством.

Определение:

Пусть , — метрика в . Метрическое пространство называется подпространством метрического пространства .

Шар, замкнутый шар, окрестности в R с чертой

Определение:

Пусть — метрическое пространство, , . Множество называется открытым шаром радиуса с центром в точке , или окрестностью (-окрестностью) точки и обозначается ещё или , если значение несущественно. Множество называется замкнутым шаром, а множество — сферой радиуса с центром в точке .

Векторное пространство

Определение:

Пусть — поле, — множество, и над элементами и определены две операции: сложение и умножение , удовлетворяющие следующим условиям: Тогда называется векторным пространством или линейным множеством над полем

Норма

Определение:

Пусть — векторное пространство над или . Нормой в называется функция , удовлетворяющая следующим условиям: Положительная определённость: Положительная однородность: Неравенство треугольника (полуаддитивность): . Обозначается как . Пара называется нормированным пространством. Если функция удовлетворяет аксиомам 2 и 3, то называется полунормой.

Скалярное произведение

Определение:

Пусть — векторное пространство над или . Функция (или называется скалярным произведением в (обозначение: , если она удовлетворяет следующим свойствам: Линейность по первому аргументу: для всех и всех (или ) Эрмитовская симметричность: (в вещественном случае черту можно опустить) Положительная определённость:

Свойства скалярного произведения:

Последовательность, сходящаяся к бесконечности

Определение:

Последовательность, стремящаяся к бесконечности, называется бесконечно большой.

Верхняя, нижняя границы; супремум, инфимум

Определение:

Пусть , ограничено сверху. Наименьшая из верхних границ множества называется точной верхней границей, или верхней гранью, или супремумом множества и обозначается .

Определение:

Пусть , ограничено снизу. Наибольшая из нижних границ множества называется точной нижней границей, или нижней гранью, или инфимумом множества и обозначается .

Функция ограниченная сверху, снизу

Определение:

Функция называется ограниченной (сверху, снизу) на множестве , если множество ограничено (сверху, снизу).

Строго и не строго монотонная функция

Определение:

Пусть . Функция называется: возрастающей на множестве , если для любых из таких, что , будет ; строго возрастающей на множестве , если для любых из таких, что , будет ; убывающей на множестве , если для любых из таких, что , будет строго убывающей на множестве , если для любых из таких, что , будет .

Внутренняя точка множества, открытое множество, внутренность

Определение:

Точка называется внутренней точкой множества , если существует окрестность точки , содержащаяся в .

Определение:

Множество называется открытым, если все его точки внутренние.

Определение:

Множество всех внутренних точек множества называется внутренностью и обозначается или .

Предельная точка множества

Определение:

Точка называется предельной точкой или точкой сгущения множества , если в любой окрестности точки найдётся точка множества , отличная от .

Замкнутое множество, замыкание, граница

Определение:

Если точка принадлежит множеству , но не является его предельной точкой, то называется изолированной точкой множества .

Определение:

Множество называется замкнутым, если оно содержит все свои предельные точки.

Определение:

Точка называется точкой прикосновения множества , если в любой окрестности точки найдётся точка множества .

Определение:

Множество всех точек прикосновения множества называется замыканием и обозначается или .

Определение:

Точка называется граничной точкой множества , если в любой окрестности найдётся как точка, принадлежащая , так и точка, не принадлежащая . Множество всех граничных точек множества называется границей и обозначается .

Верхний и нижний пределы

Определение:

Пусть последовательность ограничена сверху. Величина называется верхним пределом последовательности .

Определение:

Пусть последовательность ограничена снизу. Величина называется нижним пределом последовательности .

Частичный предел

Определение:

Точка называется частичным пределом последовательности , если существует подпоследовательность , стремящаяся к .

Определения предела отображения (3 шт)

Определение:

Пусть , — метрические пространства, , — предельная точка , . Точку называют пределом отображения в точке и пишут , если выполняется одно из следующих утверждений: Определение на -языке, или по Коши. Для любого положительного числа существует такое положительное число , что для всех точек множества , отличных от и удовлетворяющих неравенству , выполняется неравенство : . Определение на языке окрестностей. Для любой окрестности точки существует такая окрестность точки , что образ пересечения проколотой окрестности с множеством при отображении содержится в окрестности : . Определение на языке последовательностей, или по Гейне. Для любой последовательности точек множества , отличных от , стремящейся к , последовательность стремится к : .

Предел по множеству

Определение:

Пусть , — предельная точка . Предел называется пределом отображения в точке по множеству .

Односторонние пределы

Определение:

Пусть . Если — предельная точка множества , то предел отображения в точке по множеству называется левосторонним пределом отображения в точке и обозначается или . Если — предельная точка множества , то предел отображения в точке по множеству называется правосторонним пределом отображения в точке и обозначается или .

Компактное множество

Определение:

Семейство множеств называется покрытием множества , если .

Определение:

Пусть — метрическое пространство, . Покрытие множества называется компактным, если из любого открытого покрытия можно извлечь конечное подпокрытие

Фундаментальная последовательность

Определение:

Пусть — последовательность в метрическом пространстве . Говорят, что последовательность сходится в себе, если для любого положительного числа существует такой номер , что для всех номеров и , больших , выполняется неравенство : Сходящуюся в себе последовательность также называют последовательностью Коши или фундаментальной последовательностью.

Полное метрическое пространство

Определение:

Пространство полно в любая сходящаяся в себе последовательность сходится.

Непрерывное отображение

Определение:

Пусть и — метрические пространства, . Отображение называется непрерывным в точке , если выполняется одно из следующих утверждений: Предел отображения в точке существует и равен . Это определение применимо, если — предельная точка . По Коши: для любого положительного числа существует такое положительное число , что для всех точек множества , удовлетворяющих неравенству , выполняется неравенство : . На языке окрестностей: для любой окрестности точки существует такая окрестность точки , что образ пересечения окрестности с множеством содержится в окрестности : . По Гейне: для любой последовательности точек множества , стремящейся к , последовательность стремится к : . Бесконечно малому приращению аргумента соответствует бесконечно малое приращение отображения: .

Непрерывность слева

Определение:

Пусть — метрическое пространство, . Если сужение отображения на множество ( непрерывно в точке , то говорят, что отображение непрерывно слева (справа) в точке .

Функция равномерно непрерывная на множестве

Определение:

Функция называется равномерно непрерывной на множестве , если для любого положительного числа существует такое положительное число , что для всех точек множества , удовлетворяющих неравенству , выполняется неравенство : .

Степенная функция

Показательная функция

Определение:

Пусть . Положим . При функция называется показательной функцией с основанием .

Логарифм

Определение:

Пусть . Функция, обратная к показательной с основанием , называется логарифмом по основанию .

О большое и o маленькое, эквивалентные функции или асимптотически равные функции

Определение:

Пусть — метрическое пространство, , — предельная точка . Если существует функция и окрестность точки , такие, что для всех и ограничена на , то говорят, что функция ограничена по сравнению с при , и пишут ; , то говорят, что функция бесконечно малая по сравнению с при , и пишут ; , то говорят, что функция эквивалентны или асимптотически равны при , и пишут .

Асимптотическое разложение

Наклонная асимптота графика

Определение:

Пусть . Прямая называется наклонной асимптотой функции при , если .

Функция, дифференцируемая в точке

Определение:

Пусть . Если существует такое число , что , то функция называется дифференцируемой в точке . При этом число называется производной функции в точке .

Определение:

Пусть . Если существует предел , равный числу , то функция называется дифференцируемой в точке . При этом число называется производной функции в точке .

Производная

Определение:

Пусть , — множество дифференцируемости (множество всех точек , где функция дифференцируема). Функция , которая каждому сопоставляет число , называется производной функцией функции .

Левостороняя и правосторонняя производные

Правосторонняя:

Левосторонняя:

Производная n-го порядка

Многочлен Тейлора n-го порядка

Теоремы

Аксиомы вещественных чисел

I. Аксиомы поля

В множестве определены две операции, называемые сложением и умножением, действующие из в и удовлетворяющие следующим свойствам:

1. Сочетательный закон (ассоциативность) сложения:
2. Переместительный закон (коммутативность) сложения:
3. Существует вещественное число нуль (, нейтральный элемент по сложению) такое, что для всех
4. Для любого числа существует такое число , что (это число называется противоположным числу и обозначается )
5. Сочетательный закон (ассоциативность) умножения:
6. Переместительный закон (коммутативность) умножения:
7. Существует вещественное число единица (, нейтральный элемент по умножению), отличное от нуля, такое, что для всех
8. Для любого числа существует такое число , что (это число называется обратным числу и обозначается или
9. Распределительный закон (дистрибутивность):

II. Аксиомы порядка

Между элементами определено отношение со следующими свойствами:

1. Для любых верно или
2. Транзитивность: если и , то
3. Если и , то
4. Если , то для любого
5. Если и , то

III. Аксиома Архимеда

Утверждение:

Каковы бы ни были положительные числа , существует натуральное число такое, что

IV. Аксиома Кантора о вложенных отрезках

Утверждение:

Пусть — последовательность вложенных отрезков, то есть для всех . Тогда существует точка, принадлежащая одновременно отрезкам , то есть

Законы де Моргана

Теорема (Де Моргана, законы):

Пусть — семейство множеств, — множество. Тогда

Принцип математической индукции. Неравенство Бернулли

Утверждение:

Пусть — последовательность утверждений. Если верно и для любого из следует , то верно для всех .

Теорема (Бенулли, неравенство):

light: hard:

Аксиома Архимеда. Плотность множества рациональных чисел в R

Теорема (плотность множества рациональных чисел):

Во всяком интервале есть рациональное число.

Аксиома Кантора. Десятичная запись числа

Счетные множества. Счетность множества рациональных чисел

Определение:

Множества и называют эквивалентными или равномощными и пишут ~, если существует биекция .

Определение:

Множество называется счётным, если оно эквивалентно множеству натуральных чисел.

Теорема:

Всякое бесконечное множество содержит счётное подмножество.

Теорема:

Всякое бесконечное подмножество счётного множества счётно.

Определение:

Пустое, конечное или счётное множество называется не более чем счётным.

Теорема:

Не более чем счётное объединение не более чем счётных множеств не более чем счётно.

Теорема (счётность множества рациональных чисел):

Множество рациональных чисел счётно.

Несчетность отрезка

Теорема (несчётность отрезка):

Отрезок несчётен.

Определение:

Если множество эквивалентно отрезку , то говорят, что оно имеет мощность континуума.

Несчетность множества бинарных последовательностей

Несчетность R^2

Единственность предела и ограниченность сходящейся последовательности

Теорема (единственность предела):

Последовательность в метрическом пространстве не может иметь более одного предела: если , а , то .

Определение:

Подмножество метрического пространства называется ограниченным, если оно содержится в некотором шаре: .

Теорема (ограниченность сходящейся последовательности):

Сходящаяся последовательность ограничена.

Теорема о сжатой последовательности

Теорема (о сжатой последовательности):

Пусть , и — вещественные последовательности, при всех , , . Тогда предел существует и равен .

Бесконечно малая последовательность

Определение:

Последовательность вещественных или комплексных чисел называется бесконечно малой, если она стремится к нулю.

Лемма:

Произведение бесконечно малой последовательности на ограниченную есть бесконечно малая: если — бесконечно малая, а — ограниченная, то — бесконечно малая.

Теорема об арифметических свойствах предела

Теорема (арифметические действия над сходящимися последовательностями в нормированном пространстве):

Пусть — нормированное пространство, , — последовательности в , — числовая последовательность, (или ), . Тогда

Теорема (арифметические действия над сходящимися числовыми последовательностями):

Пусть , — числовые последовательности, (или ), . Тогда Если, кроме того, при всех и , то

Неравенство Коши-Буняковского в линейном пространстве, норма, порожденная скалярным произведением

Теорема (Коши-Буняковского-Шварца, неравенство):

Теорема:

Функция — норма в .

Теорема (Коши-Буняковского, неравенство):

Леммы о непрерывности скалярного произведения и покоординатной сходимости в R^n

Определение:

Говорят, что последовательность точек в сходится к пределу поокординатно, если для всех .

Лемма:

В покоординатная сходимость и сходимость по евклидовой норме равносильны.

Теорема об арифметических свойствах предела последовательности (в R с чертой). Неопределенности

Теорема (арифметические действия с бесконечно большими):

Пусть , — числовые последовательности. Если , ограничена снизу, то . Если , ограничена сверху, то . Если , ограничена, то . Если , для всех (или ), то . Если , для всех (или ), то . Если , для всех (или ), то . Если при всех , то . Если , то . Если при всех , то .

Неопределённости:

• ,
• ,

Теорема о стягивающихся отрезках

Определение:

Говорят, что — последовательность стягивающихся отрезков, если при всех и .

Теорема (о стягивающихся отрезках):

Пусть — последовательность стягивающихся отрезков. Тогда пересечение всех отрезков состоит из одной точки, то есть , при этом и .

Теорема о существовании супремума

Теорема (о существовании супремума):

Всякое непустое ограниченное сверху (снизу) подмножество имеет верхнюю (нижнюю) грань.

Лемма о свойствах супремума

Утверждение:

Если , то , а . Если , , то

Теорема о пределе монотонной последовательности

Теорема (о пределе монотонной последовательности):

Всякая возрастающая ограниченная сверху последовательность сходится. Всякая убывающая ограниченная снизу последовательность сходится. Всякая монотонная ограниченная последовательность сходится.

Определение числа e, соответствующий замечательный предел

Определение:

Предел последовательности называют числом Непера или основанием натуральных логарифмов и обозначают буквой .

Теорема о свойствах открытых множеств, внутренность множества

[искать в районе 50-ой страницы]

Теорема о связи открытых и замкнутых множеств, свойства замкнутых множеств

Описание замкнутых и открытых множеств в подпространстве

Свойства верхнего и нижнего пределов

Теорема (о верхнем и нижнем пределе):

Пусть — вещественная последовательность. Тогда справедливы следующие утверждения: Верхний предел — наибольший, а нижний — наименьший из частичных пределов . Предел в существует тогда и только тогда, когда верхний и нижний пределы равны, при этом предел последовательности равен их общему значению.

Техническое описание верхнего предела

Теорема о существовании предела в терминах верхнего и нижнего пределов

Теорема о характеризации верхнего предела как частичного

Эквивалентность определений Гейне и Коши

Теорема:

Определения предела отображения по Коши и по Гейне равносильны.

Единственность предела, локальная ограниченность отображения, имеющего предел, теорема о стабилизации знака

Теорема (единственность предела):

Отображение в данной точке не может иметь более одного предела: если и — метрические пространства, , — предельная точка , , то .

Теорема (локальная ограниченность отображения, имеющего предел):

Пусть и — метрические пространства, , — предельная точка , . Тогда существует такая окрестность точки , что ограничено в (то есть содержится в некотором шаре пространства .

Арифметические свойства пределов

[уже было для последовательностей, то же самое]

Теорема о сжатой функции. Предельный переход в неравенстве

Теорема (предельный переход в неравенстве для функици):

Пусть — метрическое пространство, , — предельная точка , для всех {}, . Тогда .

Теорема (о сжатой функции):

Пусть — метрическое пространство, , — предельная точка , для всех {}, . Тогда и .

Теорема о пределе монотонной функции

Теорема (о пределе монотонной функции):

Пусть , — предельная точка . Если возрастает и ограничена сверху на , то существует конечный предел . Если убывает и ограничена снизу на , то существует конечный предел .

Теорема о компактности в пространстве и в подпространстве

Теорема (компактность в пространстве и подпространстве):

Пусть — метрическое пространство, — подпространство , . Тогда свойства компактности в и равносильны.

Простейшие свойства компактных множеств

Теорема (свойства компактов):

Пусть — метрическое пространство, . Если компактно, то замкнуто и ограничено. Если компактно, а замкнуто, то компактно.

Компактность замкнутого куба в R^m

Теорема (компактность замкнутого куба в R^m):

Замкнутый куб в компактен.

Теорема о характеристике компактов в R^m

Теорема (характеристика компактов в R^m):

Пусть . Тогда следующие утверждения равносильны: замкнуто и ограничено. компактно. Из всякой последовательности точек можн извлечь подпоследовательность, имеющую предел, принадлежащий .

Принцип выбора Больцано—Вейерштрасса

Теорема (Больцано-Вейерштрасса, принцип выбора):

Из всякой ограниченной последовательности в можно извлечь сходящуюся подпоследовательность.

Сходимость в себе и её свойства

Лемма (свойства сходимости в себе):

Сходящаяся в себе последовательность ограничена. Если у сходящейся в себе последовательности есть сходящаяся подпоследовательность, то сама последовательность сходится.

Теорема:

Во всяком метрическом пространстве любая сходящаяся последовательность сходится в себе. В любая сходящаяся в себе последовательность сходится.

Критерий Коши для отображений

Теорема (Больцано-Коши, критерий для отображений):

Пусть и — метрические пространства, полно, , — предельная точка . Тогда существование в точке предела , принадлежащего , равносильно следующему утверждению: Для любого положительного числа существует такая окрестность точки , что для любых двух точек и множества , принадлежащих проколотой окрестности , выполняется неравенство :

Свойства непрерывных отображений: арифметические, стабилизация знака, композиция

Теорема (арифметические действия над непрерывными отображениями):

Пусть — метрическое пространство, — нормированное пространство, , отображения непрерывны в точке . Тогда отображения непрерывны в точке .

Теорема (о стабилизации знака):

Если функция непрерывна в точке , причём , то существует такая окрестность , что для всех .

Теорема (непрерывность композиции):

Пусть — метрические пространства, , непрерывно в точке , непрерывно в точке . Тогда непрерывно в точке .

Теорема о топологическом определении непрерывности

Теорема Вейерштрасса о непрерывном образе компакта. Следствия

Теорема (Вейерштрасс, о непрерывных отображениях):

Пусть и — метрические пространства, компактно, . Тогда компактно.

Или: непрерывный образ компакта — компакт.

Следствия:

1. Непрерывный образ компакта замкнут и ограничен
2. Функция, непрерывная на отрезке, ограничена
3. Непрерывная на компакте функция принимает наибольшее и наименьшее значение
4. Функция, непрерывная на отрезке, принимает наибольшее и наименьшее значение

Теорема Кантора

Теорема (Кантор):

Непрерывное на компакте отображение равномерно непрерывно.

Лемма о связности отрезка. Теорема Больцано—Коши о промежуточном значении

Теорема (Больцано-Коши, о промежуточном значении):

Пусть функция непрерывна на . Тогда для любого числа , лежащего между и , найдётся такое , что .

Теорема о сохранении промежутка

Теорема (о сохранении промежутка):

Множество значений непрерывной на промежутке функции есть промежуток.

Теорема о непрерывности монотонной функции. Следствие о множестве точек разрыва

Теорема (о непрерывности монотонной функции):

Пусть , монотонна. Тогда справедливы следующие утверждения: не может иметь разрывов второго рода. Непрерывность равносильна тому, что её множество значений — промежуток.

Теорема о существовании и непрерывности обратной функции

Теорема (о существовании и непрерывности обратной функции):

Пусть , строго монотонна, . Тогда справедливы следующие утверждения: обратима, — биекция. строго монотонна одноимённо с . непрерывна.

Две леммы к определению показательной функции

Лемма:

Пусть — последовательность рациональных чисел, . Тогда .

Лемма:

Пусть — последовательность рациональных чисел, . Тогда существует конечный предел последовательности .

Свойства показательной функции: монотонность, экспонента суммы, непрерывность

Теорема:

Показательная функция строго возрастает на при и строго убывает при . Показательная функция непрерывна на .

Свойства показательной функции: композиция экспонент, обратимость. Логарифм. Его свойства.

Теорема:

показательная функция — биекция между и

Непрерывность тригонометрических функций и обратных к ним

Теорема:

и обратные к ним непрерывны на .

Замечательные пределы с участием синуса, логарифма, степенной и показательной функции

Теорема о замене на эквивалентную при вычислении пределов. Таблица эквивалентных

Теорема (замена на эквивалентную при вычислении пределов):

Пусть — метрическое пространство, , — предельная точка , . Тогда справедливы следующие утверждения: Если — предельная точка области определения , то

Теорема единственности асимптотического разложения

Теорема (о единственности асимптотического разложения):

Пусть — метрическое пространство, , — предельная точка , , при всех , и для любой окрестности существует точка , в которой . Тогда, если асимптотическое разложение функции по системе существует, то оно единственно: из равенств следует, что при всех

Равносильность двух определений производной. Правила дифференцирования.

Теорема:

Два определения производной равносильны.

Правила: производные суммы-разности; произведения; частного; композиции ; обратной функции

Дифференцирование композиции и обратной функции

Теорема Ферма (с леммой)

Теорема Ролля

Теоремы Лагранжа и Коши. Следствия об оценке приращения и о пределе производной

Теорема Дарбу. Следствия

Формула Тейлора с остатком в форме Пеано

Формула Тейлора с остатком в форме Лагранжа

Здравствуйте на странице расположен курс лекций по дискретной математике с примерами решения заданий и выполнением задач. В лекциях рассматриваются все темы по предмету «Дискретная математика«: теория множеств (множества, отношения, функции), комбинаторика и общая алгебра (алгебраические системы). Для краткой записи утверждений используются следующие обозначения символов:

Для любых предложений запись означает, что предложения равносильны по определению (от англ. definition — определение).

Содержание:

Множества

Определение и способы задания множеств

Множество — это любое собрание вполне определенных и различимых объектов нашей интуиции или интеллекта, мыслимое как единое целое. Это описание множества принадлежит основателю теории множеств Георгу Кантору (1845 — 1918). 

Объекты,  из  которых  состоит  множество,  называются  его  эле- ментами. Множества будем обозначать прописными буквами латинского алфавита (A, B, C, X, Y, Z, . . .) , а элементы множеств — строчными (x, y, z, a, b, c, . . .) . Зафиксируем следующие обозначения для наиболее важных числовых множеств: N — множество натуральных чисел, Z — множество целых чисел, R — множество действительных чисел.

Множество  A  называется подмножеством множества  B  (обозначается —  A ⊆ B , знак  ⊆ называется знаком включения),если каждый элемент множества A является элементом множества B .

Множества  A  и  B  равны ( A = B ), если одновременно имеют место включения A ⊆ B и B ⊆ A . Принадлежность элемента x  множеству A обозначается x ∈ A , непринадлежность элемента   x   множеству A  обозначается x ∈/ A .

Множество, не содержащее элементов, называется пустым и обозначается ∅ .

Множество, включающее элементы всех рассматриваемых в конкретной ситуации множеств, называется универсальным для данной ситуации и обозначается U . Для любого множества имеют место включения: ∅ ⊆ A ⊆ U .

Рассмотрим способы задания множеств. Множество может быть задано:

• а) описанием характеристического свойства его элементов,
• б) при помощи списка или перечисления элементов множества,
• в) при помощи порождающей процедуры и т. д.

При задании множества A при помощи его характеристического свойства P (x) пишут A = {x|  P (x)}.

При помощи списка могут задаваться только конечные множества, т. е. множества, состоящие из конечного числа элементов.

Порождающая процедура описывает способ получения элементов множества из уже полученных элементов или других объектов. Весьма распространенной порождающей процедурой является образование множеств из других множеств при помощи операций, которые рассмотрим ниже.

Операции над множествами и их свойства

Объединением множеств A и B называется множество A ∪ B , состоящее  из  тех  и  только  тех  элементов,  которые  принадлежат хотя бы одному из множеств A или B :

A ∪ B = {x | x ∈ A или x ∈ B}.

Пересечением множеств A и B называется множество A ∩ B , состоящее  из  тех  и  только  тех  элементов,  которые  принадлежат одновременно множествам A и B :

A ∩ B = {x | x ∈ A и x ∈ B}.

Разностью множеств A и B называется множество A B тех и только тех элементов из  A , которые не принадлежат множеству B :

 A B = {x | x ∈ A  и  x ∈/ B}.

Дополнение    определяется равенством    — универсальное множество.

Симметричной разностью множеств  A  и  B  называется множество:

Эти операции можно наглядно проиллюстрировать следующим образом:

Приведенные здесь рисунки называются диаграммами Эйлера-Венна.

Операции над множествами обладают следующими свойствами:

1. = A (закон двойного отрицания);
2. A ∪ B = B ∪ A (коммутативность объединения);
3. A ∩ B = B ∩ A (коммутативность пересечения);
4. A ∪ (B ∪ C) = (A ∪ B) ∪ C (ассоциативность объединения);
5. A ∩ (B ∩ C) = (A ∩ B) ∩ C (ассоциативность пересечения);
6. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (1-й дистрибутивный закон);
7. A ∪ (B ∩ C)  = (A ∪ B) ∩ (A ∪ C) (2-й дистрибутивный закон);
8.  
9. 
10. A ∪ (A ∩ B) = A (закон поглощения);
11. A ∩ (A ∪ B) = A (закон поглощения);
12. A ∪ ø = A ;
13. A ∩ ø = ø;
14. A ∪ U = U ;
15. A ∩ U = A .

Мощность конечного множества

Число элементов конечного множества A называется его мощностью и обозначается |A| .

Говорят,  что  между  множествами  A   и  B   установлено  взаимооднозначное  соответствие,  если  задан  закон,  по  которому каждому элементу множества  A  соответствует один и тот же элемент множества B .

Между конечным непустым множеством A мощности n и отрезком натурального ряда {1, 2, . . . , n} существует взаимооднозначное соответствие.

Приведем очевидные свойства мощности конечных множеств:

1) | ø | = 0 ; 2) из A ⊆ B следует |A| ≤ |B| , если при этом , то |A| <  |B| , следует отметить, что обратное утверждение не верно; 3) |AOB| ≤ |A| + |B| ; 4) |A ∩ B| ≤ min{|A|, |B|}; 5) |A ∪ B| = |A| + |B| − |A ∩ B| ; 6) |A B| ≤ |A| ; 7) |AOB| = |A ∪ B| − |A ∩ B| .

Прямое произведение двух и более множеств.

Прямым произведением двух множеств A = {a1, . . . , am}  и  B = {b1, . . . , bn} называется множество A × B упорядоченных пар вида (ai, bj) , где

Прямым произведением k множеств A1 , A2 , . . . , Ak называется множество A1 × A2 × . . . × Ak упорядоченных наборов  длины k , где

Эти определения кратко можно записать так:   A × B = {(a, b) | a ∈ A, b ∈ B}.

Теорема о мощности прямого произведения. Мощность прямого произведения конечного числа конечных множеств равна произведению мощностей этих множеств

|A1 × A2 × . . . × Ak| = |A1| · |A2| · . . . · |Ak|, k ∈ N.

Доказательство. Рассмотрим вначале случай двух множеств и докажем формулу |A × B| = |A| · |B| .

Пусть A = {a1, . . . , am} и B = {b1, . . . , bn}, тогда элементы A × B множества можно раcположить в виде следующей таблице:

которая содержит m строк и n столбцов. Поэтому число записанных в таблице упорядоченных пар равно mn = |A | * | B |.

Для доказательства теоремы в случае произвольного k воспользуемся методом математической индукции. При k = 1 теорема, очевидно, имеет место. Предположим, что она выполняется для случая (k − 1) -го множества и докажем ее для случая k множеств. С этой целью установим взаимооднозначное соответствие между множествами:

A1 × A2 × . . . × Ak  и  (A1 × A2 × . . . × Ak−1) × Ak

по правилу: элементу поставим в соответствие элемент и наоборот. В силу взаимооднозначного соответствия между множествами

их мощности совпадают; используя утверждение теоремы для случая двух множеств, получаем:

|A1×A2×. . .×Ak| = |(A1×A2×. . .×Ak−1)×Ak| = |A1×A2×. . .×Ak−1||Ak|.

В силу предположения индукции |A1 × . . . × Ak−1| = |A1| . . . |Ak−1| , что завершает доказательство теоремы.

Множество  называется  k -ой  степенью  множества  A . 

Из  теоремы  о  мощности  прямого  произведения  следует: 

Пусть E = {0, 1}, тогда  откуда следует  т. е. мощность множества всех наборов длины n  из нулей и единиц равна .

Булеан множества

Булеаном  Б(A) множества A называется множество всех подмножеств этого множества: Б(A) = {X|X ⊆ A}, если  A = {a1, . . . , an}, то

Теорема о мощности булеана. Пусть A — конечное множество мощности n , тогда мощность его булеана равна 2n : |Б(A)| = 2n .

Доказательство. Установим соответствие между множествами Б(A) и En по правилу: подмножеству  поставим в соответствие набор длины n  из нулей и единиц, в котором на местах с номерами i1, . . . , is стоят единицы, а на остальных местах нули. Это соответствие является взаимооднозначным, поэтому |Б(A)| = |En| = 2n . Теорема доказана.

В качестве примера приведенного в доказательстве теоремы соответствия рассмотрим случай n = 3 . Пусть A = {α, β, γ}, тогда

Б(A) = {ø, {α}, {β}, {γ}, {α, β}, {α, γ}, {β, γ}, {α, β, γ}};

E3 = (0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, 1, 1) .

Соответствие между E3 и Б(A) может быть установлено 8! различными способами (оно равно числу перестановок из элементов множества E3 ). В данном случае элементы множества E3 записаны так, что эле- менту, стоящему на k -ом месте, в Б(A) соответствует k -ый элемент множества соответствует (0, 0, 1) , {α, β} — (1, 1, 0) и т. д.

Отметим следующее свойство булеана: 

Б(A ∪ B) = {A1 ∪ B1|A1 ∈ Б(A), B1 ∈ Б(B)}.

Действительно, пусть произвольное множество C ∈ Б(A ∪ B) , т. е. C ⊆ A ∪ B . Обозначим через A1 = C ∩ A , B1 = C ∩ B . Тогда A1 ⊆ A , B1 ⊆ B  и C = A1 ∪ B1 , где A1 ∈ Б(A) , B1 ∈ Б(B) . Докажем обратное включение. Если A1 ∈ Б(A) , B1 ∈ Б(B) , то  A1 ⊆ A ,  B1 ⊆ B . Тогда  A1 ∪ B1 ⊆ A ∪ B ⇒ A1 ∪ B1 ∈ Б(A ∪ B) .

Рекомендации к решению задач:

Предположим, что все встречающиеся в задачах этого и следующего параграфов множества являются подмножествами некоторого универсального множества U . При решении предложенных для самостоятельной работы задач ( § 7 ) полезно использовать следующие факты.

1) Изображение множеств при помощи диаграмм Эйлера-Венна, при этом множества A , B , C  располагаются в в общем положении , когда

Пример №1

Проверим равенство множеств (A∪B)∩C и A∪(B∩C) .

Для этого изобразим их с помощью диаграмм Эйлера-Венна:

На рис.6 штриховкой обозначено множество (A ∪ B) ∩ C , а на рис.7 — A ∪ (B ∩ C) . Очевидно, что это разные множества.

2) Определения и основные свойства операций над множествами, а также доказанные свойства этих операций.

Пример №2

Докажем второй дистрибутивный закон,

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),

используя определение операций объединения и пересечения для множеств и второй дистрибутивный закон для высказываний. При этом и в дальнейшем используется символ . . . ⇐⇒ . . . , который означает эквивалентность утверждений, стоящих слева и справа от него.

Решение. Пусть и

x ∈ A ∪ (B ∩ C) ⇐⇒ x ∈ A или x ∈ (B ∪ C) ⇐⇒

⇐⇒ x ∈ A или (x ∈ B и x ∈ C) ⇐⇒ (x ∈ A или x ∈ B) и (x ∈ A или x ∈ C) ⇐⇒ (x ∈ A∪B) и (x ∈ A∪C) ⇐⇒ x ∈ (A∪B)∩(A∪C).

3) При рассмотрении равенств, содержащих символы операций и   полезно выразить последние через дополнение, пересечение и объединение:

 

Первое из этих равенств непосредственно следует из определения операции   :

Второе из равенств (1.1) является следствием первого.  

Пример №3

Докажем равенство  (A B) C = (A C) (B C).

Используем при этом первое из равенств (1.1), закон де Моргана, первый дистрибутивный закон и др.

Пример №4

Докажем равенство множеств

На первом шаге использовалось второе из равенств (1.1), на следующем шаге использовался закон де Моргана, далее первый дистрибутивный закон для множеств. Выражения в первой и третьей скобках последнего равенства есть пустые множества, поэтому

Пример №5

Докажем равенство  (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D).

Произвольным элементом множества, стоящего справа, является упорядоченная пара (x, y) . Пусть

(x, y) ∈ (A∩B)×(C∩D) ⇐⇒ (x ∈ A∩B) и (y ∈ C∩D) ⇐⇒ (x ∈ A и x ∈ B)

и (y ∈ C и y ∈ D) ⇐⇒ (x, y) ∈ (A × C) и (x, y) ∈ (B × D) ⇐⇒

⇐⇒ (x, y) ∈ (A × C) ∩ (B × D).

Бинарные отношения

Определение и способы задания отношений

Подмножество множества называется n -местным отношением на множестве А.

Говорят, что элементы находятся в отношении , если

Одноместное отношение это просто подмножество множества Такие отношения называют свойствами или признаками: свойство четности чисел, признак делимости на 3 и т.д.

Наиболее часто встречающимися являются двуместные или бинарные отношения. Ниже будем рассматривать только бинарные отношения, поэтому для краткости слово «бинарные» будем опускать. Если а и b находятся в отношении , то пишут или

Примерами отношений на множестве вещественных чисел являются отношения: На множестве натуральных чисел рассмотрим отношения: а) иметь один и тот же остаток от деления на « 5 » ; б) иметь общий делитель, отличный от « 1 ». На множестве плоских прямых отметим отношения параллельности, перпендикулярности, симметричности относительно начала координат и др.

Областью определения отношения на множестве А называется множество тех х € А, для которых существует у € А такое, что

Областью значений отношения  на множестве А называется множество тех значений х € А, для которых существует у € А такое, что

Рассмотрим способы задания отношений. Для задания отношений можно использовать любые способы задания множеств (например, отношение может быть задано списком пар, для которых это отношение выполняется). Отношения на конечном множестве могут быть заданы в виде таблицы (матрицы).

Таблица бинарного отношения на множестве содержит  m  строк и столько же столбцов, на пересечении i -й строки и j-го столбца находится элемент , который определяется следующим образом:

Так, для бинарных отношений  и  на множестве таблицы будут иметь следующий вид:

Отношение также можно задать с помощью рисунка, который называют графом. Каждому элементу , на плоскости ставится в соответствие точка, которую также обозначают через   Пара точек  и соединяется направленным отрезком или кривой тогда и только тогда, когда пара точек  Для вышезаданного отношения   построим граф (см. рис. 8).  

Операции над отношениями

Поскольку отношения на множестве А являются подмножествами множества , для них можно определить те же операции, что и для множеств: объединение, пересечение, дополнение, разность. Так отношение на множестве натуральных чисел является объединением отношений  Отношение является дополнением отношения , а отношение равенства является пересечением отношений на множестве действительных чисел.

Отношение называется обратным к отношению , если тогда и только тогда, когда

Произведением отношений и на множестве А называется отношение , состоящее из пар (х, у), для которых существует, элемент z € А, такой, что

Транзитивным замыканием отношения на множестве А называется отношение , которое определяется следующим образом: тогда и только тогда, когда существует цепочка из конечного числа элементов , в которой для каждой пары соседних элементов выполняется отношение

Транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком». Оно представляет собой объединение отношений «быть сыном», «быть внуком» , «быть правнуком» и т.д. Транзитивным замыканием «жить в одном городе» является то же отношение.

Свойства отношений

Отношение на множестве называется, рефлексивным, если для , и антирефлексивным в противоположном случае:

Примерами рефлексивных отношений являются отношения ,  и на произвольном числовом множестве.

Отношения , «быть сыном», «быть старше» являются примерами антирефлексивных отношений.

Отношение на множестве А называется, симметричньм, если из  следует . Отношение называется антисимметричным, если из   следует

Отношения «жить в одном городе», «иметь общий делитель, отличный от 1» на множестве целых чисел, «быть симметричным относительно оси» на множестве точек плоскости являются примерами симметричных отношений. Отношения на R, отношение включения на Б(А) являются антисимметричными.

Таблица (матрица) симметричного отношения симметрична относительно главной диагонали

Теорема. Отношение   симметрично тогда и только тогда, когда

Доказательство. Действительно, пусть , что означает симметричность . Наоборот, если симметрично, то , следовательно . Теорема доказана.

Отношение на множестве А называется транзитивным, если для любых х, у, z из множества А из следует

Отношения на множестве действительных чисел, отношение параллельности прямых, отношение «быть соседом » также являются транзитивными. Отношение перпендикулярности прямых, отношение «иметь общий делитель, отличный от 1» на множестве натуральных чисел свойством транзитивности не обладают.

Теорема. Если — транзитивное отношение, то

Доказательство. Из определения транзитивности замыкания следует, что  Пусть  тогда существует последовательность элементов из А таких, что   откуда в силу транзитивности получаем Так как произвольная пара из , то , что и доказывает утверждение теоремы.

Отношение эквивалентности

Отношение называется отношением эквивалентности и (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивио.

Будем говорить, что имеет место разбиение множества А на классы, если существует система  непустых, попарно не пересекающихся множеств такая, что

Теорема. Между совокупностью различных разбиений множества А на классы, и семейством всех отношений эквивалент пост а на этом множестве существует взаимнооднозначное соответствие.

Доказательство. Пусть имеет место разбиение (2.1) множества А на классы. Построим отношение на множестве А но правилу: для пара , если элементы ,   принадлежат одному и тому же классу ; в представлении (2.1). Рефлексивность и симметричность этого отношения очевидны, покажем его транзитивность. Пусть  Это означает, что и принадлежат классу  и одновременно   и   принадлежат классу . Если то получается, что элемент принадлежит двум различным классам. Последнее противоречит тому, что . Поэтому , все элементы  ,   и принадлежат одному классу, откуда следует  Мы доказали, что отношение эквивалентности.

Пусть — произвольное отношение эквивалентности на множестве А. Построим разбиение этого множества на классы. С этой целью выберем произвольный элемент и определим класс следующим образом:  Класс  не пуст, так как в силу рефлексивности   элемент . Выберем элемент и построим класс . Построив классы , выбираем элемент и класс . Элемент , назовем представителем класса Процесс продолжается до тех пор, пока  В результате получим представление Покажем, что оно является разбиением множества А на классы, а именно .

Предположим, что последнее не верно: существует элемент , классы и такие, что — тогда   . В силу симметричности и транзитивности получаем , а поэтому , что противоречит выбору элемента . Теорема доказана.

Если  отношение эквивалентности на А и , соответствующее ему разбиение множества А на классы, то множества   называются классами эквивалентности, а семейство  обозначается, символом и называется фактор-множеством множества А по отношению .

Мощность множества называется индексом разбиения.

Фактор-множество множества N по отношению «иметь общий остаток от деления на 5» состоит из пяти счетных классов:  

Отношение порядка

Отношение на множестве А называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.

Отношение  на А называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

Говорят, что два элемента и   из множества А сравнимы по отношению порядка , если или .

Множество А, на котором задано отношение порядка (строгого или нестрогого), называется полностью упорядоченным, если любые его два элемента сравнимы, и частично упорядоченным, если это не так.

Пусть множество А упорядочено отношением порядка .

Элемент называется наибольшим элементом множества А, если для всех имеет место отношение . Наибольший элемент множества А обозначают mах А.

Элемент называется, наименьшим элементом множества А, если для всех имеет место отношение . Наименьший элемент множества А обозначают minA.

Из этих определений следует, что наибольший и наименьший элементы упорядоченного множества имеет лишь такое множество, которое упорядочено рефлексивным отношением .

Отношения  и  для чисел являются отношениями нестрогого порядка, а отношения и — отношениями строгого порядка. Оба отношения полностью упорядочивают множества R и N.

Отношение включения на множестве всех подмножеств Б(A) некоторого множества А задает нестрогий частичный порядок. Отношение строгого включения задает строгий частичный порядок.

В качестве А рассмотрим множество упорядоченных наборов длины n  из нулей и единиц. Введем отношение предшествования: набор предшествует набору . , записывается как , если ,• для всех  

Построенное отношение является отношением нестрогого порядка на частично упорядоченном множестве .

Рекомендации к решению задач:

При доказательстве равенств и включений для отношений можно пользоваться методикой, разработанной в главе 1, §7 для множеств. При этом следует учитывать, что элементами отношения на множестве А являются упорядоченные пары

Пример №6

Докажем справедливость равенства 

Решение. Пусть

Пример №7

Пусть — отношения на множестве А, тогда из включений следует включение

Действительно, имеет место следующая последовательность утверждении:

которая завершает доказательство.  

При решении задач на построение отношений с заданными свойствами и на исследование свойств заданных отношений следует иметь в виду, что то или иное свойство имеет место, если его характеристика, например в случае антирефлексивности, должна выполняться для всех элементов множества А. Отсутствие того или иного свойства можно доказать, указав но крайней мере один элемент или пару элементов из А, для которых характеристика свойства не имеет места.

Пример №8

Пусть на множестве задано отношение . Это отношение не является рефлексивным, так как ; оно антирефлексивно: ; не симметрично антисимметрично: и  и  не транзитивно:

Пример №9

Покажем, что отношение  на R:

    (2.2)

является отношением эквивалентности.

Действительно, отношение (2.2.) рефлексивно, так как

симметрично:

и транзитивно:

Комбинаторика

Настоящая глава состоит из четырех параграфов: «Основные правила комбинаторики », «Понятие -выборки », «Размещения, перестановки, сочетания», «Формула включений и исключений». Каждый из этих параграфов содержит основные определения и теоремы по соответствующей тематике. Приводимые здесь подробные доказательства теорем являются также иллюстрацией методики решения теоретических задач разного уровня, помещенных в конце каждого раздела. Для успешного овладения материалом по теме «Комбинаторика» читателю рекомендуется предварительно ознакомиться с главами «Множества» и «Бинарные отношения», результаты которых используются в настоящей главе.

Комбинаторика изучает различные комбинации элементов множества. Все задачи, вопрос в которых начинается со слов «Сколькими способами » или «Сколько», относятся к разделу математики, который называется комбинаторикой.

Итак, комбинаторика — раздел математики, изучающий вопрос о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из конечного числа заданных элементов.

Основные правила комбинаторики

Основными способами решения комбинаторных задач являются методы, которые мы будем именовать «правило суммы» и «правило произведения ».

Правило суммы. Правило суммы для двух объектов: Пусть объект  а можно выбрать m способами, а объект b  —  n способами, и существует к общих способа выбора объектов а и b. тогда один из объектов  а  или  b  можно выбрать способами.

Это правило эквивалентно следующему свойству мощности:

Правило суммы можно сформулировать для произвольного числа объектов. Для этого достаточно использовать формулу для мощности объединения конечного числа множеств. Для случая трех множеств формула имеет вид:

Правило суммы для трех объектов: Пусть объект а  можно выбрать способами, объект b — способами и объект с — способами, и существует  общих способа выбора одного из объектов  а  и  b,  общих способа выбора одного из объектов а и с,  общих способа выбора одного из объектов b и с,  а также известно общих способа выбора одного из объектов а, b и с, тогда число всех способов выбора одного из объектное а или b или с вычисляется по формуле:

Правило произведения. Правило произведения для двух объектов: Пусть объект  а  можно выбрать  m способами и после каждого такого выбора объект  b  можно выбрать  n  способами, тогда выбор пары объектов  а  и b в указанном порядке можно осуществить m • n  способами.

Данное правило произведения равносильно утверждению

Правило произведения является следствием теоремы о мощности прямого произведения конечного числа конечных множеств.

Правило произведения для случая произвольного числа объектов формулируется следующим образом: Пусть объект   можно выбрать   способами,  способами,  . . . , способами, причем выбор каждого из последующих объектов не зависит от выбора предыдущих объектов, тогда общее число полученных таким образом упорядоченных наборов можно выбрать способами.

Последнее правило применяется, если требуется выполнить одно за другим одновременно действий, на одно из которых наложено ограничение.

Понятие k-выборки

Понятие -выборки

Пусть конечное непустое множество. Возможны два способа выбора элементов из множества А : выбор с возвращением и выбор без возвращения. Опишем их при помощи следующей таблицы.

При реализации описанных в таблице процедур мы получаем комбинацию элементов из множества А вида , которая называется -выборкой из  а   элементов.

В случае  «выбора с возвращением» эта комбинация может содержать повторяющиеся, элементы, и называется, -выборкой из n элементов с повторениями.

При реализации процедуры «выбор без возвращения» полученная комбинация не содержит повторяющихся элементов и называется r-выборкой из  n  элементов без повторений.

Выборка называется упорядоченной, если существенным является не только состав элементов в ней, но и порядок их выбора.

Две упорядоченные -выборки считаются различными, если они отличаются либо составом элементов, либо порядком их расположения. В неупорядоченных выборках порядок расположения элементов не существенен, две различные неупорядоченные-выборки имеют разный состав элементов.

Элементы упорядоченной выборки заключаются в круглые скобки (например (1,2)).

Элементы неупорядоченной выборки без повторений заключаются в фигурные скобки (например {1,2}), а элементы неупорядоченной выборки с повторениями в квадратные скобки (например [1,2]).

Упорядоченные выборки (3,2) и (2,3) считаются различными, хотя и составлены из одних и тех же элементов. Для тех же самых элементов «2» и «3» неупорядоченные выборки {3,2} и {2,3} (или [3,2] и [2,3]) считаются одной и той же.

Рассмотрим множество, которое содержит три элемента А — {1, 2, 3} . Составим из элементов этого множества всевозможные 2 — выборки.

Упорядоченные 2-выборки без повторений: (1,2), (2,1), (1,3), (3, 1), (2,3), (3,2).

Упорядоченные 2-выборки с повторениями: (1,2), (2, 1), (1,3), (3,1), (2,3), (3,2), (1,1), (2,2), (3,3).

Неупорядоченные 2-выборки без повторений: {1,2}, {1,3}, {2,3}.

Неупорядоченные 2-выборки с повторениями: [1,2], [1,3], [2,3 , [1,1], [2,2], [3,3].

В следующих параграфах будут даны формулы для подсчета количества -выборок из n элементов.

Размещения с повторениями и без повторений. Перестановки без повторений

Размещениями из n элементов по к называются упорядоченные -выборки из n элементов.

Размещениями без повторений из  n  элементов по называются упорядоченные -выборки из n элементов без повторений. Их число обозначается  

Размещениями с повторениями из  n  элементов по называются упорядоченные -выборки из n элементов с повторениями. Их число обозначается

Перестановками из n элементов называются размещения без повторений из  n  элементов по n . Их число обозначается, .

Теорема. Имеют место следующие равенства:

где 

Доказательство. Пусть произвольное множество, — упорядоченная -выборка без повторений, составленная из элементов множества. Она представляет собой набор длины вида , в котором

Число таких наборов равно мощности прямого произведения множеств

В силу теоремы о мощности прямого произведения имеем:

Умножим и разделим последнее выражение на и получим первое равенство из (3.1).

Размещения с повторениями из элементов множества А по к представляют собой упорядоченный набор , в котором каждый из элементов ,  может быть выбран  n  способами. В силу правила произведения указанный набор может быть выбран  способами, что и доказывает второе из равенств (3.1).

Третье получается из первого при Теорема доказана.

Сочетания с повторениями и без повторений

Сочетаниями из а элементов по называются неупорядоченные k-выборки из n элементов.

Сочетаниями без повторений из n элементов по k называются неупорядоченные k -выборки из n элементов без повторений. Их число обозначается .

Сочетаниями с повторениями из n элементов по k называются неупорядоченные k -выборки из n элементов с повторениями. Их число обозначается .

Теорема. Имеют место следующие равенства:

 (3.2)

Доказательство. Прежде чем доказать равенство для  в общем случае, рассмотрим пример. Пусть , тогда выборки, , представляют собой сочетания без повторений по 2, составленные из элементов множества А. Из каждого сочетания можно получить, производя в нем «перестановку» элементов, размещения без повторений по 2 из элементов множества А. Этот процесс изобразим в виде следующей схемы (см. рис. 13).

На основании вышеизложенного имеем равенство:

Аналогичная ситуация имеет место в общем случае: чтобы получить все размещений, нужно получить всевозможные сочетания из а элементов по к (их число равно ), затем в каждом из сочетаний сделать всевозможные «перестановки». Число перестановок, которые можно получить из одного сочетания длины k, равно Р(k). Очевидно, что из разных сочетаний без повторений не могут получиться одинаковые перестановки. Поэтому , откуда следует первое из равенств (3.2).

Перейдем к доказательству второго равенства (3.2). Введем обозначения:   — множество сочетаний с повторениями из чисел {1,2,…, n)

по ,    множество сочетаний без повторений из натуральных чисел  

Неупорядоченная k-выборка однозначно определяется комбинацией из номеров ее элементов . Не ограничивая общности рассуждений, можно считать, что . Положим, , тогда для и выборка

Пусть     произвольная комбинация из    так как она не зависит от порядка расположения элементов, то можно считать, что  . Положим , так как  для , следовательно, 

Мы установили взаимооднозначное соответствие между множествами , откуда следует, что их мощности совпадают

Теорема доказана.

Перестановки с повторениями. Подсчет числа беспорядков

Классическая задача комбинаторики о числе разбиений с повторениями формулируется следующим образом: сколькими способами можно разбить n различных предметов на k групп, по предметов в первой группе, по  во второй группе, …,  — в последней группе?

Такие комбинации называются перестановками с повторениями.

Число различных перестановок из предметов первого вида, предметов второго вида, …,  предметов -го вида вычисляется по формуле:

Действительно, для первой группы можно выбрать предметов из имеющихся в наличии способами. Для второй группы предметов из оставшихся в наличии способами. Для третьей группы предметов из оставшихся в наличии способами. Этот процесс продолжается вплоть до последней группы. Общее число разбиений, которое мы будем обозначать , равно:

Таким образом, число разбиений обобщает число сочетаний. Действительно, если мы разбиваем а предметов на две группы, то , откуда и

Рассмотрим еще один вид перестановок  n  предметов — циклические перестановки.

Задача заключается в следующем: рассматриваются  n  предметов, расположенных не в ряд, а по кругу. В этом случае перестановки считаются одинаковыми, если они получаются при переходе друг в друга при вращении, т.е. при циклическом сдвиге. Число таких перестановок из различных предметов

Немаловажной является и задача о «подсчете числа беспорядков» , когда требуется найти число  перестановок из цифр {1,2,…, n} , таких, что никакая цифра не остается на своем месте. Число таких перестановок находится но формуле:

Свойства сочетаний. Бином Ньютона

При помощи формулы (3.2) посредством алгебраических преобразований легко получить следующие свойства сочетаний:

Биномом Ньютона называется равенство

 

Докажем его, пользуясь методом математической индукции. При n = 1 имеем очевидное равенство:

Предположим, что равенство (3.3) имеет место при  n = k  и, исходя из этого предположения, докажем его для случая n = к + 1:

Из равенства (3.3), положив сначала х = а = 1, затем х = {—а) — 1, получим новые свойства сочетаний:

Так как сочетание без повторений из n элементов по k представляет собой k-элементное подмножество множества мощности n, то величина равна числу различных подмножеств этого множества. В связи с этим из свойства 5) сочетаний получаем теорему о мощности булеана (см. стр. 10).

Общий случай формулы включений и исключений

Пусть имеется N элементов, каждый из которых может обладать или не обладать свойствами . Через обозначается количество элементов, обладающих свойствами . . Если необходимо подчеркнуть, что берутся элементы, заведомо не обладающие некоторым свойством, то это свойство пишется с чертой; например, количество элементов, не обладающих свойством и обладающих свойством

Задача состоит в том, чтобы найти количество элементов, не обладающих ни одним из свойств

Для решения этой задачи в случае трех свойств воспользуемся следующим выражением для мощности объединения множеств А, В и С:

(3.4)

Обозначим через А, В, С множества элементов, обладающих свойствами соответственно, тогда

На приведенном рисунке множество элементов, изображенное в виде прямоугольника, имеет мощность N. Множество элементов, не обладающих ни одним из свойств (его мощность равна ), представлено заштрихованной частью прямоугольника. Исходя из того, что и используя равенство (3.4), получим формулу включений и исключений для случая трех свойств:

Теорема. При сделанных ранее предположениях и обозначениях формула включений и исключений для случая  n  свойств имеет, вид:

Доказательство. Следует отметить, что алгебраическая сумма

в (3.5) распространена на все сочетания свойств из множества  по s, причем, знак плюс ставится, если число s учитываемых свойств четно, и знак минус, если это число нечетно.

Доказательство равенства (3.5) будем проводить методом математической индукции но числу а свойств. В случае n — 1 равенство (3.5) приобретает вид: . Оно верно, так как каждый элемент либо обладает свойством , либо не обладает. Далее пусть

Это равенство верно для любого конечного множества элементов, в частности для множества элементов, обладающих свойством . Общее количество этих элементов равно . Число элементов, не обладающих свойством на множестве элементов, обладающих свойством , вычисляется по формуле, которая следует из (3.6):

В каждом слагаемом здесь присутствует . Вычтем это равенство из (3.6). В левой части результата получим выражение:

а в правой части, сгруппировав слагаемые с одинаковым количеством свойств, получим правую часть равенства (3.5). Теорема доказана.

Частный случай формулы включений и исключений

Предположим, что число элементов, обладающих свойствами , не зависит от характера свойств, а зависит от их числа, т.е. пусть

Используя введенные обозначения, получим следующие выражения для сумм в (3.5):

Положив далее , из (3.5) получим равенство

Применение формулы включений и исключений

Рассмотрим множество чисел  {1,2,… ,n}  и найдем число D(n) перестановок этих чисел, в которых ни одно из них не остается на своем первоначальном месте а,

Обозначим через — свойство перестановки, заключающее в том. что число  стоит на своем месте, а через обозначим количество перестановок, обладающих этим свойством.

Нетрудно заметить, что . Пусть количество перестановок, в которых числа стоят на своих местах, тогда

Здесь мы имеем тот случай, когда величины не зависят от характера свойств, а зависят только от их числа:

Число элементов N  в рассматриваемом случае равно числу перестановок из n элементов: . Подставляя найденные значения для , а также выражения для в формулу (3.7), получим равенство 

В случае n =  3  из (3.8) находим, что число D(3) перестановок, в которых числа 1, 2, 3 не стоят на своих местах, равно 2.

Рекомендации к решению задач:

При решении комбинаторных задач, в которых требуется определить количество некоторых выборок (комбинаций) из данного множества элементов, основным моментом является правильное определение типа (характера) выборок — упорядоченные это выборки или нет, с повторениями или без повторений. Эти различные комбинации называются размещениями, сочетаниями и перестановками, определения которых были даны выше.

Добавим, что при решении задач комбинаторики можно пользоваться терминологией: элементы (объекты), из которых состоит k-выборка, помещаются в «ячейки». Порядок заполнения «ячеек» может быть произвольным, но нужно выбирать наиболее простой.

Пример №10

Сколько есть трехзначных чисел, делящихся на 4, в записи которых не используются цифры 0, 4, 5, 6, 8, 9?

Решение. Число делится на 4 тогда и только тогда, когда две последние его цифры образуют число, делящееся на 4. В нашем случае это числа 12, 32, 72. Для построения комбинации понадобятся две «ячейки»: в первую можно поместить одну из цифр 1, 2, 3, 7; во вторую одну из ранее перечисленных двухзначных чисел. Первый объект можно выбрать 4 способами, второй объект 3 способами. По правилу произведения ответом на поставленный вопрос является число 4 • 3 = 12.

Применяя правило произведения, следует обратить внимание на условие. Выбор каждого последующего элемента не должен зависеть от выбора предыдущего. Следующий пример является иллюстрацией к этому замечанию.

Пример №11

Сколько есть шестизначных чисел, в каждом из которых нет одинаковых цифр, а вторая и четвертая цифры нечетны?

Решение. Очевидно, что надо взять шесть «ячеек». Заполним эти «ячейки» . В первую «ячейку» поместим одну любую из 9 цифр (кроме «0»). Во вторую «ячейку» нужно поместить нечетную цифру. Так например, если на первое место мы поставили цифру 2, то на второе место можно поставить одну из цифр «1», «3», «5», «7» или «9». Если же на первом месте уже стоит цифра «9», то на второе место можно поставить только «1», «3», «5» или «7». Указанный способ выбора является неудобным, поэтому рассмотрим другой порядок заполнения «ячеек» вторая, четвертая, первая, третья, пятая, шестая. Во вторую поместить одну из 5 нечетных цифр, в четвертую любую из 4 оставшихся нечетных цифр, в первую одну из 7 (кроме «О» и тех двух, что уже стоят, в третью любую из 7 оставшихся, в пятую любую из 6 оставшихся, в шестую — любую из 5 оставшихся. В результате получим .5 • 4 • 7 • 7 • 6 • 5 = 29 400 чисел, обладающих заданным свойством.

В некоторых случаях для того, чтобы найти число элементов конечного множества, обладающих требуемым свойством, удобно найти сначала число элементов, не обладающих этим свойством, и затем вычесть это число из общего числа элементов множества.

Пример №12

Сколько есть пятизначных чисел, в записи которых есть хотя бы одна четная цифра?

Решение. Всего пятизначных чисел 9 • 10 • 10 • 10 • 10 = 90 000, из них

5 • 5 • 5 • 5 • 5 = 3125 чисел, которые состоят только из нечетных цифр. Поэтому количество требуемых чисел равно 86 875.

Разберем типичные задачи на применение правила суммы и формулы включений и исключений.

Пример №13

Сколькими способами из 28 костей домино можно выбрать кость, на которой есть «1» или «6»?

Решение. Выбрать кость, содержащую « 1 » , можно семью способами, содержащую «6» тоже семью способами, но среди этих способов есть один общий — это выбор кости «1 : 6 ». В соответствии с правилом суммы общее число способов нужной кости можно осуществить 7 + 7— 1 = 13 способами.

Пример №14

Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал шести различных цветов?

Решение. Нужно найти число 3-выборок из 6 элементов без повторений (так как все цвета различны). Порядок, в котором располагаются выбранные цвета, существенен. Следовательно, нужно найти число упорядоченных выборок, т.е. число размещений из 6 по 3 без повторений:

(способов).

Данную задачу можно решить и другим способом. Для выбора цвета первой полосы имеется 6 вариантов. После произведенного выбора цвет для второй полосы можно выбрать 5 из оставшихся 5 способов. Далее выбираем цвет для третьей полосы из 4 оставшихся 4 способами. По правилу произведения имеем: 6 • 5 • 4 = 120 способов.

Пример №15

Сколько существует различных наборов длины 10 из нулей и единиц?

Решение. Так как набор состоит из десяти элементов, которые принимают только два возможных значения « 0 » или « 1 » , то в этом наборе будут присутствовать одинаковые значения элементов (т.е. элементы повторяются). Следовательно, нужно найти число упорядоченных выборок с повторениями:

(наборов).

Пример №16

В магазине имеются в продаже мобильные телефоны 7 торговых марок. Сколькими способами можно купить: а) 5 аппаратов разных торговых марок; б) 4 аппарата; в) 15 аппаратов?

Решение. В случае а) нужно подсчитать число неупорядоченных 5-выборок из 7 возможных без повторений (все телефонные аппараты разных торговых марок). Их число определяется по формуле:

  (способ).

В случаях б) и в) нас интересуют неупорядоченные выборки из 7 элементов с повторениями длины 4 и 15 соответственно. Их значения определяются по формулам:

б)   (способов),

в)  (способа).  

Пример №17

Семь девушек водят хоровод. Сколькими различными способами они могут встать в ряд?

Решение. Если девушки стояли бы на месте, то получилось бы 7! способов перестановок в ряду. Но так как они кружатся, то их положение относительно окружающих предметов несущественно, а важно только их взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении (циклическом сдвиге), нужно считать одинаковыми. Так как из каждой перестановки сдвигом можно получить еще 6 новых, то количество интересующих нас перестановок будет равно: 7!/7 = б!.

Пример №18

В ходе экзаменационной сессии 1 студентов получили оценки «отлично», 12 — «хорошо», 13 — «удовлетворительно», 5 — «хорошо» и «отлично», 7 «хорошо» и «удовлетворительно», 8 — «отлично» и «удовлетворительно». У трех студентов все виды оценок. Сколько студентов в группе, если известно, что все они сдали сессию? Сколько отличников в группе? Сколько в группе чистых «троечников»?

Решение. В условии задачи , . По формуле для правила суммы трех объектов находим общее число студентов в группе:

число отличников в группе равно:

 

число чистых «троечников» равно:

.

Теперь рассмотрим комбинаторные задачи с ограничениями на порядок элементов, когда на порядок элементов накладываются некоторые дополнительные условия. В таких задачах удобно применять следующий метод объединение нескольких одинаковых элементов в блоки.

Затем рассмотрим задачи на разбиения, где требуется разделить элементы на две и более групп в соответствии с некоторыми условиями и найти число всевозможных различных способов раздела. При этом необходимо учитывать, существенен ли порядок элементов в группах, различаем ли мы элементы, входящие в группы, и сами группы и т.д. При решении этих задач обычно элементы располагают в ряд и применяют так называемый метод введения перегородок.

Пример №19

Имеются предметы  k сортов:   предметов одного сорта, предметов другого сорта предметов  -го сорта, где все предметы одного сорта все же различны друг от друга. Найти число перестановок этих предметов, в которых все предметы одного и того же сорта стоят рядом.

Решение. Из данных сортов (блоков) можно сделать Р(k) = k!  перестановок. Но еще можно переставить предметы внутри блоков  способами. Далее по правилу произведения имеем  перестановок.

Пример №20

Сколькими способами можно переставить буквы слова «перелет» так, чтобы три буквы «е» не шли подряд?

Решение. Объединим все буквы «е» в один блок «еее». Число перестановок, в которых все три буквы «е» идут подряд, равно числу перестановок из 5 объектов: «еее», «и», «р», «л», «т», т.е. Р(5) = 5! = 120. Всего же перестановок с повторениями из букв данного слова можно составить . Значит, искомое число перестановок, где три буквы «е» не идут рядом, равно N = 840 — 120 = 720.

Пример №21

Сколькими способами можно расставить  m  нулей и k единиц, где , так, чтобы никакие две единицы не стояли рядом?

Решение. Выпишем сначала m  нулей. Для единиц получается m + 1 место (одно место слева, m — 1 в промежутках между нулями и одно справа). На любые из этих  m + 1  мест можно поставить одну из k единиц. Это можно осуществить способами. Если условие не будет выполняться, то в результате расстановки две единицы в любом случае будут стоять рядом.

Пример №22

Найти число способов разбиения  n  одинаковых предметов по k урнам (n и k произвольные натуральные числа).

Решение. Переименуем урны, расположив их в ряд. Между ними будет (k — 1)  промежуток. Поставим в соответствии каждому разбиению предметов но урнам последовательность из нулей и единиц следующим образом: сначала последовательность имеет группу из «0», число которых равно числу предметов в первой урне, затем ставим одну перегородку, обозначив ее за «1»; далее столько «0», сколько предметов во второй урне, и опять ставим «1»; затем столько «0», сколько в третьей урне, и т.д., заканчивается последовательность группой «0»; их столько, сколько предметов в последней урне. Следовательно, в такой последовательности будет n  нулей и (k — 1) единиц, всего (n + k — 1) цифр. Тогда число способов разбиения будет равно   .

Пример №23

Комиссия состоит из  n  человек. Документы хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как распределить между членами комиссий, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся вместе не менее  m  человек комиссии  — наименьшее число членов, при котором возможен доступ к сейфу)?

Решение. Какие бы  m — 1  членов комиссии не собрались, должен найтись замок, который они не смогут открыть, но ключ от этого замка имеется у каждого из  n — (m — 1) = n — m + 1 > 0   остальных членов комиссии (появление кого-нибудь из которых дает возможность открыть сейф). Следовательно, число замков равно ; число ключей равно (n — m + 1) • . Замечание в условии задачи является существенным, так как доступ к замкам сейфа имеют только n  человек, которые являются членами комиссии.

Пример №24

Сколькими способами можно расставить в шеренгу  n  различных львов и  m  различных тигров так, чтобы никакие два тигра не шли друг за другом ()?

Решение. Расставим сначала всех львов, оставив между каждыми двумя промежуток. Это можно сделать Р(n) способами, так как все львы разные, если бы все львы были одинаковы, то расставить их в ряд можно было одним способом. Теперь для расстановки тигров имеется (n + 1) место (либо одно впереди всех львов, либо одно после всех, либо между ними — (n — 1)). Так как порядок тигров существенен (они все разные), то число их способов расстановки равно  . Следовательно, общее число способов расстановки хищников найдем с помощью правила произведения . Замечание в условии задачи (m < n + 1)  является необходимым, в противном случае какие-нибудь два тигра окажутся рядом.

Линейные рекуррентные соотношения второго порядка

Линейным рекуррентным соотношением второго порядка (ЛРС) называется функциональное уравнение вида

где  — неизвестная функция, определенная на множестве натуральных чисел N со значениями в R,  — вещественные числа.

Из вида ЛРС (4.1) следует, что для вычисления значения функции при фиксированном значении аргумента необходимо и достаточно знать и . Условия

   (4.2)

называются начальными условиями для ЛРС (4.1).

Рассмотрим в качестве примера ЛРС

   (4.3)

Если и т.д.

Нетрудно убедиться, что и в случае произвольных начальных условий (4.3) значение функции    при любом фиксированном n € N однозначно определяется из ЛРС.

Решением ЛРС называется функция f(n) (f : N —► R), при подстановке которой в (4-1) получается, равенство, истинное при всех n € N.

Функция    является решением ЛРС (4.3), так как, положив в уравнении (4.3), получим тождество: .

Частным решением ЛРС (4.1) называется, решение, удовлетворяющее начальным условиям (4.2).

В дальнейших рассуждениях используется очевидный факт: при любых задача (4.1), (4.2) имеет единственное решение, другими словами, частное решение всегда единственно.

Общим решением ЛРС (4-0 называется вещественная функция , зависящая, от натурального аргумента  n  и двух вещественных произвольных постоянных и , такая , что: 1) при. конкретных значениях произвольных постоянных и функция является частным решением ЛРС (4-1); любое частное решение, т. е. решение, удовлетворяющее начальным условиям (4-2) с произвольными  а  и  b, получается, из при определенных значениях и . которые зависят от а  и b.

Свойства решений

Лемма. Пусть решения ЛРС (4-1), тогда их линейная комбинация , где и произвольные вещественные числа, также является решением ЛРС (4.1).

Доказательство. Так как и являются решениями ЛРС (4.1), то имеют место тождества

Умножим первое тождество на , а второе на и сложим полученные выражения, в результате имеем:

откуда следует, что функция является решением ЛРС (4.1). Лемма доказана.  

Алгебраическое уравнение второго порядка

   (4.4)

называется характеристическим уравнением, соответствующим ЛРС (4.1).

Случай простых корней характеристического уравнения

Теорема (об общем решении JIPC в случае простых корней характеристического уравнения). Пусть и различные вещественные корни характеристического уравнения (4.4), тогда общее решение ЛРС (4.1) находится по формуле

    (4.5)

Доказательство. Покажем, что функция , является решением ЛРС (4.1). При подстановке в (4.1) получаем:

 (4.6)

что равносильно равенству: , истинность которого вытекает из предположений теоремы. Функция в равенстве (4.5) представляет собой линейную комбинацию решений и в силу доказанной выше леммы также является решением ЛРС (4.1).

Пусть — произвольное частное решение ЛРС (4.1), удовлетворяющее начальным условиям (4.2). Найдем и из равенств:

Последнее представляет собой линейную алгебраическую систему второго порядка с неизвестными и . Решая ее, находим

Здесь мы воспользовались тем, что и  различны, поэтому

Частные решения и удовлетворяют одним и тем же начальным условиям (4.2) и в силу единственности решения задачи (4.1), (4.2) совпадают:

Теорема доказана.

Случай кратных корней характеристического уравнения

Рассмотрим случай, когда двухкратный корень характеристического уравнения (4.4). Тогда, используя формулы Виета, получим

    (4.8)

Теорема (об общем решении ЛРС в случае кратного корня).

Пусть двухкратный корень характеристического уравнения (4.4). тогда общее решение ЛРС (4.1) находится по формуле

   (4.9)

Доказательство. Покажем, что функция является решением ЛРС (4.1). Подставляя в (4.1) и учитывая равенства (4.8), получим

что равносильно равенству , истинность которого при всех  очевидна. Формула (4.9) задает решение ЛРС (4.1), так как является линейной комбинацией решений .

Повторяя рассуждения предыдущей теоремы, находим постоянные и из уравнений . Так как , то  . Мы получили, что решение задачи (4.1), (4.2) в случае кратного корня характеристического уравнения (4.4) находится но формуле:

Теорема доказана.

Соотношение Фибоначчи

Рекуррентное соотношение

    (4.10)

известно как соотношение Фибоначчи. Характеристическое уравнение для соотношения (4.10) имеет вид: . Корни характеристического уравнения  Таким образом, общее решение соотношения Фибоначчи находится по формуле:

   (4.11)

Числами Фибоначчи называется решение соотношения (4.10), удовлетворяющее начальным условиям F( 1) = 0, F(2) = 1. Полагая в формуле (4.11) n = 1 и n = 2, получим для и систему уравнений:

откуда находим  Поэтому

Отметим, что это последнее выражение при всех натуральных значениях а принимает целые неотрицательные значения.

Рекомендации к решению задач:

Нахождение общего и частного решений рекуррентного соотношения

состоит из следующих шагов:

1) выписывается характеристическое уравнение

 

и находятся его корни

2) если , общее решение ЛРС записывается в виде:

3) если , общее решение ЛРС также содержит две произвольные и постоянные

4)    для нахождения частного решения , удовлетворяющего условию  составляется система уравнений с неизвестными и .  В случае 2) она имеет вид

   в случае  3) — 

Затем найденное решение системы подставим в формулу для  2) в случаях 2) или 3) соответственно, получим частное решение ЛРС.

Если (это возможно, когда , решение рекуррентного соотношения имеет вид . Решением в этом случае будет функция .

Пример №25

Найти общее решение ЛРС   с начальными условиями .

Решение. Характеристическое уравнение в этом случае имеет вид: , его корни различны . Общее решение . Частное решение находим, составляя систему уравнений: . Откуда получаем = 0, = 3. Частное решение

Пример №26

Найти общее и частное решение ЛРС

с начальными условиями

Решение. Характеристическое уравнение имеет двухкратный корень  Общее решение в этом случае имеет вид

Далее находим частное решение. Система уравнений для и

Решая эту систему, находим = 29,  = —27. Частное решение: .

Пример №27

Пусть решение уравнения Фибоначчи 

 удовлетворяющее условию . Требуется доказать тождество:

    (4.12)

Для доказательства воспользуемся методом математической индукции. При равенство (4.12) приобретает вид , что верно, так как  Предположим, что равенство (4.12) верно при , т.е. 

Докажем его для случая n = k + 1. Действительно, по предположению индукции и из уравнения Фибоначчи получаем:

  что и доказывает утверждение.

Пример №28

Построить ЛРС, частные решения которого имеют вид:

Решение. Из вида частных решений искомого рекуррентного соотношения корни его характеристического уравнения  Составим квадратное уравнение с указанными корнями

Перепишем его в стандартном виде , откуда находим , по и запишем ЛРС

Множества, функции, отношения

Множества и операции над ними

Основные понятия теории множеств:

Определение: Множеством М  называется объединение в единое целое определенных различимых однотипных объектов , которые называются элементами множества.

Множество можно описать, указав какое-то свойство, присущее всем элементам этого множества.

Замечание. Вообще говоря, понятие множества считается первичным (исходным) понятием, и, как таковое, не определяется. Приведённое выше определение следует, скорее, считать уточнением понятия множества.

Множество, все элементы которого являются числами, называется числовым. В дальнейшем мы будем, прежде всего, рассматривать именно такие множества. Множество, элементами которого являются другие множества, называется классом или семейством.

Множество, содержащее конечное число элементов, называется конечным. При подсчёте количества элементов учитываются только различные (неповторяющиеся) элементы.

Множество, не содержащее элементов, называется пустым и обозначается символом

Множество может быть задано перечислением (списком) своих элементов, порождающей процедурой или описанием характеристических свойств (предикатом), которым должны обладать его элементы. Причём в последнем случае необходимо формулировать описание характеристических свойств элементов множества достаточно корректно, для того, чтобы множество было определено вполне однозначно. Добавим, что многие числовые множества могут быть заданы всеми тремя указанными способами (например, множество четных однозначных чисел).

Пример №29

Некоторые примеры множеств, заданных различными способами.

а)  б)  в) 

Мощностью конечного множества называется количество его элементов. Обозначается . Если то множества A и В называются равномощными.

Определение: Если все элементы множества являются также элементами множества В, то говорят, что множество  включается (содержится) в множестве В.

Определение: Если A с В, то множество A называется подмножеством множества В (также говорят, что В  покрывает A). Если при этом , то множество A называется собственным подмножеством множества В  и обозначается .

Замечание. Не следует считать равносильными отношения принадлежности  и вхождения одного множества в другое . Можно привести следующий пример. Пусть А — множество всех студентов данной группы, а В — множество всех учебных групп данного института. Здесь , но , поскольку элементы этих множеств разнородны. Этот пример показывает также, что элементами множеств могут являться другие множества.

Парадокс Рассела. Задание множеств характеристическим предикатом может привести к противоречиям. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента: . Если такое множество существует, то можно ответить на следующий вопрос: принадлежит ли оно само себе. С одной стороны, если , то . С другой стороны, если , то ! Это противоречие можно разрешить различными способами, в целом сводящимся к тому, что Y  не является множеством.

Для трех множеств А, В, С справедливы следующие соотношения:

Связь между включением и равенством множеств устанавливается следующим соотношением:

Здесь знак обозначает конъюнкцию (логическое «и»).

В заключение добавим, что Г. Кантор предложил использовать понятие «универсального множества» (универсум), как бы противоположного понятию пустого множества. По мысли Кантора, универсальное множество содержит все мыслимые множества, и при этом оно само содержится во множестве своих подмножеств в качестве элемента. В дальнейшем смысл и содержание понятия универсального множества будут раскрыты более подробно.

Операции над множествами и их свойства

Определение: Объединением множеств А и В называется множество С, элементы которого принадлежат хотя бы одному из множеств А и В. Обозначается . 

Геометрическое изображение множеств в виде области на плоскости называется диаграммой Эйлера-Вэйна.

Определение: Пересечением множеств А и В называется множество С, элементы которого принадлежат каждому из множеств А и В. Обозначение .

Для множеств А, В и С справедливы следующие свойства:

Определение: Разностью множеств А и В  называется множество, состоящее из элементов множества А, не принадлежащих множеству В. Обозначается:

Определение: Симметрической разностью множеств А и В называется множество С, элементы которого принадлежат в точности одному из множеств А или В. Обозначается:

Определение:   называется дополнением множества А относительно множества Е, если . Для множеств А, В и С справедливы следующие соотношения:

Пример №30

Исходя из определения равенства множеств и операций над множествами, доказать тождество и проверить его с помощью диаграммы Эйлера-Вэйна.

Из записанных выше соотношений видно, что

Что и требовалось доказать. Для иллюстрации полученного результата построим диаграммы Эйлера — Вэйна:

Пример №31

Исходя из определения равенства множеств и операций над множествами, доказать тождество.

Если некоторый элемент , то это означает, что этот элемент принадлежит множеству А, но не принадлежит множествам В и С.

Множество представляет собой множество элементов множества А, не принадлежащих множеству В.

Множество представляет собой множество элементов множества А, не принадлежащих множеству С.

Множество представляет собой множество элементов, которые принадлежат множеству А, но не принадлежат ни множеству В, ни множеству С.

Таким образом, тождество можно считать доказанным.

Векторы и прямые произведения

Вектором (кортежем) в линейной алгебре и дискретной математике называют упорядоченный набор элементов. Это не есть определение вектора, поскольку целесообразнее это понятие считать основным.

Элементы, определяющие вектор, называются координатами или компонентами. Координаты нумеруются слева направо, а их число называется длиной или размерностью вектора. В отличие от элементов множества, координаты вектора могут совпадать. Координаты вектора заключаются в круглые скобки, например . Иногда скобки или запятые опускаются. Часто векторы длины 2 называются упорядоченными парами, длины 3 — тройками и т. д.

Определение: Два вектора равны, если они имеют равную длину и их соответствующие координаты равны. Иначе говоря, векторы и равны, если .

Определение: Прямым произведением множеств А и В (обозначение ) называется множество всех упорядоченных пар , таких, что . В частности, если А=В, то обе координаты принадлежат множеству А, такое произведение обозначается 

Аналогично, прямым произведением множеств называется множество всех векторов  длины , таких, что .

Пример №32

Множество — это множество всех упорядоченных пар действительных чисел, геометрической интерпретацией которого служит декартова координатная плоскость.

Координатное представление точек плоскости было впервые предложено Р.Декартом и исторически является первым примером прямого произведения. Поэтому часто прямое произведение множеств называют декартовым произведением.

Пример №33

Даны множества  и . Тогда есть множество обозначений клеток шахматной доски.

Вообще конечное множество, элементами которого являются какие-либо символы (буквы, цифры, знаки препинания, знаки операций и т. д.) называется алфавитом. Любые элементы множества в этом случае являются словами длины в алфавите А. Например, десятичное целое число — это слово в алфавите цифр.

Определение: Проекцией вектора на некоторую ось называется его компонента (координата) с соответствующим порядковым номером (обозначается ). Например, проекция точки плоскости на 1-ю ось есть её абсцисса (первая координата).

Теорема 1.1. Мощность произведения конечных множеств равна произведению мощностей этих множеств:  

Следствие.

Эта простая теорема и сё следствие впоследствии широко используются в комбинаторике.

Соответствия и функции

Соответствия

Определение: Соответствием между множествами А и В называется некоторое подмножество G их декартова произведения: .

Если , то говорят, что b  соответствует а  при соответствии G . При этом множество всех таких а называют областью определения соответствия D(G), а множество соответствующих значений b называются областью значений соответствия E(G).

В принятых обозначениях, каждый элемент , соответствующий данному элементу называется  образом  а  при соответствии G , наоборот, элемент называется  прообразом  элемента при данном соответствии.

Соответствие называется полностью определённым, если D(G) = А, то есть каждый элемент множества А имеет хотя бы один образ во множестве В;  в противном случае соответствие называется частичным.

Соответствие G называется сюрьективным, если E(G) = В, то есть если каждому элементу множества В соответствует хотя бы один прообраз во множестве А .

Соответствие G  называется функциональным (однозначным), если любому элементу множества А соответствует единственный элемент множества В.

Соответствие называется иньективным, если оно является функциональным, и при этом каждый элемент множества В  имеет не более одного прообраза.

Соответствие G называется взаимнооднозначным (биективным), если любому элементу множества А соответствует единственный элемент множества В, и наоборот. Можно сказать также, что соответствие является взаимнооднозначным, если оно является полностью определённым, сюръектпвным, функциональным, и при этом каждый элемент множества В имеет единственный прообраз.

Пример №34

а) Англо-русский словарь устанавливает соответствие между множествами слов русского и английского языка. Оно не является функциональным, так как почти каждому русскому слову соответствует несколько английских переводов; оно, также, не является, как правило, полностью определённым соответствием, так как всегда существуют английские слова, не включённые в данный словарь. Таким образом, это частичное соответствие.

б) Соответствие между аргументами функции и значениями этой функции является функциональным. Однако оно не является взаимнооднозначным, так как каждому значению функции   соответствуют два прообраза

в) Соответствие между расположенными на шахматной доске фигурами и занимаемыми ими полями является взаимно однозначным.

г) Соответствие между телефонами города Вязьмы и их пятизначными номерами обладает, на первый взгляд, всеми свойствами взаимнооднозначного соответствия. Однако оно, например, не сюръективно, поскольку существуют пятизначные числа, не соответствующие никаким телефонам.

Взаимнооднозначные соответствия и мощности множеств

Если между двумя конечными множествами А и В существует взаимнооднозначное соответствие, то эти множества равномощны. Этот очевидный факт позволяет, во-первых, установить равенство мощности этих множеств, не вычисляя их. Во-вторых, часто можно вычислить мощность множества, установив его однозначное соответствие с множеством, мощность которого известна, либо легко вычисляется.

Теорема 2.1. Если мощность конечного множества А равна  n, то число всех подмножеств А равно , то есть.

Множество всех подмножеств множества М  называется булеаном и обозначается .

Для конечных множеств выполняется: .

Определение: Множества А и В называются равномощными, если между их элементами можно установить взаимнооднозначное соответствие.

Заметим, что для конечных множеств это утверждение легко доказать. Для бесконечных множеств оно определят само понятие равномощности.

Определение: Множество А называется счётным, если оно равномощно множеству натуральных чисел

Очень упрощённо можно сказать, что данное бесконечное множество является счётным, если для его элементов можно установить нумерацию с помощью натуральных чисел.

Без доказательства примем ряд важных фактов:

1. Любое бесконечное подмножество множества натуральных чисел является счётным.
2. Множество является счётным.
3. Множество рациональных чисел R является счётным (является следствием из предыдущего утверждения).
4. Объединение конечного числа счётных множеств является счётным.
5. Объединение счётного числа конечных множеств является счётным.
6. Объединение счётного числа счётных множеств является счётным.

Все эти утверждения, как можно видеть, позволяют достаточно успешно устанавливать факт, что данное множество является счётным. Однако сейчас будет показано, что не всякое бесконечное множества является счётным; существует множества большей мощности.  

Теорема 2.2 (теорема Кантора). Множество всех действительных чисел из отрезка [0; 1] не является счётным.

Доказательство. Допустим, что множество является счётным и существует его нумерация. Поскольку любое действительное число можно представить в виде бесконечной десятичной дроби (периодической или непериодической), то проделаем это с числами данного множества. Расположим их в порядке этой нумерации:

Теперь рассмотрим любую бесконечную десятичную дробь вида , организованную таким образом, что и так далее. Очевидно, что данная дробь не входит в рассматриваемую последовательность, поскольку от первого числа она отличается первой цифрой после запятой, от второго — второй цифрой и так далее. Следовательно, мы получили число из данного интервала, которое не пронумеровано и, таким образом, множество М  не является счётным. Его мощность называется континуум, а множества такой мощности называются континуальными. Приведённый метод доказательства называется диагональным методом Кантора.

Следствие 1. Множество действительных чисел R  континуально.

Следствие 2. Множество всех подмножеств счётного множества континуально. Как показывается в теории множеств (с помощью метода, аналогичного приведённому выше), для множества любой мощности множество всех его подмножеств (булеан) имеет более высокую мощность. Поэтому не существует множества максимальной мощности. Например, множество-универсум , описанное Кантором должно содержать все мыслимые множества, однако оно само содержится в множестве своих подмножеств в качестве элемента (парадокс Кантора). Получается, что множество не является множеством максимальной мощности.

Отображения и функции

Функцией называется любое функциональное соответствие между двумя множествами. Если функция устанавливает соответствие между множествами А и В, то говорят, что функция имеет вид (обозначение ). Каждому элементу а   из своей области определения функция ставит в соответствие единственный элемент  b  из области значений. Это записывается в традиционной форме . Элемент а  называется аргументом функции, элемент b — её значением.

Полностью определённая функция называется отображением  А в В; образ множества А при отображении обозначается . Если при этом , то есть соответствие сюръективно, говорят, что имеет отображение А на В.

Если состоит из единственного элемента, то называется функцией-константой.

Отображение типа называется преобразованием множества А.

Пример №35

а) Функция является отображением множества натуральных чисел в себя (инъективная функция). Эта же функция при всех является отображением множества целых чисел в множество рациональных чисел.

б) Функция является отображением множества целых чисел (кроме числа 0) на множество натуральных чисел. Причём в данном случае соответствие не является взаимно однозначным.

в) Функция является взаимнооднозначным отображением множества действительных чисел на себя.

г) Функция не полностью определена, если её тип , но полностью определена, если её тип или .

Определение: Функция типа называется -местной функцией. В этом случае принято считать, что функция имеет аргументов: , где  

Например, сложение, умножение, вычитание и деление являются двухместными функциями на , то есть функциями типа .

Определение: Пусть дано соответствие . Если соответствие таково, что тогда и только тогда, когда , то соответствие называют  обратным к и обозначают .

Определение: Если соответствие, обратное к функции является функциональным, то оно называется функцией, обратной к .

Очевидно, что в обратном соответствии образы и прообразы меняются местами, поэтому для существования обратной функции требуется, чтобы каждый элемент из области значения имел бы единственный прообраз. Это означает, что для функции  обратная функция существует тогда и только тогда, когда является биективным соответствием между своей областью определения и областью значений.

Пример №36

Функция имеет тип . Отрезок отображает на отрезок [ -1 ; 1 ]. Поэтому для неё на отрезке [ -1 ; 1 ] существует обратная функция. Как известно, это .

Определение: Пусть даны функции . Функция  называется композицией функций и  ), если имеет место равенство: .

Композиция функций  и  представляет собой последовательное применение этих функций; применяется к результату. Часто говорят, что функция получена подстановкой в .

Для многоместных функций  возможны различные варианты подстановок в , дающие функции различных типов. Особый интерес представляет случай, когда задано множество функций типа: . В этом случае возможны, во-первых, любые подстановки функций друг в друга, а во-вторых, любые переименования аргументов. Функция, полученная из данных функций некоторой подстановкой их друг в друга и переименованием аргументов, называется их суперпозицией.

Например, в математическом анализе вводится понятие элементарной функции, являющейся суперпозицией фиксированного (не зависящего от значения аргумента) числа арифметических операций, а также элементарных функций ( и т. п.).

А.Н. Колмогоровым и В.И. Арнольдом доказано, что всякая непрерывная функция  переменных представима в виде суперпозиции непрерывных функций двух переменных.

Замечание. Понятие функции широко используется в математическом анализе, более того, является в нём базовым понятием. В целом, подход к пониманию термина «функция» в матанализе несколько уже, чем в дискретной математике. Как правило, в нём рассматриваются так называемые вычислимые функции. Функция называется вычислимой, если задана процедура, позволяющая по любому заданному значению аргумента найти значение функции.

Отношения и их свойства

Основные понятия и определения:

Определение: Подмножество называется -местным ( — мерным) отношением на множестве А. Говорят, что элементы находятся в отношении , если .

Одноместное (одномерное) отношение — это просто некоторое подмножество А. Такие отношения называют признаками. Говорят, что обладает признаком R, если . Свойства одноместных отношений — это свойства подмножеств А, поэтому для случая = 1 термин «отношения» употребляется редко.

Наиболее часто встречающимися и хорошо изученными являются двухместные или бинарные отношения. Если  а  и  b  находятся в отношении R , это обычно записывается в виде .

Пример:

Бинарные отношения на множестве N .

а) Отношение выполняется для пар (7;9), (7;7) и не выполняется для пары (9;7). б) Отношение «иметь общий делитель, не равный единице» выполняется для пар (3; 6), (4; 10) и не выполняется для пар (6; 5), (11;3). в) Отношение «быть делителем» выполняется для пар (2; 6), (5; 5) и не выполняется для пар (4;2),(6;1).

Пример:

Бинарные отношения на множестве точек координатной плоскости.

а) Отношение «быть равноудалёнными от начала координат» выполнятся для пар точек (1;-4) и (-4;1), но не выполнятся для пары точек (3;0) и (-2; 6). б) Отношение «принадлежать окружности, центр которой находится в начале координат», выполняется для первой пары точек из предыдущего примера и не выполняется для второй пары. в) Отношение «быть удалёнными на разное расстояние от начала координат» выполняется для всех точек, для которых не выполняется отношение, описанное в пункте «б».

Пусть дано отношение   на множестве . Для любого подмножества определяется отношение , называемое сужением на , которое получается из отношения удалением всех пар, содержащих элементы, не принадлежащие . Иначе говоря, — .

Строго говоря, само отношение   и его сужение — это разные отношения, с разными областями определения. Однако, по умолчанию, если не возникает явных разночтений, эта разница не учитывается. Например, вполне можно говорить об отношении «быть делителем», не уточняя, задано оно на множестве или на каком-нибудь его подмножестве.

Для задания бинарных отношений можно использовать любые способы задания множеств (например, список пар, для которых данное отношение выполняется). Отношения на конечных множествах обычно задаются списком или матрицей. Матрица бинарного отношения на конечном множестве — это квадратная матрица порядка , в которой каждый элемент определяется следующим образом:

Пример:

Для конечного множества матрицы отношении из примера 1 (а — в) приведены в следующих таблицах.

а)                         

б)                           

в)                        

Поскольку отношения на множестве задаются подмножествами , для отношений можно определить те же операции, что и для множеств. Например, отношение является объединением отношений и

Определение: Отношение называется обратным к отношению , если   тогда и только тогда, когда

Непосредственно из определения следует, что . Например, для отношения обратным является отношение

Свойства отношений

Определение: Отношение   называется рефлексивным, если для любого элемента имеет место .

Главная диагональ матрицы рефлексивного отношения содержит только единицы.

Определение: Отношение называется антирефлексивным, если ни для какого элемента не выполняется .

Главная диагональ матрицы рефлексивного отношения содержит только нули.

Например, отношения и «иметь общий делитель» являются рефлексивными. Отношения и «иметь сына» являются антирефлексивными. Отношение «быть симметричным относительно оси абсцисс» не является ни рефлексивным, ни антирсфлексив-ным: точка плоскости симметрична сама себе, если лежит на этой оси, и не симметрична себе, если не лежит на ней.

Определение: Отношение называется симметричным, если для любой пары из отношения следует . Иными словами, отношение R является симметричным тогда и только тогда, когда для любой пары оно выполняется в обе стороны (или вовсе не выполняется).

Матрица симметричного отношения симметрична относительно главной диагонали: .

Определение: Отношение называется антисимметричным, если из отношений и следует, что .

Отношение «быть симметричным относительно оси абсцисс» является симметричным: если первая точка симметрична второй относительно этой оси, то и вторая точка симметрична первой. Отношение является антисимметричным. Действительно, если , это означает, что .

Нетрудно убедиться в том, что отношение симметрично тогда и только тогда, когда .

Определение: Отношение называется транзитивным, если для любых  а,b,с  из отношений и   следует .

Отношения «быть равным», «жить в одном городе», «быть параллельным» являются транзитивными. Отношения «пересекаться», «быть сыном» не являются транзитивными.

Замечание. В отличие от отношений рефлексивности и симметричности, для отношения транзитивности не формулируется противоположного понятия (антитранзитивности).

Определение: Транзитивным замыканием отношения называется отношение, определяемое следующим образом: если в множестве существует цепочка из элементов , в которой между каждыми двумя соседними элементами выполняется отношение , то говорят, что существует транзитивное замыкание .

Замечание. Замыкание является весьма общим математическим понятием. Упрощенно говоря, замкнутость означает, что многократное повторение допустимых шагов не выводит за определённые границы. Например, множество натуральных чисел замкнуто относительно операции сложения, однако открыто (то есть незамкнуто) относительно операции деления.

Если отношение транзитивно, то, очевидно, (и наоборот). Например, отношение «быть делителем» транзитивно для любой цепочки элементов и само является транзитивным замыканием этого отношения.

Если отношение не транзитивно, то

Например, транзитивным замыканием отношения «быть сыном» является отношение «быть прямым потомком», включающее в себя понятия «быть сыном», «быть внуком», «быть правнуком» и так далее.

Основные виды отношений

Из содержания предыдущей лекции и рассмотренных в ней примеров видно, что понятие «отношение» следует понимать весьма широко. В данной лекции мы попытаемся ввести определённую классификацию отношений и рассмотреть наиболее значительные с точки зрения математики виды отношений — а именно отношения эквивалентности и порядка.

Отношения эквивалентности

Определение: Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно.

Пример 1.

а) Отношение равенства (часто обозначается ) на любом множестве является отношением эквивалентности. Равенство — это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из этого отношения (то есть любой единицы на главной диагонали матрицы ) оно перестаёт быть рефлексивным и, следовательно, уже не является эквивалентностью.

б) Утверждения вида или , состоящие из формул, соединённых знаком равенства, задают бинарное отношение на множестве формул, описывающих суперпозиции элементарных функций. Это отношение обычно называется отношением равносильности и определяется следующим образом: две формулы равносильны, если они задают одну и ту же функцию. Равносильность в данном случае, хотя и обозначена знаком означает не то же самое, что отношение равенства, так как оно может выполняться для различных формул. Впрочем, можно считать, что знак равенства в таких отношениях относится не к самим формулам, а к функциям, которые ими описываются. Для формул же отношение равенства — это совпадение формул по написанию. Оно называется графическим равенством. Кстати, чтобы в подобных ситуациях избежать разночтений, часто для обозначения отношения равносильности используют знак

в) Рассмотрим множество треугольников на координатной плоскости, считая, что треугольник задан, если даны координаты его вершин. Два треугольника будем считать равными (конгруэнтными), если при наложении они совпадают, то есть, переведены друг в друга с помощью некоторого перемещения. Равенство является отношением эквивалентности на множестве треугольников.

г) Отношение «иметь один и тот же остаток отделения на натуральное число » на множестве натуральных чисел является отношением эквивалентности.

е) Отношение «быть делителем» не является на множестве отношением эквивалентности. Оно обладает свойствами рефлексивности и транзитивности, но является антисимметричным (см. ниже).

Пусть на множестве задано отношение эквивалентности . Осуществим следующее построение. Выберем элемент и образуем класс (подмножество ), состоящий из элемента , и всех элементов, эквивалентных ему в рамках данного отношения. Затем выберем элемент , и образуем класс , состоящий из и эквивалентных ему элементов. Продолжая эти действия, получим систему классов (возможно, бесконечную) такую, что любой элемент из множества входит хотя бы в один класс, то есть

Эта система обладает следующими свойствами:

1) она образует разбиение множества , то есть классы попарно не пересекаются; 2) любые два элемента из одного класса эквивалентны; 3) любые два элемента из разных классов не эквивалентны.

Все эти свойства прямо следуют из определения отношения эквивалентности. Действительно, если бы, например, классы и , пресекались, то они имели бы хотя бы один общий элемент. Этот элемент был бы, очевидно, эквивалентен и . Тогда, в силу транзитивности отношения выполнялось бы . Однако, по способу построения классов, это не возможно. Аналогично можно доказать другие два свойства.

Построенное разбиение, то есть система классов — подмножеств множества , называется системой классов эквивалентности по отношению . Мощность этой системы называется индексом разбиения. С другой стороны, любое разбиение множества на классы само определяет некоторое отношение эквивалентности, а именно отношение «входить в один класс данного разбиения».

Пример 2.

а) Все классы эквивалентности по отношению равенства состоят из одного элемента. б) Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. В данном случае счётными являются само множество формул, множество классов эквивалентности (то есть индекс разбиения) и каждый класс эквивалентности. в) Разбиение множества треугольников по отношению равенства имеет континуальный индекс, причём каждый класс имеет также мощность континуум. г) Разбиение множества натуральных чисел по отношению «иметь общий остаток при делении на 7» имеет конечный индекс 7 и состоит из семи счётных классов.

Отношения порядка

Определение 1. Отношение называется отношением нестрогого порядка, если оно является рефлексивным, антисимметричным и транзитивным.

Определение 2. Отношение называется отношением строгого порядка, если оно является антирефлексивным, антисимметричным и транзитивным.

Оба типа отношений вместе называются отношениями порядка. Элементы  сравнимы по отношению порядка , если выполняется одно из двух отношений или . Множество , на котором задано отношение порядка, называется полностью упорядоченным, если любые два его элемента сравнимы. В противном случае, множество называется частично упорядоченным.

Пример 3.

а) Отношения и являются отношениями нестрогого порядка, отношения и — отношениями строгого порядка (на всех основных числовых множествах). Оба отношения полностью упорядочивают множества и .

б) Определим отношения и на множестве следующим образом:

1)  

2)   если и при этом ходя бы для одной  i — ой координаты выполняется

Тогда, например, (1, 2, 3) < (1, 2,4), но (1,2,3) и (1,-2,4) несравнимы. Таким образом, эти отношения частично упорядочивают .

в) На системе подмножеств множества отношение включения задаёт нестрогий частичный порядок, а отношение строгого включения задаёт строгий частичный порядок. Например, {l, 2} {l, 2, З}, a {l, 2} и {l, 3, 4} не сравнимы.

г) Отношение подчинённости в трудовом коллективе создаёт строгий частичный порядок. В нём, например, несравнимыми являются сотрудники различных структурных подразделений (отделов и т. п.).

д) В алфавите русского языка порядок букв зафиксирован, то есть всегда один и тот же. Тогда этот список определяет полное упорядочение букв, которое называется отношением предшествования. Обозначается ; ( предшествует ). Ha основании отношения предшествования букв построено отношение предшествования слов, определяемое примерно, таким образом, как производится сравнение двух десятичных дробей. Это отношение задаёт полное упорядочение слов в русском алфавите, которое называется лексикографическим упорядочением.

Пример 4.

а) Наиболее известным примером лексикографического упорядочения слов является упорядочение слов в словарях. Например, лес лето (так как с  m ), поэтому слово лес расположено в словаре раньше слова лето.

б) Если рассматривать числа в позиционных системах счисления (например, в десятичной системе) как слова в алфавите цифр, то их лексикографическое упорядочение совпадает с обычным, если все сравниваемые числа имеют одинаковое количество разрядов. В общем же случае эти два вида могут не совпадать. Например, 10 < 1073  и  20 < 1073,  но  10 1073,  а  20  1073. Для того, чтобы они совпадали, нужно уравнять число разрядов у всех сравниваемых чисел, приписывая слева нули. В данном примере при этом получим  0020  1073. Такое выравнивание происходит автоматически при записи целых чисел в ЭВМ.

в) Лексикографическое упорядочивание цифровых представлений дат вида 19.07.2004 (девятнадцатое июля две тысячи четвёртого года) не совпадает с естественным упорядочением дат от более ранних к более поздним. Например, дата 19.07.2004 «лексикографически» старше восемнадцатого числа любого года. Чтобы возрастание дат совпадало с лексикографическим упорядочением, обычное представление надо «перевернуть», то есть записать в виде 2004.07.19. так обычно делают при представлении дат в памяти ЭВМ.

Введение в общую алгебру

Свойства бинарных алгебраических операций:

Определение: На множестве А  определена алгебраическая операция, если каждым двум элементам этого множества, взятым в определенном порядке, однозначным образом поставлен в соответствие некоторый третий элемент из этого же множества.

Примерами алгебраических операций могут служить такие операции как сложение и вычитание целых чисел, сложение и вычитание векторов, матриц, умножение квадратных матриц, векторное умножение векторов и др.

Отметим, что скалярное произведение векторов не может считаться алгебраической операцией, т.к. результатом скалярного произведения будет число, и числа не относятся к множеству векторов, к которому относятся сомножители.

Замечание. Вообще говоря, операция, определённая таким образом, называется бинарной, поскольку в ней участвуют два элемента. Но также можно говорить об унарных операциях, в которых участвует только один элемент данного множества, и в соответствие ему однозначным образом поставлен второй элемент этого множества. Таковы, например, операции извлечения корня квадратного или нахождения модуля числа.

Аналогично можно определить тринарную  и прочие операции на данном множестве, в зависимости от количества участвующих в них элементов. В общем случае, — арной операцией на множестве будем называть функцию типа .

Определение: Операция , отображающая любой элемент множества в себя, называется тождественной операцией.

Тождественной операцией на множестве , например, является умножение на единицу.

Для того чтобы описанные ниже соотношения выглядели бы более привычно, положим результат применения бинарной операции элементам  записывать не в функциональном виде , а виде , принятом для записи арифметических операций.

Определение: Операция  называется коммутативной, если для любых элементов выполняется: .

Операции сложения и умножения чисел коммутативны, а вычитание и деление некоммутативны. Также некоммутативна операция умножения матриц (как известно из курса линейной алгебры).

Определение: Операция называется ассоциативной, если для любых элементов выполняется: .

Выполнение условия ассоциативности означает, что скобки в выражении можно не расставлять. Сложение и умножение чисел ассоциативны, что и позволяет не ставить скобки в выражениях типа и . В качестве примера неассоциативной операции можно привести возведение в степень:

.

Правда, запись является допустимой, но служит сокращением записи выражения , а не сокращённая запись которого — ). Важным примером ассоциативной операции является композиция отображений.

Определение: Операция называется  дистрибутивной  слева  относительно операции , если для любых выполняется:

,

и дистрибутивной справа относительно операции , если для любых выполняется:

Наличие свойства дистрибутивности позволяет раскрывать скобки. Например, умножение дистрибутивно относительно сложения (и вычитания) и справа, и слева:

Возведение в степень дистрибутивно относительно умножения справа: , но не слева: . Сложение (и вычитание) чисел недистрибутивно относительно умножения: . Ниже будет показано, что операции пересечения и объединения множеств дистрибутивны относительно друг друга и слева, и справа.

Алгебраические структуры

Определение: Пусть дано некоторое множество , на котором задана совокупность операций . Структура вида называется алгеброй; множество называется несущим множеством, совокупность операций — сигнатурой, вектор «арностей» операций называется типом.

Определение: Множество называют замкнутым относительно — арной операции на множестве , если значения функции на аргументах  принадлежат  (то сеть . Если множество замкнуто относительно всех операций , то структура называется подалгеброй алгебры .

Пример 1.

а) Алгебра называется полем действительных чисел (определение понятия поля будет дано ниже). Её тип — (2,2). Это означает, что сигнатура данной алгебры содержит две бинарные операции. Здесь все конечные подмножества (кроме множества ) не замкнуты относительно обеих операций и, следовательно, не могут образовывать подалгебры. Но алгебра вида — поле действительных чисел — образует подалгебру.

б) Пусть задано множество . Множество всех его подмножеств — булеан, обозначается как или . Алгебраназывается булевой алгеброй множеств над множеством . Её тип: (2,2,1). Для любого будет являться подалгеброй

в) Множество одноместных функций на (то есть функций вместе с унарной операцией дифференцирования является алгеброй. Множество элементарных функций замкнуто относительно этой операции (поскольку производная любой элементарной функции есть также элементарная функция), поэтому образует подалгебру данной алгебры.

Определение: Замыканием множества относительно сигнатуры (обозначается) называется множество всех элементов, которые можно получить из элементов этого множества, применяя операции из сигнатуры (включая сами элементы ).

Например, в алгебре целых чисел замыканием числа 2 является множество чётных чисел.

Теорема 5.1. Непустое пересечение подалгебр образует подалгебру.

Гомоморфизм и изоморфизм

Алгебры с различными типами (в смысле, определённом в пункте 1), очевидно, имеют существенно различное строение. Если же алгебры имеют одинаковый тип, то наличие у них сходства характеризуется вводимых ниже понятий.

Определение: Пусть даны две алгебры и . Гомоморфизмом алгебры А в алгебру В  называется функция, такая, что для всех выполняется условие:

Смысл данного определения состоит в следующем. Независимо от того, выполнена ли сначала операция в алгебре , а потом произведено отображение , либо сначала произведено отображение , а потом в алгебре выполнена соответствующая операция  результат будет одинаков.

Сейчас мы определим некоторые виды гомоморфизма, обладающие дополнительными свойствами.

Определение: Гомоморфизм, который является инъекцией, называется мономорфизмом.

Определение: Гомоморфизм, который является сюръекцией, называется эпиморфизмом.

Определение: Гомоморфизм, который является биекцией, называется изоморфизмом.

Таким образом, можно сказать, что изоморфизм — это взаимно однозначный гомоморфизм.

Замечание. Если множества-носители двух данных алгебр равны, то их гомоморфизм называется эндоморфизмом, а изоморфизм — автоморфизмом.

Теорема 5.2. Если и — две алгебры одного типа и — изоморфизм, то — тоже изоморфизм.

Пример 2.

а) Пусть — множество натуральных чисел, — множество натуральных чётных чисел. Алгебры и изоморфны; изоморфизмом является отображение , причём условие (*) здесь имеет вид . Поскольку , то данный изоморфизм есть изоморфизм алгебры в себя.

б) Изоморфизмом между алгебрами и является, например, отображение . Условие (*) имеет вид .

в) Булевы алгебры, образованные двумя различными множествами одинаковой мощности, изоморфны: операции у них просто одинаковы (см. выше), а отображением может служить любое взаимнооднозначное соответствие.

Теорема 5.3. Отношение изоморфизма является отношением эквивалентности на множестве алгебр.

Понятие изоморфизма является одним из важнейших понятий в математике. Его сущность можно выразить следующим образом. Если две алгебры изоморфны, то элементы и операции любой из них можно переименовать таким образом, что эти алгебры совпадут. Это позволяет, получив некоторое эквивалентное соотношение в данной алгебре, распространять его на любую изоморфную ей алгебру. Распространённое в математике выражение «с точностью до изоморфизма» означает, что рассматриваются только те свойства объектов, которые сохраняются при изоморфизме, то есть являются общими для всех изоморфных объектов. В частности, изоморфизм сохраняет коммутативность, ассоциативность и дистрибутивность.

Различные виды алгебраических структур

Полугруппы

Определение: Полугруппой называется алгебра вида с одной ассоциативной бинарной операцией .

Как правило, в качестве такой операции используется умножение. Поэтому результат её применения к двум различным элементам записывают в виде или , а результат неоднократного применения к одному элементу записывают в виде и так далее. Такая запись называется мультипликативной. Полугруппу часто обозначают записью .

Замечание. Не следует понимать сказанное выше в том смысле, что полугруппа всегда включает в себя именно арифметическую операцию умножения. Термин «умножение» здесь является достаточно условным. Символ применяется именно для того, чтобы указать на это. Под символом может пониматься и произведение матриц или векторов, и композиция каких-либо преобразований, и даже сложение.

В общем случае, (как, например, произведение матриц), то есть данная операция некоммутативна. Если же умножение коммутативно, то полугруппа называется коммутативной или  абелевой  полугруппой.

Если множество-носитель полугруппы содержит такой элемент , что для любого выполняется , то этот элемент называется единицей (нейтральным элементом), а такая полугруппа называется моноидом. Легко показать, что если полугруппа содержит единицу, то она единственна. Действительно, допустим, существуют две единицы и . Тогда и , следовательно .

Пример 1.

а) Алгебра , где — множество чётных чисел является абелевой полугруппой. Однако, очевидно, она не имеет единицы.

б) Алгебра , где -множество квадратных матриц одинаковой размерности образует некоммутативную полугруппу. Причём эта полугруппа является моноидом, а роль единицы в ней выполняет единичная матрица .

в) Алгебра является коммутативной полугруппой с единицей.

Определение: Если любой элемент полугруппы можно представить в виде произведения конечного числа элементов множества , то множество называется порождающим множеством или системой образующих полугруппы, а его элементы называются образующими.

Например, в полугруппе порождающим множеством служит бесконечное множество простых чисел.

Определение: Полугруппа, которая имеет только одну образующую, называется циклической.

Можно показать, что в циклической полугруппе все элементы являются степенями (в смысле имеющейся операции) этой образующей. Например, циклической полугруппой является полугруппа , поскольку любое натуральное число — это сумма некоторого количества единиц.

Пусть полугруппа имеет конечное число образующих  Если в записи опустить обозначение операции (как это обычно делается для умножения), то все элементы полугруппы можно рассматривать как слова в алфавите . Причём некоторые различные слова могут оказаться равными, как элементы (равные элементы записаны различными словами). В коммутативной полугруппе для двух любых элементов выполняется равенство , позволяющее устанавливать равенство элементов, в том числе, записанных различными словами. Подобные равенства называются определяющими соотношениями.

Определение: Полугруппа, в которой нет определяющих соотношений, и любые два различных слова обозначают различные элементы группы, называется свободной.

Доказано, что каждую полугруппу можно получить из некоторой свободной полугруппы введением некоторых определяющих соотношений. Элементы заданной так полугруппы — это слова в алфавите образующих, причём некоторые слова равны (то есть задают один элемент) в силу определяющих соотношений. Они позволяют из любого слова получить любые эквивалентные ему слова. Отношение равенства слов есть отношение эквивалентности. Кстати, намного сложнее выяснить для двух данных слов, можно ли получить одно из другого с помощью определяющих соотношений. Исследование этой проблемы оказало значительное влияние на теорию алгоритмов.

Группы

Определение 1. Группой называется полугруппа с единицей, в которой для каждого элемента существует элемент называемый обратным к элементу и удовлетворяющий условию

Если не использовать в определении понятие полугруппы, то определить понятие группы можно следующим образом.

Определение 2. Множество с определенной на нем алгебраической операцией (например, умножением) называется группой, если выполнены следующие условия:

1) для любых трех элементов выполняется свойство ассоциативности:

2) в множестве существует такой элемент , что для любого элемента из этого множества выполняется равенство:

3) для любого элемента существует элемент из этого же множества такой, что

Замечание. Различные множества могут образовывать группу относительно какой-либо операции и не являться группой относительно другой операции.

Число элементов в множестве-носителе называется порядком группы. Группа, в которой операция коммутативна, называется коммутативной или абелевой. Группа, в которой все элементы являются степенями одного элемента, называется циклической. Для абелевых групп часто применяется аддитивная форма записи: операция обозначается, как сложение, а единица обозначается, как 0.

Пример 2.

а)  является абелевой циклической группой, в которой роль единицы играет 0,  а роль элемента, обратного к элементу играет .

б) Алгебра