Zadania
- Niech \(\alpha : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) będzie bijekcją i niech \(g : P(\mathbb{N}) \to (\mathbb{N} \to P(\mathbb{N}))\) będzie taką funkcją, że
\[ g(A)(n) = \{ i \in \mathbb{N} \mid \alpha(n,i) \in A \}. \]
Udowodnić, że g jest bijekcją.
- Podać przykład takiej funkcji \( f : \mathbb{N} \to \mathbb{N}\) i zbioru \( X \subseteq \mathbb{N}\), aby funkcja \(g: \mathbb{N} \to P(\mathbb{N})\) określona wzorem
\[ g(i) = (f^i)^{-1}(X) \]
była różnowartościowa.
- Podać przykład pary funkcji \( f, g : \mathbb{N} \to \mathbb{N}\) spełniających wszystkie poniższe warunki:
a) \(\forall x( g(x) \neq x)\),
b) \(g \circ g = id_{\mathbb{N}}\),
c) \(g \circ f = f\),
d) f jest funkcją na \(\mathbb{N}\),
e) obrazem zbioru liczb naturalnych parzystych jest zbiór liczb naturalnych nieparzystych.
- Skonstruować bijekcję \(f : \mathcal{D} \times (\mathcal{E} \oplus \mathcal{H}) \to (\mathcal{D} \times \mathcal{E}) \oplus (\mathcal{D} \times \mathcal{H})\).
- Czy istnieje taka bijekcja \( f : \mathbb{N} \to \mathbb{N}\), że dla dowolnych \(m,n \in \mathbb{N}\) jeśli \(n \geq 1\), to \(f^n(m) \neq m\)?
- Permutacją zbioru X nazwiemy dowolną bijekcję \(\pi : X \to X\). Powiemy, że funkcja \( f : \mathbb{N} \to \mathbb{N}\) jest niezmiennicza ze względu na permutacje wtedy i tylko wtedy, gdy dla każdej permutacji \( \pi : \mathbb{N} \to \mathbb{N}\) oraz dla każdej liczby \(n \in \mathbb{N}\) zachodzi równość \(f(\pi(n)) = \pi (f(n))\). Znaleźć zbiór wszystkich funkcji niezmienniczych ze względu na permutacje.
Praca domowa
- Niech \( P'(\mathbb{N}) = P(\mathbb{N})- \{\emptyset\}\) i niech \( f : P'(\mathbb{N}) \times P'(\mathbb{N}) \to P(\mathbb{N} \times \mathbb{N})\) będzie taka, że \(f(\langle C, D\rangle) = C \times D\).
a) Czy f jest różnowartościowa?
b) Czy f jest na \(P(\mathbb{N} \times \mathbb{N})\)?
c) Znaleźć \( f^{-1}(P(\mathcal{P} \times \mathcal{P}))\), gdzie \(\mathcal{P}\) to zbiór liczb parzystych.
- Dla \(a \in \mathbb{N}\) określamy \(a^*: ( \mathbb{N} \to \mathbb{N}) \to \mathbb{N}\) wzorem \(a^*=\lambda f.f(a)\). Czy funkcja \(\lambda a:\mathbb{N}.a^*\) jest różnowartościowa i czy jest na \(( \mathbb{N} \to \mathbb{N}) \to \mathbb{N}\)?
Zadania
- Ile jest funkcji, funkcji częściowych, funkcji na, funkcji różnowartościowych:
a) \(\emptyset \to \emptyset\),
b) \(\emptyset \to \{ \cdot \}\),
c) \(\{ \cdot \} \to \emptyset\),
d) \(\{ \cdot \} \to \{ \cdot \}\),
e) \(\{ \cdot, \square \} \to \{ \cdot \}\),
f) \(\{ \cdot \} \to \{ \cdot, \square \}\)?
- Niech \(f: A \to B\). Pokazać, że \(f\) jest różnowartościowa wtedy i
tylko wtedy, gdy dla każdego zbioru \(C\) i dla każdych funkcji
\(g,h:C\to A\) zachodzi implikacja
\[f \circ g = f\circ h \to g=h\].
- Podać przykład \(f : A \to B, X\subseteq A, Y \subseteq B\) takich, że
a) \(\vec{f^{-1}}(\vec{f}(X)) \neq X\),
b) \(\vec{f}(\vec{f^{-1}}(X)) \neq X\),
c) \(\vec{f}(C \cap D) = \vec{f}(C)\cap \vec{f}(D)\).
- Niech \( \varphi : \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) będzie taka, że
\[ \varphi(\langle n, k\rangle) = n \cdot k. \]
a) Czy \(\varphi\) jest różnowartościowa?
b) Czy \(\varphi\) jest na?
c) Znaleźć \(\varphi(P \times \mathbb{N})\).
d) Znaleźć \(\varphi^{-1}(\{10\})\).
e) Znaleźć \(\varphi^{-1}(\mathbb{N} - P)\).
Tutaj P oznacza zbiór liczb parzystych.
- Funkcja \(F : (\mathbb{N} \to P(\mathbb{N})) \to P(\mathbb{N})\) wzorem
\[ F(x) = \bigcup \{ x(i) \mid i \in \mathbb{N} \}.\]
a) Czy F jest różnowartościowa?
b) Czy F jest na?
c) Czy istnieje zbiór \(A \subseteq \mathbb{N}\) taki, że \(F^{-1}(\{ A\})\) jest zbiór jednoelementowy?
d) Czy istnieje zbiór \(A \subseteq \mathbb{N}\) taki, że \(F^{-1}(\{ A\})\) jest zbiór czteroelementowy?
- Niech \( a \not \in A, b \not \in B\). Pokazać, że następujące warunki są równoważne.
a) Istnieje bijekcja z \(A\) do \(B\).
b) Istnieje bijekcja z \(A \cup \{a\}\) do \(B \cup \{b\}\).
- Zdefiniujmy \(F : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))\) wzorem
\(F(f)(X) = f(X)\). Czy F jest na?
Praca domowa
- Niech \(f: A \to B\). Pokazać, że \(f\) jest na wtedy i
tylko wtedy, gdy dla każdego zbioru \(C\) i dla każdych funkcji
\(g,h:B\to C\) zachodzi implikacja
\[g \circ f = h\circ f \to g=h\].
- Niech \(\varphi : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))\) będzie określona tak
\[ \varphi(f)(A) = f^{-1}(A).\]
a) Czy \(\varphi\) jest różnowartościowa?
b) Czy \(\varphi\) jest na?
c) Znaleźć \(\varphi^{-1}(\{id_{P(\mathbb{N})}\})\).
d) Czy istnieje \(f \in Rg\varphi\), która jest różnowartościowa?
e) Czy każda funkcja \(f \in Rg\varphi\) jest różnowartościowa?
- a) Czy jeśli \(A \subseteq B\), to \(\bigcap A \subseteq \bigcap B\)?
b) Czy jeśli \(A \subseteq B\), to \(\bigcap B \subseteq \bigcap A\)?
- Czy dla dowolnych niepustych \(A\), \(B\) o niepustym przecięciu zachodzą równości:
a) \(\bigcap A \cap \bigcap B = \bigcap (A \cap B)\),
b) \(\bigcap A \cap \bigcap B = \bigcap (A \cup B)\),
c) \(\bigcup A \cup \bigcup B = \bigcup (A \cap B)\)?
- Które z następujących równości zachodzą dla dowolnego zbioru A:
a) \( \bigcap \{ P(B) \mid B \subseteq A\} = \{ \bigcap P(B) \mid B \subseteq A \}\),
b) \( \bigcup \{ P(B) \mid B \subseteq A\} = \{ \bigcup P(B) \mid B \subseteq A \}\)?
- Kiedy \(A \times B = B \times A\)?
- Czy następująca równość zachodzi dla dowolnych niepustych rodzin \(A\), \(B\):
\[\bigcap A \times \bigcap B = \bigcap \{ \alpha \times \beta \mid \alpha \in A \wedge \beta \in B\}?\]
- Znaleźć \(\bigcup_{t \in \mathbb{R}^+} A_t\) i \(\bigcap_{t \in \mathbb{R}^+} A_t\), gdzie
\[A_t = \{\langle x, y \rangle \in \mathbb{R} \times \mathbb{R} \mid | x - t | + |y | \leq 1\}.\]
Praca domowa
- Czy dla dowolnych niepustych \(A\), \(B\) o niepustym przecięciu zachodzą równości:
a) \(\bigcap A \cup \bigcap B = \bigcap (A \cup B)\),
b) \(\bigcup A \cap \bigcup B = \bigcup (A \cap B)\).
- Udowodnić, że dla dowolnych niepustych A, B, X, Y zachodzi równoważność
\[ A \times B \subseteq X \times Y \Leftrightarrow A \subseteq X \wedge B \subseteq Y. \]
Czy założenie niepustości jest istotne?
Zadania
- Czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzą równości:
a) \(A - (B \cup C) = (A - B) - C\),
b) \(A - (B - C) = (A - B) \cup C\) ?
- Sprawdzić, czy dla dowolnych zbiorów w \(A\), \(B\), \(C\) zachodzi następująca implikacja:
a) jeśli \( A - B = B - A \), to \( A = B\),
b) jeśli \(C - B \subseteq C - A\), to \(A \subseteq B\),
c) jeśli \(A \cup B = C\), to \(C - B = A - B\).
- Zbadać, czy dla dowolnych \(A\), \(B\) zachodzi:
a) \(P (A \cup B) = P(A) \cup P(B)\),
b) \(P (A \cap B) = P(A) \cap P(B)\).
- Która z implikacji jest prawdziwa dla dowolnych zbiorów \(A\), \(B\):
\[ A \subseteq B \hbox{ wtw. } P(A) \subseteq P(B) ? \]
- Udowodnić, że \(\bigcup P(A) = A\) dla dowolnego A.
- Czy jeśli \(A \subseteq B\), to \( \bigcup A \subseteq \bigcup B\)?
Czy jeśli \( \bigcup A \subseteq \bigcup B\), to \(A \subseteq B\)?
- Sprawdzić, czy dla dowolnych \(A\), \(B\) zachodzi
\[ \bigcup A \cup \bigcup B = \bigcup (A \cup B) ?\]
Praca domowa
- Czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzą równości:
a) \(A \cup (A \cap B) = A\),
b) \(A - (B \cup C) = (A-B)\cup(A-C)\).
- Czy istnieją zbiory A, B takie, że \(P(A-B) = P(A) - P(B)\)?