Vocab Flashcards
set
A collection of things called elements or members.
irrational numbers
A number that cannot be written in the form m/n with m and n both integers.
rational numbers
Numbers, which are ratios of integers with nonzero denominators. Rational numbers have decimal expansions which terminate or repeat.
integers
The set of natural numbers, their negatives, and zero.
natural numbers
All positive whole numbers excluding zero.
complex numbers
Numbers, which have the form a+bi.
Sets A and B are equal
A = B, if and only if A and B contain the same elements or neither set contains any element.
subset
Set A is a subset of set B, if and only if every element of A is an element of B.
power set
P(A), is the set of all subsets of A: P(A) = {B | B subset A}
union of sets A and B
A U B, is the set of elements in A or in B (or in both).
intersection of A and B
A ∩ B, is the set of elements that belong to both A and B.
set difference of sets A and B
A \ B, is the set of elements of A that are not in B.
symmetric difference of sets A and B
A ⨁ B, is the set of elements in A or in B, but not in both.
Cartesian product of A and B
The set A x B = {(a,b) | a∈A,b∈B}
binary relation from A to B
1) Is a set
2) A x B = {(a,b) | a∈A,b∈B}
3) is a subset of A x B
binary relation on A (from A to A)
1) Is a set
2) A x A = {(a,b) | a∈A, b∈A}
3) is a subset of A x A
reflexive relation
Given R on set A: If (a,a)∈R for ALL a∈A,then the relation is reflexive.
symmetric relation
If (a,b) ∈ R, then (b,a) ∈ R.
antisymmetric relation
If (a,b) ∈ R and (b,a) ∈ R, then a = b.
transitive relation
A binary relation R on a set A is transitive if and only if a, b, c ∈ A, and both (a,b) and (b,c) ∈ R, then (a,c) ∈ R.
equivalence relation on set A
A binary relation R on A that is reflexive, symmetric, and transitive. You must prove:
1) a ~ a for all a ∈ A,
2) if a ∈ A, and b ∈ A, and a ~ b, then b ~ a, and
3) if a, b, c ∈ A, and both a ~ b and b ~ c, then a ~ c.
equivalence class
The group into which an equivalence relation divides the underlying set. The equivalence class of an element is the collection of all things related to it.
The equivalence class of element a ∈ A is the set a ̅ = {x ∈ A | x ~ a}.quotient set of A mod ~
Denoted A/~, it is the set of all equivalence classes.
x ~ a or a~x?
An equivalence relation is symmetric, so it doesn’t matter. The set of things related to a is the same as the set of things to which a is related.
Set A and set B are disjoint
A⋂B=∅
equivalence relations
Equivalence classes of any equivalence relation divide A into disjoint (that is, non overlapping) subsets that cover the entire set, just like the pieces of a jigsaw puzzle. We say that the equivalence classes “partition” A or “form a partition of” A.
partition of set A
A collection of disjoint nonempty subsets of A whose union is A.
cells
Also blocks, are the disjoint sets of a partition. The cells are said to partition A.
partial order
(≤) - A binary relation on real numbers that possesses the properties of:
reflexivity - a ≤ a for all a ∈ A.
antisymmetry - If a, b ∈ A, a≤b and b≤a, then a=b, and
transitivity - If a, b, c ∈ A, a≤b and b≤c, then a≤c.
partial order set
poset - for short, is a pair (A, ≤) where ≺ is a partial order on the set A.
total order
When ≤ is a partial order on a set A and every two elements of A are comparable.
totally ordered set
The pair (A, ≤) in a total order.
maximum poset element
The element a of poset (A, ≤), iff b≤a for every b ∈ A.
minimum poset element
The element a of poset (A, ≤), iff a≤b for every b ∈ A.
maximal poset element
The element a of poset (A, ≤), iff, if b ∈ A and a≤b, then b=a.
minimal poset element
The element a of poset (A, ≤), iff, if b ∈ A and b≤a, then b=a.
greatest lower bound(∧)
glb - (A, ≤) is a poset, the element g iff a,b,g ∈ (A, ≤), and
1 - g≤a, g≤b, and
2 - if c≤a, and c≤b for some c ∈ A, then c≤g.
least upper bound (⋁)
lub - (A, ≤) is a poset, the element t iff a,b,t ∈ (A, ≤), and
1 - a≤t, b≤t, and
2 - if a≤c, and b≤c for some c ∈ A, then t≤c.
lattice
A poset (A, ≤) in which every two elements have a greatest lower bound in A and a least upper bound in A.
sequence
A function whose domain is some infinite set of integers (often N) and whose range is a set of real numbers.
terms of the sequence
Then numbers in the list, the range of the function.
recurrence relation
A relation which defines one member of the sequence in terms of a previous one.
arithmetic sequence
With first term a and common difference d, is the sequence defined by:
a_1 = a,
and for k≥1,
a_(k+1) = ra_k
geometric sequence
A sequence of numbers in which each term is determined by multiplying the previous term by a fixed number.
With the first term a and common ratio r, it is the sequence defined by
a_1 = a,
and for k≥1,
a_(k+1) = a_k + d
common ratio
The fixed number that each term in a geometric sequence is multiplied by to get the next term in the sequence.
generating function
A polynomial that “goes on forever,” that is, and expression of the form:
f(x)=a_0 + a_1 x + a_2 x^2 + a_n x^n + ⋯
The union |A∪B| =
|A| + |B| - |A∩B|
The intersection |A∩B|≤min{|A|,|B|}
the minimum of |A| and |B|
Only A |A \ B|
= |A| - |A∩B| ≥ |A| - |B|
Not A |A^C |
= |U| - |A|
A + B but not A&B |A⨁B|
=|A∪B| - |A∩B| = |A| + |B| - 2|A∩B| = |A\B|+|B\A|
AxB |AxB|
= |A| x |B|
mutually exclusive
The two events can not happen at the same time.
n!
Denotes the product of all the natural numbers from 1 to n (inclusive).
n! = n(n-1)(n-2) … (3)(2)(1)
P(n,r)
Denotes that product of the first r factors of n!
P(n,r) = (n(n-1)(n-2) … (n-r+1))/(n-r)!
permutation of a set
of distinct symbols is an arrangement of them in a line in some order.
binomial coefficient
n
r
= n!/(r!(n-r)!
combination of a set
of objects is a subset of them. A subset of r objects is called an r-combination or a combination of objects taken r at a time.
The distinction between permutation and combination
is the distinction between order and selection. A permutation takes order into account; a combination involves only selection.
