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

Доказательство Рассмотрим отображение : NxN N, заданное следующим правилом: Проверим биективность отображения и укажем алгоритмы вычисления и -1 Доказательство Рассмотрим отображение : NxN N, заданное следующим правилом: Проверим биективность отображения и укажем алгоритмы вычисления и -1 Множество NxN является эффективно счетным

Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Пусть (m 1,n 1 )= (m 2,n 2 ). Тогда: Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Пусть (m 1,n 1 )= (m 2,n 2 ). Тогда: Множество NxN является эффективно счетным

Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Пусть (m 1,n 1 )= (m 2,n 2 ). Тогда: Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Пусть (m 1,n 1 )= (m 2,n 2 ). Тогда: Множество NxN является эффективно счетным Из однозначности канонического разложения, получаем: m 1 = m 2 Каноническое разложение – представление натурального числа в виде произведения степеней простых чисел

Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Пусть (m 1,n 1 )= (m 2,n 2 ). Тогда: Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Пусть (m 1,n 1 )= (m 2,n 2 ). Тогда: Множество NxN является эффективно счетным Т.к. m 1 = m 2, то 2n 1 +1= 2n 2 +1 или n 1 = n 2 Т.о.: (m 1,n 1 ) = (m 2,n 2 ) Т.к. m 1 = m 2, то 2n 1 +1= 2n 2 +1 или n 1 = n 2 Т.о.: (m 1,n 1 ) = (m 2,n 2 )

Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Доказательство а) Инъективность (если х 1 х 2, то f(x 1 ) f(x 2 )) Множество NxN является эффективно счетным Получили: если (m 1,n 1 )= (m 2,n 2 ), то (m 1,n 1 ) = (m 2,n 2 ) По закону контрпозиции верно и обратное противоположному утверждение: если (m 1,n 1 ) (m 2,n 2 ), то (m 1,n 1 ) (m 2,n 2 ) Инъективность доказана Получили: если (m 1,n 1 )= (m 2,n 2 ), то (m 1,n 1 ) = (m 2,n 2 ) По закону контрпозиции верно и обратное противоположному утверждение: если (m 1,n 1 ) (m 2,n 2 ), то (m 1,n 1 ) (m 2,n 2 ) Инъективность доказана

Рассмотрим примеры определения номера пары (m; n) и нахождения по номеру соответствующей пары (0;0) … (1;0) … (0;1) … (1;1) … (2;0) … (0;2) … (3;0) … (2;1) … (1;2) … (0;3) …

Рассмотрим примеры определения номера пары (m; n) и нахождения по номеру соответствующей пары Какие номера пропущены?

Рассмотрим примеры определения номера пары (m; n) и нахождения по номеру соответствующей пары Пропущены номера 8 и 10. Найдем соответствующие им пары:

Рассмотрим примеры определения номера пары (m; n) и нахождения по номеру соответствующей пары Пропущены номера 8 и 10. Найдем соответствующие им пары:

Рассмотрим примеры определения номера пары (m; n) и нахождения по номеру соответствующей пары Выпишем четные номера:

Рассмотрим примеры определения номера пары (m; n) и нахождения по номеру соответствующей пары Остальные пары задают нечетные номера, например: … …

Рассмотрим примеры определения номера пары (m; n) и нахождения по номеру соответствующей пары Остальные пары задают нечетные номера, например:

Доказательство б) Сюръективность (у каждого образа хотя бы один прообраз ) По натуральному числу а N (номеру) найдем упорядоченную пару (m;n) с условием (m;n)=a: Доказательство б) Сюръективность (у каждого образа хотя бы один прообраз ) По натуральному числу а N (номеру) найдем упорядоченную пару (m;n) с условием (m;n)=a: Множество NxN является эффективно счетным

Доказательство б) Сюръективность Доказательство б) Сюръективность Множество NxN является эффективно счетным m – число двоек в каноническом разложении числа (а+1). Если разделить (а+1) на 2 m, то можно определить n Значит, каждому числу а N соответствует упорядоченная пара (m;n) Сюръективность доказана m – число двоек в каноническом разложении числа (а+1). Если разделить (а+1) на 2 m, то можно определить n Значит, каждому числу а N соответствует упорядоченная пара (m;n) Сюръективность доказана

Множество NxN является эффективно счетным Алгоритм определения пары (m;n) по номеру а N : 1) m – количество двоек в числе (а +1) 2) а 1 = (а+1) / 2 m 3) n= (а 1 – 1) / 2 Алгоритм определения номера а N пары (m;n) задается выражением Алгоритм определения пары (m;n) по номеру а N : 1) m – количество двоек в числе (а +1) 2) а 1 = (а+1) / 2 m 3) n= (а 1 – 1) / 2 Алгоритм определения номера а N пары (m;n) задается выражением

Литература 1.Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, с.