Skip to main content

PLP: An introduction to mathematical proof

Seçkin Demirbaş, Andrew Rechnitzer

Exercises 8.6 Exercises

1.

Consider the following sets
  • \(A_1=\set{ x\in\mathbb{Z}\colon x^2 \lt 2 }\text{,}\)
  • \(A_2=\set{ x\in\mathbb{N}\colon (3\mid x)\land (x\mid 216) }\text{,}\)
  • \(A_3=\set{ x\in\mathbb{Z}\colon \dfrac{x+2}{5}\in\mathbb{Z} }\text{,}\)
  • \(A_4=\set{ a\in B\colon 6\leq 4a+1 \lt 17 }\text{,}\) where \(B=\set{1,2,3,4,5,6}\text{,}\)
  • \(A_5=\set{ x\in C\colon 50 \lt xd \lt 100 \text{ for some } d\in D}\text{,}\) where \(C=\set{ 2,3,5,7,11,13, \ldots }\) and \(D=\set{ 5,10 }\text{,}\)
  • \(A_6=\set{5,10,15,20,25,\ldots}\text{,}\)
  • \(A_7=\set{2,3,4,6,8,9,12,16,18, 24\ldots }\text{,}\)
Write down the sets below by listing their elements.
  1. \(A_2- A_3\text{,}\)
  2. \(A_5\cap A_6\text{,}\)
  3. \(\pow{A_1})\text{,}\)
  4. \(\pow{\pow{A_1-\set{-1} }} \text{,}\)
  5. \(A_3\cap A_4\text{,}\)
  6. \(A_3-A_7\text{,}\)
  7. \(A_5\cup A_2\text{,}\)
  8. \(A_2\cap A_7\text{.}\)
  9. \(A_5\cap \overline{A_2}\text{,}\) given the universal set \(U=\mathbb R\text{.}\)
  10. Verify whether \((A_4\times B)\cap(B\times A_4)=A_4\times A_4\) and \((A_4\times B)\cup(B\times A_4)=B\times B\text{.}\)

2.

Write down the set \(F\cap G\) where
\begin{equation*} F=\set{(x,x^2-3x+2)\in\mathbb{R}^2: x\in\mathbb R } \qquad \text{and}\qquad G=\set{ (a, a+2)\in\mathbb{R}^2: a\in\mathbb R } \end{equation*}
by listing out all of its elements. Prove your answer.

3.

Prove or disprove the following statement:
Suppose \(A\text{,}\) \(B\) and \(C\) are sets. If \(A = B-C\text{,}\) then \(B = A \cup C\text{.}\)

4.

Suppose \(x, y \in\mathbb{R}\) and \(k \in\mathbb N\) satisfying, \(x,y\gt 0\) and \(x^k = y\text{.}\) Then prove that \(\set{x^a\st a \in \mathbb{Q}}=\set{ y^a\st a\in\mathbb{Q} }\text{.}\)

5.

Prove or disprove the following statement:
If \(m,n \in\mathbb{N}\text{,}\) then \(\set{x \in\mathbb{Z} : m\mid x}\cap\set{x \in\mathbb{Z} : n\mid x}\subseteq \set{x \in\mathbb{Z} : mn\mid x} \text{.}\)

6.

Prove or disprove the following statement:
Let \(m,n \in\mathbb{Z}\text{.}\) Then \(\set{x \in\mathbb{Z} : mn\mid x}\subseteq \set{x \in\mathbb{Z} : m\mid x}\cap\set{x \in\mathbb{Z} : n\mid x}\text{.}\)

7.

Let \(A\) be a set. Prove or disprove the following statements. If the statement is false in general, determine if there are any sets for which the statement is true.
  1. \(\displaystyle A\times \emptyset \subseteq A.\)
  2. \(\displaystyle A\times \emptyset = A.\)

8.

Suppose that \(A, B\neq \emptyset\text{,}\) and \(C\) are sets such that \(A\subseteq B\text{.}\)
  1. Prove that \(A\times C \subseteq B\times C.\)
  2. Suppose we have a strict containment \(A\subset B\) instead. What additional constraints do we need (if any) to show that
    \begin{equation*} A\times C \subset B\times C? \end{equation*}
    Prove your claim.

9.

Prove or disprove the following statement:
If \(A\) and \(B\) are sets, then \(\mathcal{P}(A)\cap\mathcal{P}(B) = \mathcal{P}(A\cap B)\text{.}\)

10.

Prove or disprove the following statement:
If \(A\) and \(B\) are sets, then \(\mathcal{P}(A)\cup\mathcal{P}(B) = \mathcal{P}(A\cup B)\text{.}\)

11.

Let \(A\) be a finite set with \(|A|=n\text{.}\) Prove that \(|\pow A|=2^n\text{.}\)

12.

Let \(A\) and \(B\) be sets. Prove or disprove the following statements:
  • \(\pow{A - B} \subseteq \pow{A} - \pow{B}\text{,}\) and
  • \(\pow{A} - \pow{B} \subseteq \pow{A - B}\text{.}\)

13.

Prove that
  1. \(\displaystyle \ds \bigcup_{n=3}^\infty \left(\frac{1}{n},1-\frac{1}{n}\right) = (0,1) \)
  2. \(\displaystyle \ds \bigcap_{n=1}^\infty \left(-\frac{1}{n}, 1+\frac{1}{n}\right)=[0,1] \)

14.

Determine what each of the following unions is equal to, and prove your answer.
  1. \begin{equation*} \bigcup_{n\in\mathbb{N}}[-n,n] \end{equation*}
  2. \begin{equation*} \bigcup_{r\in\mathbb{R}, r\gt0} B_r \end{equation*}
    where
    \begin{equation*} B_r = \{(x,y)\in \mathbb{R}\times\mathbb{R}:x^2+y^2\lt r\}. \end{equation*}

15.

Let \(S\subset\mathbb{R}\text{.}\) We say \(b\in\mathbb{R}\) is an upper bound of \(S\) if \(s\leq b\) for every \(s\in S\text{.}\) Further, we say \(a\in\mathbb{R}\) is the supremum (or the least upper bound) of \(S\text{,}\) denoted by \(\sup(S)\text{,}\) if
  • \(a\) is an upper bound for \(S\text{,}\) and
  • if \(b\) is an upper bound for \(S\text{,}\) then \(a\leq b\text{.}\)
We also call \(c\in S\) the maximum element of \(S\text{,}\) denoted by \(\max(S)\text{,}\) if it is the largest element in \(S\text{.}\) So, \(\max(S)\) belongs to \(S\text{,}\) and is an upper bound of \(S\text{.}\)
For each of the following sets, determine its maximum and supremum, if they exist. Justify your answers.
  1. \(\displaystyle [1,3]= \set{x \in \mathbb{R} \;:\; 1\leq x \leq 3}\)
  2. \(\displaystyle (1,3)= \set{x \in \mathbb{R} \;:\; 1\lt x \lt 3}\)
  3. \(\displaystyle \set{m\in\mathbb{Z}\;:\; |2(m-4)|\leq 15}\)
  4. \(\displaystyle \set{2-\frac{1}{n}\;:\;n\in\mathbb{N}}\)
  5. \(\displaystyle \set{x\in\mathbb{R}\;:\;\cos(2x)=1}\)

16.

This question involves the supremum, which we first introduced in a previous exercise, Exercise 8.6.15. We recommend that you complete that question before you attempt this one.
Let \(S\subset\mathbb{R}\text{.}\) We say \(b\in\mathbb{R}\) is an upper bound of \(S\) if \(s\leq b\) for every \(s\in S\text{.}\) Further, we say \(a\in\mathbb{R}\) is the supremum (or the least upper bound) of \(S\text{,}\) denoted by \(\sup(S)\text{,}\) if
  • \(a\) is an upper bound for \(S\text{,}\) and
  • if \(b\) is an upper bound for \(S\text{,}\) then \(a\leq b\text{.}\)
Suppose that \(S,T\) are non-empty subsets of \(\mathbb{R}\text{,}\) and \(s=\sup(S)\text{,}\) \(t=\sup(T)\text{,}\) where \(s,t \in\mathbb{R}\text{.}\)
  1. Show that \(\sup(S\cup T)=\max\set{s,t}\text{.}\)
  2. Can you determine \(\sup(S\cap T)\text{?}\)
  3. Define \(S+T=\set{s+t:s\in S, t\in T}\text{.}\) Show that \(\sup(S+T)=s+t\text{.}\)

17.

Before completing this question you should look at Exercise 8.6.15 and Exercise 8.6.16. Let \(\{a_n\}_{n\in\in\mathbb{N}}\) be a sequence such that \(a_{n+1}\geq a_n\) for all \(n\in \mathbb{N}\text{,}\) and such that
\begin{equation*} a = \sup\{a_n:n\in\mathbb{N}\} \end{equation*}
exists as a real number. Show that
\begin{equation*} \lim_{n\to\infty}a_n = a. \end{equation*}
<Prev^TopNext>