IMO-1959

1. Prove that the fraction \(\frac{21n+4}{14n+3}\) is irreducible for every natural number \(n\).
• To show that a fraction is irreducible, we need to prove that the numerator and denominator are relatively prime. Note that we have \(3 (14n+3) - 2 (21n+4) = 1\), \(\forall n \in \mathbb{N}\). Let \(d\) be the g.c.d of \(21n+4\) and \(14n+3\). Hence, \(d | \left( 3 (14n+3) - 2 (21n+4) = 1 \right) \). Hence, \(d | 1 \implies d = 1\). Hence, \(21n+4\) and \(14n+3\) are relatively prime. Hence, the fraction \(\frac{21n+4}{14n+3}\) is irreducible for every natural number \(n\).
2. For what real values of \(x\) is \[\sqrt{\left( x + \sqrt{2x-1} \right)} + \sqrt{\left( x - \sqrt{2x-1} \right)} = A,\] given (a) \(A = \sqrt{2} \), (b) \(A = 1\), (c) \(A = 2\), where only non-negative real numbers are admitted for square roots?
• Only non-negative real numbers are admitted for square roots, we need \(2x-1 \geq 0\) and \(x \geq \pm \sqrt{2x-1}\). The two conditions yield us \(x \geq \frac12\). Squaring both sides, we get, \[\left( x + \sqrt{2x-1} \right) + \left( x - \sqrt{2x-1} \right) + 2 \sqrt{\left( x + \sqrt{2x-1} \right)\left( x - \sqrt{2x-1} \right)} =A^2\] \[2x + 2 \sqrt{x^2 -2x + 1} = A^2\] \[2x + 2 \left \lvert x - 1 \right \rvert = A^2 \]
• If \(x \geq 1\), we get \[2x + 2x - 2 = A^2 \implies 4x = A^2 + 2 \implies x = \frac{A^2 + 2}{4}\] Hence, if \(A \geq \sqrt{2}\), we have \(x = \frac{A^2 + 2}{4}\).
• If \(\frac12 \leq x \leq 1\), we get \(2x + 2 - 2x = A^2 \implies 2 = A^2\), \(\forall x \in \left[\frac12,1\right]\).
• So the solution can be written as follows: \(x = \left \{ \begin{array}{lr} \frac{A^2+2}{4} & \text{If } A \gt \sqrt{2}\\ \text{Any value }\in \left[\frac12,1\right] & \text{If } A = \sqrt{2} \\ \text{No solution } & \text{If }A \lt \sqrt{2} \end{array} \right. \)
• For the current problem, we get \(x = \left \{ \begin{array}{lr} \frac{3}{2} & \text{If } A = 2 \\ \text{Any value }\in \left[\frac12,1\right] & \text{If } A = \sqrt{2} \\ \text{No solution } & \text{If }A = 1 \end{array} \right. \)
3. Let \(a,b,c\) be real numbers. Consider the quadratic equation in \(\cos(x)\) : \[ a \cos^2(x) + b \cos(x) + c = 0. \] Using the numbers \(a,b,c \) form a quadratic equation in \(\cos(2x)\), whose roots are the same as those of the original equation. Compare the equations in \(\cos(x)\) and \(\cos(2x)\) for \(a=4\), \(b=2\) and \(c=-1\).
• We have \(\cos^2(x) = \frac{1 + \cos(2x)}{2}\). Hence, the equation becomes \[\displaystyle a \left( \frac{1 + \cos(2x)}{2} \right) + b \sqrt{\frac{1 + \cos(2x)}{2}} + c = 0\] Rearranging and squaring both sides, we get \[\left( a \left( \frac{1 + \cos(2x)}{2} \right) + c \right)^2 = b^2 \left( \frac{1 + \cos(2x)}{2} \right) \] \[ a^2 + a^2 \cos^2(2x) + 4c^2 + 2a^2 \cos(2x) + 4ac + 4ac \cos(2x) = 2b^2 + 2b^2 \cos(2x)\] \[a^2 \cos^2(2x) + (2a^2 + 4ac -2 b^2) \cos(2x) + (a^2 + 4c^2 + 4ac - 2b^2) = 0\] Plugging in \(a = 4, b=2\) and \(c=-1\), we get the equation in terms of \(\cos(x)\) as \[4 \cos^2(x) + 2 \cos(x) - 1 = 0\] and the equation in terms of \(\cos(2x)\) as \[16 \cos^2(2x) + 8 \cos(2x) - 4 = 0.\] Hence, \(\cos(x)\) and \(\cos(2x)\) satisfy the same quadratic equation.

Algorithms - Exercises from Chapter 0

1. In each of the following situations, indicate whether \(f = \mathcal{O}(g)\) (or) \(f = \Omega(g)\) or both (in which case \(f = \Theta(g)\)).
• \(n-100 = \Theta(n-200)\)
• \(n^{1/2} = \mathcal{O}(n^{2/3})\)
• \(100n + \log n = \mathcal{O}(n + (\log n)^2)\)
• \(n \log n = \Theta (10n \log 10n)\)
• \(\log 2n = \Theta (\log 3n)\)
• \(10 \log n = \Theta (\log \left( n^2 \right))\)
• \(n^{1.01} = \Omega (n \log^2 n)\)
• \(n^2 / \log n = \mathcal{O}(n (\log n)^2)\)
• \(n^{0.1} = \mathcal{O}(\left( \log n \right)^{10})\)
• \((\log n)^{\log n} = \Omega(n / \log n\))
• \(\sqrt{n} = \Omega ((\log n)^3)\)
• \(n^{1/2} = \mathcal{O}(5^{\log_2n})\)
• \(n2^n = \mathcal{O}(3^n)\)
• \(2^n = \Theta (2^{n+1})\)
• \(n! = \Omega (2^n)\)
• \(\left(\log n \right)^{\log n} = 2^{\left(\log_2 n \right)^2}\)
• \(\sum_{i=1}^{n} i^k = \Theta (n^{k+1})\)
2. Show that, if \(c\) is a positive real number, then \(g(n) = 1 + c + c^2 + \cdots + c^n\) is:
• \(\Theta(1) \) if \(c \lt 1\)
• \(\Theta(n) \) if \(c = 1\)
• \(\Theta(c^n) \) if \(c \gt 1\)
• Solution: We have that \(g(n) = \frac{c^{n+1}-1}{c-1}\) whenever \(c \neq 1\). Note that \(g(n)\) is a monotonously increasing function for all positive real \(c\) i.e. we have \(g(n+1) \gt g(n)\).
• If \(c \lt 1\), we have \(1 \leq g(n) \lt \frac1{1-c}\), for all \(n \in \mathbb{Z}^+\). Hence, we get \(g(n) = \Theta(1)\).
• If \(c = 1\), we have \(g(n) = n+1\). Hence, we have that \(g(n) = \Theta(n)\).
• Since \(c \in \mathbb{R}^+\), we have \(g(n) \gt c^n, \forall n \in \mathbb{Z}^+\). For \(c \gt 1\), choose \(k = \frac{c}{c-1}\). We have \(1 + c + c^2 + \cdots + c^n =\frac{c^{n+1}-1}{c-1} \lt \frac{c^{n+1}}{c-1} = \frac{c}{c-1} c^n = k c^n\). Hence, we have for any \(n\), \[c^n \lt 1 + c + c^2 + \cdots + c^n \lt k c^n.\] Hence, we get \(g(n) = \Theta(c^n)\).
3. The Fibonacci numbers are defined by the rule \[F_0 = 0, F_1 = 1, F_{n} = F_{n-1} + F_{n-2}, n \geq 2.\] In this problem, we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.
• Use induction to prove that \(F_n \geq 2^{0.5n}\) for \(n \geq 6\).
• We have \(F_6 = 8 = 2^{0.5 \times 6}\) and \(F_7 = 13 \gt 12 \gt 8 \times 1.5 \gt 8 \times \sqrt{2} = 2^{3.5}\). Assume that for all \(k\) such that \(6 \leq k \leq m\), we have \(F_k \geq 2^{0.5k}\). We have \(F_{m+1} = F_{m} + F_{m-1} \gt 2^{0.5 m} + 2 ^{0.5 (m-1)} = 2 ^{0.5 m} \left(1 + \frac1{\sqrt{2}} \right) \gt 2^{0.5 m} \sqrt{2} = 2^{0.5 (m+1)}.\) We have checked the base cases for \(k=6\) and \(k=7\) and hence by induction we have \(F_n \geq 2^{0.5n}\). Hence proved.
• Find a constant \(c \lt 1\) such that \(F_n \leq 2^{cn}\) for all \(n \geq 0\). Show that the answer is correct.
• We need \(2^{c(n+1)} \geq 2^{cn} + 2^{c(n-1)}\) i.e. we need \(2^c \geq 1 + \frac1{2^c}\). Setting \(2^c = x\), we need \(x\) such that \(x \geq 1 + \frac1x\) i.e. we need \(x\) such that \(x^2 \geq x + 1\). Since we have \(x = 2^c\) and \(0 \leq c \lt 1\), we need \(x\) such that \(1 \leq x \lt 2\). Setting \(x^2 - x - 1 = 0\), we get \(x = \frac{1 \pm \sqrt{5}}{2}\). Since \(1 \leq x \lt 2\), we get \(x = \frac{1 + \sqrt{5}}{2}\). Hence, set \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\). We shall now check that setting \(c = \log_2 \left(\frac{1 + \sqrt{5}}{2}\right)\), we have \(F_n \leq 2^{cn}\). Clearly, we have \(F_0 = 0 \lt 1 = 2^{c \times 0}\). Similarly, we have \(F_1 = 1 \lt \frac{1 + \sqrt{5}}{2} = 2^{\log_2 \left(\frac{1 + \sqrt{5}}{2}\right)}\). Assume that we have \(F_k \leq 2^{ck}\) for all \(k \leq m\). Hence, we get \(F_{m+1} = F_m + F_{m-1} \leq 2^{cm} + 2^{c(m-1)} = 2^{cm} \left(1 + \frac1{2^c} \right) = 2^{cm + c} = 2^{c(m+1)}\). Hence, \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
• What is the largest \(c\) you can find for which \(F_n = \Omega (2^{cn})\)?
• By a similar argument as above, we get that \(c = \log_2 \left(\frac{1+\sqrt{5}}{2} \right)\) does the job.
4. Is there a faster way to compute the \(n^{th}\) Fibonacci number? One idea involves \(matrices\). We start by writing the equations \(F_1 = F_1\) and \(F_2 = F_0 + F_1\) in matrix notation: \[ \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] Similarly, \[\begin{pmatrix}F_2 \\ F_3 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix}F_1 \\ F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^2 \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] and in general, we have \[\begin{pmatrix} F_n \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix}F_0 \\ F_1 \end{pmatrix}\] So, in order to compute \(F_n\), it suffices to raise this \(2 \times 2\) matrix, call it \(X\), to the \(n^{th}\) power.
• Show that two \(2 \times 2\) matrices can be multiplied using \(4\) additions and \(8\) multiplications.
• \[\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} e & f \\ g & h \end{pmatrix} = \begin{pmatrix} a \times e + b \times g & a \times f + b \times h \\ c \times e + d \times g & c \times f + d \times h \end{pmatrix}\] Hence, it is clear that we need \(4\) additions and \(8\) multiplications.

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

This post contains the solution to the exercises of the book by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani named "Algorithms". This post is a work in progress.

1. Exercises in Chapter 0
2. Exercises in Chapter 1

Elementary Number Theory - 1 Problems

1. Suppose that \(a,b,c \in \mathbb{N}\). Prove each of the following:
• If \(a|b\) and \(b|c\), then \(a|c\).
• Since \(a|b\) and \(b|c\), we have \(b= ak_1\) and \(c = b k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, we get \(c = b k_2 = a k_1 k_2 = a (k_1 k_2)\). Since \(k_1,k_2 \in \mathbb{Z}\), we get \(k_1 k_2 \in \mathbb{Z}\). Hence, we get \(a | c\).
• If \(a|b\) and \(a|c\), then \(a| (bx+cy)\) for every \(x,y \in \mathbb{Z}\).
• Since \(a|b\) and \(a|c\), we have \(b = a k_1\) and \(c = a k_2\) where \(k_1,k_2 \in \mathbb{Z}\). Hence, \(bx + cy = a k _1 x + a k_2 y = a \left(k_1 x + k_2 y \right)\). Note that since \(k_1,k_2,x,y \in \mathbb{Z}\), we have \(k_1 x + k_2 y \in \mathbb{Z}\). Hence, we get \(a | \left( bx + cy \right)\).
2. Prove that if \(n \in \mathbb{N}\) is composite, then it has a prime factor not exceeding \(\sqrt{n}\).
• Let \(n = p_1 p_2 \ldots p_r\) where \(p_i\)'s are prime not necessarily distinct. Further we are given that \(n\) is composite. Hence, we have \(r \geq 2\). Now assume the contrary that all the prime factors of \(n\) exceed \(\sqrt{n}\) i.e. \(p_k > \sqrt{n}\), \(\forall k \in \{1,2,\ldots,r \}\). Then \(n = p_1 p_2 \ldots p_r > \left(\sqrt{n} \right)^r = n^{r/2}\). Hence, we have \(n > n^{r/2}\). This implies \(r < 2\). This contradicts the fact that \(r \geq 2\). Hence there is at-least one prime factor not exceeding \(\sqrt{n}\).
3. Prove that \(n^4 + 4\) is composite for every natural number \(n > 1\).
• \(n^4 + 4 = n^4 + 4n^2 + 4 - 4n^2 = \left(n^2+2 \right)^2 - \left( 2n \right)^2 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\). Note that \(n^2+2 + 2n > n^2 + 2 -2n\), \(\forall n \in \mathbb{N}\). For \(n > 1\), we have \(n^2 + 2 -2n = (n-1)^2 + 1 > 1\). Hence, \(n^4 +4 = \left( n^2+ 2 + 2n \right) \left( n^2 + 2 - 2n\right)\) where \(\left( n^2+ 2 + 2n \right) \in \mathbb{Z}\) and \(\left( n^2 + 2 - 2n\right) \in \mathbb{Z}\). Further for \(n > 1\), we have \(\left( n^2+ 2 + 2n \right) > \left( n^2+ 2 - 2n \right) > 1\). Hence, \(n^4 +4\) is a product of two natural numbers greater than \(1\). Hence, \(n^4+4\) is composite for every natural number \(n > 1\).

Elementary Number Theory - 1.3 Definitions and Propositions

Theorem: (Euclid)
There are infinitely many primes.


Proof:
This is a classic proof by contradiction. Assume that there are only finitely many primes, say \(n\) of them and denote them by \(\mathbb{P} = \{p_1,p_2,\ldots,p_n\}\). Consider the number \(m = p_1p_2 \ldots p_n +1\). If \(m\) is a prime, we have \(m \neq p_l\) for any \(l \in \{1,2,\ldots,n\}\). Hence, we have constructed a new prime not in \(\mathbb{P}\). This means either \(m\) is not a prime (or) there are infinitely many primes. Hence, if \(m\) is a prime, we have proved that there are infinitely many primes. If \(m\) is not a prime, then since \(m\) is also not an irreducible, and since we have assumed that only finitely many primes exist, we have that \(p_i | m\) for some \(p_i\). But we have \(m - p_1p_2 \ldots p_n = 1\). This means the \(p_i | 1\). CONTRADICTION. Hence, there are infinitely many primes.

Definition:
The greatest integer part of a real number \(\alpha\), denoted by \(\lfloor \alpha \rfloor\), is the greatest integer less than or equal to \(\alpha\) i.e. the unique integer \(m \in \mathbb{Z}\) such that \(m \leq \alpha \lt m+1\).


Proposition:
Suppose \(\alpha,\beta \in \mathbb{R}\).

1. We have \(\alpha-1 \lt \lfloor \alpha \rfloor \leq \alpha\) and \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\).
• By definition, we have that \(\lfloor \alpha \rfloor \in \mathbb{Z}\) such that \(\lfloor \alpha \rfloor \leq \alpha \lt \lfloor \alpha \rfloor + 1\). Rearranging the inequalities, we get \(\alpha - 1 \lt \lfloor \alpha \rfloor \leq \alpha\). Again by rearranging, we get \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\).
2. If \(\alpha \geq 0\), then \(\lfloor \alpha \rfloor\) counts the number of positive integers not exceeding \(\alpha\). In other words, \[\lfloor \alpha \rfloor = \sum_{1 \leq n \leq \alpha} 1.\]
• \(\sum_{1 \leq n \leq \alpha}\) 1 = \(\sum_{1 \leq n \leq \lfloor \alpha \rfloor} 1 + \sum_{\lfloor \alpha \rfloor \lt n \leq \alpha} 1\). Since we have \(0 \leq \alpha - \lfloor \alpha \rfloor \lt 1\), the contribution of the second term is zero as there is no integer \(n\) such that \(\lfloor \alpha \rfloor \lt n \leq \alpha\). The first term is nothing but \(\lfloor \alpha \rfloor\).
3. For every \(n \in \mathbb{Z}\), we have \(\lfloor \alpha + n \rfloor = \lfloor \alpha \rfloor + n\).
• Let \(\lfloor \alpha \rfloor = m \in \mathbb{Z}\). We have that \(m \leq \alpha \lt m+1\). Hence, we have \(m + n \leq \alpha + n \lt (m+n) + 1\). Hence, we get \(\lfloor \alpha +n \rfloor = m + n = \lfloor \alpha \rfloor + n\).
4. We have \(\lfloor \alpha \rfloor + \lfloor \beta \rfloor \leq \lfloor \alpha + \beta \rfloor \leq \lfloor \alpha \rfloor + \lfloor \beta + 1\).
• Let \(\lfloor \alpha \rfloor = m\) and \(\lfloor \beta \rfloor = n\). This means \(m \leq \alpha \lt m + 1\) and \(n \leq \beta \lt n + 1\). Adding the two, we get \(m + n \leq \alpha + \beta + m + n + 2\). Hence, we get \(\lfloor \alpha \rfloor + \lfloor \beta \rfloor \leq \lfloor \alpha + \beta \rfloor \leq \lfloor \alpha \rfloor + \lfloor \beta + 1\).
5. If \(\alpha \in \mathbb{Z}\), then \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = 0\). If \(\alpha \not \in \mathbb{Z}\), then \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = -1\).
• If \(\alpha \in \mathbb{Z}\), then \(-\alpha \in \mathbb{Z}\). Hence, we have \(\lfloor \alpha \rfloor = \alpha\) and \(\lfloor -\alpha \rfloor = - \alpha\). Hence, \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = \alpha + (- \alpha) = 0\). If \(\alpha \notin \mathbb{Z}\), then let \(m = \lfloor \alpha \rfloor\). Since \(\alpha \notin \mathbb{Z}\), we get \(m \lt \alpha \lt \alpha + 1\). Multiplying by negative one, we get \(-m-1 \lt -\alpha \lt -m \). This means \(\lfloor \alpha \rfloor = - m - 1\). Hence, we get \(\lfloor \alpha \rfloor + \lfloor -\alpha \rfloor = m + (-m-1) = -1\).
6. The number \(- \lfloor -\alpha \rfloor\) is the smallest integer not less than \(\alpha\).
• Let \(m = \lfloor \alpha \rfloor\). If \(\alpha \in \mathbb{Z}\), then \(m = \alpha\). We get \(-\alpha = -m \in \mathbb{Z}\). Hence, \(- \lfloor -\alpha \rfloor = m\) which is nothing but the smallest integer not less than \(\alpha\). If \(\alpha \notin \mathbb{Z}\), then \(m \lt \alpha \lt m + 1\). Hence, \(-m - 1 \lt -\alpha \lt -m \). Hence, we get \(\lfloor -\alpha \rfloor = - m - 1\). Hence, we get \(- \lfloor -\alpha \rfloor = m + 1\) which is nothing but the smallest integer not less than \(\alpha\).
7. If \(n \in \mathbb{Z}^+\), then \(\lfloor \lfloor \alpha \rfloor / n \rfloor = \lfloor \alpha/n \rfloor\).
• If \(\alpha \in \mathbb{Z}\), then it follows trivially since \(\lfloor \alpha \rfloor = \alpha\). If \(\alpha \notin \mathbb{Z}\), let \(m = \lfloor \alpha \rfloor\). We then have \(m = qn + r\) where \(r \in \{0,1,2,\ldots,n-1\}\). Hence, \(\alpha = qn + r + \{\alpha\}\) where \(\{\alpha\} \in [0,1)\). Note that \(r + \{\alpha\} \in (0,n)\). We then get \(\lfloor \lfloor \alpha \rfloor / n \rfloor = \lfloor \frac{qn+r}{n} \rfloor = q\). We also get \(\lfloor \alpha/n \rfloor = \lfloor (qn + r + \{\alpha\})/n \rfloor\) = q. Hence, we get the desired result.
8. The number \(\lfloor \alpha + \frac12 \rfloor\) is one of the two nearest integers to \(\alpha\). Furthermore, if these two integers differ from \(\alpha\) by the same value, then \(\lfloor \alpha + \frac12 \rfloor\) is the larger of these two integers.
• Follows immediately from the definition.
9. If \(\alpha \gt 0\) and \(n \in \mathbb{N}\), then \(\lfloor \frac{\alpha}{n} \rfloor\) is the number of positive integers not exceeding \(\alpha\) and which are multiples of \(n\).
• Follows from the second part of this problem.

Theorem:

Suppose that \(n \in \mathbb{N}\) and \(p\) is a prime. Then the largest integer \(k\) such that \(p^k | n!\) is given by \[k = \sum_{j=1}^{\infty} \left \lfloor \frac{n}{p^j} \right \rfloor .\]
Proof:
Let \(r_m\) be the highest power of \(p\) dividing \(m\). Then we get \(k = \displaystyle \sum_{m=1}^{n} r_m\). We have \(r_m = \displaystyle \sum_{l=1}^{\infty} 1_{\{p^l | m\}} \). Hence, we get \(k = \displaystyle \sum_{m=1}^{n} \sum_{l=1}^{\infty} 1_{\{p^l | m\}} = \sum_{l=1}^{\infty} \sum_{m=1}^{n} 1_{\{p^l | m\}} = \sum_{l=1}^{\infty} \left \lfloor \frac{n}{p^l} \right \rfloor\). Hence, the largest integer \(k\) such that \(p^k | n!\) is given by \[k = \sum_{j=1}^{\infty} \left \lfloor \frac{n}{p^j} \right \rfloor .\]

Elementary Number Theory - 1.2 Definitions and Propositions

Definition: We say \(a \in \mathbb{Z}^+\) and \(a \gt 1\) is an irreducible if it has exactly two positive divisors, namely \(1\) and \(a\).
Definition: We say \(p \in \mathbb{Z}^+\) and \(p \gt 1\) is a prime if \(p | ab \implies p | a\) (or) \(p | b\).
Definition: We say \(a \in \mathbb{Z}^+\) and \(a \gt 1\) is composite if \(a\) is not a prime.


Proposition:
\(p\) is a prime if and only if \(p\) is irreducible.

Proof:

• We shall first prove that "If \(p\) is a prime, then \(p\) is an irreducible".
• If \(p\) is not irreducible, then \(p=ab\) for some \(a,b \in \mathbb{Z}^+\) where \(1 \lt a,b \lt p\). Clearly, \(p|p\) i.e. \(p|ab\) but \(p\not | a\) and \(p\not | b\) since \(1 \lt a,b \lt p\). Hence, \(p\) is not a prime.
• We shall now prove that "If \(p\) is an irreducible, then \(p\) is a prime".
• If \(p\) is an irreducible, we shall prove that if \(p\not | a\) and \(p\not | b\), then \(p\not ab\). Since \(p\) is an irreducible, the divisors of \(p\) are \(1\) and \(p\). Since \(p\not | a\) and \(p\not | b\), we have \((p,a) = 1\) and \((p,b) = 1\). Hence, we get \(ax_1 + py_1 = 1\) and \(bx_2 + py_2 = 1\). Multiplying out the two, we get \((ax_1 + py_1)(bx_2 + py_2) = 1\). i.e. we get \(abx_1x_2 + p(ax_1y_2 + bx_2y_1 + py_1 y_2) = 1\). Hence, we get that \((ab,p) = 1\). Hence, we have that \(p\not| ab\). Hence, \(p\) is a prime.

Proposition:

Suppose that \(a_1,a_2,\ldots,a_k \in \mathbb{Z}\), and \(p\) is a prime. If \(p | a_1a_2\ldots a_k\), then \(p|a_j\) for some \(j \in \{1,2,\ldots,k\}\).

Proof:

The proof follows immediately from the previous proposition and induction. Since \(p\) is a prime, it divides either \(a_1\) (or) \(a_2a_3 \ldots a_k\) and then get the rest by simple induction.

Proposition (Fundamental Theorem of Arithmetic):

Every natural number \(n > 1\) is representable as a product of primes, uniquely up to the order of factors.

Proof:
First, we shall prove by induction that any natural number is a product of prime(s). Let \(P(n)\) be the statement that \(n+2\) can be written as a product of prime(s). Let \(S = \{n \in \mathbb{N}: P(n) \text{ is true }\}\). Clearly, \(0 \in S\). This is so since \(2\) is a prime and can be written as \(2=2\). Assume that all natural numbers up-to \(k\) is in \(S\). Now consider \(k+1\). If \(k+3\) is irreducible, we proved that it is a prime and hence \(k+3 = k+3\). If \(k+3\) is not an irreducible, then we have \(k+3 = ab\), where \(1 \lt a,b \lt k+3\). Now by induction hypothesis, since \(1 \lt a,b \leq k+2\), we have \(a\), \(b\) to be product of primes i.e. \(a = p_1p_2 \ldots p_l\) and \(b = p_{l+1} p_{l+2} \ldots p_{l+m}\) where \(p_i\) are primes. Hence, \(k+3 = ab = p_1 p_2 \ldots p_l p_{l+1} p_{l+2} \ldots p_{l+m}\). Hence, \(k+3\) can also be expressed as a product of primes. Hence, \(k+1 \in S\). By principle of mathematical induction, we have that every natural number. Hence, every natural number is representable as a product of primes.
We still needs to prove uniqueness. Assume that the representation is not unique i.e. let \(n=p_1 p_2 \ldots p_l = q_1 q_2 \ldots q_k\). Consider \(p_1\). We have \(p_1 | n\). This means that \(p_1 | \prod_{j=1}^{k} q_j\) and from the definition of a prime we get \(p_1 | q_j\) for some \(j\). From the definition of a prime, we get that \(p_1 | q_j\). But from an earlier proved proposition since \(q_j\) is a prime, the only factors of \(q_j\) are \(1\) and \(q_j\) itself. This gives us \(p_1 = q_j\). Repeat this argument a finite number of times to conclude that \(l = k\) and get the desired result.

Proposition:
Every natural number \(n > 1\) is uniquely representable in the form \[n = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_k^{\alpha_k}\] where \(p_1 < p_2 < \cdots \lt p_k\) are primes and \(\alpha_k \in \mathbb{Z}^+\).

Proof:
Follows immediately from the above proposition and grouping together equal primes. The above is the canonical prime decomposition of a natural number \(n\).

Convergence of sequence of rationals and irrationals

Note that both \(\mathbb{Q}\) and \(\mathbb{R} \backslash \mathbb{Q}\) are dense in \(\mathbb{R}\).

1. Convergence of sequence of distinct rationals to a
• Rational number:
• Want sequence of distinct rationals say \(\{a_n\}_{n=1}^{\infty}\) to another rational number say \(a\). Choose \(a_k = a + \frac1k\) where \(k \in \mathbb{Z}^+\). Clearly, \(a_k\)'s are rationals and converge to the rational number \(a\).
• Irrational number:
• Want sequence of distinct rationals say \(\{a_n\}_{n=1}^{\infty}\) to an irrational number say \(a\). Choose \(a_k = \frac{\lfloor 10^k a \rfloor}{10^k}\) where \(k \in \mathbb{Z}^+\). Clearly, \(a_k\)'s are rationals and converge to the irrational number \(a\).
2. Convergence of sequence of distinct irrationals to a
• Rational number:
• Want sequence of distinct irrationals say \(\{a_n\}_{n=1}^{\infty}\) to a rational number say \(a\). Choose \(a_k = a + \frac{x}k\) where \(k \in \mathbb{Z}^+\) and \(x\) is any irrational number. Clearly, \(a_k\)'s are irrationals and converge to the rational number \(a\).
• Irrational number:
• Want sequence of distinct irrationals say \(\{a_n\}_{n=1}^{\infty}\) to another irrational number say \(a\). Choose \(a_k = a + \frac1k\) where \(k \in \mathbb{Z}^+\). Clearly, \(a_k\)'s are irrationals and converge to the irrational number \(a\).

Topology without Tears - 2.2 Exercises

Exercises:

1. In this exercise, you will prove that the disc \(\{(x,y): x^2 + y^2 < 1\}\) is an open subset of \(\mathbb{R}^2\), and then that every open disc in the plane is an open set.
• Let \((a,b)\) be any point in the disc \(D = \{(x,y):x^2+y^2<1\}\). Put \(r = \sqrt{a^2 + b^2}\). Let \(R_{(a,b)}\) be the open rectangle with vertices at the points \(\left(a \pm \frac{1-r}{8}, b \pm \frac{1-r}{8} \right)\). Verify that \(R_{(a,b)} \subset D\).

• All we need to show is that all the four vertices lies inside the disc, for which we need to show that the distance from the origin to each of the four vertices is less than unity. To show that all we need to show is that the distance of the farthest vertex from the origin is less than unity. The distance of the farthest vertex from the origin is given by \(d = r+ \sqrt{2} \frac{1-r}{8} = \frac{\sqrt{2}}{8} + r \left(1 - \frac{\sqrt{2}}{8} \right) \). Since \(0 \leq r \lt 1\), we get \(\frac{\sqrt{2}}{8} \leq d \lt 1\). Hence, we get that \(R_{(a,b)} \subset D\).
• Using the previous part show that \(D = \bigcup_{(a,b) \in D} R_{(a,b)}\).
• Consider any point \((a,b) \in D\). Clearly, \((a,b) \in R_{(a,b)}\). Hence, any point in the disc is contained in an open rectangle centered about that point. Hence, \(D \subseteq \bigcup_{(a,b) \in D} R_{(a,b)}\). From the previous part, we have that for any \((a,b)\) we have \(R_{(a,b)} \subseteq D\). Hence, \(D \supseteq \bigcup_{(a,b) \in D} R_{(a,b)}\). Combining the two, we get \(D = \bigcup_{(a,b) \in D} R_{(a,b)}\).
• Deduce from above that \(D\) is an open set in \(\mathbb{R}^2\).
• Every open rectangle is an open set. Hence, any arbitrary union of open sets is again an open set. From the previous part, we have that \(D\) is an arbitrary union of open rectangles. Hence, \(D\) is an open set.
• Show that every disc \(\{(x,y): (x-a)^2 + (y-b)^2 \lt c^2, a,b,c \in \mathbb{R}\}\) is open in \(\mathbb{R}^2\).
• Let \((m,n)\) be any point in the disc \(D = \{(x,y): (x-a)^2 + (y-b)^2 \lt c^2\}\). Put \(r = \sqrt{(m-a)^2 + (n-b)^2}\). Let \(R_{(a,b)}\) be the open rectangle with vertices at the points \((a + m \pm \frac{c - r}{8}, b + n \pm \frac{c-r}{8})\). Now the same arguments as the above three gives us that the disc \(D = \{(x,y): (x-a)^2 + (y-b)^2 \lt c^2\}\) is open in \(\mathbb{R}^2\).
2. In this exercise you will show that the collection of all open discs in \(\mathbb{R}^2\) is a basis for a topology on \(\mathbb{R}^2\). [Later we shall see that this is the euclidean topology.]
• Let \(D_1\) and \(D_2\) be any open discs in \(\mathbb{R}^2\) with \(D_1 \cap D_2 \neq \emptyset\). If \((a,b)\) is any point in \(D_1 \cap D_2\), show that there exists an open disc \(D_{(a,b)}\) with centre \((a,b)\) such that \(D_{(a,b)} \subseteq D_1 \cap D_2\).

• We are given that \(D_1 \cap D_2 \neq \emptyset\). Let the center and radius of \(D_1\) be \((a_1,b_1)\) and \(r_1\) respectively. Let the center and radius of \(D_2\) be \((a_2,b_2)\) and \(r_2\) respectively. Since, we have \(D_1 \cap D_2 \neq \emptyset\), we have \(r_1 + r_2 \gt \sqrt{(a_1-a_2)^2 + (b_1-b_2)^2}\). Let \(r = \min(r_1-\sqrt{(a-a_1)^2+(b-b_1)^2},r_2-\sqrt{(a-a_2)^2 + (b-b_2)^2})\). Consider the disc centered at \((a,b)\) with radius \(r\). This disc lies completely inside \(D_1 \cap D_2\).
• Show that \[D_1 \cap D_2 = \bigcup_{(a,b) \in D_1 \cap D_2} D_{(a,b)}.\]
• Consider any \((x,y) \in D_1 \cap D_2\). Note that \((x,y) \in D_{(x,y)}\). \((x,y)\) is one such \((a,b)\) in the union. Hence \((x,y) \in D_{(x,y)} \subseteq \bigcup_{(a,b) \in D_1 \cap D_2} D_{(a,b)}\). Hence, we get \(D_1 \cap D_2 \subseteq \bigcup_{(a,b) \in D_1 \cap D_2} D_{(a,b)}\). Now, for any \((x,y) \in D_1 \cap D_2\), we have \(D_{(x,y)} \subseteq D_1 \cap D_2\). Hence, we get \(\bigcup_{(a,b) \in D_1 \cap D_2} D_{(a,b)} \subseteq D_1 \cap D_2\).
• Using the above and the proposition proved earlier, prove that the collection of all open discs in \(\mathbb{R}^2\) is a basis for a topology on \(\mathbb{R}^2\).
• First note that we have \(\mathbb{R}^2 = \bigcup D_{(a,b)}(n)\) where \(D_{(a,b)}(n)\) denotes an open unit disc of radius \(n\) centered at \((a,b)\). The proof is trivial since any \(D_{(a,b)}(n) \subseteq \mathbb{R}^2\) and also for any point \((x,y) \in \mathbb{R}^2\), we have \(n \in \mathbb{N}\) such that \(n \gt \sqrt{x^2 + y^2}\) and hence \((x,y) \in D_{(0,0)}(n)\). Next note that from the part above, we have that intersection of any two discs is again a union of open discs. Hence, by the proposition proved earlier we have that the collection of all open discs in \(\mathbb{R}^2\) is a basis for a topology on \(\mathbb{R}^2\).
3. Let \(\mathcal{B}\) be the collection of all open intervals \((a,b)\) in \(\mathbb{R}\) with \(a \lt b\) and \(a\) and \(b\) rational numbers. Prove that \(\mathcal{B}\) is a basis for the euclidean topology on \(\mathbb{R}\).
• We shall prove that if \(S \subseteq \mathbb{R}\) is an open set then given any \(x \in S\) we can find an open interval \((a_q,b_q) \subseteq S\) where \(a_q,b_q \in \mathbb{Q}\). Since \(S\) is an open set, we know that there exists \(a,b \in \mathbb{R}\) such that \(x \in (a,b) \subseteq S\). Further, since the rationals are dense in \(\mathbb{R}\), given any \(r \in \mathbb{R}\), there exists a sequence of rationals monotonously converging to \(r\). For instance, there exists a sequence of monotonously increasing \(b_n \in \mathbb{Q}\) such that \(\lim_{n \rightarrow \infty}b_n = b\). Similarly, there exists a sequence of monotonously decreasing \(a_n \in \mathbb{Q}\) such that \(\lim_{n \rightarrow \infty}a_n = a\). This means that \((a,b) = \bigcup_{n \rightarrow \infty} (a_n,b_n)\). Hence, if \(x \in (a,b)\), then \(x \in (a_n,b_n)\) for some \(n\) where \(a_n,b_n \in \mathbb{Q}\). Hence, given any open set \(S\), for every \(x \in S\), there exists an open interval with rational end points containing \(x\) lying within \(S\). Hence, the set of open intervals with rational end points generate the same topology as the euclidian topology.
4. A topological space \((X,\tau)\) is said to satisfy the second axiom of countability or to be second countable if there exists a basis \(\mathcal{B}\) for \(\tau\), where \(\mathcal{B}\) consists of only a countable number of sets.
• Using the previous exercise show that \(\mathbb{R}\) satisfies the second axiom of countability.
• We have \(\mathcal{B} = \{(a_q,b_q): a_q,b_q \in \mathbb{Q}\}\)  is a basis for the euclidean topology. We have the set of rational numbers to be countable. The set \(\mathcal{B}\) can be written as \(\mathcal{B} = \bigcup_{a_q \lt b_q; a_q \in \mathbb{Q}} \bigcup_{b_q \in \mathbb{Q}} (a_q,b_q)\) which is again a countable set.
•  Prove that the discrete topology on an uncountable set does not satisfy the second axiom of countability.
• Let \(\mathcal{B}\) be a basis for the discrete topology. For every \(x \in X\), we have \(\{x\}\) to be an open set in the discrete topology. This means that we have \(\{x\}\) to be a union of elements in \(\mathcal{B}\). This means that the singleton sets should be in the basis \(\mathcal{B}\). Hence, we have \(\{\{x\} : x \in X\} \subseteq \mathcal{B} \). Since \(X\) is uncountable, we have \( \{\{x\} : x \in X\}\) to be an uncountable set. Hence, we have that \(\mathcal{B}\) to be an uncountable set. Hence, \((X,\tau)\) satisfies the second axiom of countability.
• Prove that \(\mathbb{R}^n\) satisfies the second axiom of countability, for each positive integer \(n\).
• We proceed by induction. Let \(P(n)\) be the statement that \(\mathbb{R}^n\) satisfies the second axiom of countability. Let \(S = \{n \in \mathbb{N}: P(n) \text{ is true}\}\). From the first part of this problem, we have \(1 \in S\) i.e there exists a countable basis \(\mathcal{B}\) for the euclidean topology on \(\mathbb{R}\). Assume that \(k \in S\). Note that \(\mathbb{R}^{k+1} = \mathbb{R}^k \times \mathbb{R}\). By induction hypothesis, we have that there exists a countable basis \(\mathcal{B}^k\) for the euclidean topology on \(\mathbb{R}^k\). From the question \(6\), which is proved later we have that \(\mathcal{B}^k \times \mathcal{B}\) is a basis for \(\mathbb{R}^k \times \mathbb{R} = \mathbb{R}^{k+1}\). Product of two countable sets is again a countable set. Hence, \(\mathcal{B}^k \times \mathcal{B}\) is a countable basis for \(\mathbb{R}^k \times \mathbb{R} = \mathbb{R}^{k+1}\). Hence, \(\mathbb{R}^n\) satisfies the second axiom of countability, for each positive integer \(n\).
• Let \((X,\tau)\) be the set of all integers with the finite-closed topology. Does the space \((X,\tau)\) satisfy the second axiom of countability?
• Let \(\tau^c = \{A \subseteq X: X \backslash A \in \tau\}\) i.e. \(\tau^c\) contains all the closed sets induced by the topology \(\tau\). In this case, we have \(\tau^c = \{A \subseteq X : A \text{ is finite}\}\). Note that \(\tau\) is equivalent to \(\tau^c\) since there is a clear bijection from \(\tau\) to \(\tau^c\) as \(A \in \tau\) iff \(X \backslash A \in \tau^c\). We shall prove that \(\tau^c\) is a countable set. This would mean that \(\tau\) is a countable set and since any basis \(\mathcal{B} \subseteq \tau\) we would have proved that the \((X,\tau)\), with the finite-closed topology, satisfies the second axiom of countability. Since \(X\) is a countable set, list the element of \(X\) as \(\{x_0,x_1,\ldots,x_n,\ldots\}\). Any finite subset \(B\) of \(X\) is of the form \(B = \{x_{k_0},x_{k_1},\ldots,x_{k_n}\}\) where \(n \in \mathbb{N}\) and \(k_i \in \mathbb{N}\) for \(i \in \{0,1,\ldots,n\}\). Let \(\displaystyle f(B) = \sum_{l=0}^{n} 2^{k_l}\). It is not hard to see that \(f: \tau^c \rightarrow \mathbb{N}\) is a bijection. Hence, \(\tau^c\) is a countable set. This means that the topology, \(\tau\), is also countable and hence any basis is also a countable set. Hence, \((X,\tau)\), with the finite-closed topology, satisfies the second axiom of countability.
5. Prove the following statements.
• Let \(m\) and \(c\) be real numbers, with \(m \neq 0\). Then the line \(L = \{(x,y): y = mx+c\}\) is a closed subset of \(\mathbb{R}^2\).

• Consider \(L^c = \mathbb{R}^2 \backslash L\). We shall prove that \(L^c\) is an open set. Consider \((a,b) \in L^c\). We shall prove that there is a rectangle \(R \subseteq L^c\) such that \((a,b) \in R\). Let \(d\) denote the distance of the point \((a,b)\) from the line \(L\). We have \(d = \frac{b-am-c}{\sqrt{1+m^2}} \gt 0\). Consider the open rectangle \(R\) with vertices \((a \pm \frac{d}{2}, b \pm \frac{d}{2})\). We get \((a,b) \in R\) and \(R \subseteq L^c\). Hence, \(L^c\) is an open set. Hence, \(L\) is a closed set.
• Let \(\mathbb{S}^1\) be the unit circle given by \(\mathbb{S}^1 = \{(x,y) \in \mathbb{R}^2: x^2 + y^2 = 1\}\). Then \(\mathbb{S}^1\) is a closed subset of \(\mathbb{R}^2\).
• Consider \(\mathbb{T} = \mathbb{R}^2 \backslash \mathbb{S}^1\). We shall prove that \(\mathbb{T}\) is open. Consider any \((a,b) \in \mathbb{T}\). Let \(r = \text{abs}(1-\sqrt{a^2+b^2})\). Consider the open rectangle \(R\) with vertices at \(( a \pm \frac{r}{2}, b \pm \frac{r}{2})\). Clearly, we have \((a,b) \in R \subseteq \mathbb{T}\). This is true for any \((a,b) \in \mathbb{T}\). Hence, \(\mathbb{T}\) is an open set. Hence, \(\mathbb{S}^1\) is a closed set of \(\mathbb{R}^2\).
• Let \(\mathbb{S}^n\) be the unit \(n\)-sphere given by \[\mathbb{S}^n = \{(x_1,x_2,\ldots,x_n,x_{n+1}) \in \mathbb{R}^{n+1}: x_1^2 + x_2^2 + \cdots + x_{n+1}^2 = 1\}.\] Then \(\mathbb{S}^n\) is a closed subset of \(\mathbb{R}^{n+1}\).
• Consider \(\mathbb{T} = \mathbb{R}^{n+1} \backslash \mathbb{S}^n\). We shall prove that \(\mathbb{T}\) is open. Consider any \((a_1,a_2,\ldots,a_{n+1}) \in \mathbb{T}\). Let \(r = \text{abs} \left(1 - \sqrt{a_1^2 + a_2^2 + \cdots + a_n^2 + a_{n+1}^2} \right)\). Consider the open rectangle \(R\) with vertices at \( \left(a_1 \pm \frac{r}{n+1}, a_2 \pm \frac{r}{n+1}, \ldots, a_{n} \pm \frac{r}{n+1}, a_{n+1} \pm \frac{r}{n+1} \right)\). Clearly, we have \((a_1,a_2,\ldots,a_n,a_{n+1}) \in R \subseteq \mathbb{T}\). Hence, \(\mathbb{T}\) is an open set. Hence, \(\mathbb{S}^n\) is a closed subset of \(\mathbb{R}^{n+1}\).
• Let \(B^n\) be the closed unit \(n\)-ball given by \[B^n = \{(x_1,x_2,\ldots,x_{n}): x_1^2 + x_2^2 + \cdots + x_n^2 \leq 1\}.\] Then \(B^n\) is a closed subset of \(\mathbb{R}^n\).
• Consider \(\mathbb{T} = \mathbb{R}^n \backslash B^n\). We shall prove that \(\mathbb{T}\) is open. Consider any \((a_1,a_2,\ldots,a_n) \in \mathbb{T}\). Let \(r = \sqrt{a_1^2 + a_2^2 + \cdots + a_n^2} - 1\). Consider the open rectangle \(R\) with vertices at \( \left(a_1 \pm \frac{r}{n+1}, a_2 \pm \frac{r}{n+1}, \ldots, a_{n} \pm \frac{r}{n+1}, a_{n+1} \pm \frac{r}{n+1} \right)\). Clearly, we have \((a_1,a_2,\ldots,a_n,a_{n+1}) \in R \subseteq \mathbb{T}\). Hence, \(\mathbb{T}\) is an open set. Hence, \(B^n\) is a closed subset of \(\mathbb{R}^{n}\).
• The curve \(C = \{(x,y) \in \mathbb{R}^2 : xy=1\}\) is a closed subset of \(\mathbb{R}^2\).
• Consider \(\mathbb{T} = \mathbb{R}^2 \backslash C\). We shall prove that \(\mathbb{T}\) is open. Consider any \((a,b) \in \mathbb{T}\). Let \(r\) be the minimum distance from the point \((a,b)\) to the curve \(C\). Consider the open rectangle \(R\) with vertices at \(( a \pm \frac{r}{2}, b \pm \frac{r}{2})\). Clearly, we have \((a,b) \in R \subseteq \mathbb{T}\). This is true for any \((a,b) \in \mathbb{T}\). Hence, \(\mathbb{T}\) is an open set. Hence, \(C\) is a closed set of \(\mathbb{R}^2\).
6. Let \(\mathcal{B}_1\) be a basis for the topology \(\tau_1\) on a set \(X\) and \(\mathcal{B}_2\) be a basis for the topology \(\tau_2\) on a set \(Y\). The set \(X \times Y\) consists of all ordered pairs \((x,y)\), \(x \in X\) and \(y \in Y\). Let \(\mathcal{B}\) be the collection of subsets of \(X \times Y\) consisting of all the sets \(B_1 \times B_2\) where \(B_1 \in \mathcal{B}_1\) and \(B_2 \in \mathcal{B}_2\). Prove that \(\mathcal{B}\) is a basis for a topology on \(X \times Y\). The topology so defined is called the product topology on \(X \times Y\).
• All we need to do is to check the definitions of a basis. We are given that \(\mathcal{B}_1\) and \(\mathcal{B}_2\) are a basis for \(\tau_1\) and \(\tau_2\) respectively. Hence, we have \(\cup_{B \in \mathcal{B}_1} B = X\) and \(\cup_{B \in \mathcal{B}_2} B = Y\). Also, if we have \(C,D \in \mathcal{B}_1\), then \(C \cap D \in \mathcal{B}_1\). Similarly, if we have \(C,D \in \mathcal{B}_2\), then \(C \cap D \in \mathcal{B}_2\). Now consider any element in \(\mathcal{B}_1 \times \mathcal{B}_2\). It is of the form \(B_1 \times B_2\) where \(B_1 \in \mathcal{B}_1 \) and \(B_2 \in \mathcal{B}_2 \). Now the union over all elements in \(\mathcal{B}_1 \times \mathcal{B}_2\) can be written as \(\cup_{B_1 \in \mathcal{B}_1 , B_2 \in \mathcal{B}_2} B_1 \times B_2\). We then have \(\cup_{B_1 \in \mathcal{B}_1 , B_2 \in \mathcal{B}_2} B_1 \times B_2 = \cup_{B_1 \in \mathcal{B}_1} \left( B_1 \times \cup_{B_2 \in \mathcal{B}_2} B_2 \right) = \cup_{B_1 \in \mathcal{B}_1} B_1 \times Y = \cup_{B_1 \in \mathcal{B}_1} \left( B_1 \right) \times Y = X \times Y\). Also, if we have \(A,B \in \mathcal{B}\), then \(A = A_1 \times A_2\) and \(B= B_1 \times B_2\) where \(A_1,B_1 \in \mathcal{B}_1\) and \(A_2,B_2 \in \mathcal{B}_2\). Then \(A \cap B = \left( \right)\).

Topology without Tears - 2.2 Definitions and Propositions

Proposition:

A subset \(S\) of \(\mathbb{R}\) is open if and only if it is a union of open intervals.

Proof:

• We shall first prove that a union of open intervals is an open set in \(\mathbb{R}\). Let \(S = \bigcup_{\alpha \in \Gamma} (a_{\alpha},b_{\alpha})\) where \((a_{\alpha},b_{\alpha})\) is an open interval in \(\mathbb{R}\). We proved in the previous section that any open interval is an open set. From the definition of a topology, we have any arbitrary union of open sets to be an open set. Hence, \(S = \bigcup_{\alpha \in \Gamma} (a_{\alpha},b_{\alpha})\) is an open set.
• Now we shall now prove that any open set in \(\mathbb{R}\) is a union of open intervals. From the definition of an open set in \(\mathbb{R}\), we have that for every \(x \in S\), we can find an open interval \((a_x,b_x)\) containing \(x\) such that \((a_x,b_x) \subseteq S\). Now consider \(\cup_{x \in S} (a_x,b_x)\). We shall now prove that \(S = \cup_{x \in S} (a_x,b_x)\).

• We shall prove first that \(S \subseteq \cup_{x \in S} (a_x,b_x)\). Consider any \(y \in S\). We hence have \(y \in (a_y,b_y)\). Hence, \(y \in \cup_{x \in S} (a_x,b_x)\). Hence, \(S \subseteq \cup_{x \in S} (a_x,b_x)\).
• We shall prove next that \(S \supseteq \cup_{x \in S} (a_x,b_x)\). Consider any \(y \in \cup_{x \in S} (a_x,b_x)\). This means that \(y \in (a_x,b_x)\) for some \(x \in S\). But \((a_x,b_x) \subseteq S\). Hence, we get \(y \in S\). Hence, \(S \supseteq \cup_{x \in S} (a_x,b_x)\).

This gives us that a subset \(S\) of \(\mathbb{R}\) is open if and only if it is a union of open intervals.

Definition:

Let \((X, \tau)\) be a topological space. A collection \(\mathcal{B}\) of open subsets of \(X\) is said to be a basis for the topology \(\tau\) if every open set is a union of members of \(\mathcal{B}\).

Proposition:

Let \((X,\tau)\) be a discrete space and \(\mathcal{B}\) the family of all singleton subsets of \(X\); that is, \(\mathcal{B} = \{\{x\}: x \in X\}\). Then \(\mathcal{B}\) is a basis for \(\tau\).

Proof:

The discrete topology contains all the subsets of \(X\). Note that any subset, \(A \subseteq X\), can be written as \(A = \cup_{x \in A} \{x\}\). Hence, the singleton set generate the topology.

Proposition:

There are many different bases for the same topology. If \(\mathcal{B}\) is a basis for a topology \(\tau\) on a set \(X\) and \(\mathcal{B}_1\) is a collection of subsets of \(X\) such that \(\mathcal{B} \subseteq \mathcal{B}_1 \subseteq \tau\), then \(\mathcal{B}_1\) is also a basis for \(\tau\).

Proof:

The topology generated by \(\mathcal{B}\) is \(\tau\). Let \(\tau(\mathcal{B}_1)\) be the topology generated by \(\mathcal{B}_1\). We need to show that \(\tau(\mathcal{B}_1) = \tau\).

• We shall first show that \(\tau(\mathcal{B}_1) \supseteq \tau\). We are given that \(\mathcal{B} \subseteq \mathcal{B}_1\) and \(\tau(\mathcal{B}) = \tau\). This means that any element in \(\tau\) can be written as \(\bigcup_{A_{\alpha} \in \mathcal{B}} A_{\alpha}\). Since any element in \(\mathcal{B}\) is also an element of \(\mathcal{B}_1\), we have that any element in \(\tau\) can be written as \(\bigcup_{A_{\alpha} \in \mathcal{B}_1} A_{\alpha}\). Hence, we have \(\tau(\mathcal{B}_1) \supseteq \tau\).
• Now we shall show that \(\tau(\mathcal{B}_1) \subseteq \tau\). We are given that \(\mathcal{B}_1 \subseteq \tau\). Let us look at the topology generated by \(\mathcal{B}_1\). Any element in the \(\tau(\mathcal{B}_1)\) is an arbitrary union of elements in \(\mathcal{B}_1\). Consider any arbitrary union of elements in \(\mathcal{B}_1\) i.e. \(\bigcup_{A_{\alpha} \in \mathcal{B}_1} A_{\alpha}\). Since \(\mathcal{B}_1 \subseteq \tau\), we have that \(A_{\alpha} \in \tau\) for all \(A_{\alpha} \in \mathcal{B}_1\). Since \(\tau\) is a topology, it is closed under arbitrary unions and hence we get \(\bigcup_{A_{\alpha} \in \mathcal{B}_1} A_{\alpha} \in \tau\). Hence any element in \(\tau(\mathcal{B}_1)\) is also an element in \(\tau\). Hence, we get \(\tau(\mathcal{B}_1) \subseteq \tau\). 

Hence, we get that \(\mathcal{B}_1\) is also a basis for \(\tau\).

Proposition:

Let \(X\) be a non-empty set and let \(\mathcal{B}\) be a collection of subsets of \(X\). Then \(\mathcal{B}\) is a basis for a topology on \(X\) if and only if \(\mathcal{B}\) has the following properties:

1. \(X = \bigcup_{B \in \mathcal{B}} B\)
2. For any \(B_1,B_2 \in \mathcal{B}\), then the set \(B_1 \cap B_2\) is a union of members of \(B\).

Proof:

If \(\mathcal{B}\) is a basis for a topology \(\tau\), then any element in \(\tau\) can be written as an arbitrary union of elements in \(\mathcal{B}\). Since, \(X \in \tau\), we have that \(X = \bigcup_{\alpha \in \Gamma} B_{\alpha}\) where \(B_{\alpha} \in \mathcal{B}\). But \(\bigcup_{\alpha \in \Gamma} B_{\alpha} \subseteq \bigcup_{B \in \mathcal{B}} B\). Hence, we get \(X \subseteq \bigcup_{B \in \mathcal{B}} B\). Further, for any \(B \in \mathcal{B}\), we have \(B \subseteq X\). Hence, we get \(\bigcup_{B \in \mathcal{B}} \subseteq X\). Hence, we have \(X = \bigcup_{B \in \mathcal{B}} B\). Also, for any \(B_1,B_2 \in \mathcal{B}\), we also have \(B_1,B_2 \in \tau\). Since \(\tau\) is closed under intersections, we have \(B_1 \cap B_2 \in \tau\). Since \(\mathcal{B}\) generates \(\tau\), we have \(B_1 \cap B_2\) is a union of members of \(\mathcal{B}\).

To prove the other way around, that is, if \(X = \bigcup_{B \in \mathcal{B}} B\) and for any \(B_1,B_2 \in \mathcal{B}\), the set \(B_1 \cap B_2\) is a union of members of \(\mathcal{B}\), then \(\mathcal{B}\) is a basis for the topology on \(X\). Let \(\tau(\mathcal{B}) = \{\bigcup_{\alpha} B_{\alpha}: B_{\alpha} \in \mathcal{B}\}\). We need to prove that \(\tau\) is a topology.

1. Clearly, we have \(X, \emptyset \in \tau\). (This follows from the condition in the problem and from the fact that the empty set is a union of no sets.)
2. Any arbitrary union of elements in \(\tau\) is nothing but an arbitrary union of elements in \(\mathcal{B}\) which is again in \(\tau\).
3. Consider two elements in \(\tau\). These two elements can be written as \(\bigcup_{\alpha} B^1_{\alpha}\) and \(\bigcup_{\beta} B^2_{\beta}\) where \(B^1_{\alpha},B^2_{\beta} \in \mathcal{B}\) forall \(\alpha,\beta\). The intersection of these two elements is given by \(\left(\bigcup_{\alpha} B^1_{\alpha} \right) \cap \left(\bigcup_{\beta} B^2_{\beta} \right) = \bigcup_{\alpha,\beta} \left(B^1_{\alpha} \cap B^2_{\beta} \right)\). But we are given that intersection of two elements in \(\mathcal{B}\) can be written as union of members of \(\mathcal{B}\) i.e. \(B^1_{\alpha} \cap B^2_{\beta} = \bigcup_{\gamma} B_{\gamma,\alpha,\beta}\). Hence, the intersection of any two elements in \(\tau\) is given by \(\bigcup_{\alpha,\beta,\gamma} B_{\gamma,\alpha,\beta}\). Hence, closed under finite intersections.

Hence, \(\tau(\mathcal{B})\) is a topology.

Elementary Number Theory - 1.1 Definitions and Propositions

Definition:

Suppose that \(a,b \in \mathbb{Z}\) and \(a\neq 0\). Then we say that \(a\) divides \(b\), denoted by \(a|b\), if there exists \(c \in \mathbb{Z}\) such that \(b=ac\). In this case, we also say that \(a\) is a divisor of \(b\) (or) \(b\) is a multiple of \(a\).

Theorem:

Suppose that \(a \in \mathbb{N}\) and \(b \in \mathbb{Z}\). Then there exists unique \(q,r \in \mathbb{Z}\) such that \(b=aq+r\) and \(0 \leq r \lt a\)

Proof:

First we need to show the existence of \(q,r \in \mathbb{Z}\). Consider the set \[S = \{b-as \geq 0 : s \in \mathbb{Z}\}.\] \(S \subset \mathbb{N}\) and hence by well-ordering principle there exists a least element in \(S\). Call the least element \(r\). Claim now is that \(0 \leq r \lt a\). Clearly, since \(r \in S\), we have \(r \geq 0\). Now assume that \(r \geq a\). Now \(r = b-as_1 \geq a\) for some \(s_1 \in \mathbb{Z}\). Consider \(r_1 = r-a = b- as_1 - a \geq a-a = 0\) i.e. \(r_1 = b- a (s_1 + 1) \geq 0 \implies r_1 \in S\). However, \(r_1 < r\). This contradicts the minimality of \(r\). Hence, \(0 \leq r \lt a\) and thereby the existence follows.

To prove the uniqueness, as always, assume that there are two distinct sets of numbers \(q_1,r_1 \in \mathbb{Z}\) and \(q_2,r_2 \in \mathbb{Z}\) such that \(aq_1 + r_1 = b = aq_2 + r_2\) and \(0 \leq r_1,r_2 \lt a\). Assume without loss of generality that \(q_1 \lt q_2\). This obviously implies \(r_1 \gt r_2\). Hence, we get \(0 \lt a(q_2-q_1) = r_1 - r_2\). This means that \(a|(r_1 - r_2)\). But, since \(r_1 \gt r_2\), \(0 \lt r_1 - r_2 \lt a\). CONTRADICTION. Hence, the uniqueness follows. \(\Box\)

Theorem:

Suppose that \(a,b \in \mathbb{N}\). Then there exists a unique \(d \in \mathbb{N}\) such that

1. there exists \(x,y \in \mathbb{Z}\) such that \(d = ax+by\);
2. \(d|a\) and \(d|b\);
3. for every \(k\in \mathbb{N}\) such that \(k|a\) and \(k|b\), we have \(k|d\).

Proof:

Consider the set \(I = \{au + bv : u,v \in \mathbb{Z}\}\). Clearly, \(I \subseteq \mathbb{Z}\). By well-ordering principle, there exists a least positive element in \(I\). Call it \(d\). We have \(d = ax+by\) for some \(x,y \in \mathbb{Z}\). 

We now want to show that \(d|a\) and \(d|b\). In fact, we shall show that \(d|(au+bv)\), \(\forall u,v, \in \mathbb{Z}\). By the previous theorem, we get that \(au+bv = dq + r\) where \(0 \leq r \lt d\). Since \(d = ax+by\), we get \(au+bv - (ax+by)q = r\) i.e. \(r = a(u-qx) + b(v-qy)\). Hence, \(r \in I\) and \(0 \leq r \lt d\). But \(d\) is the least positive element in \(I\). This gives us that \(r=0\). Hence, \(d\) divides all elements in the set \(I\). Setting \(u=1\) and \(v=0\) gives us that \(d|a\) and setting \(u=0\) and \(v=1\) gives us that \(d|b\).

We now need to prove that for every  \(k\in \mathbb{N}\) such that \(k|a\) and \(k|b\), we have \(k|d\). We have that \(d = ax+by\). Further since \(k|a\) and \(k|b\), we get \(a=ka_1\) and \(b=kb_1\), where \(a_1,b_1 \in \mathbb{Z}\). Hence, we get \(d = k (a_1x + b_1y)\). Since \(a_1x + b_1y \in \mathbb{Z}\), we get \(k|d\).  \(\Box\)

Definition:

The number \(d\) satisfying the criteria in the above theorem is called the greatest common divisor of \(a\) and \(b\). It is typically denoted as \(d=(a,b)\)

Theorem: (Euclid Algorithm)

Suppose that \(a,b \in \mathbb{N}\). Suppose further that \(q_1,q_2,\ldots,q_{n+1} \in \mathbb{Z}\) and \(r_1,r_2,\ldots,r_n \in \mathbb{N}\) satisfy \(0 \lt r_n \lt r_{n-1} \lt \cdots \lt r_1 \lt a\) and \[b = aq_1 + r_1\] \[a = r_1q_2 + r_2\] \[r_1 = r_2q_3 + r_3\] \[\vdots\] \[r_{n-2} = r_{n-1}q_n + r_n\] \[r_{n-1} = r_{n}q_{n+1}\] Then \((a,b) = r_n\)

Proof:

We shall first prove that \((b,a) = (a,r_1)\). This is not hard to prove. This follows immediately once we note that if \(k\) divides \(a\) and \(b\) then \(k\) has to divide \(r_1\). Similarly, if \(m\) divides \(a\) and \(r_1\) then \(m\) has to divide \(b\). Hence, \((b,a) = (a,r_1)\). Now it follows by repeatedly recognizing this fact that \((b,a) = (a,r_1) = (r_1,r_2) = (r_2,r_3) = \cdots = (r_{n-2},r_{n-1}) = (r_{n-1},r_{n}) = (q_{n+1}r_{n},r_{n}) = r_n\). \(\Box\)

Theorem:

Suppose that \(a,b \in \mathbb{N}\) and \((a,b) = 1\). Suppose further that \(w \in \mathbb{N}\) satisfies \(w|ab\), then there exists a unique \(u,v \in \mathbb{N}\) such that \(u|a\), \(v|b\) and \(w = uv\)

Proof:

Let \(u = (w,a)\) and \(v = (w,b)\). We shall show that \(u|a\), \(v |b\) and \(w = uv\). From the definition of \(u\) and \(v\) it is clear that \(u|a\) and \(v|b\). All we need to show is that \(uv = w\). From the theorem proved earlier, we have that \(u = wx_1 + ay_1\) for some \(x_1,y_1 \in \mathbb{Z}\) and \(v = wx_2 + by_2\) for some \(x_2,y_2 \in \mathbb{Z}\). Hence, we get \(uv = (wx_1 + ay_1)(wx_2 + by_2)\). We also have \(ab = wk\) for some \(k \in \mathbb{Z}\). Hence expanding we get, \(uv = w(wx_1x_2 + x_1by_2 + ay_1x_2 + ky_1y_2)\). Hence, \(w|(uv)\).

Now we will show that \((uv)|w\). Since \((a,b) = 1\), \(\exists x,y \in \mathbb{Z}\) such that \(ax+by = 1\). Multiply by \(w\) to get \(w = wax + wby\). Since \(u = (w,a)\), we get \(w = uw_u\) and \(a = ua_u\). Also since \(v = (w,b)\), we get \(w = v w_v\) and \(b = v b_v\). Hence, \(w = v w_v u a_u x + u w_u v b_v y \implies w = u v (w_v a_u x + w_u b_v y) \implies (uv)|w\).

Now, we still need to show uniqueness. If we have another set, say \(u_1,v_1\), such that \(u_1 | a\), \(v_1 | b\) and \(w = u_1 v_1\). We have that \(u = wx_1 + ay_1 = u_1 v_1 x_1 + u_1 k_1 y_1 = u_1 (v_1 x_1 + k_1 y_1)\) . Hence, we get \(u_1|u\) i.e. \(u = u_1 m_1\). Similarly, we have that \(v = wx_2 + by_2 = u_1 v_1 x_2 + v_1 k_2 y_2 = v_1 (u_1 x_2 + k_2 y_2)\) . Hence, we get \(v_1|v\) i.e. \(v = v_1 l_1\). But we have that \(uv = w = u_1v_1\) and hence we get \(l_1m_1 = 1\) and since \(u,v,u_1,v_1 \in \mathbb{N}\), we get \(l_1 = m_1 = 1\) and hence \(u_1 = u\) and \(v_1 = v\). \(\Box\)

Topology without Tears - 2.1 Definitions and Propositions

Definition:

A subset \(S\) of \(\mathbb{R}\) is said to be open in the euclidean topology on \(\mathbb{R}\) if it has the following property:

For each \(x \in S\), there exists \(a,b \in \mathbb{R}\), with \(a \lt b\) such that \(x \in (a,b) \subseteq S\).

Notation: Whenever we refer to the topological space \(\mathbb{R}\) without specifying the topology, we mean \(\mathbb{R}\) with the euclidean topology.

Proposition:

The euclidean topology is indeed a topology on \(\mathbb{R}\)

Proof:

The drill again.

• Clearly, \(\mathbb{R} \in \tau\) since given any \(x \in \mathbb{R}\), the interval \((x-1,x+1) \subset \mathbb{R}\). \(\emptyset \in \tau\) since the statement "for each \(x \in \emptyset\), there exists \(a,b \in \mathbb{R}\), with \(a \lt b\) such that \(x \in (a,b) \subseteq \emptyset\)" is vacuously true.
• Let \(A_{\alpha} \in \tau\) for every \(\alpha \in \Gamma\). Let \(A = \bigcup_{\alpha \in \Gamma} A_{\alpha}\). Consider \(x \in A\). This means \(x \in A_{\alpha}\) for some \(\alpha \in \Gamma\). Since \(A_{\alpha} \in \tau\), we can find an interval say \((a,b)\) containing \(x\) such that \((a,b) \subseteq A_{\alpha}\). But we have \(A_{\alpha} \subseteq A\) and hence \((a,b) \subseteq A\). Hence, for each \(x \in A\), there exists \(a,b \in \mathbb{R}\) with \(a \lt b\) such that \(x \in (a,b) \subseteq A\). Hence, \(\tau\) is closed under arbitrary unions.
• Let \(A_1,A_2 \in \tau\). Let \(A = A_1 \cap A_2\). Consider \(x \in A\). This means we also have \(x \in A_1\) and \(x \in A_2\) where \(A_1,A_2 \in \tau\). Hence, there exists an interval \((a_1,b_1)\) containing \(x\) such that \((a_1,b_1) \subseteq A_1\) and an interval \((a_2,b_2)\) containing \(x\) such that \((a_2,b_2) \subseteq A_2\). Now let \(a = \max(a_1,a_2)\) and \(b = \min(b_1,b_2)\). Note that \(x \in (a,b)\). We also have \((a,b) \subseteq (a_1,b_1) \subseteq A_1\) and \((a,b) \subseteq (a_2,b_2) \subseteq A_2\). Hence, there exists \(a,b \in \mathbb{R}\), with \(a \lt b\), such that \(x \in (a,b) \subseteq A_1 \cap A_2\). Hence \(\tau\) is closed under finite intersections. \(\Box\)

Proposition:

Let \(r,s \in \mathbb{R}\) with \(r \lt s\). In the euclidean topology \(\tau\) on \(\mathbb{R}\), the open interval \((r,s)\) does indeed belong to \(\tau\) and so is an open set.

Proof:

Given any \(x \in (r,s)\), we want to find an open interval containing \(x\) and lying within \(r,s\). However note that we have \(x \in (r,s) \subseteq (r,s)\). Hence, \((r,s)\) is indeed an open set. \(\Box\)

Proposition:

The open intervals \((r, \infty)\) and \((-infty,r)\) are both open sets in \(\mathbb{R}\), for every real number \(r\).

Proof:

1. The open interval \((r, \infty)\) is an open set. Consider any \(x \in (r,\infty)\). Consider the open interval \((r,x+1)\). Clearly, we have \(x \in (r,x+1) \subset (r,\infty)\). Hence, the open interval \((r, \infty)\) is an open set.
2. The open interval \((-\infty,r)\) is an open set. Consider any \(x \in (-\infty,r)\). Consider the open interval \((x-1,r)\). Clearly, we have \(x \in (x-1,r) \subset (-\infty,r)\). Hence, the open interval \((-\infty,r)\) is an open set. \(\Box\)

Proposition:

For each \(c,d \in \mathbb{R}\) with \(c \lt d\), the closed interval \([c,d]\) is not an open set in \(\mathbb{R}\). In fact, the closed interval \([c,d]\) is a closed set in \(\mathbb{R}\).

Proof:

Consider the complement of \([c,d]\). We have \(\mathbb{R} \backslash [c,d] = (-\infty,c) \cup (d, \infty)\). From previous part, we have that \((-\infty,c)\) and \((d,\infty)\) are open sets. And union of open sets is also open and hence \(\mathbb{R} \backslash [c,d] \) is open. Hence, \([c,d]\) is a closed set. We still need to prove that it is not open. Consider the point \(c \in [c,d]\). Suppose that there exists \(a,b \in \mathbb{R}\) such that \(c \in (a,b)\). We will prove that \((a,b) \not\subseteq [c,d]\). To see this, consider the point \(\frac{a+c}{2}\). We have \(a \lt \frac{a+c}{2} \lt c\). Hence, we have that \(\frac{a+c}{2} \in (a,b)\) but \(\frac{a+c}{2} \notin [c,d]\). Hence, \((a,b) \not\subseteq [c,d]\). CONTRADICTION. Hence, \([c,d]\) is not an open set. \(\Box\)

Proposition:

Every singleton set \(\{a\}\) is closed in \(\mathbb{R}\).

Proof:

One way to think of \(\{a\}\) is nothing but the closed interval \([a,a]\). The proof is same as the one for the previous case. There is no difference in the proof if \(a \lt b\) (or) \(a=b\).

Proposition:

The set \(\mathbb{Z}\) of all integers is a closed subset of \(\mathbb{R}\).

Proof:

Consider the complement of \(\mathbb{Z}\) in \(\mathbb{R}\) i.e. \(A = \mathbb{R} \backslash \mathbb{Z}\). Now consider any point \(x \in A\). Let \(\epsilon = \min(\{x-\lfloor x \rfloor , \lceil x \rceil - x\})\). Note that \(\epsilon > 0\) since \(x\) is never an integer. Consider the open interval \((x-\epsilon,x+\epsilon)\). Hence, for every \(x \in \mathbb{R} \backslash \mathbb{Z}\), we can find \((x-\epsilon,x+\epsilon) \in \mathbb{R} \backslash \mathbb{Z}\). Hence, the set \(\mathbb{R} \backslash \mathbb{Z}\) is open. This gives us that the set \(\mathbb{Z}\) is a closed set.

Proposition:

The set \(\mathbb{Q}\) of all rational numbers is neither a closed subset of \(\mathbb{R}\) nor an open subset of \(\mathbb{R}\).

Proof:

Let \(\mathbb{I} = \mathbb{R} \backslash \mathbb{Q}\) be the set of irrationals.

1. We shall first prove that \(\mathbb{Q}\) is not open under the euclidean topology. To see this, we shall prove it by contradiction. Assume that the set is open i.e. given any point \(x \in \mathbb{Q}\), there exists an open interval of the form \((a,b) \subseteq \mathbb{Q}\). Let \(\epsilon = \min(\{x-a,b-x\})\). By Archimedean property, there exists an \(n \in \mathbb{N}\) such that \(\frac{\sqrt{2}}{n} < \epsilon\). This gives us that \(x \pm \frac{\sqrt{2}}{n} \in (a,b)\). However note that \(x \pm \frac{\sqrt{2}}{n} \notin \mathbb{Q}\). This gives us a CONTRADICTION. Hence, \(\mathbb{Q}\) is not open under the euclidean topology.
2. We shall now prove that \(\mathbb{Q}\) is not closed. To prove this, we shall prove that \(\mathbb{I}\) is not open. We shall prove this by contradiction. Assume that \(\mathbb{I}\) is open i.e. given any point \(x \in \mathbb{I}\), there exists an open interval of the form \((a,b) \subseteq \mathbb{I}\). Let \(\epsilon = \min(\{x-a,b-x\})\). There exists \(n \in \mathbb{N}\) such that \(\frac1{10^n} < \epsilon\). Assuming \(x\) is expressed in decimal system, for any \(x\), we get \(\displaystyle x - \frac{\lfloor 10^{n} x \rfloor}{10^{n}} \lt \frac1{10^n} \lt \epsilon\). But note that \(y = \frac{\lfloor 10^{n} x \rfloor}{10^{n}}\) is a rational number and \(y \in (a,b)\). CONTRADICTION. Hence, \(\mathbb{I}\) is not open under the euclidean topology. Hence, \(\mathbb{Q}\) is not closed under the euclidean topology.

Hence, \(\mathbb{Q}\) is neither open nor closed.