Ciągi zbiorów

[mol_ksiazkowy]

Zbiory \(\displaystyle{ A_n}\) i \(\displaystyle{ B_n}\) są zdefiniowane \(\displaystyle{ A_1 = \emptyset}\) ,\(\displaystyle{ B_1 = \{ 0 \}}\) oraz
\(\displaystyle{ A_{n+1} = \{ x+1 : x \in B_n \}}\) , \(\displaystyle{ B_{n+1}= A_n \cup B_n \backslash (A_n \cap B_n)}\).
Dla jakich \(\displaystyle{ n}\): \(\displaystyle{ B_n= \{ 0 \}}\) ?

[a4karo]

A ile to jest \(\displaystyle{ \{0\}+1}\)?

[Jan Kraszewski]

A ile to jest \(\displaystyle{ \{0\}+1}\)?

A skąd to wziąłeś?

JK

[a4karo]

No właśnie. Tez się zastanawiam.

[Premislav]

\(\displaystyle{ \left\{ 0\right\}+1=\left\{0\right\}\cup\left\{ \left\{ 0\right\} \right\} =\left\{ 0, \left\{ 0\right\} \right\}=2}\)
Pozdro dla kumatych, elo, WdTZ reprezentuj

[Jakub Gurak]

Nie, polecenie jest sensowne, to są ciągi zbiorów złożonych z liczb naturalnych.

Zauważmy, że \(\displaystyle{ A _{1},B _{1}}\) są zbiorami złożonymi z liczb naturalnych. I jeśli \(\displaystyle{ A _{n},B _{n} \subset \NN}\), to \(\displaystyle{ A_{n+1}, B _{n+1} \subset \NN,}\) co łatwo sprawdzić.

A czy nie ma pomyłki w treści, przecież \(\displaystyle{ A_{n} \cup B _{n} \setminus \left( A _{n} \cap B _{ n} \right)=A _{n} \cup \left( B _{n} \setminus A _{n} \right)=A _{n} \cup B _{n}.}\)

[Premislav]

Moim zdaniem jest pewna nieścisłość w zapisie, chodzi o różnicę symetryczną zbiorów \(\displaystyle{ A_n}\) i \(\displaystyle{ B_n}\).

[kerajs]

A czy nie ma pomyłki w treści, przecież \(\displaystyle{ A_{n} \cup B _{n} \setminus \left( A _{n} \cap B _{ n} \right)=A _{n} \cup \left( B _{n} \setminus A _{n} \right)=A _{n} \cup B _{n}.}\)

Jaka pomyłka? Wiadomo (he, he): wpierw dodawanie, potem dopiero odejmowanie i wtedy ładnie wychodzi:
\(\displaystyle{ A _{2^k}=\left\{ 1,2,4,... , 2^{k-1}\right\} \ \ , \ \ B_{2^k}=\left\{ 0 \right\} \ \ \text{dla} \ \ k \in \NN \setminus \left\{ 0,1\right\}}\)

[Dasio11]

Wprost z treści wynika, że

\(\displaystyle{ B_{m+2} = B_{m+1} \mathbin{\Delta} (B_{m} + 1), \quad (*)}\)

gdzie \(\displaystyle{ \mathbin{\Delta}}\) oznacza różnicę symetryczną, a \(\displaystyle{ B + 1 = \{ b+1 : b \in B \}.}\) Pokażę najpierw indukcyjnie, że \(\displaystyle{ B_{2n} = 2 \cdot B_n := \{ 2 \cdot b : b \in B_n \}}\) dla \(\displaystyle{ n \ge 0}\) (po naturalnym dookreśleniu \(\displaystyle{ B_0 = \varnothing}\), zgodnie z \(\displaystyle{ (*)}\)).

Teza jest oczywista dla \(\displaystyle{ n = 0, 1,}\) bo \(\displaystyle{ B_2 = B_1 = \{ 0 \}.}\) Załóżmy więc, że stwierdzenie jest prawdziwe dla wszystkich \(\displaystyle{ n' < n+2}\). Stosując trzykrotnie \(\displaystyle{ (*)}\) i potem założenie indukcyjne dla \(\displaystyle{ n' = n, n+1}\), otrzymujemy

\(\displaystyle{ $ \begin{align*}
B_{2n+4} & = B_{2n+3} \mathbin{\Delta} (B_{2n+2} + 1) = \big[ B_{2n+2} \mathbin{\Delta} (B_{2n+1} + 1) \big] \mathbin{\Delta} \big[ (B_{2n+1} + 1) \mathbin{\Delta} (B_{2n} + 2) \big] \\
& = B_{2n+2} \mathbin{\Delta} (B_{2n} + 2) = (2 \cdot B_{n+1}) \mathbin{\Delta} (2 \cdot B_n + 2) = 2 \cdot \big( B_{n+1} \mathbin{\Delta} ( B_n + 1 ) \big) = 2 \cdot B_{n+2},
\end{align*} $}\)

co należało wykazać.

Niech teraz \(\displaystyle{ n = 2^k \cdot s}\), gdzie \(\displaystyle{ k \ge 0}\) oraz \(\displaystyle{ s}\) jest liczbą nieparzystą. Powyższa teza indukcyjna daje nam równoważność

\(\displaystyle{ B_n = \{ 0 \} \iff 2^k \cdot B_s = \{ 0 \} \iff B_s = \{ 0 \}.}\)

Wiemy już, że \(\displaystyle{ B_1 = \{ 0 \}}\). Gdy natomiast \(\displaystyle{ s \neq 1}\), to łatwa indukcja daje \(\displaystyle{ 1 \in B_s}\), a zatem ostateczna odpowiedź brzmi:

\(\displaystyle{ B_n = \{ 0 \}}\) wtedy i tylko wtedy, gdy \(\displaystyle{ n = 2^k}\) dla pewnego \(\displaystyle{ k \ge 0}\).