2014 dxdy logo

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

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




 
 Лемма Кенига о бесконечном дереве
Сообщение06.04.2013, 10:51 
У Верещагина и Шеня Матлогика формулировка леммы такая:
Любое бесконечное дерево содержит бесконечную ветвь.
Мне кажется, что лемма неверна. Контрпример: дерево, состоящее из корня $0$ и объединения веток $0\leftarrow 1, 0\leftarrow 2\leftarrow 3, 0\leftarrow 4\leftarrow 5\leftarrow 6,...$. В нем нет бесконечной ветки, но число вершин бесконечно.
Я что-то упустил из контекста?

-- Сб апр 06, 2013 07:55:02 --

А все, я нагуглил более правильную формулировку:
Любое бесконечное дерево с конечным ветвлением содержит бесконечную ветвь.

 
 
 
 Re: Лемма Кенига о бесконечном дереве
Сообщение06.04.2013, 11:03 
Аватара пользователя
Как Вы понимаете ветвь - и как авторы?

 
 
 
 Re: Лемма Кенига о бесконечном дереве
Сообщение06.04.2013, 18:03 
Аватара пользователя
Sonic86 в сообщении #706480 писал(а):
У Верещагина и Шеня Матлогика формулировка леммы такая:
Любое бесконечное дерево содержит бесконечную ветвь.

А это точно, что у авторов именно такая формулировка?

Ведь в оригинале лемма утверждается только для бесконечных деревьев с конечной степенью всех вершин (в том числе и корня).

Вот, например, что пишет Википедия

 
 
 
 Re: Лемма Кенига о бесконечном дереве
Сообщение06.04.2013, 18:07 
whitefox в сообщении #706660 писал(а):
А это точно, что у авторов именно такая формулировка?
Да, только сверху еще есть контекст - видимо, сформулировали в контексте (2-я часть, теорема 22). Можете сами глянуть.

nikvic в сообщении #706485 писал(а):
Как Вы понимаете ветвь - и как авторы?
Ну я так и понимаю: ветка мощности $|\mathbb{N}|$ - $v_0\to v_1\to v_2\to ...$. Авторы вроде тоже так. :?

 
 
 
 Re: Лемма Кенига о бесконечном дереве
Сообщение06.04.2013, 18:39 
Аватара пользователя
Sonic86 в сообщении #706666 писал(а):
Да, только сверху еще есть контекст - видимо, сформулировали в контексте (2-я часть, теорема 22). Можете сами глянуть.

Посмотрел.

Действительно в предшествующем лемме абзаце, авторы описывают деревья для которых они формулируют свою лемму.

Любая вершина их дерева имеет степень не больше двух.
Поэтому для таких деревьев упоминание о конечной степени излишне.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group