20721

Мощность множества. Арифметика счетной мощности

Доклад

Математика и математический анализ

Пусть A некоторое счетное мнво тогда по определению A N.Из всякого бесконечного мнва можно выделить счетное подмново.Сумма конечного числа счетных мнв есть счетное мнво. Сумма счетного числа конечных мнв есть счетное мнво.

Русский

2013-07-31

59.5 KB

11 чел.

20. Мощность множества. Арифметика счетной мощности.

Мн-ва A и B назыв. эквивалентными, если существует биекция мн-ва A на мн-во B т.е  .  

Биекция – инъекция + сюръекция (одновременно).

Ф-ия (отображение)  назыв. сюръекцией (наложением), сюръективным отображением, если Im(F) = Y  (мн-во X отображ. на Y).   F: XY, Im(F)=

Отображение F назыв. инъективным, если .

Биективное отображение – взаимнооднозначное.  Иногда используют  запись «инъективное отображение X на Y».

Для того чтобы отображение было обратимым необх. и достаточно, чтобы отображ. было биективным. Обратимое отображение (x = ,y =), биективное отображ.-  x=(0;+ ),Y.

Отношение эквивалентности  разбивает все мн-во  на попарно-пересек. классы.

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

Например, мн-во эквив. мн-ву натур.чисел назыв. счетным мн-вом и обознач.- a.

Тоже самое по Галканову.

Опр1: Если и ,то такое соответствие назыв. взаимнооднозначным соответствием между мн-вами A и B (1-1 –соответствие).

Примеры: 1-1 –соответствие между двумя конечными мн-вами возможно, если они сосотоят из одинакового кол-ва элементов. (A~N)

A={2,4,6,…,2n,…}- мн-во четн.чисел.  N={1,2,3,…,n,…}   

Между точками малой и большой окр-ти можно установить 1-1 соотв.

             

Опр: Если A~N, то оно назыв. счетным мн-вом.

Опр: Если между  мн-вом A и B установлено 1-1 соответствие, то они назыв.       

эквивалентными мн-вами .

Всем счетным мн-вам приписыв. буква – a, кот. называется их мощностью.

Если A~N,то =a.

Пример: мн-во всех четн., нечетн., натур. чисел имеют мощность a.

Три свойства отношения эквивалентности:

  1.  A~A – рефлексивность
  2.  A~BB~A – симметричность
  3.  A~B ^ B~C A~C – транзитивность

___

Теорема1.Для того, чтобы мн-во A было счетным необходимо и достаточно, чтобы оно было  представимо в виде A={a1,a2,…,an…}-(бескон.мно-во попарно-различн.эл-ов) т.е. его элементы представляют собой некоторую последовательность.

Док-во: 

1) НЕОБХОДИМОСТЬ. Пусть A – некоторое счетное мн-во, тогда по определению A~N.

из A берем a =a1, из A берем b =a2  и т.д. A={a1,a2,…}справедливость утверждения.

2) ДОСТАТОЧНОСТЬ. anA .  A-cчетное мн-во.

Т2.Из всякого бесконечного мн-ва можно выделить счетное подмно-во.()

Т3.Если A~сч.мн-во и A’, то A-счетно.

Т4.Сумма конечного числа  счетных мн-в есть счетное мн-во.

Т5. Сумма счетного числа конечных мн-в есть счетное мн-во.

Т6. Сумма счетного числа  счетных мн-в есть счетное мн-во.

Т7. Мн-во рацион.чисел – счетно.

Т8. Если к бесконечному мн-ву M прибавить конечное или счетное мн-во A новых элементов, то это не изменит его мощности. M+A~M.

Т9. Если бесконечное мн-во S – несчетно и AS –конечно или счетно, то S\A~S.

Т10. Если елементы мн-ва A таковы, что A={ax1,x2,..xn}(x1,xn – индексы), и каждое из этих индексов пробегает счетное мн-во не зависимо от других, то мн-во A-счетно.

следствия из Т 1-10 :

1) Мн-во точек пл-ти с рац.координатами – есть счетное мн-во.

2) Мн-во точек n-мерного евклидова пр-ва с рац. координатами – есть счетное мн-во.

3) Мн-во векторов с m – натур. или рац. координатами – есть счетное мн-во.

4) Мн-во полиномов a0+a1x+a2x2+…+anxnc цел.коэффиц. - есть счетное мн-во.

5) Мн-во алгебраич.чисел счетно. (Число назыв. алгебраическим, если оно не явл. корнем многочлена с целыми коэффицентами, иначе оно трансцендентное).


 

А также другие работы, которые могут Вас заинтересовать

28546. О возможности реализации абсолютной секретности в постановке Шеннона 58.5 KB
  А это в свою очередь может повлиять на выбор противником своих действий и таким образом совершенной секретности не получится. Следовательно приведенное определение неизбежным образом следует из нашего интуитивного представления о совершенной секретности. Для совершенной секретности системы величины PEM и PM должны быть равны для всех E и M.
28548. Режим ECB 31 KB
  ECBрежим идеален для небольшого количества данных например для шифрования ключа сессии. Режим шифрования Электронная Кодовая Книга ECB Под режимом шифрования здесь понимается такой алгоритм применения блочного шифра который при отправке сообщения позволяет преобразовывать открытый текст в шифротекст а после передачи этого шифротекста по открытому каналу позволяет однозначно восстановить первоначальный открытый текст. Как видно из определения сам блочный шифр теперь является лишь частью другого алгоритма алгоритма режима шифрования....
28549. Режим CBC 39 KB
  Дешифрование в режиме СВС Для получения первого блока зашифрованного сообщения используется инициализационный вектор IV для которого выполняется операция XOR с первым блоком незашифрованного сообщения. В режиме CBC при зашифровании каждая итерация алгоритма зависит от результата предыдущей итерации поэтому зашифрование сообщения не поддаётся расспараллеливанию. Однако расшифрование когда весь шифротекст уже получен можно выполнять параллельно и независимо для всех блоков сообщения см. Это дает значительный выигрыш во времени при...
28550. Режим CFB 66.5 KB
  Как и в режиме CBC здесь используется операция XOR для предыдущего блока зашифрованного текста и следующего блока незашифрованного текста. Таким образом любой блок зашифрованного текста является функцией от всего предыдущего незашифрованного текста. Для левых J битов выхода алгоритма выполняется операция XOR с первыми J битами незашифрованного текста Р1 для получения первого блока зашифрованного текста С1. При дешифровании используется аналогичная схема за исключением того что для блока получаемого зашифрованного текста выполняется...
28551. Режим шифрования с обратной связью по выходу (OFB) 52.55 KB
  Разница заключается в том что выход алгоритма в режиме OFB подается обратно в регистр тогда как в режиме CFB в регистр подается результат применения операции XOR к незашифрованному блоку и результату алгоритма см. Шифрование в режиме OFB Основное преимущество режима OFB состоит в том что если при передаче произошла ошибка то она не распространяется на следующие зашифрованные блоки и тем самым сохраняется возможность дешифрования последующих блоков. Дешифрование в режиме OFB Недостаток режима OFB заключается в том что он более уязвим к...
28552. Симметричные методы шифрования DES 63.46 KB
  Функция перестановки одна и та же для каждого раунда но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа. Последовательность преобразований отдельного раунда Теперь рассмотрим последовательность преобразований используемую на каждом раунде. Создание подключей Ключ для отдельного раунда Ki состоит из 48 битов. На каждом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита в зависимости от номера раунда.
28553. Примеры современных шифров проблема последнего блока DES 26.44 KB
  Альтернативой DES можно считать тройной DES IDEA а также алгоритм Rijndael принятый в качестве нового стандарта на алгоритмы симметричного шифрования. Также без ответа пока остается вопрос возможен ли криптоанализ с использованием существующих характеристик алгоритма DES. Алгоритм тройной DES В настоящее время основным недостатком DES считается маленькая длина ключа поэтому уже давно начали разрабатываться различные альтернативы этому алгоритму шифрования.
28554. Распределение ключей. Использование базовых ключей 13.15 KB
  Он заключается в доставке абоненту сети связи не полного комплекта ключей для связи со всеми другими абонентами а некоторой универсальной заготовки уникальной для каждого абонента по которой он может вычислить необходимый ему ключ. Пусть в сети связи действуют N абонентов занумеруем их от 0 до N1 и поставим каждому абоненту уникальный открытый идентификатор Yi из некоторого множества Y открытый в смысле общеизвестный. Генерация ключей для абонентов сети связи заключается в выработке N секретных ключей Xi из некоторого множества X....