MATH 220
# Final Review

Updated 2017-12-17

- Denoted by
- Element in the set:
- Subset:

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

Suppose sets

If or then

If and then

If and then

If then

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

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

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

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

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

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

- is an even number.

**Implication**:

**Converse**:

**Contrapositive**:

**Negation**:

Also referred to as “if and only if”

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

- (this would make the statement false)
- (this would make the statement true)

To prove , the structure is:

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

To prove , the structure is:

To prove , the structure is:

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

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

Gives an explicit example that proves and existence proof.

Proves an example exists without actually providing it.

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

Strong induction works the same as regular induction, except:

- instead of assuming is true, we assume all to be true.

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

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

- Relation is
**reflexive**iff - Relation is
**symmetric**iff - Relation is
**transitive**iff

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

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 .

- Denoted as
- Where
- If there exists , there is still only one equivalence class.

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

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 apartitionof .

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

- Property 1:
- Property 2:

- A
**function**is denoted as , where is the domain and is the codomain - The
**range**of function is the set - Two functions and are the same iff

A function is **injective** iff .

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

A function is **surjective** iff such that

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

A function **bijective** iff the function is both *injective* and *surjective*

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

- If then is not injective
- If then is not surjective

Suppose and are finite sets and , then:

- If then a surjective
- If then an injective
- If then a bijective

Suppose , then the **composition** is

Theorem 12.1: If , , , then

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

For a bijective , its **inverse** is the function .

Composition with inverse yields *identity function*:

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

Suppose :

- If , the
**image**of is the set - If , the
**preimage**of is the set

…

- An integer is
**even**iff if for some - An integer is
**odd**iff for some - Integers and have the
**same parity**if and are both even or odd. - An integer is a
**multiple of**an integer iff for some - A positive integer is a
**prime number**iff has exactly two positive divisors, namely and .

- Given a subset , and , then there is an element such that is the smallest element in
- Given an integer , any non-empty subset is
**well-ordered**

- Given integers and , there exists integer and for which and

- Every integer greater than 1 is either a prime number itself or is the product of prime numbers

Given ,

- The
**GCD**of and is the largest integer that divides both and - The
**LCM**of and is the smallest integer that is a multiple of both and

If , then there exists integers and for which

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

- Given , is congruent to , denoted by , iff

Assuming and for , then:

- If and then

*see above*

Theorem 12.4: Suppose and