Про счетные множества

[Ulya]

Я понимаю,что есть счетное множество(т.е. можно осуществить биекцию на множество натуральных чисел или биекцию на счетное множество),мощность континуума(множество,эквивалентное [0,1] или эквивалентное мн-ву мощности континуума).
А задачи решить не представляю как:
1)Доказать,что мн-во всех монотонных функций f(x),заданных на [a,b],имеет мощность континуума.
2)Доказать,что мн-во точек $R^n$,имеет мощность континуума.
3)Доказать,что мн-во точек разрыва монотонной функции f(x) не более,чем счетно.
4)Доказать,что мн-во точек строгого локального максимума произвольной функции f(x),x из [a,b],не более чем счетно.
5)Доказать,что объединение континуума множеств мощности континуума имеет мощность континуума.
6)Доказать,что мн-во всех точек любого интервала (a,b) имеет мощность континуумаю
7)Доказать,что мн-во точек (x,y) единичного квадрата имеет мощность континуума.
8)Доказать,что проивольный набор попарно непересекающихся интервалов не более чем счетен.
9)Доказать,что произвольное мн-во точек на плоскости,расстояние между любыми двумя из которых превосходит фиксированное число a>0,не более чем счетно.
10)Доказать,что любая последовательность {a1,a2,...} имеет континуум подпоследовательностей.
11)Доказать,что мн-во всех последовательностей непрерывных на [a,b] функций имеет мощность континуума.
12)Доказать,что мн-во всех интервалов на прямой R имеет мощность континуума.
13)Доказать,что мн-во всех непрерывных на [a,b] функций имеет мощность континуума.
14)Доказать,что мн-во всех чисел,являющихся корнем какого-либо алгебраического многочлена с целыми коэффициентами,счетно.
15)Доказать,что мн-во точек разрыва первого рода функции f(x) имеет мощность континуума.
16)Доказать,что мн-во всех точек из $R_n$ все координаты которых рациональны,счетно.
17)Д-ть,что мн-во всех замкнутых подмножеств прямой R имеет мощность континуума.
18)Д-ть,что мн-во всех счетных подмн-в мн-ва мощности континуума имеет мощность континуума.
19)Д-ть,что мн-во всех конечных подмн-в счетного мн-ва счетно.
20)Д-ть,что мн-во всех интервалов (a,b) с рациональными концами a,b счетно.
21)Д-ть,что проивольный надор попарно непересекающихся интервалов не более чем счетен.

и т.д.

[PAV]

Ну и что, Вы хотите, чтобы мы все сели и написали Вам решения всех этих задач, да еще и с учетом многообещающего "и т.д." в конце?

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

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

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

[Ulya]

PAV что Вы так плохо обо мне думаете...
Про то,что мн-во рациональных чисел счетно я прочитала в учебнике (там есть соответствующее доказательство).
Про то,что пары рац.чисел явл. счетными можно определить (я думаю) так:

$$ \begin{array}{l} x_1^{(1)} \;x_1^{(2)} \;x_2^{(1)} \;x_2^{(2)} \;x_3^{(1)} \;x_3^{(2)} \ldots \\ x_1 \quad x_2 \quad x_3 \quad x_4 \quad x_5 \quad x_6 \ldots \quad \\ \end{array} $$

(вверху пара рац. чисел,внизу просто рац. число,т.е. мы осуществили биекцию).И т.д. с любым кол-вом рац.чисел...или не так я доказала?
Ну а как быть с заданиями в первом посте?

[PAV]

Нет, это доказательство неверно. Доказать счетность множества пар рациональных чисел - значит, пронумеровать их. Я не понимаю, как Вы пронумеровали.

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

Ну и когда Вы с этим разберетесь, то получите решение задач 16 и 20 из списка....

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

[Woland]

Некоторые задания достаточно просто доказать. Однако
я не как не могу доказать задание 8. Даже подступиться не
получается. Не подскажите идею?

[RIP]

Woland писал(а):

Некоторые задания достаточно просто доказать. Однако
я не как не могу доказать задание 8. Даже подступиться не
получается. Не подскажите идею?

В каждом интервале можно найти рациональную точку.

[PAV]

Я не понимаю формулировку задания 15. Там, вероятно, должна быть указана конкретная функция f. И нет ли там ошибки, ведь если взять монотонную функцию f, то для нее множество точек разрыва первого рода конечно или счетно.

[Ulya]

Цитата:

Я не понимаю формулировку задания 15.

- \infty < x < \infty

17)Я нашла:декартово произведение счетного мн-во счетно.Пара рац.чисел (x,y) явл. декартовым произведением R на R. Но R-счетно.Значит,и R на R счетно.А значит,и мн-во пар счетно.Аналогично и с n-мерынм пространством.Получается,что 16 сделано.

Цитата:

Я не понимаю формулировку задания 15

Woland а как?Мне вообще не понятно как доказывать.
14)Докажем,что биекция мн-ву натуральных чисел существует.Алгебр.ур-ие=декартово произведение ${\rm Z} \times {\rm Z} \ldots {\rm Z} = n$,где n-степень алгебр.ур-ия.Корни ур-ия-это объединение счетного мн-ва....?
4)Все точки лок.максимума ф-ии f(x) на [a,b] можно занумеровать в порядке их следования (от a к b).Эти точки есть декартово произведение R на R.И аналог.пункту 17.
А больше я не знаю:подскажите вообще алгоритм какой-нибудь решения таких задач и парочку примеров из этих пунктов.А я попробую при Вас решить аналогично!

Спасибо.

[PAV]

4: неверно. Где Вы использовали условие, что это строгие локальные максимумы?

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

Добавлено спустя 5 минут 38 секунд:

Общий принцип такой: чтобы показать, что некоторое множество $X$ не более чем счетно, нужно придумать способ, как сопоставить каждому элементу $x\in X$ какой-нибудь элемент из счетного множества. Чаще всего это множество рациональных чисел. При этом самый существенный момент - это доказать, что разным элементам множества $X$ сопоставляются обязательно разные числа, иначе доказательство неверное.

[Woland]

PAV писал(а):

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

А иррациональную, что нельзя? То есть откуда следует, что таких интервалов счётно?

[PAV]

Иррациональную нельзя, так как множество всех иррациональных чисел имеет мощность континуума. Мы фактически ставим в соответствие каждой точке разрыва (или, если хотите, каждому такому интервалу) некоторое рациональное число, причем разным точкам - разные числа (поскольку интервалы не пересекаются). Отсюда и следует, что таких точек не более чем счетно, поскольку рациональных чисел счетное число.

[Woland]

Извените за тупость. Но вдруг интервалов не счётно.

[PAV]

1. Каждому интервалу сопоставлена рац. число.

2. Разным интервалам сопоставлены разные рац. числа.


Это значит, что установлено взаимно-однозначное соответствие между всеми указанными интервалами и некоторым подмножеством $A$ рац. чисел. Таким образом, мощность множества интервалов не может превосходить мощность множества рац. чисел. Более точно, множество интервалов равномощно множеству $A$. Если $A$ конечно, то и интервалов конечно. Если же $A$ бесконечно, тогда оно счетно, т.е. и множество интервалов счетно.

Итог: множество интервалов не более чем счетно.

[Ulya]

Ну это сейчас идет все д-во для счетных мн-в.
А для мн-в мощности континуума как поступить?Например,для 1,2,7?
Про 4: по определению ф-ия возрастает слева от точки сторого лок. максимума и убывает справа.Возьмем такой интерал,содержащий точку лок.максимума,для к-рого значение функции в точках (стоящих слева от максимума) этого интервала отрицально,а справа-положительно.Такие отрезки будут не пересекаться (можно выбрать отрезок достаточно малым длины dx).В каждом этом отрезке выберем рациональную точку.Т.е. каждому интервалу мы поставили в соответствие некие рац. числа (она различны),т.е. осуществили биекцию на подмн-во рац.чисел.Значит,4 доказали.

[Woland]

1)Идея: возьмите какую-нибудь монотонную функцию, и параллельным
переносом двигайте, её параллельно оси Y. Замете, что все они различны,
а множество точек интервала (0,1) равно континууму.
2)Это стандартная задача. Поищете на форуме, она здесь уже рассматривалась (и не однократно).

Добавлено спустя 21 минуту 19 секунд:

Насчёт 7. Можно действовать так: поскольку существует биекция
между (0,1)^w(множеством всевозможных, бесконечных, двоичных
последовательностей) и R_{[0,1]}. То необходимую нам биекцию
строим так: для двух бесконечных последовательностей
A_1=0,a_1a_2.... и A_2=0,b_1b_2.... ,где a_i, b_i
принимают значения лишь нуль либо один. Формируем 3-ю
A_3=0,a_1b_1a_2b_2.... легко видеть,что построенное отображение
биективно. Значит множество точек квадрата(A_i,B_i) равномощно
отрезку [0,1]. Оставшихся же точек на квадрате т.е. таких,что какая либо
координата записывается лишь с конечным числом знаков после запятой не более чем счётно.