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 .

  1. When , .
  2. When , .
  3. 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: