Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Wykazać, przeliczalność

STUDIA

  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
2 odpowiedzi w tym temacie

#1 Ktos Jakies

Ktos Jakies

    Przeliczalny

  • Użytkownik
  • 37 postów
0
Neutralny
  • Płeć:Kobieta

Napisano 08.12.2013 - 20:24

 Niech Z będzie zbiorem tych nieskończonych ciągów o wyrazach naturalnych,
które mają tylko skończenie wiele wyrazów niezerowych. Dla f ∈ N^N deniujemy
 
W_F \lbrace= g\in N^N: \ \exists k\in N \forall n\geq k \ g(n)\leq f(n) \rbrace
a) Wykaż, że jeżeli f ∈ Z oraz g ∈ W_f, to g ∈ Z.
b) Wykaż, że jeżeli f ∈ Z, to zbiór W_f jest przeliczalny

Użytkownik Ktos Jakies edytował ten post 08.12.2013 - 20:24

  • 0

Dziekuje wszystkim użytkownikom forum, jesteście bardzo pomocni i sprawiacie, ze moje studiowanie staje sie łatwiejsze :)!


Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1007
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 08.12.2013 - 23:53

a) jest łatwe

w b) zauważ, że wystarczy jak pokażemy, że Z jest przeliczalny. Niech A_k oznacza zb. ciągów które od k+1-ego miejsca są zerowe. Wówczas A_k jest przeliczalny, bo ma moc \mathbb{N}^k a Z = \bigcup_{k=0}^{\infty} A_k czyli też jest przeliczalny jako przeliczalna suma zb. przeliczalnych.


  • 0

#3 hmm

hmm

    Operator całkujący

  • VIP
  • 478 postów
312
Instruktor I
  • Płeć:Mężczyzna

Napisano 09.12.2013 - 00:13

Inny sposób pokazania, że zbiór Z jest przeliczalny: mamy funkcję różnowartościową Z\to \mathbb{Q} która ciąg f:\mathbb{N}\to\mathbb{N} odwzorowuje na ułamek łańcuchowy [f(0);f(1),f(2),\ldots, f(N),2], gdzie N jest największą liczbą taką, że f(N)\neq 0 (dwójka na końcu jest sztucznie dorzucona po to, żeby odwzorowanie było różnowartościowe, inaczej byłby problem gdyby ostatnią niezerową liczbą było 1).

 

I jeszcze mała uwaga: tak naprawdę jeśli f\in Z, to W_f=Z.


  • 0