Advanced Math Test 1

set

collection of things

elements

the things in a set

infinite set

a set with infinitely many elements

finite set

a set with a finite number of elements

set equality

two sets are equal if they have the same elements

natural numbers

denoted N. Set of positive counting numbers.

integers

denoted Z. Set of positive and negative whole numbers and zero.

real numbers.

denoted R. A set of all non-imaginary numbers.

cardinality

Size. If a set is finite, then its cardinality is the number of elements it has and is denoted |X|

empty set

slashed o. The set with no elements: {}. Its cardinality is 0.

set builder notation

used to describe big or complex sets. “The set of all things of the form… such that …” Set builder for evens: E = {2n: n epsilon Z} - read The set of all things of the form 2n such that n is an element of the set of integers.

ordered pair

a list of two things enclosed in parentheses and separated by a comma

cartesian product

denoted AxB. defined as AxB = {(a,b): a epsilon A, b epsilon B}

|A x B|

|A| * |B|

Cartesian power

Aⁿ = A x A x … x A = {(x1, x2, x3, …, xn) : x1, x2, x3, …. xn epsilon A}

subset

A is a subset of B if every element of A is also an element of B.

True or False: The empty set is a subset of all sets

True

How many subsets does a finite set with n elements have?

2ⁿ

power set.

denoted with a cursivey P. The set of all subsets.

If A is a finite set, what size is its power set?

|P(A)| = 2^|A|

union in set builder notation

{x : x epsilon A or x epsilon B}

intersection in set builder notation

{x : x epsilon A and x epsilon B}

set difference in set builder notation

{x : x epsilon A and x epsilon B}

universal set

The overarching set from which other sets are drawn.

complement

If A is a set with universal set U, then the complement of A is U-A and denoted as A with a bar on top.

indexed sets

sets given a letter and subscript for their name. Usually the sets are related in some more meaningful way.

intersection and union for indexed sets

index set

the set of possible subscripts for an indexed set

statement

a sentence or mathematical expression that is either definitely true or definitely false

open sentence

a sentence whose truth depends on the value of one or more variables

logically equivalent

resulting in the same truth values

DeMorgan’s Laws

~(P ^ Q) = (~P) v (~Q)

~(P v Q) = (~P) ^ (~Q)

quantifiers

Ɐ : universal quantifier. stands for “for all”, “for every”, or “for each”

Ǝ : existential quantifier. stands for “there exists a” or “there is a”

~(Ɐ x, P(x))

Ǝ x, ~P(x)

~(Ǝ x, P(x))

Ɐ x, ~P(x)

P → Q is true and P is true

Q must be true

P → Q is true and Q is false

P must be false

theorem

mathematical statement that is true and can be verified as true

proof

a written verification of a theorem that shows the theorem is definitely and unequivocally true

definition

an exact, unambiguous explanation of the meaning of a mathematical word or phrase

even

An integer n is even if n=2a for some integer a epsilon Z

odd

An integer n is odd if n = 2a for some integer a epsilon Z

parity

describes the eveness and oddness of integers. Integers have the same parity if they are both even or they are both odd. Integers have opposite parity otherwise.

a | b

Given integers a and b, we say that a divides b if b = ac for some integer c. Can also then say that a is a divisor of b and that b is a multiple of a.

prime

A natural number n is prime if it has exactly two positive divisors 1 and n. If it has more than two positive divisors, it is called composite.

Greatest common denominator

given integers a and b, it is the largest integer that divides both a and b

least common multiple

given non-zero integers a and b, it is the smallest natural number that is a multiple of both a and b

If a and b are integers, what can be said about their sum, product, or difference.

Also an integer.

Division Algorithm

Given integers a and b with b > 0, there exist unique integers q and r for which a = qb + r and 0 <= r < b

direct proof 

used for a proposition in the form If P, then Q. Assume P is true and work to deduce that Q is true.

contrapositive proof

used for a proposition in the form If P, then Q. Assume ~Q and deduce ~P.

congruent modulo n

given integers a and b and natural number n, we say that a and b are congruent modulo n if n|(a-b). Expressed as a ≡ b (mod n).

proof by contradiction

given P → Q, assume P is true but Q is false. Use this assumption to produce an obviously incorrect statement (a contradiction).

rational

a real number x is rational if x = a/b for some integers a and b

proving P iff Q

prove P → Q with whichever method and prove Q → P with whichever method