FS22

Task 1

a)

7.) Irreflexive relations on $A=\{a,b,c\}$.
Note that a relation is irreflexive only if $\rho \cap \text{id}=\varnothing$, and not if it’s “not reflexive”!!!
$\{a,b,c\}\times \{a,b,c\}=....$ we remove $(a,a),(b,b),(c,c)$ from it which leaves us with 6 elements, $2^6=64$.

e)

Equivalence relation $\sim$ such that $A/\sim$ and $[a{]}_{\sim }$ are uncountable.
$A=\mathbb{R}\times \mathbb{R}$ and $(a,b)\sim (c,d)\iff a=c$.
My answer was wrong here.

f) $S=\{f\in \{0,1{\}}^{\mathbb{N}}|\forall i\in \mathbb{N}f(i)+f(i+1)\le 1\}$

Show uncountable/countable.

We define an injection g…

Task 2:

a)

Don’t be stupid with the gcd

c) Find a $n\in \mathbb{N}$ such that $5^n{\equiv }_{23}1$ and $3^n{\equiv }_{31}9$

As 23 and 31 are prime, $5^{22n}{\equiv }_{23}1$ and $3^{30}{\equiv }_{31}1$ thus $3^{30m+2}{\equiv }_{31}{3}^2{\equiv }_{23}9$
Therefore we’re looking for $22n=30m+2$
$11n=15m+1$ $⟹11\cdot n{\equiv }_{15}1$, we use the extended euclidean to find the inverse $n=11$ thus $22n=22\cdot 11=242$ which is our solution.

Task 3:

a)

1.) Find a generator of ${\mathbb{Z}}_{14}^{\ast }$?
To find a generator of ${\mathbb{Z}}_{14}^{\ast }$, we list all elements first $=\{1,3,5,9,11,13\}$ Note that the order is $6$. As the subgroup order divides the group order, all subgroups have order $1,2,3,6$.
Therefore we need to find an element such that $ord(x)=6$ and $ord(x)\ne 1,2,3$.

Task 4

a)

4.) Find a formula $F$ such that $F$ is satisfiable but $\forall xF$ is unsatisfiable
$F=P(x)\wedge \neg P(y)$

d) Prove that: ”${\Pi }_3$ complete $⟹$ ${\Pi }_1\vee {\Pi }_2$ complete

We use an indirect proof.
Assume that ${\Pi }_1\wedge {\Pi }_2$ are incomplete.
Then there exist ${\tau }_1(s_1)=1$ and ${\tau }_2(s_2)=1$ (otherwise vacuously complete).
Thus $\forall (p_1,p_2)\in P_1\times P_2$ we have ${\varphi }_1(s_1,p_1)=0$ and ${\varphi }_2(s_2,p_2)=0$.
Thus ${\tau }_3(s_1,s_2)=1$ but forall $(p_1,p_2)$\phi_3((s_1, s_2),(p_1, p_2)) = 0$.Thus$\Pi_3$ incomplete.

f) Prove that $\neg F\wedge \forall F\models G$

Because both cases lead to a contradiction, there cannot exist a model for LHS.

Therefore it is trivially (vacously) satisfied, that for every model of LHS, there exists a model for RHS, which proves it.