zbiór przeliczalny

[rochaj]

Pokaż że zbiór A jest przeliczalny \(\displaystyle{ A=\{f\in\mathbb{N}^{\mathbb{N}}:\bigvee k\bigwedge n\ge k\ (f(2n) = f(2k)\wedge f(2n+1) = f(2k+1))\}}\)

[bartek118]

\(\displaystyle{ A = \bigcup_k \left\{ f \ : \ \forall_{n \geq k} f(2n)=f(2k) \wedge f(2n+1)=f(2k+1) \right\} = \bigcup_k \bigcup_a \bigcup_b \left\{ f \ : \ \forall_{n \geq k} f(2n) =a \wedge f(2n+1) = b \right\}}\)

Dla ustalonych \(\displaystyle{ a,b,k}\) zbiory:
\(\displaystyle{ \left\{ f \ : \ \forall_{n \geq k} f(2n) =a \wedge f(2n+1) = b \right\}}\)
są przeliczalne. Istotnie - możemy wskazać bijekcję: \(\displaystyle{ F : \left\{ f \ : \ \forall_{n \geq k} f(2n) =a \wedge f(2n+1) = b \right\} \rightarrow \mathbb{N}^{k-1}}\) wzorem; dla \(\displaystyle{ f = (f_1, f_2, \ldots)}\):
\(\displaystyle{ F(f) = (f_1, \ldots f_{k-1})}\)
Odwzorowanie to jest odwracalne - dla takiego ciągu skończonego należy dopisać na koniec na przemian \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Mamy zatem:
\(\displaystyle{ A = \bigcup_{(k,a,b) \in \NN^3} \left\{ f \ : \ \forall_{n \geq k} f(2n) =a \wedge f(2n+1) = b \right\}}\)
czyli \(\displaystyle{ A}\) jest przeliczalny.