Граф из простого бесконечного цикла

[Xaositect]

shkolnik в сообщении #885893 писал(а):

Счетным называется множество, мощность которого меньше или равна $\omega$, (если равна, то оно называется счетно-бесконечным), где $\omega$ - минимальное индуктивное множество.

Хорошо, а что такое мощность?

shkolnik в сообщении #885893 писал(а):

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

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

shkolnik в сообщении #885893 писал(а):

В той же теореме о счетности множества рациональных чисел, явно используется факт линейной упорядоченности $\mathbb Q$.

Каким образом? Доказательство почти буквально такое же для $\mathbb{N}\times\mathbb{N}$, на котором линейного порядка не предполагается.

shkolnik в сообщении #885893 писал(а):

Все его элементы конечны, я же с первого сообщения говорю о простой бесконечной цепи. В множестве $X$ есть только одна, простая бесконечная цепь, а не бесконечное множество конечных. Геометрически, мне кажется, описал довольно подробно: бесконечный граф в виде многоугольника, аппроксимирующий окружность (число вершин и ребер бесконечно и составляет цикл).
Я просто не соображу, как это записать формально.

Вот пока мы формально это множество не запишем, мы ничего о его мощности сказать не сможем. Давайте разбираться. Множество состоит из элементов. Какие элементы будут в нашем множестве?

shkolnik в сообщении #885893 писал(а):

В моем понимании, бесконечные множества можно разделить на счетные и несчетные. Из счетности множества с необходимостью следует, что оно вполне упорядочено (является ординалом), но из вполне упорядоченности множества, еще не следует его счетность.
Счетные обязательно вполне упорядочены. А несчетные или вполне упорядочены (но их мощность превышает $\mathbb N$) или же они неупорядочены вполне (или хотя бы линейно), соответственно, их мощность не определить.

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

[patzer2097]

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

shkolnik в сообщении #885893 писал(а):

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

а Вы почитайте о биективных отображениях

shkolnik в сообщении #885893 писал(а):

В той же теореме о счетности множества рациональных чисел, явно используется факт линейной упорядоченности $\mathbb Q$.

даже не знаю что сказать

shkolnik в сообщении #885893 писал(а):

Из счетности множества с необходимостью следует, что оно вполне упорядочено

а Ваш пример с $\mathbb Q$ строчкой выше Вы тут же после написания забыли?

shkolnik в сообщении #885893 писал(а):

Геометрически, мне кажется, описал довольно подробно: бесконечный граф в виде многоугольника, аппроксимирующий окружность (число вершин и ребер бесконечно и составляет цикл). Я просто не соображу, как это записать формально.

Никак не записать. Вы сможете понять это, если будете хорошо знакомы с понятиями окружности, многоугольника, графа и цикла.

[arseniiv]

shkolnik в сообщении #885893 писал(а):

Непонятки остаются в связи с тем, как можно утверждать сводимость всех свойств по разному упорядоченных множеств к какому-то одному линейному порядку (к ординалам) ?

Какую сводимость каких всех свойств, постойте?

Боюсь, проблемы с вашим случаем в основном в том, что вы подразумеваете гораздо больше, чем высказываете. И почему-то подразумеваете очень много непонятно как могущего появиться при чтении нормальной книги по теории множеств. Что вы читали?

shkolnik в сообщении #885893 писал(а):

цифры (в которые уже заложен линейный порядок)

Ещё раз повторяю, в натуральные числа не «заложен» никакой порядок. Плюньте вы на $\in$, возьмите $\ni$ — им оно уже не вполне упорядочено. Возьмите $\equiv\pmod3$ — и вообще никакого порядка не получите, зато перед вами отношение эквивалентности.

shkolnik в сообщении #885893 писал(а):

А разве эта аксиома (теорема) не есть эта самая "связь" ?

Да, ZF и ZFC — это разные теории, и можно в порядке болтологии это оформить как «C сказывается на свойствах $\in$», но на том, что это частичный порядок и не линейный порядок на классе всех множеств, это не сказывается, и C всё-таки независима от ZF, что я и написал выше и что, видимо, стоит перечитать. Ну и ещё, по поводу скобок, для ясности, теорема Цермело является теоремой ZFC и не является теоремой ZF, и C является аксиомой и потому и теоремой ZFC и не является теоремой ZF.

shkolnik в сообщении #885893 писал(а):

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

Кантору почему-то C для рассуждений о мощности не была нужна. Мощность или хотя бы отношение равномощности определяются без опоры на вполне упорядочиваемость и вполне упорядоченность каким-то $R$. Равномощность — это существование биекции и больше ничего! Это существование может следовать для конкретных множеств из каких-то конкретных фактов о них, но это не значит, что порядок потому как-то связывается с равномощностью. Он так же с ней связан как сюръекция с синусом.

[shkolnik]

Xaositect в сообщении #885916 писал(а):

Хорошо, а что такое мощность?

Мощность множества - это равномощный кардинал этого множества. Кардинал – наименьший из равномощных ординалов.

Xaositect в сообщении #885916 писал(а):

Каким образом? Доказательство почти буквально такое же для $\mathbb N \times \mathbb N$, на котором линейного порядка не предполагается.

Порядка не предполагается, а доказательства похожи, потому что, и там, и там, для проверки существования биекции пары обоих множеств взаимоупорядочиваются.

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

Что вы читали?

Дудаков С.М. Основы теории моделей (pdf, скачать, например тут).

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

Кантору почему-то C для рассуждений о мощности не была нужна.

Если не ошибаюсь, он считал, что существует класс всех ординалов, который сам не является ординалом (из-за противоречивости ординала всех ординалов).

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

Мощность или хотя бы отношение равномощности определяются без опоры на вполне упорядочиваемость и вполне упорядоченность каким-то $R$. Равномощность — это существование биекции и больше ничего!

Отношение $R$ это подмножество Декартова произведения множеств, элементами которого являются упорядоченные пары из всех элементов исходных множеств. Само оно не упорядочено и исходные множества могут быть не упорядоченными. Но для того, чтобы определить, каким именно это отношение (множество пар) $R$ является (биективным или нет), само это множество пар $R$ нужно упорядочить. Иначе просто не понять, повторяются ли элементы в упорядоченных парах (инъекция или сюръекция), или они все разные (биекция).

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

Это существование может следовать для конкретных множеств из каких-то конкретных фактов о них, но это не значит, что порядок потому как-то связывается с равномощностью. Он так же с ней связан как сюръекция с синусом.

Боюсь вызвать Ваш гнев, но синус, это функция, а функция это - отношение (с условием $((x,y_1) \in f, (x,y_2) \in f) \to (y_1=y_2)$. Т.е. в каких-то случаях синус - это отношение, возможно, сюръекция.

Xaositect в сообщении #885916 писал(а):

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

Этот тонкий момент я пока не осмыслил полностью. Если кардинал - равномощный представитель ординалов, то при отсутствии ординала-представителя, кардинала как бы тоже нет ? Если же он есть, а ординала нет, значит и множество неупорядочиваемо ?

Xaositect в сообщении #885916 писал(а):

Вот пока мы формально это множество не запишем, мы ничего о его мощности сказать не сможем. Давайте разбираться. Множество состоит из элементов. Какие элементы будут в нашем множестве?

Давайте
Попытка №3:
$X=\{(k,k+1),(k+1,k+2),…(k+n,k+n+1): n \in \mathbb N\} \cup \{(\{\mathbb N\},0)\}$

[Xaositect]

shkolnik в сообщении #886149 писал(а):

Мощность множества - это равномощный кардинал этого множества. Кардинал – наименьший из равномощных ординалов.

Угу, и это определение, которое работает только в присутствии аксиомы выбора, когда у любого множества есть равномощный ему ординал.

shkolnik в сообщении #886149 писал(а):

Иначе просто не понять, повторяются ли элементы в упорядоченных парах (инъекция или сюръекция), или они все разные (биекция).

Нет, для того, чтобы понять, одинаковы элементы или различны, никакого порядка не нужно. Для этого в теории множеств есть равенство.

shkolnik в сообщении #886149 писал(а):

Попытка №3:
$X=\{(k,k+1),(k+1,k+2),…(k+n,k+n+1): n \in \mathbb N\} \cup \{(\{\mathbb N\},0)\}$

А откуда у нас свободная переменная $k$?

-- Чт июл 10, 2014 15:10:43 --

shkolnik в сообщении #886149 писал(а):

Порядка не предполагается, а доказательства похожи, потому что, и там, и там, для проверки существования биекции пары обоих множеств взаимоупорядочиваются.

Что такое "взаимоупорядочиваются"?
Биекцию между $\mathbb{N}\times\mathbb{N}$ и $\mathbb{N}$ можно задать без всякого порядка, например, $f(x, y) = \frac{(x+y)(x+y+1)}{2} + y$

[shkolnik]

Xaositect в сообщении #886162 писал(а):

Нет, для того, чтобы понять, одинаковы элементы или различны, никакого порядка не нужно. Для этого в теории множеств есть равенство.

Кажется, намек понял. Да, из равенства следует равномощность. Но ведь именно благодаря способу построения индуктивных множеств ($(x \in \omega) \to (x \cup \{x\} \in \omega)$) и наличию одного и того же основания $\varnothing$, в Декартовом произведении равномощных ординалов их пары элиминируются в одно и тоже исходное множество. А если множества не индуктивны ? Если одно из них не ординал ? В таком случае, равенство установить так же трудно, как равномощность. Мне почему-то кажется, что без ординалов (упорядоченности) не обойтись.

Xaositect в сообщении #886162 писал(а):

Что такое "взаимоупорядочиваются"?
Биекцию между $\mathbb{N}\times\mathbb{N}$ и $\mathbb{N}$ можно задать без всякого порядка, например, $f(x, y) = \frac{(x+y)(x+y+1)}{2} + y$

Слишком тонкий намек на моё корявое определением $X$, пока не дошло.
Кажется, Ваша формула - тавтология, в смысле любая рациональная функция из $\mathbb{N}\times\mathbb{N}$ в $\mathbb{N}$ будет биективной (элементы $x$ на декартовом квадрате $\mathbb N$ элиминируются с элементами $y$ на $\mathbb N$ из-за способа построения индуктивных множеств).

Xaositect в сообщении #886162 писал(а):

А откуда у нас свободная переменная $k$?

Сам не знаю
Попытка №4:
$X=\{(k,k \cup \{k\}): k \in \omega\} \cup \{(\{\omega\},\varnothing)\}$
Может так будет лучше ?

[Xaositect]

shkolnik в сообщении #886198 писал(а):

Слишком тонкий намек на моё корявое определением $X$, пока не дошло.

Это было не по поводу $X$, это было по поводу "для проверки существования биекции пары обоих множеств взаимоупорядочиваются"

shkolnik в сообщении #886198 писал(а):

Кажется, намек понял. Да, из равенства следует равномощность. Но ведь именно благодаря способу построения индуктивных множеств ($(x \in \omega) \to (x \cup \{x\} \in \omega)$) и наличию одного и того же основания $\varnothing$, в Декартовом произведении равномощных ординалов их пары элиминируются в одно и тоже исходное множество. А если множества не индуктивны ? Если одно из них не ординал ? В таком случае, равенство установить так же трудно, как равномощность. Мне почему-то кажется, что без ординалов (упорядоченности) не обойтись.

Я Вас не понимаю. Вы в предыдущем посте говорили, что "для того, чтобы определить, каким именно это отношение (множество пар) $R$ является (биективным или нет), само это множество пар $R$ нужно упорядочить." Это, вообще говоря, неправда.

shkolnik в сообщении #886198 писал(а):

Кажется, Ваша формула - тавтология, в смысле любая рациональная функция из $\mathbb{N}\times\mathbb{N}$ в $\mathbb{N}$ будет биективной (элементы $x$ на декартовом квадрате $\mathbb N$ элиминируются с элементами $y$ на $\mathbb N$ из-за способа построения индуктивных множеств).

Я не нашел смысла в этом абзаце. Моя формула - не тавтология, а определение некоторой функции, которая будет биекцией $\mathbb{N}^2\to\mathbb{N}$. Очевидно, есть куча рациональных функций $\mathbb{N}^2\to\mathbb{N}$, не являющихся биекциями.

shkolnik в сообщении #886198 писал(а):

$X=\{(k,k \cup \{k\}): k \in \omega\} \cup \{(\{\omega\},\varnothing)\}$
Может так будет лучше ?

Ну и чем здесь так неочевидна счетность? $f\colon X\to \mathbb{N}, f(a,b) = b$ - биекция.

В нашем разговоре как-то все меньше смысла становится.

[arseniiv]

shkolnik в сообщении #886149 писал(а):

Если не ошибаюсь, он считал, что существует класс всех ординалов, который сам не является ординалом (из-за противоречивости ординала всех ординалов).

Как это относится к C (на всякий случай явно напишу, что под C имеется в виду аксиома выбора, но это должно было стать ясно из контекста употребления) или теореме Цермело? Несуществование множества всех ординалов или то, что ординал можно определить в ZF (классы — это, в сущности, формулы с одной свободной переменной). Наивная теория множеств, использованная аккуратно, вся целиком запихивается в ZF(C) — для того ZF и другие аксиоматические теории множеств и создавались — так что эти утверждения об ординалах не влекут C, опять же.

shkolnik в сообщении #886149 писал(а):

Боюсь вызвать Ваш гнев, но синус, это функция, а функция это - отношение (с условием $((x,y_1) \in f, (x,y_2) \in f) \to (y_1=y_2)$. Т.е. в каких-то случаях синус - это отношение, возможно, сюръекция.

(Отступление: обычно удобно, чтобы область значения функции могла быть любым надмножеством $\{y : f(x) = y\}$ (в вашей книжке как раз это названо областью значений), и поэтому или функцию определяют не как отношение, а как тройку, в которую, кроме отношения, называемого при этом графиком функции, входят ещё область значений и определения, или в одном месте бинарное отношение определялось не как подмножество декартова произведения, а как тройка описанного вида. В указанной вами книжке функция — это отношение, и отношение состоит из пар, так что непонятно, как там предлагается разделять $f\colon A\to B_1$ и $f\colon A\to B_2$ и почему осмыслено понятие сюръекции, когда в таком случае все функции — сюръекции, или ко всем функциям сюръективность просто никак не применима. Так что я возьму первый набор определений.)

Ну да, график синуса — всегда отношение, но синус (вещественный) не всегда сюръекция из-за того что множество значений можно брать, например, $\mathbb R$. (Можно так же поопределять синус рядом на тех множествах, с которыми ассоциировано всё нужное для такого определения, и там тоже синус может быть как сюръекцией, так и нет.) И сюръекцию тоже не каждую зовут синусом. Так что некоторые синусы и сюръекции, конечно, совпадают, но не все. И подобная же вещь с порядком и равномощностью — у них не такие простые отношения, как вы пока описываете. «Аналогия» была придумана неудачно — я просто расчитывал, что вы более аккуратно посмотрите на остальное.

shkolnik в сообщении #886149 писал(а):

Если кардинал - равномощный представитель ординалов, то при отсутствии ординала-представителя, кардинала как бы тоже нет ? Если же он есть, а ординала нет, значит и множество неупорядочиваемо ?

Да (кроме второго предложения). Поэтому если в рассматриваемой теории множеств не выполняется теорема Цермело, кардинал определить как особый ординал нельзя, так что кардинал, определённый по-другому, уже не обязан быть ординалом.

В упомянутой вами книге, по крайней мере, ещё несколько (переносимых или не переносимых — зависит от читателя) недочётов подобно тому с сюръекцией (можно было бы предложить, что сюръекцией предлагается называть запись $f\colon A\to B$, но это совсем уж неестественно в тексте там записи такого вида и просто $f$ свободно меняются местами, да и инъективность определяется для функции, а не для записи, и биективность потом использует инъективность и сюръективность на равных. В результате сложившаяся от чтения в голове система может не соответствовать тому, как обычно описанное в книге описывается, если по ней изучать теорию множеств. Мне так показалось.

Вы в это всё можете не сильно вчитываться, потому что главную вещь про то, что хватит равенства, уже сказал Xaositect.

shkolnik в сообщении #886198 писал(а):

В таком случае, равенство установить так же трудно, как равномощность. Мне почему-то кажется, что без ординалов (упорядоченности) не обойтись.

Что вы понимаете под «трудно»? Длину вывода формулы $A\sim B$, что-то с вычислимостью, что-нибудь ещё?

[shkolnik]

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

В результате сложившаяся от чтения в голове система может не соответствовать тому, как обычно описанное в книге описывается, если по ней изучать теорию множеств. Мне так показалось.

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

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

В указанной вами книжке функция — это отношение, и отношение состоит из пар, так что непонятно, как там предлагается разделять $f\colon A\to B_1$ и $f\colon A\to B_2$ и почему осмыслено понятие сюръекции, когда в таком случае все функции — сюръекции, или ко всем функциям сюръективность просто никак не применима.

Единственность образа и сюръекция - не одно и тоже.
Отношения, которые не удовлетворяют условию $((x,y_1) \in f, (x,y_2)\in f) \to (y_1=y_2)$, т.е. где некоторым элементам из $A$ соответствуют несколько элементов из $B$ называют мультифункциями. Это не тоже самое, что сюръекция. Сюръекция, этого когда, наоборот, одному элементу из $B$ соответствует несколько из $A$.
Кстати, про мультифункции мне сказал gris здесь.

Для мультифункций, утверждение, что инъективное и сюръективное отображения являются биективными, либо не верно, либо понятие биективность отражает не то, что для функций. Как видно, количество элементов разное, хотя есть и сюръекция, и инъекция (а т.к. их объединение - биекция, то...).

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

Вы в это всё можете не сильно вчитываться, потому что главную вещь про то, что хватит равенства, уже сказал Xaositect.

Я никак не могу уловить, чем этот аргумент о равенстве помогает, когда мы пытаемся установить, является ли функция инъективной, сюръективной, биективной, или это вообще не функция, а мультифункция ?
Вот есть у нас Декартово произведение пары бесконечных множеств.
Мы тупо берем свойство (отношение $R$), которое выделяет, такие и только такие (нужные нам и именно так упорядоченные) пары. Дальше выделяем уже в нем какие-то функции (биекцию) и прочее. Биективные функции, конечно, существует на этом самом подмножестве Декартова произведения. Только все они, "тавтологии" свойства "быть так-то упорядоченным" и относятся именно к подмножеству Декартова произведения, которое они сами и выделяют, точнее это они и есть это подмножество.
Но, например, мы заведомо оставляем "за бортом", в Декартовом произведении, множество тех пар, на которых наше свойство (отношение $R$) не работает (скажем, нет транзитивности) или наша функция оказывается мультифункция, а не функция.
Чтобы сделать вывод о биекции между исходными множествами (а не каким-то подмножеством их произведения, выделенным свойством "быть биективным"), нужно подбирать только "однозначные" свойства (функции, а не мультифункции) и сравнивать оставшиеся "за бортом" пары, или доказывать пустоту этого множества.

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

Что вы понимаете под «трудно»? Длину вывода формулы $A\sim B$,

Может быть.
-----
Выше, я пытался определить множество $X$.
Мне казалось очевидным, что в этом множестве есть элемент $ (\{\bigcup \{\omega\}\}, \{\omega\})$, предшествующий $(\{\omega\},\varnothing )$ и элемент, предшествующий ему -
$ (\{\bigcup\{\bigcup \{\omega\}\}\}, \{\bigcup \{\omega\}\})$ и т.д. Т.е. последовательность идет и "вниз" и "вверх", они "склеены" в цикл у которого нет, ни основания, ни конца.
Может я опять не так определил $X$ ?

[arseniiv]

shkolnik в сообщении #887425 писал(а):

Единственность образа и сюръекция - не одно и тоже.

А теперь найдите, где я говорил про единственность образа. Я говорил про две функции.

shkolnik в сообщении #887425 писал(а):

Я никак не могу уловить, чем этот аргумент о равенстве помогает, когда мы пытаемся установить, является ли функция инъективной, сюръективной, биективной, или это вообще не функция, а мультифункция ?

Ну хотя бы подумайте о том, что как биективность, так и вполне упорядоченность определяются через $\in$ и $=$, а не биективность через вполне упорядоченность. Вам всё равно придётся в какой-то использованной теореме спуститься до $\in$ и $=$.

shkolnik в сообщении #887425 писал(а):

Только все они, "тавтологии" свойства "быть так-то упорядоченным"

Что имелось в виду?

Я даже уже не стану пытаться понять, каким вы хотите видеть $X$, т. к. все эти иксы оказываются счётными.