Math 3200 - FINAL DEFINITIONS

Statement

A declarative sentence that is true or false (not both).

Compound Statements

A statement built out of simpler statements, using ∧, ∨, ⇒, ~.

Logically Equivalent Statements

Statements that always have the same truth value, no matter what the truth values of the initial components are.

Implication

A statement of the form P ⇒ Q

Q ⇒ P

Converse of an implication

~P ⇒ ~Q

Inverse of an implication

~Q ⇒ ~P

Contrapositive of an implication

Direct Proof

Proof technique to show P ⇒ Q: Assume P is true, conclude that Q is true.

Proof by Contrapositive

Proof technique to show P ⇒ Q: Assume ~Q, conclude ~P

Proof by Contradiction

Proof technique to show P ⇒ Q: Rule out that P is true & Q is false: reach an absurdity

Even integer

An integer that can be written as n=2k for some integer k.

Odd integer

An integer that can be written as n=2k+1 for some integer k.

Parity Proof

A proof dealing with even or odd integers

A divides B

A | B if and only if there exists an integer k such that b = a * k

Induction

Let P(1), P(2), P(3), … be an infinite list of statements. Suppose that:
1. P(1) is true.
2. For each natural number n, if P(n) is true, then so is P(n+1).
Then P(n) is true for every natural number n.

Complete Induction

Complete Induction

Let P(1), P(2), P(3), … be an infinite list of statements. Suppose that:
1. P(1) is true.
2. For each natural number n, if all of P(1), P(2), …, P(n) are true, then so is P(n+1).
Then P(n) is true for every natural number n.

set containment (A ⊆ B)

A set A is a subset of a set B if every element of A is also an element of B, denoted as A⊆B.

set equality (A = B)

Two sets A and B are equal if they contain exactly the same elements, i.e., A=B if A⊆B and B⊆A.

the empty set ∅

The empty set is the set that contains no elements, denoted by ∅.

A∪B

The set of elements that are in either A or B or in both.

A∩B

The set of elements that are in both A and B.

A\B

The set of elements that are in A but not in B.

Commutative Property

For union and intersection, A∪B=B∪A and A∩B=B∩A

Associative Property

For union and intersection, (A∪B)∪C=A∪(B∪C) and (A∩B)∩C=A∩(B∩C).

Distributive Property

For sets, A∩(B∪C)=(A∩B)∪(A∩C) and A∪(B∩C)=(A∪B)∩(A∪C).

de Morgan’s laws

(A∪B)^c=A^c∩B^c and (A∩B)^c=A^c∪B^c, where c denotes the complement.

set product A × B

The Cartesian product of two sets A and B is the set of all ordered pairs (a,b) where a∈A and b∈B, denoted by A × B.

the power set P(S)

The power set of a set S is the set of all subsets of S, denoted by P(S).

Union ∪_i∈I A_i, where I is an index set

The set of elements that belong to at least one of the sets Ai​, where i ranges over the index set I.

Intersection ∩_i∈I A_i, where I is an index set

The set of elements that belong to all sets Ai​, where i ranges over the index set I.

relation on sets S and T

A relation from set S to set T is a subset of the Cartesian product S×T, i.e., a set of ordered pairs (s,t) where s∈S and t∈T.

relation on a set S

A relation on a set S is a subset of S×S, i.e., a set of ordered pairs (s₁​,s₂​) where both s₁​ and s_2​ are elements of S.

domain of a relation

The set of all first elements (or inputs) of the ordered pairs in a relation.

range of a relation

The set of all second elements (or outputs) of the ordered pairs in a relation.

reflexive

A relation R on a set S is reflexive if for every element a∈S, (a,a)∈R. Alternatively: xRx.

symmetric

A relation R on a set S is symmetric if for every pair (a,b)∈R, (b,a)∈R. Alternatively, if xRy, then yRx.

transitive

A relation R on a set S is transitive if whenever (a,b)∈R and (b,c)∈R, then (a,c)∈R. Alternatively, if xRy and yRz, then xRz.

equivalence relation

A relation R on a set S is an equivalence relation if it is reflexive, symmetric, and transitive.

equivalence class [x]

The equivalence class of an element x in a set S under an equivalence relation R is the set of all elements in S that are related to x, denoted by [x]={y∈S:(x,y)∈R}.

natural numbers

Numbers used for counting: 1, 2, 3, 4

Integers

All whole numbers and their negative counterparts: -2, -1, 0, 1, 2

rational numbers

Any number that can be expressed as a fraction: 1/2, .5, -3/4

real numbers

All numbers that can be found on the number line, rational or irrational: 7, -1.2, sqrt(55), e

function f: X → Y

A relation from S to T where every input has a single output, no more no less.

domain of a function

The set of all first elements (or inputs) of the ordered pairs in a function.

range of a function

The set of all second elements (or outputs) that have a corresponding input.

codomain

Every output in a function, even those with no corresponding input.

Image of A “f(A)”

If A ⊆ S, the set of all outputs f(a) that could come from the inputs A. {f(a): a∈A}

Preimage of B “f^-1(B)”

If B ⊆ T, the set of all inputs s that could have given the inputs B. {s∈S: f(s)∈B}

one-to-one function (injective function)

A function where for all x,x’ ∈ X, if f(x) = f(x’), x = x’. Equivalently, every y∈Y has at most one arrow pointing to it.

onto function (surjective function)

A function where for every y∈Y, there is an x∈X with f(x) = y. Equivalently, every element of Y has at least one arrow pointing to it.

bijection

A function that is both one-to-one and onto.

the composite function g ◦ f

If f: A → B and g: B → C, then a → C is given by (g ◦ f)(x) = g(f(x)) for all x∈A

left inverse function

(g ◦ f)(x) = x for all x∈X

right inverse function

(f ◦ g)(y) = y for all y∈Y

inverse function

When g is both a left and right inverse of f. (g ◦ f)(x) = x and (f ◦ g)(y) = y