I would appreciate any comments and corrections to my attempts at the following two proofs,the first concerning (i) set countability and the other involving (ii) Cantor's diagonal argument.

(i) Set Countability Problem

Let $A$ and $B$ be sets and suppose that $A$ is uncountable while $B$ is countable.Prove that $A$ \ $B$ is uncountable

Suppose for contradiction that ($A$ \ $B$) is countable. With ($A$ \ $B$ $\cup$ $B$)$=(A \cup B$) and both sets involved in the union on the LHS being countable, a previously established theorem implies that $(A \cup B$) is also countable. Since $A \subseteq (A \cup B$), it follows that $A$ is countable too, which provides us with the contradiction sought and as a consequence ($A$ \ $B$) is uncountable.

(ii) Cantor's Diagonal Argument Problem

Let $S=$ {q $\in \Bbb{Q} : 0<q<1$}. Is it possible to define a real number $b \in (0,1)$ not in the set?

Let $S=$ {q $\in \Bbb{Q} : 0<q<1$} be an infinite set of rational numbers between 0 and 1. Since $\Bbb{Q}$ is countable and with $S \subseteq \Bbb{Q}$, then $S$ is countably infinite and therefore denumerable. Denumerability of $S$ implies a possible enumeration of the set's elements as $q_1,q_2,q_3,\dots$

Furthermore, each of these rational numbers can be expressed in terms of an infinite decimal expansion such that for any arbitrary $i \in \Bbb{N}, q_i=0.q_{i1}q_{i2}q_{i3} \dots$

The objective is to define a real number $b \in (0,1)$ such that $b \notin S$.Since $S$ contains all rational numbers between 0 and 1, then proving that $b \notin S$ amounts to proving that there is some $b \in (0,1)$ that is not rational.

Let $b \in(0,1)$ with an infinite decimal expansion expressed as $b=0.b_1b_2,b_3 \dots b_i \dots$ where $b_i \in (0,9)$ for all $i \in \Bbb{N}$, and define $b_i$ as follows:

\begin{cases} q_{ii}+1, & \text{if $q_{ii} \lt 8$} \\ q_{ii}-1, & \text{if $q_{ii} \ge 8$} \end{cases}

Note : $b_i$ is restricted to exclude 0 and 9 to avoid duplicate representations.

To prove that $b$ is not in the enumeration $q_1,q_2,q_3,\dots$ ,suppose instead that it is and derive a contradiction. By supposition,if $b$ is to be found amongst the elements in the list,then there exists some $n \in \Bbb{N}$ such that $q_n=b_n$ or equivalently :

  • $0.q_{n1}q_{n2}q_{n3} \dots=0.b_1b_2b_3 \dots$
  • $q_{ni}=b_i$ for all $i \in \Bbb{N}$

Let $i=n$ then by supposition $q_{nn}=b_n$

[Case: $q_{nn} \lt 8$] By definition,$b_n=q_{nn}+1$ and with $q_{nn}=b_n$, it follows that $b_n=b_n+1$ or equivalently that $1=0$ which provides us with the ontradiction sought.

[Case: $q_{nn} \ge 8$] By defintion,$b_n=q_{nn}-1$ and with $q_{nn}=b_n$, it follows that $b_n=b_n-1$ or equivalently that $-1=0$ which provides us with the contradiction sought.

Conclusively,since $b \in (0,1)$ is a real number that is not in the enumeration of rational numbers between 0 and 1, $b$ must be irrational.

Thank you for your time.

  • 1
    $\begingroup$ It would be great if you can search for these questions before. Both were asked, perhaps even many times each. For the first question, you could easily find many duplicates here that would show you that your proof is fine. For the second one, what's wrong with $\frac1{\sqrt 2}$? $\endgroup$ – Asaf Karagila Apr 4 at 22:09
  • 1
    $\begingroup$ And aside of that, there are software limitations in place to make sure that everyone who wants to ask a question can have a reasonable chance to be seen (e.g. at most six questions in a rolling 24 hours period). Asking two questions which are not directly related to each other is in effect a way to circumvent this limitation and is therefore discouraged. Please avoid doing so in the future. $\endgroup$ – Asaf Karagila Apr 4 at 22:10
  • $\begingroup$ Appologies for asking two questions in a post...searching for specific questions more often than not yields unuseable results for me.I am dumb, could you elaborate on what is wrong with second proof please?... $\endgroup$ – HalfAFoot Apr 5 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.