Bijections de entrada limitada de sequências infinitas

28

Aqui está um quebra-cabeça que não consegui resolver. Gostaria de saber se esse problema já é conhecido ou tem uma solução fácil.

É possível definir uma bijeção usando as propriedades das categorias fechadas bicartesianas. Andrej Bauer postou uma explicação do que isso significa em seu blog como " jóia construtiva: exponenciais de malabarismo ".3N5N

Essa bijeção tem uma propriedade interessante: é "entrada limitada", o que significa que cada componente da saída depende apenas de muitos componentes da entrada. No entanto, para , parece que essa construção só pode mostrar que k N e l N são isomórficos se k e l forem ímpares ou ambos pares. Isso deixa em aberto a questão:k,l2kNlNkl

Existe uma bijeção de entrada limitada de a 3 N ?2N3N

Aqui está uma breve nota descrevendo o problema com mais detalhes: Uma conjectura sobre bijections de entrada limitada de sequências infinitas .

Definições:

Uma função é delimitado por uma entrada se existe um número inteiro k de modo a que cada componente da saída de f depende apenas de, no máximo, k componentes da entrada. Mais formalmente, f é uma entrada limitada se, para cada índice j J, houver índices i 1 , , i kI e uma função f m : Xf:iIXijJYjkfkfjJi1,,ikI tal que para todosxXo componente f(x)jseja igual afj(x i 1 ,,x i k ).fm:Xi1××XikYjxXf(x)jfj(xi1,,xik)

Uma bijeção é uma bijeção de entrada limitada, se for uma função de entrada limitada.f

Uma bijeção é um isomorfismo de entrada limitada se ela e seu inverso são funções de entrada limitada. Isso também é interessante.f

Colin McQuillan
fonte
Provavelmente é melhor copiar a definição de "bijeção de entrada limitada" da sua anotação. Entendi mal a definição até lê-la.
Tsuyoshi Ito 10/10
1
Feito. Gostaria de salientar que, embora a motivação da pergunta venha da semântica da teoria das categorias, o quebra-cabeça em si é combinatório.
Colin McQuillan 10/10
1
A coisa mais irritante sobre esse problema é que parece fácil! Todos os conjuntos são delimitadas-entrada isomorfo para o outro, e, assim, são todos os conjuntos ( 2 k + 1 ) N . Não vejo nenhuma razão para que esses dois não possam ser isomórficos de entrada limitada usando uma variação dos isomorfismos usados ​​nas provas existentes, mas essas tentativas parecem falhar. Aghh. (Eu não tenho experiência neste campo, então posso estar (2k)N(2k+1)N
errado
1
Eu realmente gosto dessa conjectura, e já dura um mês. Eu darei uma recompensa a qualquer um que a resolver ou progredir substancialmente em qualquer direção.
Aaron Sterling
3
Boa pergunta :-) A propósito, qual é o isomorfismo "mais simples" entre e 3 N que você conhece? 2N3N
Andrej Bauer

Respostas:

2

PNPZ

A. Del Junco, "Códigos financeiros entre turnos unilaterais de Bernoulli", Ergodic Theory Dynamical Systems, vol. 1, pp. 285–301, 1981.

PS Pretendo deixar isso como um comentário, mas não posso devido à falta de reputação. Deixe-me saber se está completamente fora do tópico, então eu o excluirei.

gondoleiro
fonte
Agradeço, por um lado, quaisquer idéias malucas de brainstorming neste momento.
Aaron Sterling
2
Observe que se os índices são retirados de ℕ ou ℤ é irrelevante nesta questão.
Tsuyoshi Ito
Eu concedi a recompensa total a essa resposta, porque, se eu não fizesse nada, a resposta receberia metade da recompensa de qualquer maneira, como a mais votada (e tendo recebido pelo menos dois votos). Se alguém postar uma prova completa ou parcial em uma data posterior, e eu a vir, provavelmente começarei outra recompensa, para atribuir um representante ao solucionador.
Aaron Sterling
0

kN2Nkk=3k2k1

2NkN

ii k

kkikki


fonte
2
Essa entrada não é limitada em nenhuma direção. De acordo com a definição de uma função de entrada limitada, você precisa de um limite uniforme para o número de variáveis ​​de entrada das quais cada variável de saída depende. Na direção direta do seu mapeamento, a i-ésima variável de saída depende das primeiras i variáveis ​​de entrada, portanto, não há um limite uniforme. Na direção inversa, a i-ésima variável de saída depende das primeiras variáveis ​​de entrada ki.
Tsuyoshi Ito
1
D'oh. Vou ler a pergunta pela 1,5ª vez. :(