empty set
the set with no elements.
subset
A set X is a subset of a set Y if and only if every element in X is also an element in Y.
free variables
Something in a sentence which can take on multiple possible values.
predicate
A sentence containing free variables which becomes a statement when the free variables are specified.
quantifier
For all" or "there exists".
quantification
The process of using quantifiers to make a statement out of a predicate.
universal quantifier
For all
existential quantifier
There exists
bound variables
The variables in a statement with quantifiers.
implication
A statement of the form "if P, then Q''. It is false only when P is true and Q is false.
hypothesis
In an implication "if P, then Q", the statement P is the hypothesis.
contrapositive
The contrapositive of an implication "A implies B" is the statement "Not B implies Not A".
converse
The converse of an implication "A implies B" is the statement "B implies A".
conjunction
The conjunction of two statements is the statement which is true precisely when both of the statements being conjoined are true.
disjunction
The disjunction of two statements is the statement which is true when at least one of the statements being disjoined is true.
direct proof
When an implication is proved by assuming that the hypothesis is true and then showing that the conclusion is also.
proof by contraposition
Proving an implication by doing a direct proof of its contrapositive.
proof by contradiction
Proving a statement by assuming that the statement is false and then deriving a contradiction.
complement
The complement of a set A in a set U is the set of all elements of U that are not elements of A.
intersection
The intersection of a family of sets is the set of elements which are elements of every one of the sets in the family.
union
The union of a family of sets is the set of elements which are elements of at least one of the sets in the family.
Power set
the power set of a set X is the set of all subsets of X
equality of ordered pair
two ordered pairs (a,b) and (c,d) are equal if and only if a=c and b=d
cartesian product
the cartesian product of sets X and Y is the set of all ordered pairs (x,y) where x is an element of X and y is an element of Y
Partition
a partition P of a set X is a subset of the power set of X such that each element of P is non-empty, distinct elements of P are disjoint, and every element of X is also an element of some element of P
Relation
a relation R on a set X is a subset of XxX. if (a,b) is an element of R, we write aRb.
Reflexive Relation
a relation in which, for all x in X, x~x
Symmetric Relation
a relation in which, for all x, y in X, if x~y, then y~x.
Transitive relation
a relation in which, for all x,y,z in X, if x~y and y~z, then x~z.
equivalence relation
a relation on a set X which is reflexive, symmetric, and transitive
equivalence class
If A is a set and ~ is an equivalence relation on A, for each x that is an element of A, the equivalence class of x is [x]={y in A: x~y}
quotient set
the set of all equivalence classes, when considering a particular equivalence relation on a set.
function
a function f:x->Y is an unambiguous assignment of a unique element of Y to each element of X
domain
for a function f:X->Y, the domain of f is X
range
for a function f:X->Y, the range of f equals {y in Y: there exists x in X such that y=f(x)}.
equality of functions
two functions f:X->Y and g:A->B are equal if and only if A=x, B=Y, and f(x)=g(x) for all x in X.
restricting the domain of a function
Suppose f:X->Y is a function and A is a subset of X and B is a subset of Y such that range(f) is a subset of B. Then, the restriction of f to A is the function f|A: A->Y defined by f|A(a)=f(a) for all a in A
restricting the codomain of a function
Suppose f:X->Y is a function and A is a subset of X and B is a subset of Y such that range(f) is a subset of B. Then, the function f:X->B is obtained from f:X->Y by restricting the codomain to B.
composition of functions
suppose f:X->Y and g:Y->Z are functions. Then the composition of f and g, gof:X->Z, is defined, for all x in X, by gof(x)=g(f(x)).
sequence
an infinite sequence in X is a function from the set of natural numbers to X. A finite sequence in X is a function from {1,2,...,n} to X for some natural number n
surjective function
a function f:x->Y is surjective if for every element y of Y there exists an element x of X such that y=f(x)
injective function
a function f:X->Y is injective if f(a)=f(b) implies a=b for all elements a,b of X. (there is only one y in Y for each x in X)
bijective function
a function is bijective if it is injective and surjective
inverse function
Suppose that f:X->Y and g:Y->X are functions. They are inverses of each other if
for all x in X, gof(x)=x and
for all y in Y, fog(y)=y.
(f and g are inverses if fog=idY and gof=idX)
Sets X and Y have the same cardinality
there is a bijection between X and Y
The cardinality of X is less than or equal to the cardinality of Y
There is an injection from X to Y
Countable set
a set is countable if it is finite or if it has the same cardinality as the set of natural numbers
Subsequence of a sequence
Suppose that (sn) is a sequence in a set X and that (nk) is a strictly increasing sequence in N*. Then the sequence (snk) is a subsequence of (sn).