Докажите что множество рациональных чисел счетно
Перейти к содержимому

Докажите что множество рациональных чисел счетно

  • автор:

Счётность множества рациональных чисел — доказательство (взаимно однозначное соответствие с натуральным рядом)

vedro-compota's picture

Доказательство (изящное и довольно понятное) приведённое в книге сводится к следующим пунтам:

    каждое рациональное число можно выразить в виде несократимой дроби

p/q, где q > 0
|p| + q

Key Words for FKN + antitotal forum (CS VSU):

  • математический факультет ВГУ
  • матфак ВГУ
  • фкн вгу
  • сообщество программистов
  • Воронеж
  • программирование Воронеж
  • математика
  • сайт о программировании
  • Log in to post comments
  • 9684 reads

Fri, 01/16/2015 — 10:01

Неточность:

напр. высота ноль — только одна дробь $\frac$,

Пустое множество дробей высоты ноль,
и лишь одна дробь высоты один: $\frac$.

  • Log in to post comments

vedro-compota's picture

Mon, 01/26/2015 — 22:38

лишь одна дробь высоты один:

это ок. поправил) спасибо)

пустое множество дробей высоты ноль,

а вот это почему? по-моему про высоту пустого множества сложно что-то конкретное сказать..разве нет?

_____________
матфак вгу и остальная классика =)

  • Log in to post comments

Wed, 01/28/2015 — 19:37

Можно сказать, что

Можно сказать, что определение высоты таково, что «высоты ноль» быть не может, то есть «высота ноль» не определена в определении высоты.
Тогда само выражение «дробь высоты ноль» не имеет определённого смысла.

Просто в неисправленной версии было выражение «высота ноль»,
и я использовал его как допустимое.

  • Log in to post comments

vedro-compota's picture

Wed, 01/28/2015 — 20:00

Счетность и несчетность множеств. Равномощность множеств.

Звезда активнаЗвезда активнаЗвезда активнаЗвезда активнаЗвезда не активна

Звезда активнаЗвезда активнаЗвезда активнаЗвезда активнаЗвезда не активна

Литература: Сборник задач по математике. Часть 1. Под ред А. В. Ефимова, Б. П. Демидовича.

Множество $X$ называется счетным, если может быть установлено взаимно однозначное соответствие между элементами этого множества и элементами множества $N$ всех натуральных чисел (то есть элементы множества $X$ можно пронумеровать 1, 2, . ).

Примеры.

Доказать, что следующие множества счетны:

Решение.

Установим взаимно однозначное соответствие между элементами этого множества и натуральными числами, например, упорядочив множество $\$ следующим образом:

$$2, 4, 6, 8, . $$ а затем каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности $$1, 2, 3, 4, . .$$ Таким образом заданное множество является счетным.

Что и требовалось доказать.

Решение.

Множество $\$ упорядочим следующим образом:

$$2^1, 2^2, 2^3, 2^4, . $$ далее каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности. Таким образом, установлено взаимно однозначное соответствие между заданнім множеством и множеством натуральніх чисел. Следовательно, множество $$\$$ является счетным.

Что и требовалось доказать.

1.68. Пусть $X_1, X_2, X_3, . -$ счетные множества. Доказать, что их объеденение $\bigcup\limits_ X_n-$ счетное множество.

Решение.

Пусть $X_n=\, x_, . x_. \>.$ Тогда элементы множества $\bigcup\limits_ X_n$ можно записать в виде следующей таблицы:

Занумеруем элементы этой таблицы следующим образом: в качестве первого элемента берем элемент $x_,$ следующие два элемента — элементы стоящие на диагонали $x_$ и $x_,$ затем считаем три элемента стоящие на следующей диагонали $x_,\,\, x_$ и $x_$ и так далее. Таким образом, каждому элементу множества $\bigcup\limits_ X_n$ можно поставить в соответствие натуральное число (порядковый номер элемента, если их пересчитывать по указанной выше схеме). Следовательно, заданное множество счетное.

Что и требовалось доказать.

1.69.Используя результат задачи 1.68 доказать, что множество всех рациональных чисел $Q=\,\,\, n\neq 0,\,\, m,\, n \in Z \>.$

Решение.

Множество рациональных чисел можно представить как объединение счетных множеств $X_n=\\, | k\in N \>=\left\,\frac, \frac, \cdots\right\>.$

Каждое множество $X_n$ счетное, поскольку каждому элементу можно поставить в соответствие натуральное число, стоящее в знаменателе. Тогда множество $$Q=\,\,\, n\neq 0,\,\, m,\, n \in Z \>=\bigcup\limits_ X_n$$ так же является счетным, как было доказано в задаче 1.68.

Что и требовалось доказать.

Множества $A$ и $B$ называются равномощными, если может быть установлено взаимно однозначное соответствие между элементами множества $A$ и элементами множества $B.$ (то есть каждому элементу множества $A$ можно поставить в соответствие один и только один элемент множеста $B,$ а каждому элементу множества $B$ можно поставить в соответствие один и только один элемент множеста $A.$ )

Примеры:

1. Докажите, что отрезки $[0, 1]$ и $[0, 2]$ равномощны.

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

Каждому элементу $x\in [0, 1]$ поставим в соответствие число $2x.$ Очевидно $2x\in [0, 2].$ Аналонгично каждому элементу $y\in[0, 2]$ соответствует, и притом единственное, число $\frac\in\,[0, 1].$

Что и требовалось доказать.

2. Докажите, что интервалы $(a, b)$ и $(c, d)$ равномощны.

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

Проведем доказательство в несколько этапов:

1) Заметим, что отображение $x\rightarrow x-a$ является взаимно однозначным соответствием между интервалами $(a, \, b)$ и $(0,\, b-a).$

2) Отображение $x\rightarrow\frac$ взаимно однозначно отображает интервал $(0, b-a)$ на $(0, \, d-c).$

3) Отображение $x\rightarrow x+c$ взаимно однозначно отображает интервал $(0, d-c)$ на $(c, d).$

Композиция приведенных отображений $x\rightarrow\frac+c$ является взаимно однозначным отображением между интервалами $(a,\, b)$ и $(c,\, d).$ Следовательно интервалы $(a,\, b)$ и $(c,\, d)$ равномощны.

Что и требовалось доказать.

Домашнее задание.

Доказать, что следующие множества счетны:

1.67. Доказать, что если множество $X$ счетно и $A\subset X$ его бесконечное подмонжество, то множество $A$ так же счето используя этот результат доказать, что множество $$n\in Z | n=k^2-k+1, k\in N$$ счетно.

1.70. Используя результат задачи 1.68, доказать, что множество всех точек плскости с рациональными координатами счетно.

1. Докажите, что полуинтервал $[0,\, 1)$ равномощен полуинтервалу $(0,\, 1].$

2. Докажите, что интервал $(0, 1)$ и луч $(0, \, +\infty)$ равномощны.

Высшая математика. Практика.

  • Матрицы, определители и системы линейных уравнений.
  • Векторная алгебра
  • Алгебраические линии первого порядка на плоскости и в пространстве.
  • Алгебраические линии второго порядка на плоскости и в пространстве.
  • Некоторые понятия математической логики теории множеств.
  • Комплексные числа
  • Предел функции.
  • Дифференцируемость функции, ее дифференциал и производная.
  • Производные и дифференциалы высших порядков. Формула Тейлора.
  • Графики функций и кривые
  • Неопределенный интеграл.
  • Определенный интеграл и его применение.
  • Числовые ряды.
  • Дифференциальное исчисление функций нескольких переменных.
  • Экстремумы функций нескольких переменных.
  • Двойные интегралы
  • Дифференциальные уравнения

Таблицы

  • Таблица производных
  • Таблица производных сложных функций
  • Таблица производных высших порядков
  • Таблица интегралов
  • Формулы Тейлора
  • Греческий алфавит
  • Таблица оригиналов и изображений.
  • Сравнение функций O(f) и o(f).
  • Тригонометрическая таблица

Книги

Счетность множества рациональных чисел

Теорема: множество рациональных чисел является счётным.

Необходимо доказать, что между множеством рациональных чисел и множеством натуральных чисел можно установить взаимо-однозначное соответствие. Для этого положительные рациональные числа запишем так:

1 строка: 1 2 3 4 5 6 7.

2 строка: ½ 2/2 3/2 4/2 5/2 6/2 7/2.

3 строка: 1/3 2/3 3/3 4/3.

Таким образом, будет записано каждое положительное число. Например, число 7/31 будет записано в 31-й строке в 7-м столбце. Вообще, дробь m/n будет записана в n-й строке m-м столбце.

Для установления взаимно-однозначного соответствия теперь уже нельзя переходить от столбца к столбцу, потому что в каждом столбце содержится бесконечное множество элементов. Для доказательства этой теоремы будем использовать диагональный метод Кантора. Он заключается в том, что мы подходим к каждому рациональному числу и, следовательно, каждому рациональному числу будет поставлено в соответствие какое-либо натуральное число.

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

Также можно доказать, что множество отрицательных рациональных чисел счётно. Сложив эти два множества и прибавив к ним конечное множество, состоящее из элемента нуль, мы получим всё множество рациональных чисел.

Теорема. Множество всех действительных чисел несчетно.

Доказательство. Для доказательства достаточно установить, что множество действительных чисел интервала образует несчетное множество. Допустим противное, что интервал есть счетное множество, т. е. все его точки можно перенумеровать:

Но это предположение противоречиво. В самом деле, построим вещественное число , где цифры подобраны так, чтобы и . Ясно, что , однако не совпадает ни с одним из чисел , так как иначе должно было бы быть , что не имеет места.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Студопедия рекомендует:

Основные понятия организации труда на предприятии Организация труда на предприятии Под организацией труда понимают приведение трудовой деятельности в определенную систему.
Определения, классификация ДТП, причины и сопутствующие факторы их возникновения. Учет отчетных и не отчётных ДТП. Анализ ДТП (качественный, количественный, топографический) Автомобильный транспорт наиболее опасный из всех видов транспорта.
КАТЕГОРИИ ЭТИКИ Категории этики – не только теоретические конструкции.
Модели и стратегии поведения личности в конфликте Анализ конфликта и выбор адекватных решений по управлению им обуславливает необходимость учета типичные моделей поведения.
Организация работы горячего цеха. Общие требования, особенности организации Горячие цехи организуются на предприятиях, выполняющих полный цикл производства.

Научный форум dxdy

Доказательство несчетности Кантора и рациональные числа.

Доказательство несчетности Кантора и рациональные числа.
21.10.2010, 18:42

Здравствуйте!
Всем известено доказательство Кантора, что множество вещественных чисел несчетно. Предполагается, что все вещественные числа из указанного диапазона счетны, и строится новое вещественное число, отличное в n-ном разряде от числа под номером n, и, таким образом, неперечисленное. (Причем цифры 0 и 9 не используются.)
Так вот, а что, если подобный способ применить к рациональным числам? Они могут быть в виде конечных десятичных дробей, либо переодических. Построенное нами число, очевидно, имеет вид бесконечной дроби, тоесть нужно доказать, что полученная бесконечная дробь непереодична. Тогда, очевидно, это число иррациональное, а значит не входит в множетсво =>множество счетно. Подскажите возможные идеи доказательства.
Спасибо.

Re: Доказательство несчетности Кантора и рациональные числа.
21.10.2010, 18:56

Заслуженный участник

Sneg0vik в сообщении #364487 писал(а):

Построенное нами число, очевидно, имеет вид бесконечной дроби, тоесть нужно доказать, что полученная бесконечная дробь непереодична.

Ну она и не будет периодической — по построению. И что нам это даст? Что существует хотя бы одно вещественное число, не являющееся рациональным. — так мы это и без того знаем.

Sneg0vik в сообщении #364487 писал(а):
а что, если подобный способ применить к рациональным числам?

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *