Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами.
Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Подобие Для Линейно Упорядоченных Множеств - Есть Бинарное Отношение Между Ли...
Подобие для линейно упорядоченных множеств - есть бинарное отношение между линейно упорядоченными множествами, являющееся отношением эквивалентности. Фактор-множество по этому отношению эквивалентности состоит из классов линейно упорядоченных множеств, так что в один класс попадают все подобные между собой множества.
Каждому такому классу поставим в соответствие символ, и будем называть его порядковым типом любого множества данного класса.
Порядковый тип линейно упорядоченного множества обозначают . Если множества и подобны, то они имеют один и тот же порядковый тип: .
Все множества, имеющие один и тот же порядковый тип , имеют одинаковую мощность, которую обозначают . Таким образом, если , то .
Определение 4: Пусть - линейно упорядоченное множество и . Множество всех элементов , строго предшествующих элементу , называют отрезком, отсекаемым элементом от множества и обозначают . Отметим, что сам элемент в отрезок не входит.
Можно доказать, что множество всех отрезков линейно упорядоченного множества подобно множеству .
Замечание: Можно заметить, что каждое конечное линейно упорядоченное множество удовлетворяет условию минимальности, и потому, вполне упорядочено, т.е. является отрезком натурального ряда чисел.
Для бесконечных множеств это не так. Как уже отмечалось, множества натуральных, целых и рациональных чисел эквивалентны между собой, с естественным порядком все они линейно упорядочены, но имеют разные порядковые типы.
Георг Кантор в своё время из множества всех множеств выделил вполне упорядоченные множества, ряд свойств которых напоминает свойства множества натуральных чисел.
В частности, вполне упорядоченное множество не может быть подобно своему отрезку или части своего отрезка; два различных отрезка вполне упорядоченного множества не могут оказаться подобными друг другу; если два вполне упорядоченных множества подобны, то существует единственный изоморфизм одного из них на другое. Из двух вполне упорядоченных множеств одно подобно другому или отрезку другого. Сумма вполне упорядоченных множеств есть вполне упорядоченное множество.
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов