97. Sets

Definition: Set

A set is a collection of objects called elements or numbers

Definition: Empty Set

Set with no elements

Notation

• : a is an element of S
• : a is not an element of S
• : for all
• : there exists
• : implies
• : if and only if

Definition:

1. if if

2. if

3. if

Set Building Notation

All satisfying property

or

Examples

4. Odd numbers:

Definition

1. Union:
2. Intersection:
3. Difference:
4. Complement:
5. Disjount:

De Morgan

If A, B, C are sets, then:

Proof

Let B, C be sets.

We want to prove that:

Since to prove the equality of two sets we need to show that Equation 1 holds:

We need to show that:

and

WTS Equation 2:

Let

Then

Thus,

WTS Equation 3:

Let

Then

Thus,

Thus,

Theorem: Induction

has an ordering

Axiom: Well ordering property

If and then has a least element: i.e.,

Let be a statement depending on . Assume:

1. (Base Case) is True
2. (Induction Step) If is True, then is True

Then is true for all

Proof

Let

WTS:

We will prove this by contradiction

(Assume the negation of the statement and derive a false statement. Rules of logic say that is false.)

Suppose , by the well ordering property (WOP) of , has a least element . Since is True (assumption), , this particular . Since is the least element of and , . Thus, by the definition of , is True. By the second property of induction (Induction Step) is True .

From , we conclude , and . Contradiction.

Thus,

Using Induction

We want to prove is True, we need to do 2 things:

1. Prove base case
2. Prove, if is True, is True

Theorem

,

Proof

Prove Equation 4 by induction: 1) (Basic Case)

2) (Induction Step)

We want to prove Equation 4 holds for

We have:

Thus, Equation 4 holds for . So by induction, Equation 4 holds for all

Theorem

If , then ,

Proof (By Induction)

1) (Base Case)

So, Equation 5