2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Континуум-гипотеза для бесконечных путей в деревьях
Сообщение28.10.2005, 14:24 
Помогите решить задачу. Есть корневое дерево (бесконечное), у каждой вершины не более, чем счетное число сыновей. Доказать, что для множества бесконечных путей, идущих из вершины (несамопересекающихся) верна континуум-гипотеза: его мощность либо конечна, либо счетна, либо равна континууму.

  
                  
 
 
Сообщение28.10.2005, 15:59 


10/06/05
100
Тюмень
:roll: А какая ещё бывает мощность у множеств :?: :oops:

 Профиль  
                  
 
 
Сообщение28.10.2005, 18:23 
Континуум-гипотеза говорит, что никаких больше (в пределах континуума) не бывает. Но бывают ли на самом деле, на данный момент не известно.

  
                  
 
 
Сообщение29.10.2005, 10:26 
Но пути в деревьях - это совсем не любое множество. Например, оно замкнуто относительно предельного перехода. Интересно бы для таких множеств доказать, что они не могут быть промежуточной мощности.

  
                  
 
 
Сообщение29.10.2005, 12:41 
Экс-модератор


12/06/05
1595
MSU
Уважаемые гости, если вы не регистрируетесь, то не могли бы вы хотя бы представляться?
В данной ветке три сообщения под гостем. Не очень понятно, сколько именно человек написали эти сообщения.

Задача хорошая. Вроде так и есть, но доказать пока не получается.

 Профиль  
                  
 
 
Сообщение29.10.2005, 13:33 
Все три сообщения написал один человек, и этот человек - я.

  
                  
 
 Re: Континуум-гипотеза для бесконечных путей в деревьях
Сообщение31.10.2005, 11:16 


31/10/05
7
Отличная, великолепная задача. Надо будет подумать на досуге.

зы: у меня подозрение, что она - задача - носит чье-то имя. Смутно вспоминаю что-то.

 Профиль  
                  
 
 
Сообщение04.11.2005, 19:35 
Вопрос снят.

http://www.cmc-online.ru/forum/study/?s ... w&msg=4099

  
                  
 
 
Сообщение04.11.2005, 23:11 
Экс-модератор


12/06/05
1595
MSU
Да, похоже на правду.

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

 Профиль  
                  
 
 
Сообщение14.12.2005, 10:23 
Заслуженный участник


13/12/05
4518
Очень интересная задача!

Будем смотреть на дерево, как на упорядоченную пару множеств T=(V,E) V-множество вершин, E-множество рёбер. Для удобства пару (пустое мн-во, пустое мн-во) тоже будем считать деревом (пустым деревом).
Пересечением произвольной системы деревьев T_i=(V_i,E_i) назовём пару (П V_i,П E_i).(П-пересечение).
Как нетрудно проверить, пересечение деревьев, являющихся поддеревом какого-то фиксированного дерева, есть его же поддерево.

Сначала заметим, что множество вершин нашего дерева не более чем счётно.

Определим процедуру "обрезания прямых веток" - переход от дерева к некоторому его поддереву.
Это поддерево получается из исходного путём выкидывания всех вершин, через которые проходит только один путь, и всех прилегающих к этим вершинам рёбер.

Рассмотрим трансфинитную последовательность деревьев T_0,T_1,...,T_a,..., a<OMEGA где OMEGA-первое несчётное порядковое число (мощности алеф1). В этой последовательности T_0-наше исходное дерево, а дерево с индексом 0<b<OMEGA получается путём обрезания прямых веток у дерева, яляющегося персечением всех деревьев с меньшими индексами.

Возможны два варианта
1) все деревья в этой последовательности непустые.
2) начиная с некоторого порядкового числа b<OMEGA все они пустые.

В первом случае существует такое порядковое число b<OMEGA, что все деревья после этого номера
совпадают. В самом деле, если бы на каждом шаге мы бы выкидывали по крайней мере по одной вершине, то их в исходном дереве было бы не менее алеф1, а их счётно. Но что значит, что процедура обрезания веток не меняеет дерева? Это значит, что число путей >=2^алеф0=континуум.

Во втором случае путей вообще нет.

Учитывая, что мы потеряли при обрезании веток не более счётного числа путей (на каждом шаге не более чем счётное *не более чем счётное число шагов до номера b), получим, что
в первом варианте их было континуум, а во втором-не более чем счётное число.

 Профиль  
                  
 
 алеф
Сообщение14.12.2005, 15:52 


12/12/05
61
а как выглядит алеф в транскрипции тега math?
а сколько всегда существует алефов, разве существовует множество, мощность которого строго больше алефа1 и строго меньше континуума?

 Профиль  
                  
 
 Re: алеф
Сообщение14.12.2005, 21:34 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
x0rr писал(а):
а как выглядит алеф в транскрипции тега math?
а сколько всегда существует алефов, разве существовует множество, мощность которого строго больше алефа1 и строго меньше континуума?


$\aleph$=\aleph

Алефов существует бесконечно много - так много, что не существует множества всех алефов (как и множества всех множеств).

Известны неравенства $\aleph_0<\aleph_1\leqslant\mathfrac c=2^{\aleph_0}$, причём, возможно как равенство $\aleph_1=\mathfrac c$ (континуум-гипотеза $[CH]$), так и неравенство $\aleph_1<\mathfrac c$ (отрицание континуум-гипотезы $[\neg CH]$). Более того, между $\aleph_1$ и континуумом $\mathfrac c$ может быть очень много промежуточных алефов, хотя, конечно, не больше континуума.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group