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

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

%

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

%

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

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

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.

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$ or $x > 0$.

1. When $% $, $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: