Странная формула. Часть 2. Множества и функции

 АЛЕКСЕЙ ВТОРНИКОВ, ЗАО КБ «Ростовский Универсальный», ведущий программист, pdp8dec@gmail.com

Странная формула
Часть 2. Множества и функции

Продолжаем обсуждение формулы Nⁿ → N, выражающей сущность программирования с точки зрения математики. На нескольких примерах детально рассмотрим фундаментальное понятие «счетность». Результаты окажутся очень и очень неожиданными!

«Большинство из нас учили математику либо очень плохо, либо вообще не учили».

С. Лилли «Теория относительности для всех

Напомним, что счетными называются такие множества, элементы которых можно поставить в 1-1 соответствие с элементами натурального ряда (т.е. числами 0, 1, 2, ...). Мы в первой части статьи [1] рассмотрели несколько таких соответствий. В этой части мы продолжим знакомство с бесконечными множествами и убедимся в удивительных свойствах некоторых, казалось бы, хорошо известных числовых последовательностей. Правда, для этого придется немного повозиться с элементарными выкладками, но если вы хоть немного помните школьный курс алгебры, то особенных сложностей быть не должно...

Нумерация целых чисел

После того как была установлена счетность последовательностей положительных четных и нечетных чисел (и их равномощность натуральному ряду), что можно сказать о последовательности целых чисел (..., -2, -1, 0, 1, 2, ...)? Существует ли функция, которая устанавливает 1-1 соответствие элементов множеств N и Z?

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

• для четных натуральных – (0, 2, 4, ...) : n/2
• для нечетных натуральных – (1, 3, 5, ...) : -(n+1)/2

Напомним, что функция может быть задана как аналитическим выражением вроде ln (sin (x/2), так и многими другими способами, в том числе тем, что использован выше.

Проверим, как «работает» эта функция:

Таким образом, мы построили 1-1 соответствие между множествами N и Z, и, следовательно, множество Z счетно и имеет мощность натурального ряда χ0. Иначе говоря, множества N и Z эквивалентны (но в то же время натуральные составляют собственное подмножество целых). Неожиданно, не правда ли? Конечно, такая нумерация выглядит непривычно (так, отрицательному целому числу -100 соответствует положительное натуральное 199), но она работает, а это в конечном счете главное. То, что целые числа расположены не подряд, а вперемешку, не должно нас смущать – мы ведь рассматриваем неупорядоченные множества, а в них порядок элементов несуществен; главное, чтобы не было пропусков.

А что же рациональные числа?

Напомним, что рациональными называются числа вида m/n, где m и n – целые, n ≠ 0 (например, 1/2, -14/5 и т.д.); целые числа являются подмножеством рациональных, так как всякое целое число, очевидно, может быть представлено в виде m/1.

Если воспользоваться традиционным способом представления чисел в виде точек на числовой оси, то целые числа расположены на ней изолированно: между соседними целыми (такими, как, например, -2 и -1 или 51 и 52) никаких других целых нет.

А что можно сказать о рациональных числах? Сколько их? Образуют ли они счетное множество (иначе говоря, можно ли их перенумеровать) или нет?

Рассмотрим два любых рациональных числа, скажем, 1/4 и 1/2 (в привычной записи с десятичной точкой им соответствуют числа 0,25 и 0,5). Совершенно очевидно, что между ними можно найти хотя бы еще одно рациональное число, равное, например, полусумме исходных, число 3/8 (или 0,375 в записи с десятичной точкой). Применяя тот же прием, но уже к паре 1/4 и 3/8 (или к паре 3/8 и 1/2), можно найти следующее рациональное число, и так до бесконечности. Таким образом, рациональные числа заполняют числовую ось гораздо плотнее целых: как бы близко ни были расположены друг к другу два рациональных числа, между ними всегда найдется еще их бесконечное количество.

Статью целиком читайте в журнале «Системный администратор», №12 за 2013 г. на страницах 76-81.

Комментарии могут оставлять только зарегистрированные пользователи