Конечные и бесконечные списки. Определения

[Mysterious Light]

Помогите разобраться:

Пусть дано понятие БУКВА (думаю, пояснять не стоит)
Далее я даю такое опредение новому понятию СЛОВО:
«СЛОВО есть либо БУКВА, либо пара БУКВА-СЛОВО».
То есть всякая БУКВА есть СЛОВО и всякая пара вида БУКВА-СЛОВО есть также слово, других же СЛОВ нет (и быть не может).
Раньше мне казалось, что такое определение корресктно и достаточно (для того, чтоб определять реальное понятие). Но недавно я запутался в следующем: может ли СЛОВО быть бесконечно длинным?

Помоги, пожалуйста, мне разобраться.

[Someone]

Mysterious Light в сообщении #471044 писал(а):

может ли СЛОВО быть бесконечно длинным?

А что ему может запретить?

[VPro]

Начну с полной аналогии. НАТУРАЛЬНОЕ ЧИСЛО есть либо 1 либо НАТУРАЛЬНОЕ ЧИСЛО+1. Вопрос: может ли натуральное число быть бесконечно большим? Ответ очевиден: нет.

[Mysterious Light]

Да вот собственно в том-то и проблема.
С одной стороны мне тоже кажется, что запрещать нет причин. Тому подтверждением может служить и то, что потенциально бесконечные структуры только так и определяются. Например, бесконечные последовательности (цифр, без о.о.) естественно определять как-то так: «БП есть цифра (голова) и БП (хвост)». Хотя на практике удобнее рассматривать как отображение $\mathbb{N}\rightarrow [0..9]$. Собственно, как-то так строятся структуры данных спискочного типа (т.е. список, деревья и им подобные в различных языках программирования), а там порой удобно оперировать бесконечными списками.
С другой же, как правильно сказал VPro, мы многие понятия определяем конструктивным образом. Натуральные числа (см. выше), или, что меня смущало ранее, λ-термы имеют такой же характер определения, но что первые, что вторые всегда конечны, так как конструируя объект (число, терм) "с нуля" мы за конечное число шагов можем "построить" только конечные по размерам объекты.

(Оффтоп)

2 vPro: натуральные числа мне кажутся столь естественными для человека (может, в школе внушили так, не знаю), что мне очень сложно работать с ними настолько формально. Это говорю к тому, что Вами приведенная аналогия является ещё одним поводом для вопроса, и не может рассматриваться как ответ в духе "очевидно ведь".

[VPro]

Мне представляется, что Вы усложняете простой вопрос.
Когда мы имеем дело с пространством бесконечных последовательностей, то мы сразу водим такой объект, как бесконечная последовательность. Мы его постулируем. Ни о каком конструктивном построении бесконечной последовательности речи не идет, поскольку никакого конструктивного способа построить бесконечную последовательность не существует.
Когда мы имеем конструктивное реккурентное определение объектов типа Вашего, то очевидно, что построенный таким образом объект может быть сколь угодно большим, но конечным.
Чтобы в Вашей конструкции появились бесконечные слова, они должны быть введены изначально, как тот "хвост" в Вашем примере.

[Kallikanzarid]

В одних моделях будет, в других - нет.

Пусть алфавитом будет $\{0, 1\}$.

Пример 1: универсум состоит из слов $(0), (1)$ и всех, которые порождаются из них вашим синтаксисом.
Пример 2: универсум примера 1 дополняем словом (00000...0) ($\omega$ нулей) и всеми словами, которые порождаются из него вашим синтаксисом.

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

[Mysterious Light]

Подведу черту (для себя)
Если вводить понятие с реккурентным определением конструктивно, то бесконечных структур нам не за что не достич.
В других же случаях возможны варианты, тогда следует четко определять все доступные нам объекты, среди которых мы выбираем те, что удовлетворяют определению. Тогда, опять же, возможны варианты. Всякое утверждение о наличии бесконечных слов не противоречит определениям.

Спасибо, Kallikanzarid и VPro. Я открою ещё одну тему, в которой спрошу о равенствах таких структур. Но пока я ещё раз подумаю, как лучше сформулировать вопрос

[Someone]

VPro в сообщении #471050 писал(а):

Начну с полной аналогии. НАТУРАЛЬНОЕ ЧИСЛО есть либо 1 либо НАТУРАЛЬНОЕ ЧИСЛО+1. Вопрос: может ли натуральное число быть бесконечно большим? Ответ очевиден: нет.

Натуральное число конечно по определению, каким бы оно ни было. Вы слышали, что арифметика имеет нестандартные модели? С точки зрения теории множеств, в такой модели есть бесконечные натуральные числа. С точки зрения самой арифметики, эти натуральные числа конечны. По определению.
Но теория множеств тоже имеет нестандартные модели... Поэтому натуральные числа, определяемые в теории множеств, также могут оказаться нестандартными.

Mysterious Light в сообщении #471074 писал(а):

С другой же, как правильно сказал VPro, мы многие понятия определяем конструктивным образом. Натуральные числа (см. выше), или, что меня смущало ранее, λ-термы имеют такой же характер определения, но что первые, что вторые всегда конечны, так как конструируя объект (число, терм) "с нуля" мы за конечное число шагов можем "построить" только конечные по размерам объекты.

"Конечное число шагов" - в том смысле, что выражается некоторым натуральным числом. Которое может оказаться нестандартным. Причём, оставаясь в рамках формальной теории, узнать мы об этом не можем...

[VPro]

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

Натуральное число конечно по определению, каким бы оно ни было. Вы слышали, что арифметика имеет нестандартные модели? С точки зрения теории множеств, в такой модели есть бесконечные натуральные числа. С точки зрения самой арифметики, эти натуральные числа конечны. По определению.
Но теория множеств тоже имеет нестандартные модели... Поэтому натуральные числа, определяемые в теории множеств, также могут оказаться нестандартными.

Да, я слушал о нестандартных моделях. Приходилось. Только модель топикастера --- стандартна. Это модель первого порядка. Как только Вы будете расширяь ее в сторону нестандартности, Вы, по существу, будете постулировать существование бесконечных элементов. Естесственно они тут же и возникнут.

[Kallikanzarid]

VPro в сообщении #471774 писал(а):

Только модель топикастера --- стандартна.

У топикстартера нет модели, у него есть только формальный синтаксис.

[Someone]

VPro в сообщении #471774 писал(а):

Да, я слушал о нестандартных моделях. Приходилось. Только модель топикастера --- стандартна. Это модель первого порядка. Как только Вы будете расширяь ее в сторону нестандартности, Вы, по существу, будете постулировать существование бесконечных элементов. Естесственно они тут же и возникнут.

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

Кстати, впервые наблюдаю термин "модель первого порядка". До сих пор мне встречались теории первого порядка.

[Kallikanzarid]

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

Формальная теория ничего не знает о своей модели. Она знает только свои аксиомы.

А если есть аксиома, начинающаяся с предиката существования? По идее тогда должна существовать некая "минимальная модель" вроде универсума фон Неймана в ZF, так?

[Someone]

???
Пусть существует "минимальная модель". Это же не отменяет возможности существования не "минимальных" моделей.

[Kallikanzarid]

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

Пусть существует "минимальная модель". Это же не отменяет возможности существования не "минимальных" моделей.

Это я понимаю :)

[epros]

VPro в сообщении #471050 писал(а):

Начну с полной аналогии. НАТУРАЛЬНОЕ ЧИСЛО есть либо 1 либо НАТУРАЛЬНОЕ ЧИСЛО+1. Вопрос: может ли натуральное число быть бесконечно большим? Ответ очевиден: нет.

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

То же самое касается и:

Mysterious Light в сообщении #471423 писал(а):

Если вводить понятие с реккурентным определением конструктивно, то бесконечных структур нам не за что не достич.

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