descriptive set theory, logical, axioms, logic, what is logic
Back to title page.
What is logic? Is logic absolute (i.e. unique, predestined) or relative (i.e. there are many kinds of logic)? The absolutist position is somewhat inconvenient - you must defend your concept of logic against heretics and dissidents.
So let us better adopt the relativist position, and define logic(s) as any common framework for building theories. For example, we can view a theory as a logic for all its extensions. The so-called absolute geometry can be viewed as a common logic for both the Euclidean and non-Euclidean geometry. Group theory serves as a common logic for theories investigating mathematical structures that are subtypes of groups. And if you decide to rebuild all your mathematical theories on set theory, then you can view set theory as your logic.
Can there be a common logic for the entire mathematics? To avoid the absolutist approach let us appreciate all the existing concepts of mathematics - classical (traditional), intuitionistic (constructivist), New Foundations etc. Of course, enthusiasts of each of these concepts must propose some specific common framework for building mathematical theories, i.e. some specific kind of logic. And they do.
Can set theory (for example, ZFC) be viewed as a common logic for the classical (traditional) mathematics? You can think so, if you do not wish (but I do!) to distinguish between the first order notion of natural numbers (i.e. discrete mathematics) and the second order notion (i.e. "continuous" mathematics based on set theory or a subset of it). Or, if you do not wish (but I do!) to investigate in parallel the classical and the intuitionist (constructivist) versions of some theories.
To retain all these possibilities, let us adopt the traditional approach used in other textbooks on mathematical logic - the notion of the so-called first order theories.
Note. Sometimes, "second order" logic is proposed as a possible escape from the restrictions and anomalies of the first order logic. Still, my restricted mind does not allow to adopt any "second order" notions without a subset of (first order!) set theory behind them.
First order languages
The vision behind the notion of first order languages is centered on the so-called "domain" - a collection of "objects" that you wish to "describe" by using the language. Thus, the first kind of language elements you will need are variables:
x, y, z, x1, y1, z1, ...
The above-mentioned "domain" is the intended "range" of all these variables. For example, when building the language of first order arithmetic (PA), we are thinking about all natural numbers as the range of variables. Or, when building the language of set theory (ZF), we think about "all sets" as the range of variables.
Note. Maybe, you have to describe two or more kinds of "objects" that cannot be reduced to "sub-kinds" of one kind of "objects". Then you will need to build a kind of the so-called many sorted first order languages.
Warning! Do not try to use many sorted logic to separate "objects" and "object properties" (i.e. sets of "objects"), i.e. do not try to build a second order language. You should better use your favorite (first order, single sorted!) set theory instead.
The next possibility we could wish to have in our language are the so-called constant letters - symbols denoting some specific "objects" of our "domain". For example, when building the language of PA, we introduced two letters - 0 and 1 to denote "zero" and "one" - two natural numbers having specific properties. When building the language of ZF, we did not introduce a constant letter denoting the empty set, showing how to do without it.
In some languages we may need also the so-called function letters - symbols denoting specific functions, i.e. mappings between "objects" of our "domain". For example, when building the language of PA, we introduced two letters - + and * to denote addition and multiplication of natural numbers, i.e. the two argument functions x+y and x*y. When building the language of ZF, we did not introduce function letters, showing how to do without them.
Normally, we are writing f(x, y) to denote the value of the function f for the argument values x, y. This is a uniform way suitable for functions having any number of arguments: f(x), g(x, y), h(x, y, z) etc. In our everyday mathematical practice some of two argument functions are represented by using the more compact "infix" notation (x+y instead of the uniform +(x, y), etc.).
The last kind of primitives we need in our language are the so-called predicate letters - symbols denoting specific properties (of) or relations between "objects" of our "domain". It may seem strange to non-mathematicians, yet the most popular relation of objects used in all mathematical theories, is equality (or identity). Still, this is not strange for mathematicians. We can select an object x in our "domain" by using a very specific combination of properties and relations of it, and then - select another object y - by using a different combination. And after this (sometimes it may take many years to do) we prove that x=y, i.e. that these two different combinations of properties and relations are possessed by a single object. Many of discoveries in mathematics can be reduced to this form.
Some of theories are using equality "=" as the only predicate letter. Then other predicates must be reduced to equality as, for example, the relation x<y for natural numbers can be reduced to equality by using the addition letter and the formula Ez(x+z+1=y). Of course, if a theory does not have function letters (as, for example, set theory ZF), then it must contain additional predicate letters (the language of ZF contains a specific letter "in" denoting the membership relation).
The uniform way of representing suitable for predicates having any number of arguments is again the "prefix" notation: p(x), q(x, y), r(x, y, z) etc. In the real mathematical practice some of two argument predicates are represented by using the more compact "infix" notation (x=y instead of the uniform =(x, y), etc.).
Thus, the specification of a first order language includes the following primitives:
1) A countable set of variable names (you can generate these names, for example, by using a single letter "x": x, xx, xxx, xxxx, ...).
2) An empty, finite, or countable set of constant letters.
3) An empty or finite set of function letters. To each function letter a fixed argument number must be assigned.
4) A finite set of predicate letters, the equality letter "=". To each predicate letter a fixed argument number must be assigned (for the equality letter this number must always be "two").
Different sets of primitives yield different first order languages.
By using the language primitives, we can build terms, atomic formulas and (compound) formulas.
Terms are expressions denoting "objects" and functions:
a) Variables names and constant letters (if any), are terms.
b) If f is a k-argument function letter, and t1, ..., tk are terms, then the string f(t1, ..., tk) is a term.
c) (If you like so,) there are no other terms.
If a term does not contain variable names, then it "denotes" an "object" of our "domain" (for example, (1+1)+1 denotes a specific natural number). If a term contains variables, then it denotes a function (for example, ((x*x)+(y*y))+1 denotes the function x2+y2+1).
If the language does not contain constant letters and function letters (as, for example, the language of the set theory ZF), then variable names are the only kind of terms.
Atomic formulas (or elementary formulas) are defined as follows:
a) If p is a k-argument predicate letter, and t1, ..., tk are terms, then the string p(t1, ..., tk) is an atomic formula.
b) (If you like so,) there are no other atomic formulas.
For the equality letter the "infix" notation is used: if t1, t2 are terms, then (t1=t2) (or, if you like it better, (t1)=(t2)) is an atomic formula.
To build compound formulas, we need a fixed set of logical connectives and quantifiers. For example, I like most the following set of them:
-> (implication letter, B->C means "if B, then C", or "B implies C").
& (conjuction letter, B&C means "B and C").
v (disjunction letter, BvC means "B, or C, or both", i.e. the so-called non-exclusive "or").
~ (negation letter, ~B means "not B").
A (the universal quantifier, AxB means "for all x: B").
E (the existential quantifier, ExB means "there is x such that B").
The widely used equivalence connective <-> can be derived in the following way: B<->C stands for (B->C)&(C->B). If you like using the so-called exclusive "or", you can define (B xor C) as ~(B<->C).
Now we can define the notion of formula of our language as follows:
a) Atomic formulas are formulas.
b) If B and C are formulas, then (B->C), (B&C), (BvC), and ~B also are formulas.
c) If B is a formula, and x is a variable name, then Ax(B) and Ex(B) also are formulas.
d) (If you like so,) there are no other formulas.
In the so-called closed formulas all variables are bound by quantifiers, for example:
Ax((x=0)v~(x=0)).
Such formulas represent "absolutely definite assertions", i.e. they are expected to be (but not always really are) either "true" or "false". Non-closed formulas contain free variables, i.e. variables that are not bound by quantifiers, for example: (x=0)v(x=1). "Truth values" of such formulas may depend from the values assigned to free variables. For example, the latter formula is "true" for x=1, yet it is "false" for x=2.
Now, for a fixed first order language L, we will formulate a list of logical axioms and inference rules that allows formalization of any "pure logical" chains of reasoning, i.e. allows to prove any "logically valid" formula of the language L (see Appendix 1 for details).
Most of our axioms will be represented by means of the so-called axiom schemas. Each schema represents an infinite, yet easily recognizable collection of single axioms (see, for example, the schema L1).
In the schemas L1-L11 below, B, C and D are any formulas. These schemas represent the so-called propositional calculus in the language L.
We will not specify properties of the equivalence connective in axioms. This connective is only a derived one: B<->C is used as a shorthand of (B->C)&(C->B).
Axioms
"Definition" of the implication connective:
L1: B->(C->B),
L2: (B->(C->D))->((B->C)->(B->D)),
"Definition" of the AND-connective:
L3: B->(C->B&C),
L4: B&C->B,
L5: B&C->C,
"Definition" of the OR-connective:
L6: B->BvC,
L7: C->BvC,
L8: (B->D)->((C->D)->(BvC->D)),
Proof by deriving a contradiction:
L9: (B->C)->((B->~C)->~B),
Contradiction implies anything:
L10: ~B->(B->C),
Law of the excluded middle:
L11: Bv~B
In the schemas L12-L13, F is any formula, and t is any term that does not contain variables bound by quantifiers in F.
L12: AxF(x)->F(t),
L13: F(t)->ExF(x),
Common properties of the equality predicate:
L14: x=x,
L15: x=y -> y=x,
L16: x=y -> (y=z -> x=z),
L17: x=t -> (F(x, x)->F(x, t)).
In schema L17, F is any formula, and t is any term that does not contain variables bound by quantifiers in F. The designation F(x, x) means that the occurences of the variable x are split into two groups. In F(x, t), the occurences of the second group have been replaced by the term t.
In the following rules of inference, B, C and F are any formulas, and G is any formula that does not contain x as a free variable.
Rules of inference
Modus Ponens: B, B->C |-- C
Generalization: G->F(x) |-- G->AxF(x),
Existence: F(x)->G |-- ExF(x)->G.
This list of logical axioms and rules of inference represents the so-called predicate calculus with equality in the first order language L (I would call it simply - the classical logic in the language L).
Some of the above axioms seem to be (at least partly) problematic.
For example, how do you find the funny axiom L10: ~B->(B->C) - if ~B and B were true simultaneously, then anything were true? Is it a really "true" axiom? Of course, it is not. Still, this does not matter: we do not need to know, were C "true" or not, if ~B and B were "true" simultaneously. By admiting that "if ~B and B were true simultaneously, then anything were true" we greatly simplify our logical apparatus. For example, to prove that some theory T is consistent (i.e. that T does not allow proving of B and ~B simultaneously), we must "simply" prove that T does not allow proving of 0=1.
The second problem is caused by L11: Bv~B - the Law of the Excluded Middle. How can we think of L11 as a "true" axiom, if (according to Goedel's incompleteness theorem) each sufficiently strong consistent theory contains undecidable propositions? I.e. we postulate that B or ~B "must be true", yet for some B we cannot prove neither B, nor ~B! Can we retain L11 as an axiom after this?
For these (and some other) reasons some people reject L11 (or even both - L10 and L11) as logical axioms. By excluding L11 from the above list the so-called intuitionistic (or constructivist) logic is obtained. By excluding both L10 and L11 the so-called minimal logic is obtained. The above list as it stands is called the classical logic.
All really working formal mathematical theories are formulated as the so-called first order theories.
Each first order theory T includes:
a) a specific first order language L(T),
b) logical axioms and rules of inference for this language (the classical, constructivist or minimal version may be adopted),
c) a set of specific non-logical axioms of T.
See Sections 2.3 and 3.1 for examples of really working first order theories.
A very useful logical principle is represented by the so-called
Deduction Theorem. If T, B |-- C, then T |-- B->C. More precisely: assume that by using some hypothesis B and the axioms of the theory T we have proved the formula C, and in this proof the second and the third rule of inference is never applied to free variables of the hypothesis B. Then we can prove B->C by using only the axioms of T.
Exercise A.3.1 (for smart students). Prove the Deduction theorem. Hint: use induction by the number of formulas in the proof T, B |-- C, and pay your attention only to axioms L1, L2.
Exercise A.3.2. Use Deduction theorem to derive L15, L16 from the other axioms.
Warning! Do not take the contents of this Appendix too seriously, it is not verified yet.
If you think that trying of "experimental" axioms of set theory (constructibility, determinateness, inaccessible cardinals etc.) is a business not serious enough for a true mathematician, you may follow prominent personalities like as H.Lebesgue, E.Borel, R.Baire, P.S.Aleksandrov, N.N.Luzin and many others. Instead of quick postulating new axioms that would allow solving of unsolvable problems (for example, the continuum problem), these people prefer working in the classical set theory (i.e. ZFC). If the axioms of ZFC do not allow proving the continuum hypothesis, a true mathematician should not search for additional axioms. Instead, he should ask: if I cannot prove the continuum hypothesis, i.e. that there are no infinite sets of real numbers with cardinality between (the countable) aleph0 and the cardinality of the entire continuum, then, perhaps, I can prove that there are no "simple" or "definable" sets of this kind?
A similar question: if the axiom of choice allows to "prove" the existence of choice functions that cannot be defined by using formulas, then where is the limit of complexity under which all sets allow "definable" choice functions?
Or, if the axiom of choice allows "building" of non-measurable sets of points, then where is the limit of complexity under which all sets are Lebesgue measurable? I.e. how complicated is the "simplest" non-measurable set?
The axiom of choice allows to "build" well ordering of the set of all real numbers (a "counter-natural" result!). How complicated must be the "simplest" of such well orderings? "Normally", only countable sets of real numbers could have a "natural" well ordering. I.e. if some infinite set of real numbers allows a "definable" well ordering, then this set "must be" countable?
The axiom of choice allows "building" of non-determined sets. How complicated is the "simplest" non-determined set?
Etc.
From this kind of questions the so-called descriptive set theory is starting. The approach was first proposed by H.Lebesgue in 1905:
H.Lebesgue. Sur le fonctions representable analytiquement. "J. de Math.", 1905, pp.139-216
Of course, it was inspired by his critique of the axiom of choice.
In the descriptive set theory the meaning of "simple", "definable" sets (of real numbers) is defined explicitly by introducing the so-called Borel sets and projective sets.
Note. In textbooks and papers about descriptive set theory, traditionally, instead of the real number system R, the so-called Baire space I is considered - the set of all functions from natural numbers into natural numbers. Baire space is homeomorphic to the set of all irrational numbers (not to R as a whole!), and it allows more convenient treatment of "descriptive" sets - mainly, because of the following feature: spaces IxI, IxIxI etc. all are (100%) homeomorphic to I, i.e. you need not to treat one-dimensional, two-dimensional, three-dimensional sets etc. separately. See the chapter "Descriptive set theory" in Barwise [1977].
Borel sets
The simplest kind of sets of real numbers is interval:
(b, c) = { x | x in R & b<x<c },
where b, c are real numbers, b<c.
The next kind of simple sets of real numbers are the so-called open sets, i.e. sets S such that: for all x, if x in S, then also some interval (b, c) around x belongs entirely to S.
Exercise A.4.1. Verify that each open set is a countable union of intervals. Do you need a kind of axiom of choice for this proof?
Complements of open sets are called closed sets, i.e. if S is open set, then R-S is a closed set.
Exercise A.4.2. Verify that each closed set S is "closed" in the following sense: if x is a real number, and every (i.e. arbitrary small) interval around x contains members of S, then x also is a member of S.
By combining the above two operations (countable union and complement) arbitrarily we obtain the so-called Borel sets (named after E. Borel). More precisely, the collection of Borel sets is the least collection B of sets such that:
a) Each interval of real numbers is a member of B.
b) If S in B, then R-S in B.
c) If for all natural numbers i: Si in B, then U{Si | i in N } also is a member of B.
In descriptive set theory the collection of all Borel sets is denoted by DELTA11.
Exercise A.4.3. a) Verify that DELTA11 is closed under countable intersections as well. b)Verify that DELTA11 is closed under the so-called inverse continuous images: if S is a Borel set, and f: R->R is a continuous function, then the set f-1(S) = { x | Ey(y in S & f(x)=y } also is a Borel set.
Projective sets
Another operation we will consider is the so-called (direct) continuous image. If f: R->R is a continuous function, and S is a set of real numbers, then the set
f"S = { y | Ex(x in S & f(x)=y) }
is called the a continuous image of S.
It appears that by applying an appropriate continuous image operation to a Borel set we can obtain a non-Borel set (do not try to prove thsi directly).
In the descriptive set theory the collection of all sets that can be obtained from Borel sets (i.e. from DELTA11 sets) by continuous image operations is denoted by SIGMA11.
DELTA11 is a proper subset of SIGMA11.
Exercise A.4.4. Verify that SIGMA11 is closed under finite unions, finite intersections, and inverse continuous images.
By PI11 we will denote the collection of complements of SIGMA11 sets. I.e. each PI11 set is obtained from a Borel set by applying, first, a continuous image operations, and then, by applying the complement operation.
Exercise A.4.5. Verify that PI11 is closed under finite unions, finite intersections, and inverse continuous images.
Thus, SIGMA11 sets and PI11 sets are the simplest kinds of non-Borel sets. It appears, that the intersection of SIGMA11 and PI11 is exactly DELTA11 (M.Suslin's theorem, do not try to prove directly).
As the next step, by applying continuous image operations to PI11 sets we obtain the so-called SIGMA12 sets. After this, by applying the complement operation to SIGMA12 sets we obtain the so-called PI12 sets. The intersection of SIGMA12 and PI12 is denoted by DELTA12.
SIGMA11 and PI11 are proper subsets of DELTA12, and DELTA12 is a proper subset of SIGMA12 (and of PI12).
In this way, by combining these two kinds operations arbitrarily (continuous images and complement) we obtain the so-called projective sets. More precisely, the class of projective sets is the least collection P of sets such that:
a) Each Borel set is a member of P.
b) If S in P, then R-S in P.
c) If S in P, and f: R->R is a continuous function, then f"S also is a member of B.
It appears that for each projective set S there is a natural number n such that S is a member of SIGMA1n, or PI1n, or DELTA1n.
Thus, the general picture is as follows (each set of the next row is a proper superset of each set of the previous row):
DELTA11 (Borel sets)
SIGMA11 PI11
DELTA12
SIGMA12 PI12
DELTA13
etc.
The class of projective sets is closed is closed under finite unions, finite intersections, and inverse continuous images, yet (unlike the class of Borel sets) it is not closed under countable unions and countable intersections.
Note. In a similar way we could classify subsets of RxR, RxRxR etc. Thus, speaking, for example, about SIGMA12 sets, I will mean SIGMA12 subsets of R, plus SIGMA12 subsets of RxR etc. If we would use Baire space I instead of R, we had no such problem.
Axioms of Choice
Now let us try to find the strongest "weak" form of the axiom of choice (AC) that can be proved in ZF - in the set theory that does not assume AC. To build sets in ZF you can use only comprehension axioms (see Section 2.3).
Let us recall the classical form of AC: if x is any set of non-empty sets, then there is a function f such that dom(f)=x, and for all y in x: f(y) in y. I.e. the function f allows to select exactly one member in each (non-empty) member of x.
Thus, we may view AC as a "schema" AC(x), where x is an arbitrary set. The complexity of selecting "members of members of x" depends, of course, on the complexity of the set x. The complexity of x has two dimensions:
a) the complexity of x itself,
b) the complexity of the members of x.
The complexity of selecting "members of members of x" depends on both of these dimensions. To take them both into account we can consider - instead of x - the set of pairs {(u, v) | u in x & v in u }. Thus we obtain an (equivalent) alternative form of AC - the "schema" AC'(y): let y be a set of pairs then there is a function f such that dom(f)=dom(y), and (u, f(u)) in y for each u in dom(y).
The classical AC is, of course, equivalent with Ay AC'(y). Still, the form of AC'(y) allows convenient discussing of various restricted axioms of choice. Indeed, for an arbitrary collection Q of sets of pairs we can consider the following "Q-restricted AC", or Q-AC: yf y in Q, then AC'{y}.
Exercise A.4.6. a) Let Q0 = P(wxw), i.e. let Q0 be the set of all sets of pairs of natural numbers. Prove Q0-AC in ZF.
b) Let Q1 = P(vxv), where v is a well ordered set. Prove Q1-AC in ZF.
c) (Open problem?) Let Q1 = P(vxv), and assume Q1-AC in ZF. Could you show that the set v can be well ordered?
d) Let Q2 = P(RxR). Do not try to prove Q2-AC in ZF.
Usually, the so-called countable axiom of choice (ACw) is formulated as follows: if S is a countable set of non-empty sets of real numbers, then there is a choice function for S, i.e. a function f such that f(x) in x for all x in S.
Thus ACw is Q-AC, where Q = P(wxR).
The so-called axiom of dependent choices (DC): let X be a set, and S - a subset of XxX such that for each x in X there is y in X such that (x, y) in S. Then there for each x in X is a function f: w->X such that f(o)=x, and (f(n), f(n+1)) in S for all natural numbers n.
Let us view X as the set of nodes, and S - as the set of edges of some oriented graph. Then DC says: if each node of the graph has an edge starting from it, then this graph contains an infinite (i.e. countable) path.
The so-called "countable" axiom of dependent choices (DCw) is DC with X = R: if S is a non-empty set of pairs of real numbers such that dom(S) = R, then for each real number x there is a function f: w->R such that f(0)=x, and (f(n), f(n+1)) in S for all natural numbers n.
Exercise A.4.7. Verify that:
a) In ZF, DC implies that any infinite set contains a countable subset.
b) In ZF, DCw implies ACw.
c) in ZF, P(RxR)-AC implies DCw.
Relativized forms...
(P.S.Novikov, M.Kondo, J.W.Addison) ZF proves SIGMA12-DC, and hence, SIGMA12-ACw.
(P.Cohen?) ZF cannot prove PI12-ACw.
To be continued.
…
Continuum Hypothesis
(P.S.Aleksandrov, F.Hausdorff, M.Suslin) In ZFC, an infinite SIGMA11 set is either countable, or has the cardinality of the entire continuum.
We cannot hope to extend this theorem to PI11 sets:
(P.J.Cohen?) The corresponding statement for PI11 sets is undecidable in ZFC.
A message from the "stratosphere":
(W.Sierpinski) In ZFC, an infinite SIGMA12 set is either countable, or has the cardinality aleph1, or has the cardinality of the entire continuum. (Note that in ZFC we cannot prove the equality of the latter two cardinalities.)
Lebesgue Measurability
(N.N.Luzin) In ZFC, all SIGMA11 and all PI11 sets are Lebesgue measurable.
(P.S.Novikov, K.Goedel) In ZF+V=L, there is a non-measurable DELTA12 set. Hence, ZFC cannot prove that all DELTA12 sets are Lebesgue measurable.
And (probably), we cannot hope to "build" in ZFC a non-measurable projective set (see below the first theorem by Levy-Solovay). Hence, the well known non-measurable set by G.Vitali (obtained by applying the axiom of choice) cannot be proved (in ZFC) to be a projective set!
Well-orderings of Real Numbers
(G.Vitali, W.Sierpinski) In ZFC, there are no SIGMA11 or PI11 well orderings of the set of all real numbers.
(A.Levy?) In ZFC, if some set X of real numbers admits a SIGMA11 well ordering, then X is finite or countable.
We cannot hope to extend these theorems to DELTA12 sets:
(J.W.Addison) In ZF+V=L, there is a DELTA12 well ordering of the set of all real numbers.
Two Theorems by A.Levy - R.M.Solovay
IC = "there is an inaccessible cardinal".
Probably, ZFC+IC is a consistent theory.
1. If Con(ZFC+IC), then one can add to ZFC the following axioms safely:
"Any infinite projective set is either countable or has the cardinality of the entire continuum",
"All projective sets are Lebesgue measurable",
"If some set X of real numbers admits a projective well ordering, then X is finite or countable ".
2. If Con(ZFC+IC), then one can add to ZF the following axioms safely:
DC,
CH, i.e. "any infinite set of real numbers is either countable or has the cardinality of the entire continuum",
"All sets of real numbers are Lebesgue measurable",
"If some set X of real numbers admits well ordering, then X is finite or countable ".
Determined Sets
(D.A.Martin) In ZFC, all DELTA11 sets are determined.
(author?) ZFC cannot prove that all SIGMA11 sets are determined.
The axiom of projective determinateness (PD)
PD = "all projective sets are determined"
Probably, ZFC+PD is a consistent theory.
(D.A.Martin, A.Kechris) In ZFC+PD, all projective sets are Lebesgue measurable.
(D.A.Martin, A.Kechris) In ZFC+PD, an infinite projective set is either countable, or has the cardinality of the entire continuum.
…
To be continued.
descriptive set theory, logical, axioms, logic, what is logic
Back to title page.