## Number Systems: Problem Sheet 7

Question 4. Question (4a) asks for a proof of the second De Morgan’s Law, stated in Claim 6.5(ii). You should be able to do this by adapting the proof given in lectures of Claim 6.5(i). You could also do it by a Venn diagram, but I think you will learn more by trying to do it in words.

For (4b), remember from Example 6.4(ii) and Claim 6.5(i) that a good way to show that two sets $A$ and $B$ are equal is to show that $A \subseteq B$ and $B \subseteq A$. So to do (4b) you should first show that

$(X \cup Y) \cap Z \subseteq (X \cap Z) \cup (Y \cap Z)$

and then that

$(X \cap Z) \cup (Y \cap Z) \subseteq (X \cup Y) \cap Z.$

For the first inclusion, try starting as follows: if $z \in (X \cup Y) \cap Z$ then $z \in Z$, and either $z \in X$ or $z \in Y$. Now show that in both cases $z \in (X \cap Z) \cup (Y \cap Z)$. [typo in final formula corrected]

If you are stuck on (4c) try rereading the top of page 31 of the printed lecture notes. You could also try comparing Question 2(c) on Sheet 6 with (4b): they should look rather similar …

Question 6. The point of this question is to show one of the paradoxes that arises when we allow any collection of mathematical objects to be a set.

The first hypothesis is that there is a ‘universe set’ $U$ which has every set you can imagine as its elements. For example, the empty set $\varnothing$, $\{1,2,3\}$, the set of natural numbers $\{1,2,3,\ldots \}$, the set of complex numbers $\mathbb{C}$, are some of the elements of $U$.

We define Russell’s set $R$ to be the subset of $U$ consisting of those sets $X$ such that $X$ is not an element of $X$. Part (a) of the question asks for examples of sets $Y$ and $Z$ such that $Y \in R$ and $Z \not\in R$. So, by definition of $R$, you need to find sets $Y$ and $Z$ such that $Y \not\in Y$ and $Z \in Z$.

Maybe one difficulty here is that it’s hard to think of a set that contains itself. For instance, $\{1,2,3\}$ is not an element of itself. (The elements of $\{1,2,3\}$ are the numbers $1 ,2, 3$.) But such sets do exist, at least in the naive version of set theory we’re using in this course. For example, the universe set $U$ has as its elements all the sets. So in particular $U$ is an element of $U$. This should help you to do (a).

A correct argument for (b) can be given in a few lines, but this doesn’t mean it is easy. The Grelling—Nelson paradox is a paradox closely analogous to Russell’s paradox that can be stated in natural language. Reading about it might suggest the right idea.

Finally, don’t worry too much if (b) still seems hard. Russell’s paradox was famously overlooked by the logician Frege, who learned of it just as the second volume of his book Die Grundlagen der Arithmetik (The foundations of arithmetic) was going into print:

‘Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished. This was the position I was placed in by a letter of Mr. Bertrand Russell, just when the printing of this volume was nearing its completion.’