## Exercise 1

1. R is an equivalence relation. In fact, x+y is an even number iff x+y = 2n for some n. Then the relation is reflexive, because x+x = 2x. Simmetry follows from the commutativity of +. As for transitivity, observe that x+y = 2n and y+z = 2m imply x+z = 2(m+n-y). The corresponding partition is constituted by the odd and the even numbers.
2. R is not an equivalence relation, because transitivity is not satisfied. As a counterexample, consider x = 1, y = 10 and z = 19.
3. R is an equivalence relation. Let us denote by rep(x) the decimal representation of x, and by all_but_last(rep(x)) the representation of x without the last digit. Then x R y iff all_but_last(rep(x)) = all_but_last(rep(y)). Since = is an equivalence relation, we have that also R is. As for the partition, note that all_but_last(rep(x)) represents the quotient of the integer division of x by 10. Hence the generic n-th element of the partition will be Pn = { x | x div 10 = n } (where div represents the integer division).
Note: the first part of this question could also be solved by observing that x and y are related iff x div 10 = y div 10.

## Exercise 2

• Proof that L is contained in L'. This is equivalent to say that
for all x in L, x is in L'
We prove the statement by structural induction on L.
• Base: abcc is in L', infact it is of the form anbc2n when we take n = 1.
• Inductive step: Take a generic x in L and assume (inductive hypothesis) that x is in L'. Then x is of the form akbc2k for some k > 0. Observe now that the string axcc is of the form aakbc2kcc, i.e. ak+1bc2(k+1) with k+1 > 0. Hence axcc is also in L'.

• Proof that L' is contained in L. This is equivalent to say that
for all x in L', x is in L.
We prove the statement by induction on n. (The proof just follows the reverse reasoning of the above one.)
• Base: for n = 1, the string anbc2n is abcc, hence it is in L.
• Inductive step: For a generic k > 0, assume that x = akbc2k is in L. Then the string ak+1bc2(k+1) is also in L, because it is equal to axcc.

## Exercise 3

1. One possible solution is: ((1+2+...+9)(0+1+...+9)*)*(0+2+4+6+8).
2. One possible solution is: (a+c)*b(a+c)*.
3. One possible solution is: ab(ab)*.
4. One possible solution is: ((a+b)(a+b))*(a+b).

## Exercise 4

The inductive step does not hold for n = 1. In fact, assume that in the room there are two persons, John and Jack. We can't prove that John and Jack have the same height, because we need at least another person to apply the transitivity reasoning implicit in the "proof". In other words, when we send away John, the remaining group is composed only by Jack. When we reintroduce John and send away Jack, the new group is composed only by John. There is nothing which links the heights of the two groups.