Matematyka.pl

Udowodnić, że istnieje funkcja \(\displaystyle{ A\colon \bigcup_{k\in\omega} 2^k\rightarrow \mathcal P\left(2^{\mathbb N}\right)}\) określona na zbiorze wszystkich skończonych ciągów zero-jedynkowych (o wartościach będących podzbiorami kostki Cantora) taka, że dla dowolnego ciągu \(\displaystyle{ x=(x_1,x_2,\ldots)\in 2^{\mathbb N}}\) i dla dowolnego ciągu skończonego \(\displaystyle{ c=(c_0,\ldots,c_{k-1})}\) długości \(\displaystyle{ k>0}\) zachodzi warunek

\(\displaystyle{ \left( \left(x\in A(\emptyset) \iff c_0=0\right)\wedge\left( c_1,\ldots, c_{k-1}\right)= \left(x_1,\ldots, x_{k-1}\right)\right)\implies\left( x_k=0 \iff (x_{k+1},x_{k+2},\ldots) \in A(c) \right) }\).

Zadanie ma fajną interpretację w postaci zagadki: PS. Nie znam rozwiązania.

A kto jest ostatni w nieskończonym ciągu?

No ten pierwszy...

JK

Jak stoisz w kolejce do sklepu i widzisz wszystkich przed sobą to znaczy, że jesteś ostatni.

Załóżmy, że \(\displaystyle{ A( \varnothing )}\) jest dane, i zobaczmy, jakie warunki nakłada to na pozostałe wartości.

Rozważmy dowolny ciąg \(\displaystyle{ x = (x_1, x_2, \ldots) \in 2^{\mathbb{N}}}\) i \(\displaystyle{ k > 0}\). Określmy \(\displaystyle{ c = (c_0, \ldots, c_{k-1})}\) tak, że \(\displaystyle{ c_0 = 0 \iff x \in A(\varnothing)}\) oraz \(\displaystyle{ (c_1, \ldots, c_{k-1}) = (x_1, \ldots, x_{k-1})}\). Wtedy musi zachodzić \(\displaystyle{ (x_{k+1}, x_{k+1}, \ldots) \in A(c) \iff x_k = 0}\). W skrócie powiemy, że ciąg \(\displaystyle{ x \in 2^{\mathbb{N}}}\) wymusza warunek \(\displaystyle{ (x_{k+1}, x_{k+2}, \ldots) \in A(c)}\) lub \(\displaystyle{ (x_{k+1}, x_{k+2}, \ldots) \notin A(c)}\) (w zależności od \(\displaystyle{ x_k}\)). Oznaczmy też \(\displaystyle{ c(x) := c}\) i \(\displaystyle{ c_0(x) = c_0}\).

Kiedy powyższe warunki są wzajemnie sprzeczne? Dokładnie wtedy, gdy dla pewnego \(\displaystyle{ z \in 2^{\mathbb{N}}}\) oraz pewnego skończonego ciągu \(\displaystyle{ c \in 2^{<\omega}}\) wymuszone jest, by \(\displaystyle{ z \in A(c)}\) i zarazem \(\displaystyle{ z \notin A(c)}\). Konkretniej, pewien ciąg \(\displaystyle{ x \in 2^{\mathbb{N}}}\) wymusza \(\displaystyle{ z \in A(c)}\), a inny ciąg \(\displaystyle{ y \in 2^{\mathbb{N}}}\) wymusza \(\displaystyle{ z \notin A(c)}\). Jest tak dokładnie wtedy, gdy \(\displaystyle{ c(x) = c = c(y)}\) oraz \(\displaystyle{ (x_{k+1}, x_{k+2}, \ldots) = z = (y_{k+1}, y_{k+2}, \ldots)}\), a ponadto \(\displaystyle{ x_k = 0}\) i \(\displaystyle{ y_k = 1}\). Upraszczając, jest tak wtedy gdy \(\displaystyle{ x}\) i \(\displaystyle{ y}\) różnią się dokładnie na \(\displaystyle{ k}\)-tej pozycji, ale \(\displaystyle{ c_0(x) = c_0(y)}\).

Zatem warunki są niesprzeczne, jeśli tylko \(\displaystyle{ \# \{ n \in \mathbb{N} : x(n) \neq y(n) \} = 1}\) implikuje \(\displaystyle{ c_0(x) \neq c_0(y)}\) dla dowolnych ciągów \(\displaystyle{ x, y \in 2^{\mathbb{N}}}\). Nietrudno znaleźć taką funkcję \(\displaystyle{ c_0}\), a to jednoznacznie definiuje \(\displaystyle{ A( \varnothing )}\) i wszystkie pozostałe wartości na mocy rozumowania wyżej.