Definitions Flashcards
Principle of Extensionality.
Formula:
For two sets a, b we say that a=b iff:
For all x (if x in a, then x in b)
Pairset axiom;
Formula:
For any set a, b, there is a set c={a, b}. Where only a, b are in c. We call c the unordered pair of a, b.
For any sets a, b, exists a set c and for any set d (d in c iff d=a or d=b)
Power set axiom
For any set x, P(x) is a set; the power set of x.
Empty set axiom
There is a set with no members.
Axiom of subsets
Let G(x) be any well defined property and x any set, then {y in x| G(y)} is a set.
Df. Of power set
Let P(x) denote the class {y|y is a subset x}
Df. Empty set
The empty set, denoted by ø, is the unique set with no members.
Df. Big union
UZ={t|exists an x in Z(t in x}. For any set Z, there’s a class, which consists precisely of the members of members of Z.
Df. Big intersection
If Z is not empty, then the big intersection of Z={t|for all x in Z(t in x)}.
Df. Ordering relation; strict partial ordering
A relation < on a set X is a strict partial ordering if it’s irreflexive and transitive:
1. x in X -> not x < x
2. (x, y, z in X and x < y and y < z) -> x < z
Df. Lower bound
If < is a p.o. of a set X, and Y is not empty and a subset of X, then an element z in X is a lower bound for Y in X if for all y(y in Y -> z before or the same as y)
Df. Greatest lower bound; infimum
An element z in X is an infimum for Y if it’s a lower bound for Y and z’ is any lower bound for Y then z’ is before or equivalent to z.
Df. Order preserving map and order isomorphism
OPM F:(X, <) -> (Y, <‘) is an order preserving map iff for all x, z in X(x < z —> f(x) <‘ f(z))
OISO: f:(X, <) —> (Y, <‘) is order isomorphism iff for all x, z in X (x < z <—> f(x) <‘ f(z))
Df. Strict total order
< is a strict total ordering relation if it’s a partial ordering which is also connected: for all x, y(x, y in X -> (x=y or x<y or y<x))
Df. Well ordering
(A, <) is a well ordering if (a) it’s a strict total ordering and (b) any subset Y of A, Y has a least of element
Df. Ordered pair (Kuratowski)
Let x, y be sets, the ordered pair <x, y> = {{x}, {x, y}}
Df. Ordered k-tuples
We define ordered k-tuples by induction; <x, x’> has been defined if <x, x’,…xk> has been defined then <x, x’,…xk, xk+1> = <x, x’, …, xk>, xk+1>
Df. Cartesian product
Let A, B be sets, then AxB={<x,y>|x in A and y in B}; if A=B, then A squared is the CP of A
Df. Binary relation and inverse
A binary relation is a class of ordered pairs, thus R is any subset of some AxB; we define R-1 to be {<y,x>|<x,y> in R} to be the inverse of R.
Df. Domain and range of a binary relation
Dom(R) = {x| exists y<x,y> in R}
Ran(R) = {y| exists x<x,y> in R}
Df. A relation F as a function Func(F)
For all x in dom(F)(there’s a unique y with <x,y> in F)
If F is a function then F is 1-1 iff for all x, x’ (<x,y> in F and <x’, y> in F —> x=x’)
Df. Transitive sets
A set x is transitive, Trans(x), iff for all y in x(y is a subset of x) or big union x is a subset of x
Df. Successor function
Let x be a set, then S(x) is x u {x}
Df. Transitive closure
Defined by recursion; TC(x) = U{Unx|n in the natural numbers}
Df. Inductive sets
A set Y is inductive if ø in Y and for all x in Y(S(x) in Y)
Df. Formal Df of natural numbers
x is a natural number if for all Y[Y is inductive —> x in Y]
Omega is the class of natural numbers; the intersection of Y|Y is an inductive set
Df. Well ordering of omega
For m,n in omega, m<n iff m in n; m less than or equal to n iff m=n or m before in n
Df of (X, <) in WO
If it is, then the <-initial segment of Xz determined by some z in X is the set of all predecessors of z: Xz = {u in X| u<z}
Df of an ordinal
(X, in) is an ordinal iff X is transitive and setting <=in, then (X, <) is a well order of X.
Df Unique ordinal isomorphism
If (X, <) in WO then the order type of (X, <) is the unique ordinal order isomorphic to it.
Df of the class of ordinals
Let On denote the class. For alpha, beta in On, we write alpha < beta = alpha in beta.
Alpha =< beta is defined as alpha < beta or alpha = beta.
