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, x_{1}, y_{1}, z_{1},
...

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 t_{1},
..., t_{k} are terms, then the string f(t_{1},
..., t_{k}) 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 x^{2}+y^{2}+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 t_{1},
..., t_{k} are terms, then the string p(t_{1},
..., t_{k}) 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 t_{1}, t_{2} are terms, then (t_{1}=t_{2})
(or, if you like it better, (t_{1})=(t_{2})) 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 L_{1}).

In the schemas L_{1}-L_{11} 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:

**L**_{1}: B->(C->B),

**L**_{2}:
(B->(C->D))->((B->C)->(B->D)),

"Definition" of the AND-connective:

**L**_{3}: B->(C->B&C),

**L**_{4}: B&C->B,

**L**_{5}: B&C->C,

"Definition" of the OR-connective:

**L**_{6}: B->BvC,

**L**_{7}: C->BvC,

**L**_{8}:
(B->D)->((C->D)->(BvC->D)),

Proof by deriving a contradiction:

**L**_{9}:
(B->C)->((B->~C)->~B),

Contradiction implies anything:

**L**_{10}: ~B->(B->C),

Law of the excluded middle:

**L**_{11}: Bv~B

In the schemas L_{12}-L_{13}, F is any
formula, and t is any term that does not contain variables bound
by quantifiers in F.

**L**_{12}: AxF(x)->F(t),

**L**_{13}: F(t)->ExF(x),

Common properties of the equality predicate:

**L**_{14}: x=x,

**L**_{15}: x=y -> y=x,

**L**_{16}: x=y -> (y=z -> x=z),

**L**_{17}: x=t -> (F(x, x)->F(x, t)).

In schema L_{17}, 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 L_{10}:
~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 L_{11}: Bv~B - the Law
of the Excluded Middle. How can we think of L_{11} 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 L_{11} as an axiom after this?

For these (and some other) reasons some people reject L_{11}
(or even both - L_{10} and L_{11}) as logical
axioms. By excluding L_{11} from the above list the
so-called **intuitionistic** (or **constructivist**) **logic**
is obtained. By excluding both L_{10} and L_{11}
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 L_{1},
L_{2}.

**Exercise A.3.2.** Use Deduction theorem to derive L_{15},
L_{16} 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) aleph_{0}
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: S_{i} in B, then U{S_{i}
| i in N } also is a member of B.

In descriptive set theory the collection of all Borel sets is
denoted by DELTA^{1}_{1}.

**Exercise A.4.3.** a) Verify that DELTA^{1}_{1}
is closed under countable intersections as well. b)Verify that
DELTA^{1}_{1} 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 DELTA^{1}_{1}
sets) by continuous image operations is denoted by SIGMA^{1}_{1}.

DELTA^{1}_{1} is a proper subset of SIGMA^{1}_{1}.

**Exercise A.4.4.** Verify that SIGMA^{1}_{1 }is
closed under finite unions, finite intersections, and inverse
continuous images.

By PI^{1}_{1} we will denote the collection of
complements of SIGMA^{1}_{1} sets. I.e. each PI^{1}_{1}
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 PI^{1}_{1 }is
closed under finite unions, finite intersections, and inverse
continuous images.

Thus, SIGMA^{1}_{1} sets and PI^{1}_{1}
sets are the simplest kinds of non-Borel sets. It appears, that
the intersection of SIGMA^{1}_{1} and PI^{1}_{1}
is exactly DELTA^{1}_{1} (M.Suslin's theorem, do
not try to prove directly).

As the next step, by applying continuous image operations to
PI^{1}_{1} sets we obtain the so-called SIGMA^{1}_{2}
sets. After this, by applying the complement operation to SIGMA^{1}_{2}
sets we obtain the so-called PI^{1}_{2} sets. The
intersection of SIGMA^{1}_{2} and PI^{1}_{2}
is denoted by DELTA^{1}_{2}.

SIGMA^{1}_{1} and PI^{1}_{1}
are proper subsets of DELTA^{1}_{2}, and DELTA^{1}_{2
}is a proper subset of SIGMA^{1}_{2} (and of
PI^{1}_{2}).

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 SIGMA^{1}_{n},
or PI^{1}_{n}, or DELTA^{1}_{n}.

Thus, the general picture is as follows (each set of the next row is a proper superset of each set of the previous row):

DELTA^{1}_{1} (Borel sets)

SIGMA^{1}_{1} PI^{1}_{1}

DELTA^{1}_{2}

SIGMA^{1}_{2} PI^{1}_{2}

DELTA^{1}_{3}

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 SIGMA^{1}_{2}
sets, I will mean SIGMA^{1}_{2} subsets of R,
plus SIGMA^{1}_{2} 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 Q_{0} = P(wxw), i.e. let
Q_{0} be the set of all sets of pairs of natural numbers.
Prove Q_{0}-AC in ZF.

b) Let Q_{1} = P(vxv), where v is a well ordered set.
Prove Q_{1}-AC in ZF.

c) (Open problem?) Let Q_{1} = P(vxv), and assume Q_{1}-AC
in ZF. Could you show that the set v can be well ordered?

d) Let Q_{2} = P(RxR). Do not try to prove Q_{2}-AC
in ZF.

Usually, the so-called **countable axiom of choice** (AC_{w})
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 AC_{w} 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** (DC_{w}) 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, DC_{w} implies AC_{w}.

c) in ZF, P(RxR)-AC implies DC_{w}.

Relativized forms...

(P.S.Novikov,
M.Kondo, J.W.Addison) ZF proves SIGMA^{1}_{2}-DC,
and hence, SIGMA^{1}_{2}-AC_{w}.

(P.Cohen?) ZF cannot prove PI12-AC_{w}.

To be continued.

…

**Continuum Hypothesis**

(P.S.Aleksandrov,
F.Hausdorff,
M.Suslin) In ZFC, an infinite SIGMA^{1}_{1} set
is either countable, or has the cardinality of the entire
continuum.

We cannot hope to extend this theorem to PI^{1}_{1}
sets:

(P.J.Cohen?) The corresponding statement for PI^{1}_{1}
sets is undecidable in ZFC.

A message from the "stratosphere":

(W.Sierpinski)
In ZFC, an infinite SIGMA^{1}_{2} set is either
countable, or has the cardinality aleph_{1}, 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 SIGMA^{1}_{1} and all PI^{1}_{1}
sets are Lebesgue measurable.

(P.S.Novikov, K.Goedel) In ZF+V=L, there is a non-measurable
DELTA^{1}_{2} set. Hence, ZFC cannot prove that
all DELTA^{1}_{2 }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 SIGMA^{1}_{1}
or PI^{1}_{1} well orderings of the set of all
real numbers.

(A.Levy?) In ZFC, if some set X of real numbers admits a SIGMA^{1}_{1}
well ordering, then X is finite or countable.

We cannot hope to extend these theorems to DELTA^{1}_{2}
sets:

(J.W.Addison) In ZF+V=L, there is a DELTA^{1}_{2}
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 DELTA^{1}_{1} sets
are determined.

(author?) ZFC cannot prove that all SIGMA^{1}_{1}
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.