Счетные множества - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Счетные множества. Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Слайд 2

Описание слайда:

Слайд 3

Описание слайда:

Теорема Теорема Множество целых чисел счетно и эффективно перечислимо.

Слайд 4

Описание слайда:

Ряд целых чисел: -n, …, -3,-2,-1,0,1,2,3,…, n,… Ряд целых чисел: -n, …, -3,-2,-1,0,1,2,3,…, n,… Будем обозначать множество целых чисел буквой Z. Расположим целые числа следующим образом: 0, 1, -1, 2, -2, 3, -3, …., n, -n, … Тогда каждому числу можно поставить в соответствие натуральное число 0, 1, -1, 2, -2, 3, …., n, -n, … 1, 2, 3, 4, 5, 6, …., 2n, 2n+1, … Таким образом доказано, что множество Z равномощно множеству N, а значит оно счетно.

Слайд 5

Описание слайда:

Для доказательства эффективной перечислимости множества Z необходимо установить тот факт, что все элементы множества Z могут быть перебраны по алгоритму и должны получить в результате такого перебора порядковые номера, без пропусков и повторений. Для доказательства эффективной перечислимости множества Z необходимо установить тот факт, что все элементы множества Z могут быть перебраны по алгоритму и должны получить в результате такого перебора порядковые номера, без пропусков и повторений. Факт эффективной перечислимости множества Z напрямую следует из приведенного способа нумерации элементов натуральными числами. Итак, множество Z счетно и эффективно перечислимо, Q.E.D.

Слайд 6

Описание слайда:

Если оперировать трансфинитными числами, получим:

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Обычно, употребляя термин «упорядоченная» пара считают, что допустим пара (1,5) и пара (5,1) имеют разный смысл и рассматриваются как различные. Чтобы установить взаимно-однозначное соответствие между упорядоченными парами натуральных чисел и натуральными числами, достаточно расположить пары (p,q) в таблицу так, что (p,q) находится в p-ой строке и в q-ом столбце. Обычно, употребляя термин «упорядоченная» пара считают, что допустим пара (1,5) и пара (5,1) имеют разный смысл и рассматриваются как различные. Чтобы установить взаимно-однозначное соответствие между упорядоченными парами натуральных чисел и натуральными числами, достаточно расположить пары (p,q) в таблицу так, что (p,q) находится в p-ой строке и в q-ом столбце. (1,1) (1,2) (1,3) ... (2,1) (2,2) (2,3) … … … … Затем указанные пары перечисляются диагональным методом, начиная с левого верхнего угла. Последовательность обхода матрицы по сути может быть любой.

Слайд 9

Описание слайда:

Таким образом доказано, что множество упорядоченных пар натуральных чисел равномощно множеству N, а значит, оно счетно. Таким образом доказано, что множество упорядоченных пар натуральных чисел равномощно множеству N, а значит, оно счетно. Факт эффективной перечислимости множества упорядоченных пар натуральных чисел независимо от конкретной трактовки термина «упорядоченный» представляется вполне очевидным. В первом случае он напрямую следует из приведенного способа нумерации элементов натуральными числами. Во втором случае к предложенному алгоритму перечисления необходимо добавить процедуру проверки соотношения между элементами p и q, и если, например, p≤q, то присваивать очередной номер этой паре, а в противном случае пропускать её. Итак, множество упорядоченных пар натуральных чисел счетно и эффективно перечислимо, Q.E.D.

Слайд 10

Описание слайда:

Если оперировать трансфинитными числами, то получим что

Слайд 11

Описание слайда:

Теорема Множество упорядоченных n-ок натуральных чисел счетно и эффективно перечислимо.

Слайд 12

Описание слайда:

Чтобы установить взаимно-однозначное соответствие между упорядоченными n-ками натуральных чисел и натуральными числами, достаточно расположить разложить n-ку вида (m1, m2, m3,…,mn) следующим образом: Чтобы установить взаимно-однозначное соответствие между упорядоченными n-ками натуральных чисел и натуральными числами, достаточно расположить разложить n-ку вида (m1, m2, m3,…,mn) следующим образом: (m1, m2, m3,…,mn) = (m1, (m2, m3,…,mn)) = (m1, (m2, (m3,…,mn))) = …=(m1, (m2, (m3, (…(mn-1,mn))))) Расположив по горизонтали таблицы пары натуральных чисел, а по вертикали – натуральные числа, диагональным методом получим нумерацию троек натуральных чисел.

Слайд 13

Описание слайда:

Далее по горизонтали таблицы располагаются тройки натуральных чисел, а по вертикали – натуральные числа, диагональным методом получаем нумерацию четверок натуральных чисел и т.д. Далее по горизонтали таблицы располагаются тройки натуральных чисел, а по вертикали – натуральные числа, диагональным методом получаем нумерацию четверок натуральных чисел и т.д. Таким образом доказано, что множество n-ок натуральных чисел равномощно множеству N, а значит оно счетно. Факт эффективной перечислимости множества напрямую следует из приведенного способа нумерации элементов натуральными числами. Итак, множество упорядоченных n-ок натуральных чисел счетно и эффективно перечислимо, Q.E.D.

Слайд 14

Описание слайда:

Если оперировать понятием кардинального числа (мощности), то получим, что произведенное n раз (n - натуральное число) умножение первого трансфинитного числа само на себя не изменяет его значения или

Слайд 15

Описание слайда:

Теорема Теорема Множество конечных комплексов натуральных чисел счетно и эффективно перечислимо.

Слайд 16

Описание слайда:

Чтобы установить взаимно-однозначное соответствие между конечными комплексами натуральных чисел и натуральными числами, можно использовать двоичное разложение вида: Чтобы установить взаимно-однозначное соответствие между конечными комплексами натуральных чисел и натуральными числами, можно использовать двоичное разложение вида: n=2^(p1-1) + 2^(p1+p2-1)+ …+2^(p1+p2+ …+pk -1), где ^ - значок степени. Например, в двоичном коде 27 = 11011= =1•20 + 1•21 +0•22 +1•23 +1•24 = 20 + 21 +23 +24, откуда получим: p1-1 = 0 ⇒ p1=1 p1+ p2 -1 = 1 ⇒ p1+ p2 =2, а т.к. p1=1 то ⇒ p2=1 p1+ p2 + p3 -1 = 3 ⇒ p1+ p2 + p3 = 4 ……..⇒ p3 =2 p1+ p2 + p3 + p4 -1 = 4 ………………………..⇒ p4 =1 Итак, натуральное число 27 является кодом комплекса (1,1,2,1).

Слайд 17

Описание слайда:

В свою очередь при разложении вида n=2^(p1-1) + 2^(p1+p2-1)+ …+2^(p1+p2+ …+pk -1) комплексу (2,1,1,1) соответствует следующий код: p1-1 = 2 -1 = 1 p1+ p2 -1 = 2 + 1 – 1 = 2 p1+ p2 + p3 -1 = 2 + 1 + 1 - 1 = 3 p1+ p2 + p3 + p4 -1 = 2 + 1 + 1 + 1 – 1 = 4 В итоге число n = 0•20 + 1•21 + 1•22 + 1•23 + 1•24 = =11110 (в двоичном коде) или 2 + 4 + 8 + 16 = 30 ( в десятичном коде). Таким образом, комплексу (2,1,1,1) соответствует натуральное число 30.

Слайд 18

Описание слайда:

В результате доказано, что множество конечных комплексов натуральных чисел равномощно множеству N, а значит оно счетно. В результате доказано, что множество конечных комплексов натуральных чисел равномощно множеству N, а значит оно счетно. Факт эффективной перечислимости множества напрямую следует из приведенного способа нумерации элементов натуральными числами. Итак, множество конечных комплексов натуральных чисел счетно и эффективно перечислимо, Q.E.D. Если оперировать трансфинитными числами, то получим:

Слайд 19

Описание слайда:

Теорема Множество рациональных чисел счетно и эффективно перечислимо.

Слайд 20

Описание слайда:

Обозначим множество рациональных чисел Q. Обозначим множество рациональных чисел Q. Рассмотрим сначала положительные рациональные числа – множество Q+. Определим положительное рациональное число как q=n/m, где n и m – натуральные числа. Запишем их в виде бесконечной матрицы, строки и столбцы которой пронумерованы натуральными числами начиная с 1. Элемент, стоящий на пересечении i-ой строки и j-ого столбца, получит наименование qij Используя диагональный метод, перечислим их (пронумеруем натуральными числами):

Слайд 21

Описание слайда:

Слайд 22

Описание слайда:

Все (и положительные, и отрицательные) рациональные числа в совокупности перечисляются по аналогии с целыми числами, путем чередования положительной дроби и её отрицательного аналога. При этом некоторые рациональные числа мы нумеруем по нескольку раз: например, 1 будет пронумерована как 1/1, 2/2, и т.д., а например 4/5 как 8/10, 12/15 и т.д. Все (и положительные, и отрицательные) рациональные числа в совокупности перечисляются по аналогии с целыми числами, путем чередования положительной дроби и её отрицательного аналога. При этом некоторые рациональные числа мы нумеруем по нескольку раз: например, 1 будет пронумерована как 1/1, 2/2, и т.д., а например 4/5 как 8/10, 12/15 и т.д. Т.о. показано, что множество рациональных чисел не превосходит по мощности множество натуральных чисел, |Q|≤|N|, т.к. каждое рациональное число получит соответствующий номер, а если быть точным – то даже несколько номеров. С другой стороны то, что множество натуральных чисел не превосходит по мощности множество рациональных чисел очевидно, |N|≤|Q| (хотя бы потому, что оно является его подмножеством). Т.о. доказано, что множество рациональных чисел равномощно множеству натуральных чисел |Q|=|N| = À0, а значит оно счетно.

Слайд 23

Описание слайда:

Факт эффективной перечислимости множества Q напрямую следует из приведенного способа нумерации элементов натуральными числами. В ходе этой нумерации каждое рациональное число получает соответствующий номер, и если к алгоритму добавить процедуру, проверяющую дробь на предмет сокращаемости (если числитель и знаменатель имеют общие делители) и исключающую из нумерации сокращаемые дроби, то мы в чистом виде получим перечисление рациональных чисел по алгоритму без пропусков и повторений, что совпадает с определением эффективной перечислимости. Факт эффективной перечислимости множества Q напрямую следует из приведенного способа нумерации элементов натуральными числами. В ходе этой нумерации каждое рациональное число получает соответствующий номер, и если к алгоритму добавить процедуру, проверяющую дробь на предмет сокращаемости (если числитель и знаменатель имеют общие делители) и исключающую из нумерации сокращаемые дроби, то мы в чистом виде получим перечисление рациональных чисел по алгоритму без пропусков и повторений, что совпадает с определением эффективной перечислимости. Итак, множество рациональных чисел счетно и эффективно перечислимо, Q.E.D.

Слайд 24

Описание слайда:

Теорема Множество алгебраических чисел счетно и эффективно перечислимо.

Слайд 25

Описание слайда:

Предложим процедуру нумерации всех алгебраических чисел числами натурального ряда. При этом каждое число будем задавать через образующее его алгебраическое уравнение: Предложим процедуру нумерации всех алгебраических чисел числами натурального ряда. При этом каждое число будем задавать через образующее его алгебраическое уравнение: для линейных уравнений будем иметь упорядоченные пары рациональных чисел для квадратных уравнений – тройки, в общем случае получаем упорядоченную n-ку рациональных чисел: (ai1,ai2, …, ain) для каждого i-ого алгебраического уравнения (n-1)-ой степени. Располагать элементы будем в двусторонне бесконечной матрице.

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

Факт эффективной перечислимости множества А напрямую следует из приведенного способа нумерации элементов натуральными числами, т.к. попутно указана эффективная процедура нумерации наборов рациональных чисел, однозначно задающих алгебраические уравнения соответствующей степени. Факт эффективной перечислимости множества А напрямую следует из приведенного способа нумерации элементов натуральными числами, т.к. попутно указана эффективная процедура нумерации наборов рациональных чисел, однозначно задающих алгебраические уравнения соответствующей степени. При этом важно то, что алгебраическое уравнение n-ой степени имеет эффективный алгоритм решения, т.о. процедура полностью эффективна. Итак, множество алгебраических действительных чисел счетно и эффективно перечислимо, Q.E.D.

Слайд 30

Описание слайда:

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

Теги Счетные множества

Похожие презентации