Размер множества

[gefest_md]

Читаю 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|$ неверно. В книге этого нет.

[Профессор Снэйп]

Дайте точную формулировку утверждения, которое Вам "не понятно, как доказать".

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

(Оффтоп)

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

[olenellus]

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

[xmaister]

(Оффтоп)

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

[muzeum]

Цитата:

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

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

[Профессор Снэйп]

xmaister в сообщении #597563 писал(а):

Я думаю, что ТС хочет доказать, что ни для какого бесконечного множества...

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

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

[xmaister]

Профессор Снэйп в сообщении #597569 писал(а):

Одно - это когда множество не равномощно никакому собственному подмножеству.

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

[olenellus]

(Оффтоп)

Профессор Снэйп в сообщении #597569 писал(а):

Вообще-то есть два определения бесконечного множества. Одно - это когда множество не равномощно никакому собственному подмножеству.

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

[Профессор Снэйп]

xmaister в сообщении #597572 писал(а):

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

olenellus в сообщении #597573 писал(а):

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

Пофиксил баг

[gefest_md]

Профессор Снэйп в сообщении #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|.$

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

[мат-ламер]

gefest_md в сообщении #597556 писал(а):

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

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

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

[gefest_md]

мат-ламер в сообщении #597619 писал(а):

А почему без доказательства?

Цитата:

For infinite A and B, we accept this assumption without proof.

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

[Профессор Снэйп]

gefest_md в сообщении #597612 писал(а):

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

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

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

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

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

gefest_md в сообщении #597636 писал(а):

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

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

[gefest_md]

Профессор Снэйп в сообщении #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.

[Профессор Снэйп]

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

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