Logika
## 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 $x$, 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$

Dowód, że $R$ jest relacją liniowego porządku jest trywialny i pozostawiam jako ćwiczenie dla czytelnika.

## Zadanie 454

### 1

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

Czy relacja jest symetryczna? Weźmy dowolne $f$ i $g$, że $fR_1g$. Wtedy łatwo jest zauważyć, że zbiór $\{n\in\mathbb{N}|f(n)\neq g(n)\}$ jest równoliczny zbiorowi $\{n\in\mathbb{N}|g(n)\neq f(n)\}$, czyli również jest skończony, zatem zajdzie $gR_1f$.

Czy relacja jest przechodnia? Weźmy dowolne $f$, $g$ i $h$, że $fR_1g$ i $gR_1h$. Załóżmy nie wprost, że zbiór $\{n\in\mathbb{N}|f(n)\neq h(n)\}$ jest nieskończony. Oznaczałoby to, że jest nieskończona ilość argumentów w których funkcje te są różne. Wtedy otrzymalibyśmy również wniosek, że albo $\{n\in\mathbb{N}|f(n)\neq g(n)\}$, $\{n\in\mathbb{N}|g(n)\neq h(n)\}$ lub oba zbiory są nieskończone, co jest sprzeczne z założeniami, więc $\{n\in\mathbb{N}|f(n)\neq h(n)\}$ jest zbiorem skończonym i relacja jest przechodnia.

Zatem wg. warunków definicji relacji równoważności, relacja $R_1$ jest relacją równoważności.

### 2

Dowód zwrotności i symetryczności $R_2$ jest taki sam jak przy relacji $R_1$. Jednakże relacja $R_2$ nie będzie przechodnia:

Wartości funkcji dla argumentów
|argument| f | g | h |
|--------| -------- | -------- | -------- |
| 0 | 0 | 1 | 2 |
| 1 | 1 | 2 | 3 |
| 2 | 2 | 3 | 4 |
| 3 | 3 | 4 | 4 |
| 4 | 4 | 4 | 5 |

a dla reszty argumentów funkcje są równe.

Wtedy $|\{n\in\mathbb{N}|f(n)\neq g(n)\}|=4 < 5$ i $|\{n\in\mathbb{N}|g(n)\neq h(n)\}|=4 < 5$, ale $|\{n\in\mathbb{N}|f(n)\neq h(n)\}|=5 \ge 5$, więc relacja $R_2$ nie będzie przechodnia.

Zatem relacja $R_2$ ani nie jest relacją równoważności ani jakiegokolwiek porządku.

### 3

Po pierwsze relacja $R_3$ na pewno nie będzie symetryczna. Wystarczy pokazać kontrprzykład $f(n)=2$ i $g(n)=3$ aby przekonać się, że symetryczność nie zachodzi.

Kontrprzykładem obalającym również słabą antysymetryczność jest
$$f(x)=
\begin{cases}
42 & x=42\\
41 & w.p.p.
\end{cases}
$$

$$g(x)=42
$$

Zatem relacja $R_2$ ani nie jest relacją równoważności ani jakiegokolwiek porządku.

### 4

Tok rozumowania jest identyczny jak dla relacji $R_3$.

### 5

Oczywistą zwrotność relacji $R_5$ pominiemy.

Relacja nie jest też oczywiście symetryczna (patrz kontrprzykład z $R_3$).

Czy zatem relacja $R_5$ jest słabo antysymetryczna? Weźmy dowolne $f$ i $g$ i załóżmy, że $fR_5g$ i $gR_5f$. Wówczas dla dowolnego $x\in\mathbb{N}$ musi zajść $f(x)\le g(x)$ i $g(x)\le f(x)$, czyli $f(x)= g(x)$, czyli $f=g$.

Teraz sprawdzimy, czy relacja jest przechodnia. Weźmy dowolne $f$, $g$ i $h$ i załóżmy, że $fR_5g$ i $gR_5h$. Wówczas dla dowolnego $x$ zajdzie $f(x)\le g(x)$ i $g(x)\le h(x)$, a ze względu na przechodność relacji $\le$ otrzymujemy $f(x)\le h(x)$, czyli zachodzi $fR_5h$, potwierdzając, że relacja $R_5$ jest przechodnia.

Udowodniliśmy więc, że relacja $R_5$ jest relacją pewnego porządku. Nie jest jednak relacją liniowego porządku ze względu na kontrprzykład.