Ограниченные входные биекции бесконечных последовательностей

28

Вот загадка, которую мне не удалось решить. Я хотел бы знать, если эта проблема уже известна, или имеет простое решение.

Можно определить биекцию используя свойства бикартезианских замкнутых категорий. Андрей Бауэр опубликовал объяснение того, что это значит, в своем блоге как « Конструктивный камень: жонглирование экспонентами ».3N5N

Эта биекция обладает интересным свойством: это «ограниченный ввод», означающий, что каждый компонент вывода зависит только от ограниченного числа компонентов ввода. Однако для кажется, что эта конструкция может показать только то, что и изоморфны, если и оба нечетны или оба четны. Это оставляет открытым вопрос:k N l N k lk,l2kNlNkl

Существует ли биекция с ограниченным входом от до ? 3 Н2N3N

Вот короткое примечание, описывающее проблему более подробно: Гипотеза относительно ограниченных входных биекций бесконечных последовательностей .

Определения:

Функция является ограниченно-входной, если существует целое число такое, что каждый компонент вывода зависит только от не более чем компонентов ввода. Более формально, является ограниченным входом, если для каждого индекса есть индексы и функция такой, что для всех компонент равен . K F к F J J я 1 , , я Kя е т : Х я 1 × × Х я кY J х Х е ( х ) j f j ( x i 1 ,f:iIXijJYjkfkfjJi1,,ikIfm:Xi1××XikYjxXf(x)jfj(xi1,,xik)

Биекция является биекцией с ограниченным входом, если она является функцией с ограниченным входом.f

Биекция является изоморфизмом с ограниченным входом, если он и его обратное являются функциями с ограниченным входом. Это тоже интересно.f

Колин Маккуиллан
источник
Вероятно, лучше скопировать определение «ограниченного ввода биекции» из вашей заметки. Я неправильно понял определение, пока не прочитал его.
Цуёси Ито
1
Выполнено. Я хотел бы отметить, что, хотя мотивация вопроса исходит из семантики теории категорий, сама головоломка является комбинаторной.
Колин Маккуиллан
1
Самое неприятное в этой проблеме то, что она выглядит просто! Все множества ограничены по входу, изоморфны друг другу, как и все множества . Я не вижу никакой причины, почему эти два нельзя сделать изоморфными с ограниченным входом, используя вариацию изоморфизмов, использованных в существующих доказательствах, но такие попытки, похоже, проваливаются. Aghh. (У меня нет опыта в этой области, поэтому я могу быть не в курсе.) ( 2 k + 1 ) N(2k)N(2k+1)N
Tsuyoshi Ito
1
Мне очень нравится эта гипотеза, и она болтается уже месяц. Я дам вознаграждение любому, кто решит его или добьется существенного прогресса в любом направлении.
Аарон Стерлинг
3
Хороший вопрос :-) Кстати, какой самый простой изоморфизм между и о котором вы знаете? 3 Н2N3N
Андрей Бауэр

Ответы:

2

Я не парень по теории КС. Но в эргодической теории этот тип отображения известен как финитарные изоморфизмы. Например, люди рассматривали вопрос о том, являются ли две последовательности Бернулли одной и той же энтропии конечно изоморфными или нет. Например (это односторонний сдвиг, потому что кажется, что вы заинтересованы в а не в ): П ЗPNPZ

А. Дель Юнко, «Финитные коды между односторонними сдвигами Бернулли», Эргодическая теория динамических систем, вып. 1, с. 285–301, 1981.

PS Я намерен оставить это как комментарий, но не могу из-за отсутствия репутации. Дайте мне знать, если это не по теме, тогда я его удалю.

гондольер
источник
Я, например, приветствую любые дурацкие идеи мозгового штурма на данный момент.
Аарон Стерлинг
2
Обратите внимание, что в этом вопросе не имеет значения, взяты ли индексы из ℕ или ℤ.
Цуёси Ито
Я получил полную награду за этот ответ, потому что, если бы я ничего не сделал, ответ все равно получил бы половину награды, как большинство проголосовавших (и получив по крайней мере два голоса). Если кто-то опубликует полное или частичное доказательство позднее, и я это увижу, я, вероятно, назначу еще одну награду, чтобы наградить представителя решателю.
Аарон Стерлинг
0

kN2Nkk=3k2k1

2NkN

ii k

kkikki


источник
2
Это не ограниченный ввод в любом направлении. В соответствии с определением функции с ограниченным входом, вам нужна равномерная граница для числа входных переменных, от которых зависит каждая выходная переменная. В прямом направлении вашего отображения i-я выходная переменная зависит от первых входных переменных i, поэтому не существует равномерной границы. В обратном направлении i-я выходная переменная зависит от первых ki входных переменных.
Tsuyoshi Ito
1
D'о. Я собираюсь пойти читать вопрос в 1,5-й раз. :(