Строгое рекурсивное задание функции

[Duelist]

Здравствуйте, помогите пожалуйста разобраться с рекурсивным заданием функций.
Сначала я понял, что мне потребовалось задать функцию с помощью трансфинитной рекурсии, когда я пытался дать строгое определение произведению произвольного количества (в т.ч. более чем счётного) коммутативных колец. Сами кольца тоже с произвольным количеством элементов.
Я точно не знал, как это делается, нашёл такую теорему: "Для каждого $g$ существует единственная функция $f$ такая, что область определения $f$ есть ординал и $f(x)=g(f|x)$ для каждого порядкового числа $x$." $f|x$ - это сужение $f$ на $x$.
Но я не совсем понимаю, как пользоваться этой теоремой. Допустим у меня есть функция $g$, которая сконструирована, чтобы из $f(x)$ сделать $f(x+1)$ (под $x+1$ подразумевается следующий ординал), ну или там из $f|x$ делать $f|(x+1)$. Но на чём задавать эту функцию? Я же ничего ещё не могу строго сказать о всех значениях функции $f$, каждое из которых должно входить в область определения $g$. Задавать эту функцию на классе всех множеств? Вот так можно?
Но даже со счётной рекурсией у меня стали возникать вопросы.
Вот пусть $a_0=0, a_1=1$, $a_i=a_{i-1}^2+a_{i-2}^2$ - таким образом задали рекурсивную последовательность. По идее, мы имеем отображение $\mathbb{N}$ в какое-то подмножество $\mathbb{N}$. Но если мы будем явно определять эту функцию, как мы определим множество её значений? Нельзя же, записывая определение функции, ссылаться на её же значения? Ведь мы ещё не определили функцию.
Действовать аналогично? Вводить какую-то функцию, которая уже существует?

[Xaositect]

Постоянно встречаются функции, у которых область значений точно неизвестна. В данном случае нам нужна не область значений, а кодомен (то, что в записи $f\colon A\to B$ обозначено буквой $B$).
Если рассматривать рекурсию на натуральных числах, то строится функции $\mathbb{N}\to \mathbb{N}$. Область значений для рекурсивного определения не важна, достаточно того, что все значения натуральные.

[whitefox]

(Codomain vs Range)

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

В данном случае нам нужна не область значений, а кодомен

Согласно русской Википедии, область значений функции это и есть её кодомен. В то время как множество значений функции это её образ (образ домена). В английской Википедии всё не столь однозначно:

WikipediA писал(а):

In mathematics, and more specifically in naive set theory, the range of a function refers to either the codomain or the image of the function, depending upon usage. Modern usage almost always uses range to mean image.

UPD: приведённая выше ссылка на статью в русской Википедии перестала быть актуальной после её правки Xaositect

[Someone]

Duelist в сообщении #1035028 писал(а):

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

Я не понял, какое отношение к произведению колец имеет трансфинитная рекурсия. В том определении произведения алгебраических систем, которое мне известно, никакая рекурсия вообще не употребляется. Вы не могли бы сформулировать определение произведения колец хотя бы для конечного случая? Или для счётного?

[Xaositect]

(wiki)

whitefox в сообщении #1035070 писал(а):

Согласно русской Википедии, область значений функции это и есть её кодомен.

Пойду перепишу.

[Duelist]

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

Я не понял, какое отношение к произведению колец имеет трансфинитная рекурсия. В том определении произведения алгебраических систем, которое мне известно, никакая рекурсия вообще не употребляется. Вы не могли бы сформулировать определение произведения колец хотя бы для конечного случая? Или для счётного?

Пусть $K$ - множество колец $A_0$ , ... , $A_n$ ; Пусть $T=\{x: \exists i (i \in (n+1) \wedge x \in A_i)\}$ ; $F^*$ - мн-во всех функций из $0 \dots n$ в $T$ ;
Тогда $F= \{x: x \in F^* \wedge ( (u,v) \in x \Rightarrow v \in A_u)\}$. Остаётся задать на $F$ алгебраическую структуру.
Если я не ошибся с этим определением, то оно вроде бы легко обобщается и на трансфинитную область.
Но это я теперь его придумал, а изначальной мыслью было построение сначала первого эл-та произведения колец, со всеми минимальными элементами колец на каждой координате, а потом определение всех остальных по рекурсии, перебирая их как бы по "секундомерному" принципу. И всё-таки это было бы возможно? Я правильно говорил о той теореме?

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

Постоянно встречаются функции, у которых область значений точно неизвестна. В данном случае нам нужна не область значений, а кодомен (то, что в записи $f\colon A\to B$ обозначено буквой $B$).
Если рассматривать рекурсию на натуральных числах, то строится функции $\mathbb{N}\to \mathbb{N}$. Область значений для рекурсивного определения не важна, достаточно того, что все значения натуральные.

Но как тогда формально записать это множество на языке теории множеств, я имею в виду функцию, заданную рекурсивно?

[Someone]

Duelist в сообщении #1035207 писал(а):

Пусть $K$ - множество колец $A_0$ , ... , $A_n$ ; Пусть $T=\{x: \exists i (i \in (n+1) \wedge x \in A_i)\}$ ; $F^*$ - мн-во всех функций из $0 \dots n$ в $T$ ;
Тогда $F= \{x: x \in F^* \wedge ( (u,v) \in x \Rightarrow v \in A_u)\}$. Остаётся задать на $F$ алгебраическую структуру.

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

Пусть $\mathscr K=\{A_t:t\in T\}$ — индексированное семейство множеств (здесь $T$ — множество индексов). Обозначим

$$\mathscr A=\bigcup\mathscr K=\bigcup\limits_{t\in T}A_t$$

объединение всех множеств семейства $\mathscr K$.

Произведение семейства множеств $\mathscr K$ — это множество всех функций $f\colon T\to\mathscr A$, удовлетворяющих условию $\forall t\in T(f(t)\in A_t)$.

В этом определении совершенно не важно, является ли множество индексов конечным или бесконечным, счётным или несчётным, упорядоченным или не упорядоченным.

Если все $A_t$, $t\in T$, являются однотипными алгебраическими системами, то операции на произведении определяются "покоординатно". Никакая индукция не требуется.

[Duelist]

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

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

Пусть $\mathscr K=\{A_t:t\in T\}$ — индексированное семейство множеств (здесь $T$ — множество индексов). Обозначим

$$\mathscr A=\bigcup\mathscr K=\bigcup\limits_{t\in T}A_t$$

объединение всех множеств семейства $\mathscr K$.

Произведение семейства множеств $\mathscr K$ — это множество всех функций $f\colon T\to\mathscr A$, удовлетворяющих условию $\forall t\in T(f(t)\in A_t)$.

В этом определении совершенно не важно, является ли множество индексов конечным или бесконечным, счётным или несчётным, упорядоченным или не упорядоченным.

Спасибо. У меня примерно тоже, только у Вас гораздо более элегантно сформулировано и обобщено. Правда, в моей форме это тоже мгновенно обобщается.

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

Если все $A_t$, $t\in T$, являются однотипными алгебраическими системами, то операции на произведении определяются "покоординатно".

Вот я определял сложение, по-моему, тоже как-то сильно чудно получилось: пусть для любого $i \in T$ $m_i$ - множество троек, определяющих сложение в кольце $A_i$, тогда в произведении колец сложение можно определить так:
$\forall A,B,C$ $\in$ $\prod\limits_{t \in T}$$A_t$ $(A+B=C\Leftrightarrow \forall i \in T, \forall a,b,c$ $(a_i \in A\wedge b_i \in B\wedge c_i\in C\Rightarrow (a,b,c) \in m_i))$

Тут правильно? И как это лучше записывается?

[Someone]

О боже! Фобос и Деймос!

Пусть $f$ и $g$ — элементы произведения колец, то есть, функции $f\colon T\to\mathscr A$ и $g\colon T\to\mathscr A$, удовлетворяющие условиям $f(t)\in A_t$ и $g(t)\in A_t$ для всех $t\in T$. Тогда по определению полагаем $(f+g)(t)=f(t)+g(t)$ и $(f\cdot g)(t)=f(t)\cdot g(t)$ для всех $t\in T$.

Конечно, надо проверить корректность определения, то есть, что определённые таким образом сумма и произведение являются элементами произведения колец, и что все аксиомы кольца выполняются.

Duelist в сообщении #1035353 писал(а):

Правда, в моей форме это тоже мгновенно обобщается.

Ага. Я уже видел. Трансфинитная рекурсия и всё такое прочее.

[Duelist]

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

О боже! Фобос и Деймос!

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

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

Пусть $f$ и $g$ — элементы произведения колец, то есть, функции $f\colon T\to\mathscr A$ и $g\colon T\to\mathscr A$, удовлетворяющие условиям $f(t)\in A_t$ и $g(t)\in A_t$ для всех $t\in T$. Тогда по определению полагаем $(f+g)(t)=f(t)+g(t)$ и $(f\cdot g)(t)=f(t)\cdot g(t)$ для всех $t\in T$.

Конечно, надо проверить корректность определения, то есть, что определённые таким образом сумма и произведение являются элементами произведения колец, и что все аксиомы кольца выполняются.

Спасибо, напишу Ваше определение себе в тетрадку вместо того, что я писал.

Someone писал(а):

Duelist писал(а):

Правда, в моей форме это тоже мгновенно обобщается.

Ага. Я уже видел. Трансфинитная рекурсия и всё такое прочее.

Ну, не согласен, тут нормально обобщается: Пусть $K$ - мн-во колец, $Card(K)=n$ ; Упорядочим $K$ отображением $f: n \rightarrow K$ ; Пусть $T=\{x: \exists i (i \in n \wedge x \in f(i))\};$ $F^*$ - мн-во всех функций из кардинала $n$ в $T$. Тогда $F= \{x: x \in F^* \wedge ( (u,v) \in x \Rightarrow v \in f(u))\}$.

[Someone]

Duelist в сообщении #1035510 писал(а):

Упорядочим $K$ отображением $f: n \rightarrow K$

А что такое $n$? Я понимаю, что кардинал, но кардинал, вообще говоря, не есть какое-то конкретное множество, и уж, конечно, совсем не обязательно на нём есть какое-то отношение порядка (в ZFC часто кардиналам сопоставляют начальные ординалы соответствующей мощности, но это не обязательно, поскольку кардинал можно представлять себе как класс равномощных множеств). И зачем упорядочивать $K$, если этот порядок потом в определении не используется?

[Duelist]

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

А что такое $n$? Я понимаю, что кардинал, но кардинал, вообще говоря, не есть какое-то конкретное множество, и уж, конечно, совсем не обязательно на нём есть какое-то отношение порядка (в ZFC часто кардиналам сопоставляют начальные ординалы соответствующей мощности...

Я, как раз, под кардиналом подразумеваю наименьший ординал из всех равномощных. И подразумеваю, что ординалы вполне упорядочены отношением принадлежности ($\in$ - отношение).

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

И зачем упорядочивать $K$, если этот порядок потом в определении не используется?

Потому что везде должен быть порядок Да, лучше сказать "проиндексируем". И ещё там надо добавить, что отображение биективное.

[Someone]

Duelist в сообщении #1035529 писал(а):

И ещё там надо добавить, что отображение биективное.

Как раз не надо. Потому что часто встречается ситуация, когда все множества $A_t$ — это одно и то же множество $A$. Тогда у нас получается степень $A^n$, где $n=\lvert T\rvert$ (часто используется обозначение $A^T$).

-- Пт июл 10, 2015 20:32:56 --

Duelist в сообщении #1035529 писал(а):

Потому что везде должен быть порядок

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

Duelist в сообщении #1035529 писал(а):

Да, лучше сказать "проиндексируем".

Индексация — это то же самое, что отображение. Просто вместо $f(t)$ пишем $f_t$.

[Duelist]

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

Duelist в сообщении #1035529 писал(а):

И ещё там надо добавить, что отображение биективное.

Как раз не надо. Потому что часто встречается ситуация, когда все множества $A_t$ — это одно и то же множество $A$. Тогда у нас получается степень $A^n$, где $n=\lvert T\rvert$ (часто используется обозначение $A^T$).

А, ну да, забыл, что необязательно все кольца в произведении различны. Биективность не нужна. Сам кардинал $n$ определяет "длину" произведения. Должно быть только $n \geq Card(K)$.

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

Индексация — это то же самое, что отображение. Просто вместо $f(t)$ пишем $f_t$.

Ну это я понимаю.

[Duelist]

Просто надо было функцию назвать не $f$, а $A$ и писать не $f(i),$ а $A_i.$