Basic Notations

We assume that you are familiar with the concepts represented by the following

symbols.

{XQ, x±,... , xn} — the set containing Xo, x\,... ,xn and no other elements;

0 — the empty set;

G — the membership relation;

C — subset;

C — proper subset;

3, V, -i, A, V, —•, - — quantifiers and logical connectives. Although Chapter 5 con-

tains a thorough discussion of these symbols in the context of formal languages,

you should already be at ease with their use.

xUy = {z : z G x\J z € y} — the union of two sets;

xC\y = {z : z £ x Az e y} — the intersection of two sets;

x\y = {z : z e x Az £ y} — the difference of two sets;

xAy = (x\y) U (y\x) = (xUy)\(xf)y) — the symmetric difference of two sets;

(J X = {z : 3Y G X [z G Y)} — union of a family of sets;

P| X = {z : VY G X (z G Y)} — intersection of a family of sets;

f : X —Y — function from X into Y\

f[W] = {yeY: 3xeW f(x) = y} — image of W under / ;

f~lZ = {x G X : f(x) G Z} — inverse image of Z under / ;

dom(f) — domain of a function /;

rn9(f) — range of a function /;

f\W — restriction of a function / to a subset W of its domain;

fog — composition of two functions;

(an : n G N) = (an)ne^ — sequence indexed by natural numbers;

N = {0,1,2,... } — the set of natural numbers;

Z — the set of integers;

Q — the set of rationals;

R — the set of reals;

P = R\Q — the set of irrationals;

C — the set of complex numbers.

A — the set of algebraic numbers

Note that we impose no restrictions on the style of letters that represent sets.

Each of the symbols x,X,X,X may stand for a set.

XVll