# CIS-375 Help Session Note 3 (Spring 2020)

Scire 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$$.

TTFFTT
TFFTFF
FTTFTT
FFTTTT

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.”

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.

TTFFTT
TFTTFF
FTFFTT
FFTFTT

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$$.

1. When $$x < 0$$, $$x^2 > 0$$.
2. When $$x = 0$$, $$x^2 = 0$$.
3. 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: