рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Трансфинитная индукция.

Реферат Курсовая Конспект

Выберите учебное заведение

Трансфинитная индукция.

Трансфинитная индукция. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Понятие Мощности Множества Является Обобщением Понятия Количе...

Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами можно производить арифметические операции. Эти операции отражают некоторые операции над множествами. Например, сложение натуральных чисел соответствует сложению двух непересекающихся конечных множеств. Если в одном множестве элементов, а в другом элементов, то в их сумме будет элементов.

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

Определение 1: Если мощность некоторого множества равна , мощность множества равна , причём и не пересекаются, то мощность множества будет равна .

Замечание: Для сложения мощностей можно использовать следующие арифметические свойства:

- коммутативность,

- ассоциативность.

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

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

Для введенных в рассмотрение кардинальных чисел имеют место следующие равенства:

1) ,

2) ,

3) ,

4) ,

5) .

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

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

Для умножения мощностей (кардинальных чисел) имеют место следующие законы:

- коммутативность;

- ассоциативность;

- дистрибутивность;

;

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

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

В частности, число всех подмножеств множества , как показано выше, равно (т.е. числу всех функций со значениями 0 и 1).

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

Определение 2: Пусть множество имеет мощность , множество имеет мощность , тогда есть мощность множества всевозможных функций из множества во множество , т.е. .

Ниже даётся понятие порядковых типов для произвольных множеств.

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

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
(для студентов специальности «Прикладная математика», «Информатика», «Системный анализ», «Компьютерные системы и сети»)

Прямое произведение множеств. Бинарные отношения.
Пусть и - произвольные элементы. Из элементов

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

И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар

Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве

Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.
Отметим, что теория решеток и теория булевых алгебр – это самостоятельные разделы алгебры. Определение 8: Линейно упорядоченное множество, удовлетворяющее условию мини

Мощность множества. Сравнение мощностей.
Пусть даны конечные множества и , число элементов которых равно

Определение 2: Множества, обладающие одинаковой мощностью, называются равномощными (эквивалентными).
Два конечных множества будут равномощными, если в них содержится одинаковое число элементов. Если имеем дело с бесконечными множествами, то вопросы, связанные с мощностями, решаются путём установле

Определение 3: Множество, эквивалентное множеству чисел натурального ряда, называется счетным.
Натуральный ряд чисел – это счётное множество. Все множества, равномощные множеству , имеют такую же мощность. Теорема 4:

Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами.
Подобие для линейно упорядоченных множеств - есть бинарное отношение между линейно упорядоченными множествами, являющееся отношением эквивалентности. Фактор-множество по этому отношению эквивалентн

Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают. 2) Обозначим через множес

Отрицание – обозначается ,читается:«не » или «неверно, что ».
2) Дизъюнкция (логическое сложение), обозначаемое(читается «и

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

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

Определение 3: Множество всех значений таких, что предикат при этих значениях принимает значение «истина», называется областью истинности предиката.
Определение 4: Предикат , определённый на множестве , называе

Формулы и тавтологии логики предикатов.
При введении определения формул логики предикатов будем использовать следующие обозначения (алфавит): 1) – индивид

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

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

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

Определение формулы и суперпозиции.
Пусть имеется счетное множество переменных , где

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

Линейные функции. Монотонные функции.
Рассмотрим систему функций: , ,

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

Задачи для самостоятельной работы.
1) Сколько имеется различных двоичных наборов длины ? 2) Сколько имеется

Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил. Существует два общих правила комбинаторики: правило сложения и правило умножения. Правило слож

Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.
Очевидно, что множество, содержащее более одного элемента, можно упорядочить не единственным способом. Например, из двух букв и

Определение 8: Конечные упорядоченные множества называются размещениями.
Теорема 3: Количество всех размещений из элементов по элемен

Определение 10: Конечные неупорядоченные множества называются сочетаниями.
Таким образом, сочетания – это такая выборка элементов, при которой их порядок совершенно не важен. Сочетаний из элементов по

Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след

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

Определение 2: Группы, составленные из объектов, которые принадлежат одному из типов элементов, называют сочетаниями с повторениями.
Число всевозможных сочетаний с повторениями обозначают следующим символом: . Сочетания с повторениями, как было показано в примере

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