существует ли бесконечное множество мощности меньше счетного

[FeelUs]

а существует ли бесконечное множество по мощности меньшее
чем счетное?

[z0ic]

А что ты подразумеваешь под словом существует ?

[arseniiv]

Нет, не существует.

[z0ic]

Ну... Может прям так сразу и не существует.

[arseniiv]

Так сразу и не существует ни одного бесконечного множества, по мощности меньшего, чем счётное.

[FeelUs]

а как это доказать?

[arseniiv]

Это следует из того, что любое подмножество счётного множества или счётно, или конечно.

-- Чт янв 26, 2012 00:32:29 --

Т. к. $|A| < |B|$ означает, что существует $C \subset B, C \not\sim B$ такое, что $A \sim C$.

Но, конечно, утверждение про счётное множество надо доказать тоже.

[FeelUs]

arseniiv в сообщении #531318 писал(а):

Это следует из того, что любое подмножество счётного множества или счётно, или конечно.

а это откуда следует?
аааа, понял, спасибо

[arseniiv]

Тут можно взять любое подмножество счётного. Теперь представим, что оно бесконечное. Значит, у него есть подмножество, равномощное ему самому. А теперь надо поколдовать с изоморфизмами и построить нужный из имеющихся. (Я видел такое доказательство. Может, есть и другое.)

[epros]

arseniiv в сообщении #531316 писал(а):

не существует ни одного бесконечного множества, по мощности меньшего, чем счётное

Маленькое уточнение: Говорят, есть нестандартная модель ZF (теории множеств без аксиомы выбора), в которой есть бесконечное, но менее чем счётное множество. Но это уже из области какого-то высшего пилотажа, не знаю, готов ли ТС к обсуждению на таком уровне.

[Someone]

Существуют два различных и, вообще говоря, неэквивалентных определения бесконечного множества.
1) Множество называется бесконечным, если оно не равномощно никакому натуральному числу (натуральный ряд начинаем с нуля, $0=\varnothing$, $n+1=n\cup\{n\}$).
2) Множество называется бесконечным по Дедекинду, если оно равномощно своему собственному подмножеству (собственным подмножеством множества $A$ называется любое его подмножество, не совпадающее с самим $A$).

Ситуация с этими определениями следующая (в ZF).
1) Множество бесконечно по Дедекинду тогда и только тогда, когда оно содержит счётное подмножество (то есть, подмножество, равномощное натуральному ряду).
2) Каждое подмножество счётного множества либо конечно, либо счётно (имея нумерацию счётного множества и пользуясь тем, что каждое непустое подмножество натурального ряда имеет наименьший элемент, легко перенумеровать любое бесконечное подмножество).
3) Может существовать множество, которое не равномощно никакому натуральному числу (то есть, бесконечно), но не содержит никакого счётного подмножества (такое множество называется конечным по Дедекинду). Из сказанного следует, что мощность $\mathfrak m$ такого множества больше любого натурального числа, но не сравнима с $\aleph_0$ (мощностью счётного множества); при этом $\mathfrak m+\aleph_0>\aleph_0$ и $\mathfrak m+\aleph_0>\mathfrak m$.
4) Если выполняется аксиома выбора, то все эти чудеса исчезают, а оба определения бесконечного множества становятся эквивалентными.

[arseniiv]

(Оффтоп)

О, интересные сведения! Спасибо, не знал так точно.

[epros]

Someone в сообщении #531638 писал(а):

... но не содержит никакого счётного подмножества

Someone, подскажите пожалуйста: Разве это условие не означает $\mathfrak{m} < \aleph_0$?

[Someone]

epros в сообщении #531829 писал(а):

Разве это условие не означает $\mathfrak{m} < \aleph_0$?

Без аксиомы выбора - не означает.

Без аксиомы выбора мы можем построить сколь угодно длинную последовательность попарно различных элементов бесконечного (в смысле первого определения) множества $A$ по такой схеме:
так как $A\neq\varnothing$, существует элемент $a_0\in A$;
так как $A\setminus\{a_0\}\neq\varnothing$, существует элемент $a_1\in A\setminus\{a_0\}$;
так как $A\setminus\{a_0,a_1\}\neq\varnothing$, существует элемент $a_2\in A\setminus\{a_0,a_1\}$;
...
Повторив это рассуждение $n$ раз, получим подмножество из $n$ элементов $\{a_0,a_1,\ldots,a_{n-1}\}$.
Однако бесконечную последовательность так получить нельзя, потому что для этого потребовалось бы бесконечно длинное рассуждение, а такие в математике не допускаются (вроде бы, есть какие-то бесконечные логики, допускающие бесконечно длинные формулы, но я о них ничего не знаю и об их применениях ничего не слышал; в любом случае, теория множеств с бесконечной логикой вместо классической - это не ZF).

Если же на множестве $2^A\setminus\{\varnothing\}$ есть функция выбора $\varphi$ (не важно, откуда она взялась, из аксиомы выбора или ещё откуда; например, если $A=\mathbb N$ - натуральный ряд, то для непустого подмножества $X\subseteq\mathbb N$ можно взять $\varphi X=\min X$), то мы можем формализовать предыдущее рассуждение как определение по индукции (аксиомы индукции доказуемы в ZF):
1) полагаем $B_0=\varnothing$, $a_0=\varphi(A\setminus B_0)$;
2) при $n>0$ полагаем $B_n=B_{n-1}\cup\{a_{n-1}\}$, $a_n=\varphi(A\setminus B_n)$.
Тогда $B=\bigcup\limits_{n=0}^{\infty}B_n$ будет счётным подмножеством множества $A$.

Для множества $A$, бесконечного по Дедекинду, счётное подмножество можно построить таким образом. Пусть $\varphi\colon A\xrightarrow{\text{в}}A$ - взаимно однозначное отображение на собственное подмножество. Определяем по индукции:
1) $A_0=\varphi A\subset A$; так как $A\setminus A_0\neq\varnothing$, существует элемент $a_0\in A\setminus A_0$; $B_0=\{a_0\}$;
2) при $n>0$ полагаем $A_n=\varphi A_{n-1}$, $a_n=\varphi a_{n-1}$, $B_n=B_{n-1}\cup\{a_n\}$.
Так как $\varphi$ взаимно однозначно, то при $n>0$ выполняются условия $A_n\subset A_{n-1}$ и $a_n\in A_{n-1}\setminus A_n$. Поэтому $a_m\neq a_n$ при $m\neq n$, и $B=\bigcup\limits_{n=0}^{\infty}B_n$ - искомое счётное подмножество множества $A$.

Если множество $A$ содержит счётное подмножество $B\subseteq A$, то обозначим $\eta\colon\mathbb N\xrightarrow{\text{на}}B$ взаимно однозначное отображение натурального ряда на $B$. Тогда можно определить взаимно однозначное отображение $\varphi\colon A\xrightarrow{\text{в}}A$ на собственное подмножество $\varphi A=A\setminus\{\eta0\}$ следующим образом:

$$\varphi x=\begin{cases}x\text{, если }x\in A\setminus B,\\ \eta(1+\eta^{-1}x)\text{, если }x\in B.\end{cases}$$

Поэтому множество $A$ бесконечно по Дедекинду.

[alex_dorin]

Как можно себе представить образно бесконечное с мощностью меньше, чем счетное множество
и которе может существовать без аксиомы выбора ?
Счетное мнжество - это первое бесконечное множество, те минимальное по мощности по формулировке Дедекинда
бесконечное множество и при АС.