Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Sprawdzanie czy funkcja jest "na". czy jest 1-1

STUDIA

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

#1 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 04.12.2013 - 17:30

Niech \mathcal{R} oznacza rodzinę wszystkich relacji rownoważnosci w zbiorze \NN liczb naturalnych i niech funkcja
F:\mathcal{R} \rightarrow \{0,1\}^{\NN} będzie dana wzorem

F®(n) = \left\{\begin{matrix}<br>\\1 & \mbox{ jeśli do } [n]_R \mbox{ należy liczba parzysta}& \\<br>\\0 & \mbox{w przeciwnym przypadku} &<br>\\\end{matrix}\right.

a) Czy F jest 1-1 ? czy jest "na" \{0,1\}

 

No więc pokażę, jak sprawdzam czy jest "na", a Wy sprawdźcie, poprawcie.

 

Niech F(S) = F ®. Chcemy pokazać, że wtedy S=R.

 

No więc równość F(S) = F® nie oznacza nic innego, jak równości zbiorów wartości tych funkcji. Wobec tego przypuśćmy przeciwnie, tj że S\neq R Oznacza to, że istnieje jakiś element, który należy do S, ale nie należy do R. A skoro tak, to te relacje są różne, a zatem wyznaczają inne podziały zbioru liczb naturalnych na klasy abstrakcji. A skoro inny podział zbioru to musi, to i F(S) \neq F®. A to jest sprzeczność z naszym założeniem. Funkcja jest różnowartościowa

 

 

Pokażę, że nie jest "na".

Powinniśmy móc uzyskać wszystkie funkcje postaci : (N -> {0,1}).

Ale jest funkcja, której nigdy nie uzyskamy, a mianowicie g(n) = 0.

 

Ok ?


Użytkownik xawery edytował ten post 04.12.2013 - 17:32

  • 0

Afroman

    Kombinator

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

Napisano 25.09.2011 - 17:55

#2 hmm

hmm

    Operator całkujący

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

Napisano 04.12.2013 - 20:39

Pokażę, że nie jest "na".

Powinniśmy móc uzyskać wszystkie funkcje postaci : (N -> {0,1}).

Ale jest funkcja, której nigdy nie uzyskamy, a mianowicie g(n) = 0.

 

Ok ?

 

To jest OK. 

 

 

Niech F(S) = F ( R ). Chcemy pokazać, że wtedy S=R.

 

No więc równość F(S) = F( R ) nie oznacza nic innego, jak równości zbiorów wartości tych funkcji. 

Nie, oznacza znacznie więcej. Zbiór wartości prawie wszystkie funkcje mają ten sam: \{0,1\}. Ale ten błąd chyba nie ma dalszych konsekwencji. Być może miałeś na myśli coś innego.

 

 

Wobec tego przypuśćmy przeciwnie, tj że S\neq R Oznacza to, że istnieje jakiś element, który należy do S, ale nie należy do R. A skoro tak, to te relacje są różne, a zatem wyznaczają inne podziały zbioru liczb naturalnych na klasy abstrakcji. 

To prawda, jeśli S\neq R to i klasy abstrakcji będą różne. Ale funkcja F zwraca uwagę tylko na to, czy w klasie danego elementu jest liczba parzysta, dlatego następne zdanie:

 

A skoro inny podział zbioru to musi, to i F(S) \neq F( R )

jest błędne. Weźmy np. dwie relacje równoważności S,R, S będzie relacją równości, tj. (x,y)\in S\Leftrightarrow x=y, a R będzie relacją przystawania modulo 2: (x,y)\in R\Leftrightarrow x=y \textrm{ mod } 2. Klasy abstrakcji pierwszej relacji są jednoelementowe, klasy abstrakcji drugiej są dwie: liczby parzyste i liczby nieparzyste. Jednak F( R )=1 \Leftrightarrow F(S)=1.


Użytkownik hmm edytował ten post 04.12.2013 - 20:39

  • 0

#3 xawery

xawery

    Operator całkujący

  • Użytkownik
  • 374 postów
5
Mały Pomocnik I
  • Płeć:Mężczyzna

Napisano 04.12.2013 - 21:13

Ok, w takim razie może inaczej zaatakuję to:
Oczywiście modulo jest relacją równoważności.

Niech teraz mod 2 będzie relacją w zbiorze N, wtedy otrzymujemy dwie klasy abstrakcji:

R:

[0]_{mod2} = \{ 0, 2, 4,...}

[1]_{mod2} = \{ 1, 3, 5,...}

Teraz:

F( R)(0) = 1

F( R)(1) = 0

F( R)(2) = 1

F( R)(3) = 0

.....

Oraz weźmy INNĄ - RÓŻNĄ relację równoważności mod 4

S:

[0]_{mod4} = \{ 0, 4, 8 , .... \}

[1]_{mod4} = \{1,5,9,.... \}

[2]_{mod4} = \{2,6,10,...\}

[3]_{mod4} = \{3,7,11,...\}

 

F(S)(0) = 1

F(S)(1) = 0

F(S)(2) = 1

F(S)(3) = 0

F(S)(4) = 1

....

 

 

Widać wyraźnie, że relacja równoważności S (mod4) jest różnca od relacji równoważności R (mod2). Mimo to mają równe zbiory wartosc => funkcja nie jest różnowartościowa. Pytanie jak pokazać to tak jak zacząłem, bez powoływania się na przykład.


Użytkownik xawery edytował ten post 04.12.2013 - 21:14

  • 0

#4 hmm

hmm

    Operator całkujący

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

Napisano 04.12.2013 - 22:26

Twój przykład oczywiście też jest dobry. Tyle, że ten jak i mój przykład pokazują, że funkcja nie jest różnowartościowa, a Ty chciałeś pokazać, że jest. Powołanie się na przykład jest w tym przypadku najlepszym sposobem. (Ogólnie czasami można zastosować inny sposób, tj. jeśli moc zbioru wartości jest mniejsza niż zbioru argumentów, to funkcja nie może być różnowartościowa. Tutaj to jednak nie zadziała, bo oba zbiory mają moc continuum.)


  • 0