Skip to main content
MathOverflow

Return to Answer

added 45 characters in body
Source Link
bof
bof
  • 13.4k
  • 2
  • 43
  • 66

This solution, for an unknown position in an $\omega$-sequence with an arbitrary palette of colors for the hats, is apparently due to F. Galvin, American Mathematical Monthly Problem 5348, 1965.

Theorem. For any set $E$ there is a function $f:E^\omega\to E$ such that, for every infinite sequence $(x_1,x_2,x_3,\dots)\in E^\omega$, we have $x_n=f(x_{n+1},x_{n+2},x_{n+3},\dots)$ for all but finitely many $n$.

Proof. Define an equivalence relation in $E^\omega$ by calling two sequences $x,y\in E^\omega$ equivalent if they have a common tailfinal segment, i.e., if $(x_m,x_{m+1},x_{m+2},\dots)=(y_n,y_{n+1},y_{n+2},\dots)$ for some $m,n$. Choose an element from each equivalence class; if there are periodic sequencesequences in the class, be sure to choose one of those. Let $C$ be the set of sequences so chosen.

Given an infinite sequence $x=(x_1,x_2,x_3,\dots)\in E^\omega$, define $f(x)=x_0$ so that, if possible, $(x_0,x_1,x_2,x_3,\dots)\in C$$(x_0,x_1,x_2,x_3,\dots)$ is a final segment of an element of $C$; if such a choice is not possible, let $x_0=x_1$. It is easy to see that this function $f$ has the desired property.

This solution, for an unknown position in an $\omega$-sequence with an arbitrary palette of colors for the hats, is apparently due to F. Galvin, American Mathematical Monthly Problem 5348, 1965.

Theorem. For any set $E$ there is a function $f:E^\omega\to E$ such that, for every infinite sequence $(x_1,x_2,x_3,\dots)\in E^\omega$, we have $x_n=f(x_{n+1},x_{n+2},x_{n+3},\dots)$ for all but finitely many $n$.

Proof. Define an equivalence relation in $E^\omega$ by calling two sequences $x,y\in E^\omega$ equivalent if they have a common tail, i.e., if $(x_m,x_{m+1},x_{m+2},\dots)=(y_n,y_{n+1},y_{n+2},\dots)$ for some $m,n$. Choose an element from each equivalence class; if there are periodic sequence in the class, be sure to choose one of those. Let $C$ be the set of sequences so chosen.

Given an infinite sequence $x=(x_1,x_2,x_3,\dots)\in E^\omega$, define $f(x)=x_0$ so that, if possible, $(x_0,x_1,x_2,x_3,\dots)\in C$; if such a choice is not possible, let $x_0=x_1$. It is easy to see that this function $f$ has the desired property.

This solution, for an unknown position in an $\omega$-sequence with an arbitrary palette of colors for the hats, is apparently due to F. Galvin, American Mathematical Monthly Problem 5348, 1965.

Theorem. For any set $E$ there is a function $f:E^\omega\to E$ such that, for every infinite sequence $(x_1,x_2,x_3,\dots)\in E^\omega$, we have $x_n=f(x_{n+1},x_{n+2},x_{n+3},\dots)$ for all but finitely many $n$.

Proof. Define an equivalence relation in $E^\omega$ by calling two sequences $x,y\in E^\omega$ equivalent if they have a common final segment, i.e., if $(x_m,x_{m+1},x_{m+2},\dots)=(y_n,y_{n+1},y_{n+2},\dots)$ for some $m,n$. Choose an element from each equivalence class; if there are periodic sequences in the class, be sure to choose one of those. Let $C$ be the set of sequences so chosen.

Given an infinite sequence $x=(x_1,x_2,x_3,\dots)\in E^\omega$, define $f(x)=x_0$ so that, if possible, $(x_0,x_1,x_2,x_3,\dots)$ is a final segment of an element of $C$; if such a choice is not possible, let $x_0=x_1$. It is easy to see that this function $f$ has the desired property.

Source Link
bof
bof
  • 13.4k
  • 2
  • 43
  • 66

This solution, for an unknown position in an $\omega$-sequence with an arbitrary palette of colors for the hats, is apparently due to F. Galvin, American Mathematical Monthly Problem 5348, 1965.

Theorem. For any set $E$ there is a function $f:E^\omega\to E$ such that, for every infinite sequence $(x_1,x_2,x_3,\dots)\in E^\omega$, we have $x_n=f(x_{n+1},x_{n+2},x_{n+3},\dots)$ for all but finitely many $n$.

Proof. Define an equivalence relation in $E^\omega$ by calling two sequences $x,y\in E^\omega$ equivalent if they have a common tail, i.e., if $(x_m,x_{m+1},x_{m+2},\dots)=(y_n,y_{n+1},y_{n+2},\dots)$ for some $m,n$. Choose an element from each equivalence class; if there are periodic sequence in the class, be sure to choose one of those. Let $C$ be the set of sequences so chosen.

Given an infinite sequence $x=(x_1,x_2,x_3,\dots)\in E^\omega$, define $f(x)=x_0$ so that, if possible, $(x_0,x_1,x_2,x_3,\dots)\in C$; if such a choice is not possible, let $x_0=x_1$. It is easy to see that this function $f$ has the desired property.