Skip to main content

PLP: An introduction to mathematical proof

Exercises 9.7 Exercises

1.

Let \(A =\set{1,2,3,4,5,6}\text{.}\) Write out the relation \(R\) that expresses “\(\nmid\)” (does not divide) on \(A\) as a set of ordered pairs. That is, \((x,y)\in R\) if and only if \(x\nmid y\text{.}\) Is the relation reflexive? Symmetric? Transitive?

2.

Define a relation on \(\mathbb{R}\) as \(x \rel y\) if \(|x-y| \lt 1\text{.}\) Is \(R\) reflexive? Symmetric? Transitive?

3.

For each of the following relations, determine whether or not they are reflexive, symmetric, and transitive.
  1. \(\displaystyle R = \set{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)}\subseteq\set{1,2,3}\times\set{1,2,3} \)
  2. For \(a,b\in\mathbb{N}\text{,}\) \(a\rel b\) if and only if \(a\mid b\text{.}\)
  3. \(\displaystyle R=\set{(x,y)\in\mathbb{R}\times\mathbb{R}:x-y\in\mathbb{Q}}\)
  4. For \(A,B\subseteq\mathbb{R}\text{,}\) \(A\rel B\) if and only if \(A\cap B=\emptyset\text{.}\)
  5. For functions \(f,g:\mathbb{R}\rightarrow \mathbb{R}\text{,}\) \(f\rel g\) if and only if \(f-g\) is linear, that is, there are constants \(m,b\in\mathbb{R}\) so that \(f(x)-g(x)=mx+b\) for all \(x\in\mathbb{R}\text{.}\) The constants \(m,b\) depend on \(f\) and \(g\text{,}\) but not on \(x\text{.}\)

4.

Determine whether the following relations are reflexive, symmetric and transitive. Prove your answers.
  1. On the set \(X\) of all functions \(\mathbb R\rightarrow \mathbb R\text{,}\) we define the relation:
    \begin{equation*} f\rel g \text{ if there exists } x\in \mathbb R \text{ such that } f(x)= g(x). \end{equation*}
  2. Let \(\rel[S]\) be a relation on \(\mathbb Z\) defined by:
    \begin{equation*} x\rel[S] y \text { if } xy\equiv 0\pmod 4. \end{equation*}

5.

For each of the following relations, show that they are equivalence relations, and determine their equivalence classes.
  1. \(\displaystyle R = \set{((x_1,y_1),(x_2,y_2))\in\mathbb{R}^2\times\mathbb{R}^2:x_1^2+y_1^2=x_2^2+y_2^2}\)
  2. Let \(L\) be the set of all lines on the Euclidean plane, \(\mathbb{R}^2\text{.}\) For \(\ell_1,\ell_2\in L\text{,}\) \(\ell_1 \rel\ell_2\) if and only if \(\ell_1\) and \(\ell_2\) have the same slope, or they are both vertical lines.
  3. Let \(R\) be a relation on \(\mathbb{Z}^2\) defined by \(x \rel y\) if and only if \(3\mid x^2-y^2\text{.}\)

6.

Define a relation on \(\mathbb{Z}\) as
\begin{equation*} a \rel b \quad \iff \quad 3\mid (2a-5b). \end{equation*}
Is \(R\) an equivalence relation? Prove your answer.

7.

Let \(E\) be a non-empty set and \(q \in E\) be a fixed element of \(E\text{.}\) Consider the relation \(\rel\) on \(\mathcal P(E)\) (power set of \(E\)) defined as
\begin{gather*} A \rel B \iff (q \in A\cap B)\lor (q \in \overline{A}\cap \overline{B}), \end{gather*}
where for any set \(S\subseteq E\text{,}\) we write \(\overline{S}=E-S\) for the complement of \(S\) in \(E\text{.}\) Prove or disprove that \(\rel\) an equivalence relation.

8.

Let \(R\) be a relation on \(\mathbb Z\) defined by \(a\rel b\) if \(7a^2\equiv 2b^2 \mod{5}\text{.}\) Prove that \(R\) is an equivalence relation. Determine its equivalence classes.

9.

Let \(n\in\mathbb{N}\) with \(n \gt 1\) and let \(P\) be the set of polynomials with coefficients in \(\mathbb{R}\text{.}\) We define a relation, \(T\text{,}\) on \(P\) as follows:
Let \(f,g\in P\text{.}\) Then we say \(f T g\) if \(f-g=c\) for some \(c\in\mathbb R\text{.}\) That is, if there exists a \(c\in \mathbb{R}\) such that for all \(x\in \mathbb{R}\text{,}\) \(f(x)-g(x) = c\text{.}\)
Show that \(T\) is an equivalence relation on \(P\text{.}\)

10.

Prove or disprove the following statements:
  1. If \(R\) and \(S\) are two equivalence relations on a set \(A\text{,}\) then \(R\cup S\) is also an equivalence relation on \(A\text{.}\)
  2. If \(R\) and \(S\) are two equivalence relations on a set \(A\text{,}\) then \(R\cap S\) is also an equivalence relation on \(A\text{.}\)

11.

Let \(R\) be a symmetric and transitive relation on a set \(A\text{.}\)
  1. Show that \(R\) is not necessarily reflexive.
  2. Suppose that for every \(a \in A\text{,}\) there exists \(b \in A\) such that \(a \rel b\text{.}\) Prove that \(R\) is reflexive.

12.

Let \(R\) be a relation on a nonempty set \(A\text{.}\) Then \(\overline{R}= (A \times A) - R\) is also a relation on \(A\text{.}\) Prove or disprove each of the following statements:
  1. If \(R\) is reflexive, then \(\overline{R}\) is reflexive.
  2. If \(R\) is symmetric, then \(\overline{R}\) is symmetric.
  3. If \(R\) is transitive, then \(\overline{R}\) is transitive.

13.

In this question we will call a relation \(R \subset \mathbb{Z}\times \mathbb{Z}\) sparse if \((a,b) \in R\) implies that \((a,b+1)\) and \((a+1,b)\) are NOT elements of \(R\text{.}\)
  1. Prove that for all \(n \in \mathbb{N}\) the equivalence relation \(R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} : n\mid (a-b)\}\) is sparse if and only if \(n \neq 1\text{.}\)
  2. Prove or disprove that every equivalence relation \(R\) on \(\mathbb{Z}\) is sparse.

14.

Let \(A\) be a non-empty set and \(P\subseteq \mathcal P(A)\) and \(Q\subseteq \mathcal P(A)\) partitions of \(A\text{.}\) Prove that the set \(R\) defined as
\begin{gather*} R=\{S\cap T : S\in P,\ T\in Q\}- \{\emptyset\} \end{gather*}
is also a partition of \(A\text{.}\)

15.

Suppose that \(n \in \mathbb{N}\) and \(\mathbb{Z}_n\) is the set of equivalence class of congruent modulo \(n\) on \(\mathbb{Z}\text{.}\) In this question we will call an element \([u]_n\) invertible if it has a multiplicative inverse. That is,
\begin{equation*} [u]_n \text{ is invertible} \iff \text{there exists } [v]_n \in \mathbb{Z}_n \text{ so that } [u]_n [v]_n = [1]_n. \end{equation*}
Now, define a relation \(R\) on \(\mathbb{Z}_n\) by
\begin{equation*} [x]_n \;R\; [y]_n \iff [x]_n[u]_n=[y]_n \text{ for some invertible } [u]_n\in \mathbb{Z}_n. \end{equation*}
  1. Show that \(R\) is a equivalence relation.
  2. Compute the equivalence classes of this relation for \(n=6\text{.}\)

16.

Let \(n\in\mathbb{Z}\) and \(p\geq 5\) be prime.
  1. Prove, using Bézout’s identity that if \(3\mid n\) and \(8\mid n\text{,}\) then \(24\mid n\text{.}\)
  2. Use the result in part (a) to show that \(p^2\equiv 1 \pmod {24}\text{.}\)

17.

  1. Let \(p\) be a prime number, and suppose that \(n\in\mathbb{Z}\) is such that \(n\not\equiv0\mod{p}\text{.}\) Show that there is some \(k\in\mathbb{Z}\) so that \(nk\equiv1\mod{p}\text{.}\)
  2. Find an example to show that (a) may not be true if \(p\) is not prime. That is, find some composite number \(p\) and \(n\in\mathbb{Z}\text{,}\) \(n\not\equiv0\mod{p}\) such that \(nk\not\equiv1\mod{p}\) for all \(k\in\mathbb{Z}\text{.}\)

18.

Let \(a,b,d\in\mathbb Z\) such that \(d\mid ab\text{.}\) Show that the integer, \(\frac{d}{\gcd(a,d)} \text{,}\) divides \(b\text{.}\)

19.

Let \(a,b\in\mathbb{Z}\text{,}\) at least one of which is non-zero.
  1. Suppose that \(d\) divides both \(a\) and \(b\text{.}\) Show that \(d\mid\gcd(a,b)\text{.}\)
  2. Let \(m\in \mathbb{N}\text{.}\) Show that \(\gcd(ma,mb)=m\gcd(a,b)\text{.}\)
  3. Let \(c\in \mathbb{Z}\text{,}\) \(c\neq0\text{.}\) Show that the statement
    \begin{equation*} \gcd(ac,b)=\gcd(a,b)\cdot\gcd(c,b) \end{equation*}
    does not hold in general.

20.

A frequently used but false statement is
\begin{equation*} (x+y)^n = x^n + y^n \end{equation*}
This is sometimes referred to by mathematicians as the “child’s binomial theorem” (a quick trip to your search engine will turn up other names). One often sees examples of it such as
\begin{equation*} \sqrt{x+y} = \sqrt{x}+\sqrt{y} \qquad \text{ and } \qquad (x+y)^2 = x^2 + y^2. \end{equation*}
While it is definitely false, there is something here that can be rescued. Notice that if we take \(x,y \in \mathbb{Z}\) and let \(n=2\text{,}\) then
\begin{equation*} (x+y)^2 = x^2 + 2xy + y^2 \end{equation*}
and so if we look at everything modulo 2 we get
\begin{equation*} (x+y)^2 \equiv (x^2 + 2xy + y^2) \equiv (x^2+y^2) \pmod 2. \end{equation*}
Similarly, with \(n=3\) we have
\begin{equation*} (x+y)^3 \equiv (x^3 + 3x^2y + 3xy^2 + y^3) \equiv (x^3+y^3) \pmod 3. \end{equation*}
Indeed, one can show that for any prime number \(p\text{,}\) and integers \(x,y\) we have
\begin{equation*} (x+y)^p \equiv x^p + y^p \pmod p. \end{equation*}
Notice that this is not true for non-prime powers:
\begin{equation*} (1+3)^4 = 4^4 = 256 \equiv 0 \pmod 4 \end{equation*}
while
\begin{equation*} 1^4 + 3^4 = 82 \equiv 2 \pmod 4. \end{equation*}
  1. Use the recurrence in Exercise 7.3.21 (see Pascal’s identity), together with the fact that \(\binom{n}{0}=\binom{n}{n}=1\text{,}\) to prove that the binomial coefficients \(\binom{n}{k}\) are integers.
  2. Prove that for prime \(p\) and integer \(0 \lt k \lt p\) the binomial coefficient \(\binom{p}{k}\) is a multiple of \(p\text{,}\) and so
    \begin{equation*} \binom{p}{k} \equiv 0 \pmod p \qquad \text{for } 0 \lt k \lt p. \end{equation*}
  3. Then using this and the Binomial Theorem (see Exercise 7.3.21) prove the result
    \begin{equation*} (x+y)^p \equiv x^p + y^p \pmod p. \end{equation*}