Цепочка функций

[CAB]

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

Допустим у нас есть цепочка функций (обратимых) $f_n$ и значений $v_n$ которые связывают эти функции, графически это можно представить так:

Как можно доказать (и нужно ли, может достаточно написать "Очевидно что..." :) ) что достаточно иметь только цепочку функций:

и хотя бы одно из значений чтобы вычислить все остальные значения?

Спасибо!

[arseniiv]

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

-- Пн май 01, 2017 21:58:17 --

Это если я правильно понял, что изображены соотношения $f_i(V_i) = V_{i+1}$ для всех $i\in1..m$ для какого-то там $m$. Хотя вместо $1..m$ можно, конечно, взять и (полу)бесконечный промежуток целых чисел.

[CAB]

Я немного переформулировал:

Пусть есть линейно упорядоченное (и возможно бесконечное) множество (цепочка) значений $V$ с элементами $v_i$ и множество произвольных обратимых функций $F$ с элементами $f_i$ связывающих их, таких что результат $f_i$ является аргументом $f_{i+1}$ т.е. $...; v_{i+1}=f_i(v_i); v_{i+2}=f_{i+1}(v_{i+1}); ...$ или в обратном порядке в случае обратных функций, т.е. $...; v_{i+1}=f_{i+1}^{-1}(v_{i+2}); v_i=f_i^{-1}(v_{i+1}); ...$.

Например конечная цепочка значений $V=[4,5,6,5,6,7]$ может быть связана функциями двух типов: инкремента и декремента т.е. $v_{i+1}=inc_i(v_i)=v_i + 1; v_{i+1}=dec_i(v_i)=v_i - 1$ (обратные к ним соответственно $inc^{-1}=dec; dec^{-1}=inc$). Тогда связывающая цепочка функций будет иметь вид: $F=[inc,inc,dec,inc,inc]$.

Лемма: Для вычисления всей цепочки значений $V$ достаточно иметь цепочку функций $F$ и как минимум одно из значений из $V$.

Доказательство: ???

Я думаю о чём то вроде "имея значение $i$ мы можем вычислить значения $i-1$ и $i+1$, имея $i-1$ и $i+1$ мы можем вычислить $i-2$ и $i+2$, и далее следуя этому методу мы вычислим все значения цепочки". Но я не уверен.

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

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

Спасибо, не могли бы вы самую малость развернуть вашу мысль.

[Xaositect]

Я плохо понимаю, в чем у Вас проблема, Вам надо это формально написать?

CAB в сообщении #1213574 писал(а):

Я думаю о чём то вроде "имея значение $i$ мы можем вычислить значения $i-1$ и $i+1$, имея $i-1$ и $i+1$ мы можем вычислить $i-2$ и $i+2$, и далее следуя этому методу мы вычислим все значения цепочки". Но я не уверен.

Да, так и надо, это называется математическая индукция.

Можно, например, сделать так. Пусть дана последовательность обратимых функций $f_i$. Назовем последовательность значений $v_i$ правильной, если $v_{i + 1} = f_i(v_i)$. По индукции можно доказать, что для любых индексов $i,j$ существуют функции $f_{ij}$ такие, что в любой правильной цепочке $v_j = f_{ij}(v_i)$. Отсюда следует, что если мы фиксируем $v_i = v$, то все элементы правильной цепочки определены однозначно: $v_j = f_{ij}(v)$

[arseniiv]

CAB в сообщении #1213574 писал(а):

Пусть есть линейно упорядоченное (и возможно бесконечное) множество (цепочка) значений $V$ с элементами $v_i$ и множество произвольных обратимых функций $F$ с элементами $f_i$ связывающих их, таких что результат $f_i$ является аргументом $f_{i+1}$ т.е. $...; v_{i+1}=f_i(v_i); v_{i+2}=f_{i+1}(v_{i+1}); ...$ или в обратном порядке в случае обратных функций, т.е. $...; v_{i+1}=f_{i+1}^{-1}(v_{i+2}); v_i=f_i^{-1}(v_{i+1}); ...$.

Тут вы не описали связь с порядком и вообще немного криво выразились: можно это понять как $V = \{v_i : i\in A\}$, где $A$ — какой-то промежуток $\mathbb Z$. На самом же деле линейно упорядочено множество значений индексов, и притом не просто линейно упорядочено, а для любого не наибольшего элемента существует наименьший, больший его, и аналогично с обратным порядком. Такие множества изоморфны промежуткам $\mathbb Z$, так что можно ограничиться последними, как в моей формулировке.

[CAB]

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

Я плохо понимаю, в чем у Вас проблема, Вам надо это формально написать?

Да, кроме того я новичок в этом деле :), спасибо за идею.

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

Тут вы не описали связь с порядком и вообще немного криво выразились...

Спасибо, ценный совет.