Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Взаимно однозначные соответствия и мощности множеств

Пример 1.

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

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

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

 

 

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

Теорема. Если мощность конечного множества А равна n, то число всех подмножеств А равно , то есть .

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

Множество N2 – счетно.

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

Разобьем N2 на классы

К 1-ому классу отнесем все пары чисел с минимальной суммой N1 (1;1)

 

       
   
 

 

 


Ко 2-му классу отнесем все пары чисел с суммой 3: N2 {(1;2), (2;1)}

К i-му классу Ni {(a;b)| (a+b=i+1}

Каждый класс будет содержать i пар.

Упорядочим классы по возрастанию индексов i, а пары внутри класса упорядоченные по возрастанию первого элемента а. Занумеруем получившуюся последовательность пар номерами 1,2,3.. Видно, что если a+b=i+1, то пара (a,b) получит номер 1+2+..+(i-1)+. Эта нумерация и доказывает счетность множества N2.

Аналогично доказывается счетность множеств N3,…,Nk.

 

Теорема (теорема Кантора). Множество всех действительных чисел из отрезка не является счётным.

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

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

Следствие 1. Множество действительных чисел континуально.

Следствие 2. Множество всех подмножеств счётного множества континуально.

 

<== предыдущая лекция | следующая лекция ==>
Соответствия и их свойства | Функции и отображения
Поделиться с друзьями:


Дата добавления: 2014-01-05; Просмотров: 1209; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.