Matematyka.pl

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

(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".