Matematyka.pl

Niech \(\displaystyle{ A =\{ 0,1\} }\), \(\displaystyle{ B = A \times A}\) oraz \(\displaystyle{ C = \NN.}\)
Zbadaj przeliczalność zbiorów \(\displaystyle{ A^{*},B^{*},C^{*}. }\)

A cóż to za zbiory (te z gwiazdkami)? Byłoby miło, gdybyś podawał znaczenie nietypowych oznaczeń, których używasz.

JK

Jeśli \(\displaystyle{ X}\) jest zbiorem, to \(\displaystyle{ X^*}\) oznacza zbiór, którego elementami są wszystkie ciągi skończonej długości złożone z elementów ze zbioru \(\displaystyle{ X}\).

To, że te zbiory będą co najwyżej przeliczalne, to znany fakt (o niezbyt pięknym dowodzie), bo jeśli \(\displaystyle{ X}\) jest zbiorem co najwyżej przeliczalnym, to rodzina wszystkich ciągów skończonych o elementach zbioru \(\displaystyle{ X}\), jest co najwyżej przeliczalna- jest to znany fakt.
Ale zauważ, że będą to zbiory nieskończone, bo nawet zbiór \(\displaystyle{ \left\{ 1\right\} ^{*}}\) jest nieskończony, bo jest to zbiór wszystkich ciągów skończonych o elementach równych \(\displaystyle{ 1}\), więc możesz utworzyć takie ciągi skończone:

\(\displaystyle{ \left( 1\right) ; \left( 1,1\right) ; \left( 1,1,1\right); \ldots}\)

których to ciągów jest nieskończenie wiele.

Jakub Gurak pisze: ↑27 lis 2023, o 21:34 To, że te zbiory będą co najwyżej przeliczalne, to znany fakt (o niezbyt pięknym dowodzie),

Z faktu, że na Ważniaku nie podali ładnego dowodu nie wynika, że takiego dowodu nie ma.
Injekcję \(\displaystyle{ \NN^*\to \NN}\) zadaje się dość banalnym wzorem

Przeliczalna suma mnogościowa zbiorów przeliczalnych jest przeliczalna (dowód: rysuje się tabelkę w stylu \(\displaystyle{ \NN \times \NN}\) i węża przez punkty kratowe). Zatem

a4karo pisze: ↑27 lis 2023, o 21:47 Injekcję \(\displaystyle{ \NN^*\to \NN}\) zadaje się dość banalnym wzorem

Janusz Tracz pisze: ↑23 lis 2023, o 23:38

\(\displaystyle{ a\mapsto \prod_{i}^{} p_i^{a_i}}\)

JK