Abstract:
I prove various results concerning un-decidability in weak
fragments of Arithmetic. All results are concerned with 
a hierarchy
of theories which have already been intensively studied in the literature.
Ideally one would like to separate these systems. However this is generally
expected to be a very deep problem, closely related to some of the most
famous and open problems in complexity theory.
In order to throw some
light on the separation problems, I consider the case where the underlying
language is enriched by extra relation and function symbols. The paper
introduces a new type of results. These state that the first three levels in
the hierarchy (i.e. 
and 
) are never able to
distinguish (in a precise sense) the ``finite'' from the ``infinite''. The
fourth level (i.e. 
) in some cases can make such a distinction.
More precisely, elementary principles from finitistical combinatorics (when
expressed solely by the extra relation and function symbols) are only
provable on the first three levels if they are valid when considered as
principles of general (infinitistical) combinatorics. I show that this does
not hold for the fourth level.
All results are proved by forcing.
Available as PostScript, PDF, DVI.