MATH 220

Final Review

Updated 2017-12-17

Chapter 1

Set

Power Set

Suppose then its power set is a set of all subsets of :

Set Operations

Suppose sets

Union

If or then

Intersection

If and then

Difference

If and then

Compliment

If then

Direct Product

Direct product of two sets is that outputs an ordered set such that .

Indexed Sets Operations

Union

Intersection

Chapter 2

Statement

A statement is a claim. A statement can be true or false.

Logical Operations

Conjunction

Binary operator also known as and. Denoted by . Suppose and are statements is true if and only if and are both true.

Disjunction

Binary operator also known as or. Denoted by . is true if is true, is true, or both is true.

Negation

Denoted by . If , then is true if and only if is false.

Open Sentence

A statement that can’t be determined to be true or false unless a quantifier is given. An example would be:

Logical Equivalences

DeMorgan

Distributive

Implications

Implication:

Converse:

Contrapositive:

Negation:

Biconditional Implications

Also referred to as “if and only if”

Quantifier

An example of quantifiers to the open sentence example (above) would be:

Negation

Chapter 4-10

Direct Proof

To prove , the structure is:

Proof By Cases

Usually use when there there is a disjunction in the proof.

Proof By Contrapositive

To prove , the structure is:

Proof By Contradiction

To prove , the structure is:

Existence Proof

To prove , where is the statement. Just provide an example.

Uniqueness Proof

To prove , is unique, provide an example for which is true (existence proof) and show that is the only unique example.

Constructive Proof

Gives an explicit example that proves and existence proof.

Non-Constructive Proof

Proves an example exists without actually providing it.

Mathematical Induction

Proof By Induction

To prove the statements are all true, the structure is:

Strong Mathematical Induction

Strong induction works the same as regular induction, except:

Proof By Smallest Counterexample

This is a hybrid of proving by induction and proving by contradiction. To prove are all true, the structure is:

Chapter 11

Relation

Definition: a relation , on a set is a subset .

Relation Properties

Equivalence Relation

A relation is an equivalence relation iff is reflexive, symmetric, and transitive.

Equivalence Class

Equivalence relations on divides into subsets called equivalence class. The equivalence class containing is the subset of consists of all elements of that relates to .

Theorem 11.1: Suppose is an equivalence relation on set and . Then iff

Partition

A partition of set is a set of non-empty subsets of such that the union of all subsets equals and intersection of any two subsets equals .

Theorem 11.2: Suppose is an equivalence relation on set . Then the set forms a partition of .

Integer Modulo n

The equivalence classes of the equivalence relation are , for some . Then the integer modulo n is the set .

Chapter 12

Function

Injective

A function is injective iff .

To prove a function is injective, the proof structure is (contrapositive):

Surjective

A function is surjective iff such that

To prove a function is surjective, the proof structure is (direct):

Bijective

A function bijective iff the function is both injective and surjective

Pigeonhole Principle

Suppose and are finite sets and is any function, then:

Suppose and are finite sets and , then:

Composition

Suppose , then the composition is

Theorem 12.1: If , , , then

Theorem 12.2: If and , if both and are injective, then is injective

Inverse Function

For a bijective , its inverse is the function .

Composition with inverse yields identity function:

Identity Function

Theorem 12.3: Function is bijective iff the reverse relation is a function

Image & Preimage

Suppose :

Chapter 13

Useful Definitions and Facts

Parity & Multiplicity

Well-Ordering Principle

Division Algorithm

Fundamental Theorem of Arithmetic

Greatest Common Divisor & Least Common Multiple

Given ,

Proposition 7.1

If , then there exists integers and for which

Proposition 10.1

Suppose there are integers . If a prime number divides , then divides at least one of the integers .

Congruence

Assuming and for , then:

Pigeonhole Principle

see above

Image & Preimage

Theorem 12.4: Suppose and