2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Размер множества
Сообщение21.07.2012, 18:49 
Аватара пользователя


01/12/06
697
рм
Читаю S.Hedman, A first course in logic. В разделе "Размер структуры" есть такой текст:

Допущение: Если $A$ и $B$ множества, то $|A|\leqslant|B|$ или $|B|\leqslant|A|.$
Если $A$ и $B$ конечные, то это допущение можно доказать. Для бесконечных же её принимают без доказательтва. Оно равносильно аксиоме выбора. Из этого допущения следует, что для любого бесконечного множества $A,$ $|\mathbb{N}|\leqslant|A|.$

Мне не понятно, как доказать, что $|\mathbb{N}|>|A|$ неверно. В книге этого нет.

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 18:52 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Дайте точную формулировку утверждения, которое Вам "не понятно, как доказать".

-- Сб июл 21, 2012 21:54:01 --

(Оффтоп)

Для Вас русский язык не родной, я правильно понимаю? Если это так и Вы испытываете трудности с формулировкой на русском языке, можете написать по английски.

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 18:59 
Заслуженный участник
Аватара пользователя


12/06/09
951
У любого бесконечного множества существует счётное подмножество. Вы знаете, как это показать?

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 19:02 
Заслуженный участник
Аватара пользователя


03/08/11
1613
Новосибирск

(Оффтоп)

Я думаю, что ТС хочет доказать, что ни для какого бесконечного множества $A$ $|A|<|\mathbb{N}|$. Если так, то это очень просто. Пусть существует, тогда можно выделить подмножество, равномощное натуральному ряду. Противоречие.

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 19:03 


07/03/12
99
Цитата:
Мне не понятно, как доказать, что $|\mathbb{N}|>|A|$ неверно. В книге этого нет.

Просто доказать, что $|\mathbb{N}|\le|A|$ построением инъективного вложения первого множества во второе используя аксиому выбора и реккурсию по натуральным числам.
Если использовать только счетную аксиому выбора, то это утверждение все равно можно доказать: сначала установить существование последовательности конечных подмножеств строго возрастающей мощности.

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 19:10 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
xmaister в сообщении #597563 писал(а):
Я думаю, что ТС хочет доказать, что ни для какого бесконечного множества...


Вообще-то есть два определения бесконечного множества. Одно - это когда множество равномощно своему собственному подмножеству. Второе - когда множество не равномощно никакому конечному ординалу (то есть натуральному числу). С аксиомой выбора можно доказать, что эти определения эквивалентны, но без аксиомы выбора понятия - разные! Вот и хотелось бы для начала услышать от ТС, какое у него определение бесконечности. В данном случае это важно.

to ТС: cardinality переводится на русский как "мощность", а не как "размер". Соответственно, заголовок темы неграмотный. Я бы Вам посоветовал изменить "размер множества" на "мощность множества".

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 19:14 
Заслуженный участник
Аватара пользователя


03/08/11
1613
Новосибирск
Профессор Снэйп в сообщении #597569 писал(а):
Одно - это когда множество не равномощно никакому собственному подмножеству.

А это разве не конечное??

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 19:14 
Заслуженный участник
Аватара пользователя


12/06/09
951

(Оффтоп)

Профессор Снэйп в сообщении #597569 писал(а):
Вообще-то есть два определения бесконечного множества. Одно - это когда множество не равномощно никакому собственному подмножеству.

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

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 19:29 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
xmaister в сообщении #597572 писал(а):
А это разве не конечное??

olenellus в сообщении #597573 писал(а):
Вы, наверно, хотели в данном случае написать про конечное множество.

Пофиксил баг :-)

 Профиль  
                  
 
 Re: Мощность множества
Сообщение21.07.2012, 20:27 
Аватара пользователя


01/12/06
697
рм
Профессор Снэйп в сообщении #597558 писал(а):
Дайте точную формулировку утверждения, которое Вам "не понятно, как доказать".


Цитата:
Assumption: If $A$ and $B$ are sets, then $|A|\leqslant|B|$ or $|B|\leqslant|A|.$
..............
It is equivalent to an axiom of mathematics known as the Axiom of Choice.
It follows from this assumption that, for any infinite set $A,$ $|\mathbb{N}|\leqslant|A|.$ This leads to a crucial dichotomy of infinite sets: either $|\mathbb{N}|=|A|$ or $|\mathbb{N}|<|A|.$

Вынужден принять это на веру, и читать дальше.

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 20:45 
Заслуженный участник
Аватара пользователя


30/01/09
6591
gefest_md в сообщении #597556 писал(а):
Читаю S.Hedman, A first course in logic. В разделе "Размер структуры" есть такой текст:

Допущение: Если $A$ и $B$ множества, то $|A|\leqslant|B|$ или $|B|\leqslant|A|.$
Если $A$ и $B$ конечные, то это допущение можно доказать. Для бесконечных же её принимают без доказательтва. .

А почему без доказательства? Из аксиомы выбора следует, что любое множество равномощно некоторому трансфинитному числу, а они все сравнимы между собой.

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 21:02 
Аватара пользователя


01/12/06
697
рм
мат-ламер в сообщении #597619 писал(а):
А почему без доказательства?

Цитата:
For infinite A and B, we accept this assumption without proof.

Может "примем её без доказательства"?

 Профиль  
                  
 
 Re: Размер множества
Сообщение21.07.2012, 21:10 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
gefest_md в сообщении #597612 писал(а):
Вынужден принять это на веру, и читать дальше.

А что именно принять на веру? То, что из аксиомы выбора следует сравнимость по мощности любых двух множеств. Или как из факта сравнимости произвольных множеств следует, что любое бесконечное множество имеет не менее чем счётную мощность?

Первое - достаточно сложная теорема, но во многих учебниках её подробное доказательство можно найти. Я не читал книгу Хедмана, так что не знаю, есть там это доказательство или нет. Если интересно и в книге Хедмана нет, почитайте другие учебники.

Второе - достаточно просто. Но тут всё зависит от того, каково определение конечного множества. Если конечным множеством называется множество, равномощное конечному ординалу, то случай $|A| < | \mathbb{N} |$ исключается по определению. А если конечное - это такое, которое не равномощно собственному подмножеству... Ну, с аксиомой выбора доказывается эквивалентность двух определений. А без аксиомы выбора вроде этот случай исключить и не получится (не уверен, могу ошибаться, но вроде бы так).

-- Вс июл 22, 2012 00:11:35 --

gefest_md в сообщении #597636 писал(а):
Может "примем её без доказательства"?

Вам не нравится, что в книге утверждение не доказано, и хочется увидеть доказательство? Я правильно понимаю?

 Профиль  
                  
 
 Re: Мощность множества
Сообщение22.07.2012, 01:32 
Аватара пользователя


01/12/06
697
рм
Профессор Снэйп в сообщении #597569 писал(а):
Вот и хотелось бы для начала услышать от ТС, какое у него определение бесконечности. В данном случае это важно.

Я могу определить через примеры. «Знаете $\mathbb{R},\ \mathbb{N} $?»… «Вот, это бесконечные множества. Могу даже показать, что $| \mathbb{N}|<|\mathbb{R}| $».
Хенман не даёт определений для конечных и бесконечных множеств. Он начинает в том разделе с определения равенства мощностей: определяет формулы $ |B|\leqslant|A|$, $|A|=|B|. $ Приводит примеры: доказывает, что $|\mathbb{R}|=|(0,\,1)| .$ Далее, доказывает теорему о том, что $ |A|=|B|$ тогда и только тогда, когда существует биекция от $A $ к $B. $ После этого, начинает рассказывать об упомянутом допущении.
(В другом источнике используется $f\colon\mathbb{N}_n\to A$ в определении конечного множества)
Профессор Снэйп в сообщении #597569 писал(а):
to ТС: cardinality переводится на русский как "мощность", а не как "размер". Соответственно, заголовок темы неграмотный. Я бы Вам посоветовал изменить "размер множества" на "мощность множества".

Согласен. Хотя в оригинале и не cardinality, а size (“size of a structure”).
Профессор Снэйп в сообщении #597644 писал(а):
А что именно принять на веру? ...

Это
Профессор Снэйп в сообщении #597644 писал(а):
как из факта сравнимости произвольных множеств следует, что любое бесконечное множество имеет не менее чем счётную мощность?



Профессор Снэйп в сообщении #597644 писал(а):
gefest_md в сообщении #597636 писал(а):
Может "примем её без доказательства"?

Вам не нравится, что в книге утверждение не доказано, и хочется увидеть доказательство? Я правильно понимаю?

Не договорил, кажется. Речь шла о возможности доказать само допущение для случая бесконечных множеств. Но конечно не доволен и тем, что Хедман, одним махом «доказал», что $ |\mathbb{N}|\leqslant|A|.$

-- Вс июл 22, 2012 01:02:07 --

Вот цитата из Хедмана, в конце параграфа «The size of a structure»:
Цитата:
At the outset of this section, we said that having a single notion of "infinity” is misleading. We have replaced this with two notions. An infinite set is either countable or uncountable. Many of the infinite sets we encounter either have the same size as $ \mathbb{N}$ or the same size as $ \mathbb{R}.$ … This dichotomy is still crude. Proposition 2.44 guarantees the existence of arbitrarily large uncountable sets, so having a single notion of “uncountable” is now misleading. In section 4.2, we introduce cardinal numbers to represent the size of a set and study the plethora of uncountable numbers in more depth. For now, we end our digression into the infinite and return to our discussion of structures.

 Профиль  
                  
 
 Re: Мощность множества
Сообщение22.07.2012, 07:27 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
gefest_md в сообщении #597791 писал(а):
Вот цитата из Хедмана, в конце параграфа «The size of a structure»:
Цитата:
At the outset of this section, we said that having a single notion of "infinity” is misleading. We have replaced this with two notions. An infinite set is either countable or uncountable. Many of the infinite sets we encounter either have the same size as $ \mathbb{N}$ or the same size as $ \mathbb{R}.$ … This dichotomy is still crude. Proposition 2.44 guarantees the existence of arbitrarily large uncountable sets, so having a single notion of “uncountable” is now misleading. In section 4.2, we introduce cardinal numbers to represent the size of a set and study the plethora of uncountable numbers in more depth. For now, we end our digression into the infinite and return to our discussion of structures.

:-)

Думаю, Вам лучше не мучиться вопросами о size сейчас, а дойти до параграфа 4.2 и прочитать про cardinal numbers. Большинство вопросов, скорее всего, отпадут.

gefest_md в сообщении #597791 писал(а):
Я могу определить через примеры.

Через примеры не годится, это не определение.

Понимаете, можно дать разные определения бесконечности. Например, такое:

Множество $A$ называется бесконечным, если неверно, что $|A| < | \mathbb{N} |$.

Надеюсь, Вы понимаете, что с таким определением утверждение, вызвавшее у Вас такое смущение, доказывать не надо. :-)

Так что если хотите доказательств, то точное определение в студию!

gefest_md в сообщении #597791 писал(а):
Хотя в оригинале и не cardinality, а size (“size of a structure”).

А слово cardinality, наверное, появится в параграфе 4.2 :-)

Я всё же призываю Вас прекратить писать про "размер" и начать использовать слово "мощность" прямо сейчас.

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

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



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

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


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

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