Set math (notations and P iff Q)

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 = 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

∩ intersection (wikipedia)

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:

  1. Write, “We use proof by contradiction.”
  2. Write, “Suppose P is false.”
  3. Deduce a logical contradiction.
  4. 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

Leave a Reply

Your email address will not be published. Required fields are marked *