## Zadanie 253

Rozpatrzmy każde zadane $R\subseteq A^{2}$ osobno.

### $R$ jest zwrotna.

Rozpatrzmy zatem najpierw $R;R\subseteq R$. Zbiór $R;R$ wygląda następująco: $\{\langle a,c\rangle : \exists b (aRb \wedge bRc)\}$. Widać od razu, że skoro jedynym wymaganiem wobec relacji $R$ jest takie, że musi być zwrotna, to możliwe jest, że istnieją takie $a,b,c\in A$ parami różne, że zachodzi $aRb$ i $bRc$, ale nie $aRc$ (innymi słowy relacja jest zwrotna ale nie przechodnia). Wówczas złożenie relacji $R;R$ będzie posiadało parę $\langle a,c\rangle$, która nie należy do $R$, czyli zdanie $R;R\subseteq R$ jest fałszywe.

Konkretny kontrprzykład:

Oczywiście kontrprzykład ten również udowadnia fałszywość zdania $R;R = R$. Czy zawsze zatem zachodzi $R\subseteq R;R$?

Czy zatem zawsze będzie prawdziwe $R\subseteq R;R$?. Weźmy zatem takie $\langle a,c\rangle$ które należy do $R$, ale nie należy do $R;R$. Z definicji, musi zajść $\neg(\exists b (aRb \wedge bRc))\equiv \forall b \neg(aRb) \vee \neg(bRc)$. Łatwo zauważyć jednak, że biorąc $a$ jako $b$, otrzymujemy zdanie $\neg(aRa) \vee \neg(aRc)\stackrel{\textrm{def}}{\equiv} Fałsz \vee Fałsz = Fałsz$.
Zatem zawsze zajdzie $R\subseteq R;R$.

### $R$ jest symetryczna.

Wiemy zatem, że dla wszystkich $a,b\in A$ zachodzi implikacja $aRb \Rightarrow bRa$.

Łatwo poprzez kontrprzykład udowodnić, że żadne ze zdań wśród $R \subseteq R;R$, $R;R \subseteq R$ i $R = R;R$ nie jest prawdziwe.

Kontrprzykład:

### $R$ jest przechodnia.

Wiemy zatem, że dla wszystkich $a,b,c\in A$ zachodzi implikacja $aRb \wedge bRc \Rightarrow aRc$.

Od razu podajmy kontrprzykład dla $R \subseteq R;R$, i $R = R;R$


Czy zawsze zajdzie $R;R \subseteq R$?

Załóżmy nie wprost, że dla $a,c\in A$, że $\langle a,c\rangle \in R;R$, ale $\langle a,c \rangle \notin R$. Musi być zatem spełnione zdanie $\exists b (aRb \wedge bRc)$. Zatem wiemy, że istnieje takie $b$, że pary $\langle a,b\rangle$ i $\langle b,c\rangle$ również należą do $R$. Ale $R$ jest przechodnia, więc wg. implikacji $aRb \wedge bRc \Rightarrow aRc$, $aRc$ również musi zajść, co prowadzi do sprzeczności.

## Zadanie 262

Definicje do zadania:

$\mathcal{T} = \{S\subseteq A^{2} : S \textrm{ jest przechodnia} \wedge R\subseteq S\}$
$R^{+} = \cap \mathcal{T}$

### 1. $R\subseteq R^{+}$

Załóżmy nie wprost, że istnieją takie $a,b\in A$, że $\langle a,b\rangle\in R$ i $\langle a,b\rangle\notin R^{+}$. Czyli $\langle a,b\rangle\notin \cap \mathcal{T}$, a to ze względu na definicję przekroju rodziny, oznacza, że $\exists S\in\mathcal{T} (\langle a,b\rangle \notin S)$.

Ale wiemy również, że $\langle a,b\rangle\in R \wedge \forall S\in \mathcal{T} (R\subseteq S)$, co jest równoważne $\forall S\in \mathcal{T} (\langle a,b\rangle\in R \wedge R\subseteq S)$, a to jest równoważne $\forall S\in \mathcal{T} (\langle a,b\rangle\in S)$, co jest sprzeczne z założeniem $\langle a,b\rangle\notin R^{+}$, więc $R\subseteq R^{+}$.

### 2. Jeśli $S$ jest taką relacją przechodnią, że $R\subseteq S$, to $R^{+}\subseteq S$

Załóżmy nie wprost, że istnieją takie $a,b\in A$, że dla pewnego takiego $S$ opisanego w zadaniu, zachodzi $\langle a,b\rangle \in R^{+}$ i $\langle a,b\rangle \notin S$.

Przyjrzyjmy się $\langle a,b\rangle \in R^{+}$. Wiemy, że $R^{+} = \cap \mathcal{T} = \{\langle a,b \rangle : \forall S\in\mathcal{T}(\langle a,b \rangle \in S) \}$. Zatem $\langle a,b\rangle \in \{\langle a,b \rangle : \forall S\in\mathcal{T}(\langle a,b \rangle \in S) \}$, czyli spełnione jest $\forall S\in\mathcal{T}(\langle a,b \rangle \in S)$. Wiemy również, że nasze zdefiniowane na początku $S$ również należy do rodziny $\mathcal{T}$, zatem musi zajść $\langle a,b \rangle \in S$, co jest sprzeczne z naszym założeniem.

### 3. $R^{+}$ jest przechodnia

Czyli dla wszystkich $a,b,c\in A$ musi zajść $aR^{+}b \wedge bR^{+}c \Rightarrow aR^{+}c$.

Załóżmy nie wprost, że mamy takie $a,b,c\in A$, że $\langle a,b \rangle \in R^{+}$, $\langle b,c \rangle \in R^{+}$ i $\langle a,c \rangle \notin R^{+}$.

Zatem wiemy, że $\forall S\in\mathcal{T}(\langle a,b \rangle \in S)$, $\forall S\in\mathcal{T}(\langle b,c \rangle \in S)$ i $\exists S\in\mathcal{T}(\langle a,c \rangle \notin S)$. Weźmy zatem takie $S\in\mathcal{T}$, która spełnia te zdania. Wiemy z definicji rodziny $\mathcal{T}$, że $S$ jest przechodnia. Zachodzi również $\langle a,b \rangle \in S$, $\langle b,c \rangle \in S$ i $\langle a,c \rangle \notin S$, czyli implikacja $aSb \wedge bSc \Rightarrow aSc$ nie jest spełniona, co jest sprzeczne z definicją relacji $S$, więc $R^{+}$ jest przechodnia.

# Inne zajęcia

## Zadanie 312
Wiemy, że $R\subseteq X\times X$ i, że $X = \mathcal{P}(\mathbb{N})$.

### Zwrotność $R$
Weźmy dowolne $A\in X$. Oczywistym jest, że $A\triangle A$ jest zbiorem pustym, czyli zbiorem skończonym. Zatem $R$ jest zwrotna.

### Symetryczność $R$
Weźmy dowolne $A,B\in X$ takie, że $\langle A,B\rangle\in R$. Wiemy zatem, że $A\triangle B$ jest skończone. Oczywiście $B\triangle A$ też jest zatem skończony. Zatem $\langle B,A\rangle\in R$.

### Przechodność $R$
Weźmy dowolne $A,B,C\in X$ takie, że $\langle A,B\rangle\in R$ i $\langle B,C\rangle\in R$. Ponieważ interesują nas głównie przypadki, gdzie $A,B,C$ są różne parami, to przyjmijmy, że tak właśnie jest. Czy zachodzi zatem $\langle A,C\rangle\in R$? Załóżmy nie wprost, że $A\triangle C$ jest nieskończonym zbiorem. Wówczas wiadomo, że zbiór $A$ jest nieskończony, lub zbiór $C$ jest nieskończony. Wówczas odpowiednio $A\triangle B$ jest nieskończony lub $B\triangle C$ jest nieskończony, co jest sprzeczne z założeniami. Więc $R$ jest przechodnia.

### Klasy abstrakcji?

Łatwo zauważyć, że wszystkie

## Zadanie 332

$$f(x)=
\begin{cases}
-1 - 2x & x \geq 0 \wedge x\in\mathbb{N}\\
2x & x \lt 0\wedge x\in\mathbb{Z}\\
x & w.p.p.
\end{cases}
$$

## Zadanie 401

### a)
Zastanówmy się najpierw, jakiej postaci będą elementy rodziny $\mathcal{A}$. Każdy taki element $A_f$ będzie zawierał argumenty, dla których funkcja $f$ przyjmuje wartość większą od $1$.

Na szczęście to jedynie zbędny szczegół, gdyż już od razu możemy wyciągnąć wniosek, że $A_f$ to jedynie zbiór pewnych wybranych liczb naturalnych. Co więcej, wiemy, że rodzina $\mathcal{A}$ zawiera wszystkie zbiory postaci $A_{f\in \mathbb{N}^\mathbb{N}}$, czyli zawiera w sobie wszystkie możliwe zbiory liczb naturalnych.

Szybki dowód: załóżmy, że istnieje taki zbiór $X$ liczb naturalnych, który nie zawiera się w $\mathcal{A}$. Tworzymy wówczas funkcję $g:\mathbb{N}\rightarrow\mathbb{N}$:

$$g(x)=
\begin{cases}
2 & x\in X\\
1 & w.p.p.
\end{cases}
$$

Wtedy istnieje $A_g\in\mathcal{A}$ i zachodzi $A_g = X$, więc $X\in\mathcal{A}$, sprzeczność.

Oczywiście może zajść, że pewne dwie różne funkcje $f_1$ i $f_2$ mogą spełniać $A_{f_1}=A_{f_2}$. Aczkolwiek, ze względu na definicję równości zbiorów, wiemy, że $\mathcal{A} = \mathcal{A}'$ gdzie $\mathcal{A}'$ to rodzina $\mathcal{A}$ bez powtórzeń.

Prostym wnioskiem z postaci rodziny $\mathcal{A}$ jest to, że będzie ona równa zbiorowi $\mathcal{P}(\mathbb{N})$, czyli jej moc to będzie continuum.

### b)

Obliczenie mocy sumy $\bigcap_{f\in\mathbb{N}^{\mathbb{N}}}A_f$ jest teraz łatwe, gdyż będzie on równa zbiorze $\mathbb{N}$, czyli jej moc będzie wynosiła $\aleph_0$.

## Zadanie 451

Zdefiniujmy relację $R\subseteq \mathbb{N}^\mathbb{N}\times \mathbb{N}^\mathbb{N}$ dla której $fRg$ gdy:
1. $f=g$

lub

2. $\exists x_0$ ($(\forall_{x<x_0} f(x)=g(x)) \wedge f(x_0)\lt g(x_0)$).

Intuicyjnie: porównujemy wartości funkcji dla pierwszego argumentu, gdzie $f(x)\neq g(x)$.

Udowodnimy, że $\langle \mathbb{N}^\mathbb{N}, R\rangle$ jest porządkiem liniowym.

### Własności relacji $R$

#### Zwrotność
Jest to oczywiste ze względu na definicję relacji $R$.

#### Słabo symetryczna
Weźmy $f,g\in\mathbb{N}^\mathbb{N}$ i załóżmy, że zachodzi $fRg$ i $gRf$. Udowodnimy, że wtedy $f=g$.

Najpierw sprawdzimy, czy relacje te spełniają drugi warunek bycia w relacji $R$.

Dla obu z relacji, weźmy ich odpowiednie $x_0$, i nazwijmy $x_{fRg}$ i $x_{gRf}$. Rozpatrzmy dwa przypadki:

1. $x_{fRg}\neq x_{gRf}$

Możemy wówczas b.s.o. założyć, że zachodzi $x_{fRg}\lt x_{gRf}$. Wiemy również, że $\forall_{x<x_{gRf}} f(x)=g(x)$, więc w szczególności $f(x_{fRg})=g(x_{fRg})$, co jest sprzeczne z założeniem $fRg$.

2. $x_{fRg}=x_{gRf}$

Wówczas musi zajść $f(x_{fRg}) < g(x_{fRg})$ i $g(x_{fRg}) < f(x_{fRg})$, co jest sprzeczne.

Zatem niemożliwe jest, aby $fRg$ i $gRf$ spełniały drugi warunek bycia w relacje $R$, zatem muszą spełniać warunek pierwszy, czyli $f=g$.

#### Przechodnia
Weźmy $f,g,h\in\mathbb{N}^\mathbb{N}$ i załóżmy, że zachodzi $fRg$ i $gRh$ i, że funkcje te są parami różne. Udowodnimy, że zachodzi również $fRh$.

Weźmy odpowiednie $x_0$ obu relacji i nazwijmy je $x_{fRg}$ i $x_{gRh}$. B.s.o. załóżmy, że $x_{fRg}\le x_{gRh}$. Wówczas, że skoro $\forall_{x<x_{fRg}} f(x)=g(x)$ i $\forall_{x<x_{gRh}} g(x)=h(x)$, to $\forall_{x<x_{fRg}} f(x)=h(x)$. Zatem zachodzi $f(x_{fRg})\lt g(x_{fRg})$ i $g(x_{fRg} = h(x_{fRg})$, więc: $\forall_{x<x_{fRg}} f(x)=h(x)$, spełnione jest $f(x_{fRg})\lt h(x_{fRg})$

Zatem zajdzie $fRh$

## Zadanie 454

### 1

Relacja jest oczywiście relacją zwrotną, gdyż dla dowolnego $f$ zdefiniowany zbiór będzie mocy 0 więc $fRf$.

Czy relacja jest symetryczna? Weźmy dowolne $f$ i $g$, że $fRg$. Wtedy łatwo jest zauważyć, że zbiór $\{n\in\mathbb{N}|f(n)\neq g(n)\}$