1.
Niech \(\displaystyle{ R \subseteq A^{2}}\) będzie pewną relacją binarną na zbiorze \(\displaystyle{ A}\) oraz
\(\displaystyle{ \mathcal{T} = S \subseteq A^{2} | S}\) jest przechodnia \(\displaystyle{ \wedge R \subseteq S}\)
\(\displaystyle{ R^{+} = \cap \mathcal{T}}\)
Pokaż, że
a) \(\displaystyle{ R \subseteq R^{+}}\)
b) Jeśli \(\displaystyle{ S}\) jest relacją przechodnią taką, że \(\displaystyle{ R \subseteq S}\) to \(\displaystyle{ R^{+} \subseteq S}\)
c) \(\displaystyle{ R^{+}}\) jest relacją przechodnią.
Relacja \(\displaystyle{ R^{+}}\) jest zatem najmniejszą (w sensie zawierania zbiorow) relacją przechodnią zawierającą relację R.
2. Udowodnij, że instnieje dokładnie jedna monotoniczna bijekcja \(\displaystyle{ f : \mathbb{N} \rightarrow \mathbb{ N}}\)
3. Udowodnij, że jeśli \(\displaystyle{ f : A \rightarrow B}\) i g : \(\displaystyle{ B \rightarrow A}\) są takimi funkcjami, że \(\displaystyle{ gf = I_{A}}\) to \(\displaystyle{ f}\) jest różnowartościowa a \(\displaystyle{ g}\) jest "na"
Z góry wielkie dzięki za pomoc - dawno mnie tu nie było, zawsze komuś pomagałem i w końcu przyszła pora, że to ja proszę o pomoc
Relacje i funkcje.
-
Tomasz Tkaczyk
- Użytkownik
- Posty: 476
- Rejestracja: 20 cze 2008, o 21:34
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 8 razy
- Pomógł: 93 razy
Relacje i funkcje.
(1) \(\displaystyle{ \mathcal{T} = \lbrace S \subseteq A^{2} |}\) S jest przechodnia \(\displaystyle{ \wedge R \subseteq S \rbrace}\).
(a) \(\displaystyle{ R \subseteq S}\) dla każdego \(\displaystyle{ S \in \mathcal{T}}\), zatem \(\displaystyle{ R \subseteq \bigcap \mathcal{T} = R^{+}}\).
(b) jeśli \(\displaystyle{ S}\) jest relacją przechodnią zawierającą \(\displaystyle{ R}\), to \(\displaystyle{ S \in \mathcal{T}}\), zatem \(\displaystyle{ \bigcap \mathcal{T} \subseteq S}\) (bo część wspólna rodziny zbiorów zawiera się w każdym z tych zbiorów).
(c) Weźmy dowolne \(\displaystyle{ a, b, c \in A}\) i załóżmy, że \(\displaystyle{ a R^{+} b}\) i \(\displaystyle{ b R^{+} c}\).
Wówczas dla każdego \(\displaystyle{ S \in \mathcal{T}}\)
\(\displaystyle{ a S b}\) i \(\displaystyle{ b S c}\).
Z przechodniości relacji ze zbioru \(\displaystyle{ \mathcal{T}}\) mamy, że
dla każdego \(\displaystyle{ S \in \mathcal{T}}\)
\(\displaystyle{ a S c}\), zatem
\(\displaystyle{ a R^{+} c}\), co dowodzi przechodniości \(\displaystyle{ R^{+}}\).
(2)
Funkcja \(\displaystyle{ Id: N \rightarrow N}\) określona wzorem \(\displaystyle{ Id(n) = n}\) jest monotoniczną bijekcją zbioru liczb naturalnych.
Pokażemy, że jest to jedyna taka bijekcja.
Załóżmy, że istnieje inna monotoniczna bijekcja \(\displaystyle{ f}\) zbioru liczb naturalnych.
Wówczas \(\displaystyle{ (\exists n \in N)(f(n) \neq n)}\).
Niech \(\displaystyle{ n_{0}}\) będzie najmniejszą liczbą naturalną, dla której \(\displaystyle{ f(n_{0}) \neq n_{0}}\).
Zatem \(\displaystyle{ \forall m < n_{0}}\)
\(\displaystyle{ f(m) = m}\).
Więc \(\displaystyle{ f(n_{0}) > n_{0}}\), gdyż \(\displaystyle{ f}\) jest bijekcją.
\(\displaystyle{ f}\) jest monotoniczna (rosnąca), zatem nie istnieje takie \(\displaystyle{ k}\), że \(\displaystyle{ f(k) = n_{0}}\), co przeczy temu, że \(\displaystyle{ f}\) jest bijekcją.
(3)
Sprawdźmy różnowartościowość funkcji \(\displaystyle{ f}\).
Weźmy różne elementy \(\displaystyle{ a, b \in A}\).
Gdyby \(\displaystyle{ f(a) = f(b)}\), to
\(\displaystyle{ a = g(f(a)) = g(f(b)) = b}\). Sprzeczność.
Sprawdzimy, że \(\displaystyle{ g}\) jest "na".
Weźmy dowolny element \(\displaystyle{ a \in A}\).
\(\displaystyle{ a = g(f(a))}\), zatem \(\displaystyle{ g}\) jest "na".
(a) \(\displaystyle{ R \subseteq S}\) dla każdego \(\displaystyle{ S \in \mathcal{T}}\), zatem \(\displaystyle{ R \subseteq \bigcap \mathcal{T} = R^{+}}\).
(b) jeśli \(\displaystyle{ S}\) jest relacją przechodnią zawierającą \(\displaystyle{ R}\), to \(\displaystyle{ S \in \mathcal{T}}\), zatem \(\displaystyle{ \bigcap \mathcal{T} \subseteq S}\) (bo część wspólna rodziny zbiorów zawiera się w każdym z tych zbiorów).
(c) Weźmy dowolne \(\displaystyle{ a, b, c \in A}\) i załóżmy, że \(\displaystyle{ a R^{+} b}\) i \(\displaystyle{ b R^{+} c}\).
Wówczas dla każdego \(\displaystyle{ S \in \mathcal{T}}\)
\(\displaystyle{ a S b}\) i \(\displaystyle{ b S c}\).
Z przechodniości relacji ze zbioru \(\displaystyle{ \mathcal{T}}\) mamy, że
dla każdego \(\displaystyle{ S \in \mathcal{T}}\)
\(\displaystyle{ a S c}\), zatem
\(\displaystyle{ a R^{+} c}\), co dowodzi przechodniości \(\displaystyle{ R^{+}}\).
(2)
Funkcja \(\displaystyle{ Id: N \rightarrow N}\) określona wzorem \(\displaystyle{ Id(n) = n}\) jest monotoniczną bijekcją zbioru liczb naturalnych.
Pokażemy, że jest to jedyna taka bijekcja.
Załóżmy, że istnieje inna monotoniczna bijekcja \(\displaystyle{ f}\) zbioru liczb naturalnych.
Wówczas \(\displaystyle{ (\exists n \in N)(f(n) \neq n)}\).
Niech \(\displaystyle{ n_{0}}\) będzie najmniejszą liczbą naturalną, dla której \(\displaystyle{ f(n_{0}) \neq n_{0}}\).
Zatem \(\displaystyle{ \forall m < n_{0}}\)
\(\displaystyle{ f(m) = m}\).
Więc \(\displaystyle{ f(n_{0}) > n_{0}}\), gdyż \(\displaystyle{ f}\) jest bijekcją.
\(\displaystyle{ f}\) jest monotoniczna (rosnąca), zatem nie istnieje takie \(\displaystyle{ k}\), że \(\displaystyle{ f(k) = n_{0}}\), co przeczy temu, że \(\displaystyle{ f}\) jest bijekcją.
(3)
Sprawdźmy różnowartościowość funkcji \(\displaystyle{ f}\).
Weźmy różne elementy \(\displaystyle{ a, b \in A}\).
Gdyby \(\displaystyle{ f(a) = f(b)}\), to
\(\displaystyle{ a = g(f(a)) = g(f(b)) = b}\). Sprzeczność.
Sprawdzimy, że \(\displaystyle{ g}\) jest "na".
Weźmy dowolny element \(\displaystyle{ a \in A}\).
\(\displaystyle{ a = g(f(a))}\), zatem \(\displaystyle{ g}\) jest "na".