CIS375 Help Session Note 3 (Spring 2020)
Scire ad trascendere  Learn to transcend.
Topics covered:
 Relations
 Indirect proof
Relations

Cartesian product
The Cartesian product of and (denoted by ) is
Note: and must be sets!
If , , then .
If , , what is ?

What are relations?
A relation is a set of ordered pairs.

Where is a relation defined?
 A relation is said to be on if .
 A relation is said to be from to if .
If is on , what elements can be present in ?
If , are on , give an example of .
If , , is true?
Yes. Because . Given the fact that , we have .
Indirect proof
Proof by contrapositive
If we look at the truth table of and , it is not difficult to find out that they are logically equivalent. Therefore, proving is equivalent to proving .
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 and , then or ”.
The proposition can be written as . The contrapositive is
In plain English, it means “if not and not , then not or not ”.
Write the contrapositive of “if is a even number, then , ”.
The proposition can be written as . The contrapositive is
In plain English, it means “If for all integer , is not equal to , then is not even.”
Proof by contradiction
We can observe that is logically equivalent to . Therefore, to prove is True, we can assume both and 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 is a real number, then is not negative.
Suppose is a real number, but is negative. If , we know that either , or .
 When , .
 When , .
 When , .
Therefore, such real number does not exist.
Remarks. The 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 and are real numbers and , then or .
Suppose and are real numbers and , but and . It is obvious that .
The technique is very useful in the proof of some very tricky statements, for example: