CIS-375 Help Session Note 3 (Spring 2020)
11 Mar 2020Scire ad trascendere - Learn to transcend.
Topics covered:
- Relations
- Indirect proof
Relations
-
Cartesian product
The Cartesian product of \(A\) and \(B\) (denoted by \(A \times B\)) is
\[\begin{align*} A \times B = \{ (x, y) : x \in A, y \in B \}. \end{align*}\]Note: \(A\) and \(B\) must be sets!
If \(\lvert A\rvert =m\), \(\lvert B \rvert =n\), then \(\lvert A \times B \rvert = m \times n\). \(\newcommand{\rrel}{\mathrel{R}}\)
If \(A = \{1, 2, 3\}\), \(B = \{4, 5, 6\}\), what is \(A \times B\)?
\(\begin{aligned} A \times B = \{& (1, 4), (1, 5), (1, 6)\\ &(2, 4), (2, 5), (2, 6),\\ &(3, 4), (3, 5), (3, 6)\}. \end{aligned}\)
-
What are relations?
A relation \(R\) is a set of ordered pairs.
-
Where is a relation defined?
- A relation \(R\) is said to be on \(A\) if \(R \subseteq A \times A\).
- A relation \(R\) is said to be from \(A\) to \(B\) if \(R \subseteq A \times B\).
If \(R\) is on \(A = \{2, 5\}\), what elements can be present in \(R\)?
\(\begin{aligned} R \subseteq A \times A = \{ (2, 2), (2, 5), (5, 2), (5, 5) \}. \end{aligned}\)
If \(R_1\), \(R_2\) are on \(A = \{2, 5\}\), give an example of \(R_1 \subseteq R_2\).
\(\begin{aligned} R_1 &= \{(2, 2)\}\\ R_2 &= \{(2, 2), (2, 5)\}. \end{aligned}\)
If \(a \mathrel{R_1} b\), \(R_1 \subseteq R_2\), is \(a \mathrel{R_2} b\) true?
Yes. Because \(a \mathrel{R_1} b \rightarrow (a, b) \in R_1\). Given the fact that \(R_1 \subseteq R_2\), we have \((a, b) \in R_2\).
Indirect proof
Proof by contrapositive
If we look at the truth table of \(a \rightarrow b\) and \((\neg b) \rightarrow \neg a\), it is not difficult to find out that they are logically equivalent. Therefore, proving \(a \rightarrow b\) is equivalent to proving \((\neg b) \rightarrow \neg a\).
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Write the contrapositive of “if \(a\) and \(b\), then \(c\) or \(d\)”.
The proposition can be written as \((a \land b) \rightarrow (c \lor d)\). The contrapositive is
\[\begin{align*} &\phantom{\Rightarrow}\quad(a \land b) \rightarrow (c \lor d)\\ &\Rightarrow\quad \neg (c \lor d) \rightarrow \neg(a \land b)\\ & \Rightarrow\quad (\neg c) \land (\neg d) \rightarrow (\neg a) \lor (\neg b) \end{align*}\]In plain English, it means “if not \(c\) and not \(d\), then not \(a\) or not \(b\)”.
Write the contrapositive of “if \(n \in \mathbb{Z}\) is a even number, then \(\exists k \in \mathbb{Z}\), \(n = 2k\)”.
The proposition can be written as \(n~\mbox{is even}\rightarrow \exists k \in \mathbb{Z}, n = 2k\). The contrapositive is
\[\begin{align*} &\phantom{\Rightarrow}\quad n~\mbox{is even}\rightarrow \exists k \in \mathbb{Z}, n = 2k\\ &\Rightarrow\quad \neg (\exists k \in \mathbb{Z}, n = 2k) \rightarrow n~\mbox{is not even}\\ &\Rightarrow\quad \forall k \in \mathbb{Z}, n \neq 2k \rightarrow n~\mbox{is not even}. \end{align*}\]In plain English, it means “If for all integer \(k\), \(n\) is not equal to \(2k\), then \(n\) is not even.”
Proof by contradiction
We can observe that \(a \rightarrow b\) is logically equivalent to \((a \land \neg b) \rightarrow \mathrm{False}\). Therefore, to prove \(a \rightarrow b\) is True, we can assume both \(a\) and \(\neg b\) are True, and verify that this will imply something False.
| T | T | F | F | T | T |
| T | F | T | T | F | F |
| F | T | F | F | T | T |
| F | F | T | F | T | T |
Proof by contradiction: if \(x\) is a real number, then \(x^2\) is not negative.
Suppose \(x\) is a real number, but \(x^2\) is negative. If \(x \in R\), we know that either \(x < 0\), \(x = 0\) or \(x > 0\).
- When \(x < 0\), \(x^2 > 0\).
- When \(x = 0\), \(x^2 = 0\).
- When \(x > 0\), \(x^2 > 0\).
Therefore, such real number \(x\) does not exist. \(\Rightarrow\Leftarrow\)
Remarks. The \(\Rightarrow\Leftarrow\) notation means: thus we have reached a conclusion. Therefore the supposition must be False, which means the original proposition must be True.
Proof by contradiction: if \(a\) and \(b\) are real numbers and \(ab = 0\), then \(a = 0\) or \(b = 0\).
Suppose \(a\) and \(b\) are real numbers and \(ab = 0\), but \(a \neq 0\) and \(b \neq 0\). It is obvious that \(ab \neq 0\). \(\Rightarrow\Leftarrow\)
The technique is very useful in the proof of some very tricky statements, for example: