ТЕОРИЯ МНОЖЕСТВ И БИНАРНЫХ ОТНОШЕНИЙ

Основные понятия теории множеств

Теоретические сведения

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

Количество элементов во множестве называется мощностью или кардинальным числом. В зависимости от мощности множества могут быть конечные и бесконечные. Множество, в состав которого не входит ни одного элемента, называется пустым и обозначается как 0. Мощность пустого множества равна нулю. Но мощность множества С, элементом которого является пустое множество, равна единице, С = {0},|С| = 1.

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

Если каждому элементу бесконечного множества можно поставить в соответствие натуральное число п1 е N, причем только одно пп без пропусков и повторений, то это множество называется счетнобесконечным и его мощность равна |А| = А0 (алеф-нуль), первому трансфинитному числу. Второе трансфинитное число А, алеф, равно мощности множества Я действительных чисел. Известно и третье

трансфинитное число А = 2А = 22 °, алеф-один, равное множеству точек в пространстве, заданных координатами (х,у, г). Трансфинитные числа обозначают буквами еврейского алфавита.

Кантор создал шкалу трансфинитных чисел: алеф-ноль, алеф, алеф-один,... .

Считаем, что множество счетное, если выполняется один из двух случаев:

  • • множество состоит из конечного числа элементов, т.е. его кардинальное число совпадает с одним из натуральных чисел;
  • • множество счетно-бесконечное, т.е. его мощность совпадает

с мощностью множества натуральных чисел.

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

Множество А называется подмножеством В, если каждый элемент а, из А, а1 е А, принадлежит одновременно и множеству В, а( е В, А с В. В предельном случае множества Л и В могут состоять из одних и тех же элементов.

Если во множестве В найдется хотя бы один элемент х/? который не принадлежит А, ЕЬс/? х,- е В, х( ё А, то Асобственное подмножество В, А с В. Пустое множество 0 всегда является подмножеством любого множества В.

Множество В в приведенных выше определениях часто называют надмножеством (собственным надмножеством) множества А

Множества Л и В равны, если являются подмножествами (надмножествами) друг друга.

Для каждого множества М можно построить новое множество, элементами которого являются все подмножества М и только они. Тогда множество М называется универсумом и обозначается как /, а множество всех его подмножеств — булеаном В(1).

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

Теорема 1.1. Основная теорема о конечных множествах

Любое конечное множество не может быть эквивалентно никакому своему собственному подмножеству.

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

Задачи

Задача 1.1. Дано множество М = {а, Ь, с, б, е}. Найти все его подмножества.

Задача 1.2. Дано множество М = {а, Ь, с, б, е}. Найти все его собственные подмножества.

Задача 1.3. Определить мощность булеана для М- {а, Ь, с, с1, е}.

Задача 1.4. Построить множество, равномощное М= {а, Ь, с, б, е}.

Задача 1.5. Задать множество четных натуральных чисел от 2 до 20 с помощью перечисления, характеристического предиката и производящей функции.

Задача 1.6. Чему равна мощность множества натуральных чисел?

Задача 1.7. Чему равна мощность множества натуральных чисел на отрезке [1, 1024]?

Задача 1.8. Чему равна мощность множества рациональных чисел?

Задача 1.9. Чему равна мощность множества вещественных чисел?

Задача 1.10. Чему равна мощность множества точек на плоскости?

 
< Пред   СОДЕРЖАНИЕ     След >