Some math basics for trying to understand https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_proofs.pdf and/or MIT’s OCW on math for computer science.

## Sets

for set A and B

∪ = union, Everything in A AND everything in B (including overlap)

∩ = intersection, Everything in A AND B (just the overlap)

A \ B = {x | x ∈ A and x ∈ B} = Everything in A but not in B

A ∈ B = A is part of B (smaller side of ∈ towards the smaller set)

Q.E.D. = Proof done (normally a block symbol, but wordpres….)

P iff Q = P if and only if Q = P ↔ Q) = P implies Q and vice-versa

## Set proof (both statements imply eachother)

With set A,B,C:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

the intersection of A with (B andor C)

=

(The intersection between A and B) andor (the intersection between A and C)

This looks correct, but let’s prove it.

**Proof**.

We show that **z ∈ A ∩ (B ∪ C)** implies that**z ∈ (A ∩ B) ∪ (A ∩ C) **and vice-versa.**First**, we show that z ∈ A ∩ (B ∪ C) implies that

z ∈ (A ∩ B) ∪ (A ∩ C):

Assume that z ∈ A ∩ (B ∪ C).

Then z is in A and z is also in B or C. Thus, z is in

either A∩B or A∩C, which implies z ∈ (A∩B)∪(A∩C)

——-**Now**, we show that z ∈ (A∩B)∪(A∩C) implies that

z ∈ A ∩ (B ∪ C).

Assume that z ∈ (A ∩ B) ∪ (A ∩ C).

Then z is in both A and B or else z is in both A and

C. Thus, z is in A and z is also in B or C. This implies

that z ∈ A ∩ (B ∪ C).

Q.E.D.

## Proof by contradiction

Proof by contra-positive ((P → Q) ↔ (¬Q → ¬P) is a tautology. )

In order to prove a proposition P by contradiction:

- Write, “We use proof by contradiction.”
- Write, “Suppose P is false.”
- Deduce a logical contradiction.
- Write, “This is a contradiction. Therefore, P must

be true.”

**Theorem: sqrt(2) is irrational**

proving something irrational is hard, so instead assume it to be rational:

sqrt(2) = a/b (in the lowest terms a and b possible)

2 = (a^2)/(b^2)

a^2 = 2(b^2)

which means a^2 is even

thus a is even

thus a^2 is a multiple of 4

thus b^2 is a multiple of 4

thus b is also even

a and b are even which is a contradiction with the lowest term rule

thus a/b is not rational