# Lösungsvorschlag Diskrete Mathematik FS18

Wechseln zu: Navigation, Suche

## Other Solutions

My solutions for this exam (incomplete and without warranty): 

## 1 a)

i) |{1,2} x {1,2,3}| = 6

ii) |$(\mathbb {N} \setminus \mathbb {Q} )\times \{1\}$| = 0, since any element of the natural numbers is also element of the rational numbers.

iii) $P(\{\{\emptyset \}\emptyset \})=\{\emptyset ,\{\emptyset \},\{\{\emptyset \}\},\{\{\emptyset \},\emptyset \}\}$

## 1 b)

i) $\emptyset$

ii) Claim: $A$ transitive $\Rightarrow A\cup \{A\}$ transitive.

Proof: $A$ transitive $\Rightarrow \forall x\in A:x\subseteq A$. We know that every element of $A$ is also a subset of $A$. Therefore, the only element of $A\cup \{A\}$ that needs to be checked is $A$ (since $A\in (A\cup \{A\})$). We know, that every element of $A$ is also element of $A\cup \{A\}$. Therefore we know $A\subseteq (A\cup \{A\})$. This means that we have $\forall x\in (A\cup \{A\}):x\subseteq (A\cup \{A\})$. The set is therefore transitive.

## 1) c)

i) Let $A\cap B=\emptyset$ and $A,B$ countable.

Claim: $A\cup B$ countable.

Proof: Define $C:=A\cup B$ and $c_{i}\in C$ arbitrary. $c_{i}=a_{i}$ if i even; $c_{i}=b_{i}$ if i odd. Since $A\cap B=\emptyset$, i.e. no element of A and B are the same, we know that we have an injection of C into $\mathbb {N}$. Therefore $C$ is countable.

ii) Claim: If $A$ countable and $C$ uncountable, then $C/A$ is uncountable.

Proof: Assume $C/A$ countable. We can affiliate each element of C with one of the sets $C/A,A$. We know that both sets are countable. However, we previously proved that then $C/A\cup A=C$ is countable. This is a contradiction to the fact, that C is uncountable! Therefore $C/A$ must be uncountable.

## 2 a)

1) Yes, an example is $\rho :=\{(1,1),(2,2),(3,3)\}=:id$ on $\{1,2,3\}$.

2) $\rho :=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2)\}$

## 2 c)

i) Let $f(n):=2$ if $n$ even and $f(n):=4$ if $n$ odd. We therefore have $f\neq f_{2},f\neq f_{4}$ and $f_{2}\leq f\leq f_{4}\iff \forall n\in \mathbb {N} :f_{2}(n)|f(n)\wedge f(n)|f_{4}(n)$.

## 3 a)

i) $R_{11}(2^{1408})=R_{11}(R_{11}(2^{10})^{140}\cdot R_{11}(2^{8}))=3$

ii) gcd(1188,954) = 18

## 3 c)

Lemma: $gcd(m,n)=gcd(m,n-qm)$

If $a+k$ and $b+k$ are relatively prime, then:

$gcd(a+k,b+k)=1\implies gcd(a+k,b+k-(a+k))=gcd(a+k,b-a)=1$

Suppose without limitation to the generality that $b-a>0$.

Then there are infinitely many numbers $k$, such that $a+k$ is prime and $a+k>b-a$.

For all these k we have $gcd(a+k,b-a)=1$ , because $a+k$ is only divided by $1$ and itself and $b-a.

## 4 d)

Let $a$, $b\in R$.

$(a+b)\in R$

$(a+b)=(a+b)^{2}$

$(a+b)=a*a+a*b+b*a+b*b$ (distributive law)

$(a+b)=a+a*b+b*a+b$ $(a*a=a)$

$(a+b)-(a+b)=a*b+b*a$ (additive inverse and commutativity)

$0=a*b+b*a$

$-a*b=b*a$

$a*b=b*a$ $(a=-a)$

## 4 e)

Let $A:=\mathbb {Z} _{2}[x]_{x^{3}+x^{2}+1}$.

i) Claim: $A$ is a field.

Proof: By Lemma 5.35, $F[x]_{m(x)}$ is a ring. Theorem 5.37 states, that a ring $F[x]_{m(x)}$ is a field iff $m(x)$ irreducible. Therefore we need to show that $m(x)$ irreducible. $m(x)$ is irreducible, if it has no roots in GF(2): $m(0)=1,m(1)=1\Rightarrow m(x)$ irreducible in $A$.

ii) Claim: All elements of $A^{*}$ are generators.

Proof: We know that $|A|=2^{3}=8$. Since $m(x)$ irreducible, $A^{*}$ contains all elements of $A$ except 0. Therefore $|A^{*}|=|A|-1=7$. 7 is a prime number and by Corollary 5.11 groups of prime order are cyclic and in such groups every element is a generator.

iii) Solve $y^{2}+(x^{2}+1)y+(x^{2}+x+1)=0$ in $A$.

Solution: Let $y:=x+1$. We then have $(x+1)^{2}+(x^{2}+1)\cdot (x+1)+(x^{2}+x+1)=(x^{2}+1)+(x^{3}+x^{2}+x+1)+(x^{2}+x+1)=x^{3}+x^{2}+1=0$.

($y=x^{2}+x$ is also a solution.)

## 5 c)

Claim: The resolution calculus is not complete.

Proof: Counterexample to res. calculus being complete:

Let $F:=A$ and $G:=A\vee B$. We know $F\models G$. But there is no way to derive $K(A\vee B)$ from $K(A)$ using the resolution calculus. Therefore the res. calculus is not complete.