[FOM] primer on vagueness

[Vladimir Sazonov]

Quoting Charles Silver <silver_1 at mindspring.com>:
> 
> Stewart Shapiro wrote:
> "Typical vague predicates give rise to the ancient *sorites paradox*, 
> sometimes called the *paradox of the heap*.  Here is an example:
> 
> Premise:  A man with no hair at all is bald.
> 
> Premise:  If a man has only n hairs on his head is bald, then so is a man 
> with n+1 hairs.
> 
> Conclusion:  A man with 50,000 hairs on his head is bald.
> 
> [Things skipped]...
> 
>     If a man with 0 hairs is bald, then so is a man with 1; 
> if a man with 1 hair is bald, then so is a man with 2; ...  
> This argument has 50,002 premises."
> 
> ****
> 
>     In "Zooming Down The Slippery Slope,"  George
> Boolos shows how in a standard natural deduction
> system it is possible to infer essentially the same 
> conclusion for 1,000,000 (one billion) hairs
> using fewer than 70 premises.   He then extends
> this reasoning to various other numbers of hairs--
> for instance 2^30--while indicating how derivations
> can be compressed.   

Recall that the proof of non-elementary complexity of cut 
elimination by V. Orevkov is based on (I guess) analogous 
compression. Roughly speaking, it is shown how to prove 
"feasibility" or "existence" of the exponential tower 
 
            2^{2^...2^{1000}} of the hight 1000 

from the totality of the successor operation. 
Without the cat rule (or by using only normal natural deductions) 
this is impossible to doo. 

R. Parikh in his paper "Feasibility in arithmetic" (JSL, 1971) 
added the predicate F (for "feasible" or, in our context, for "bold") 
to Peano Arithmetic PA with postulating that F contains 0, 1 and is 
under successor and +. He also postulated that the exponential 
tower like above, but of the hight 2^1000, denotes a number not in F. 
F is not allowed to participate in the induction axiom. 
He demonstrated that the shortest proof of contradiction is longer 
that (roughly) 2^1000. Therefotre this theory is practically consistent. 

This is a quite rigorous way of approaching to the concepts of 
feasibility and to the heap (or bold man) paradox. This 
approach is really non-classical because no model for F above 
exists in the ordinary set-theoretical framework. Intuitiuonistic, 
and modal logics as well as the approaches to this paradox 
described by Stewart Shapiro in the recent posting are reducible 
these or other ways to the classical set theory (Kripke models, 
realizability, or the like). Nothing such is evidently possible 
for Parikh's formalization of F. Feasibility is completely 
new concept for mathematics, like it was some time ago with 
negative numbers, irrationals, infinitesimals, etc. 

Parikh's upper bound for F (the exponential tower of the hight 
2^1000) is intuitively too rough. Intuitively, just one stage 
tower 2^1000 should be OK. Orevkov's result above demonstrates 
that with the cut rule alloweed this bound is impossible to 
improve essentially. In my paper "On feasible numbers", 1995, 
it is shown that without cut rule the number 2^1000 can be 
(feasibly) consistently postulated as the upper bound for F. 
(There is some plausible intuitive justification leading to 
something like this restriction on the cut rule.) 

What is interesting, are some consequences we have from such a 
theory of feasible numbers. Even for 1000 the effect of the 
heap paradox can be modelled. For some definable predicate M 
(for "medium") it is shown that 

M(0),  
forall x (M(x) => M(x+1)), and 
\neg M(1000) 

hold without any (feasible) contradiction. The point is that, 
although with the cut (or modus ponens) rule we can deduce 
M(1000), elimination of this rule will make the proof non-feasible 
(in fact, containing more than 2^1000 of symbols). For small 
numbers like 1,2,3, we can eliminate the cut rule and prove 
in the system that M(1), M(2), M(3),... 
But for bigger numbers it becomes more and more difficult to do 
this and, in fact, impossible for 1000. 

There are even more strange effects in this theory of feasibility. 

I would like to conclude on the possible opposition
of vague vs. mathematical. 

Although the first coming opinion that feasibility is a vague 
concept, and therefore non-mathematical, I strongly believe 
that this contrasting is incorrect. The ordinary intuitive 
mathematical concepts are non-vague only at the first sight. 
Under a properly understood philosophy of mathematics based 
on the formalist approach there is no reason to consider 
them in this way. Say, the above considerations give some 
formalizations (axioms + proof rules) of feasibility. 
We deduce some results on this vague concept in exactly 
the same (non-vague) manner as in the ordinary mathematics. 
As in classical mathematics some questions are undecidable. 
What is the difference, except that some axioms and rules 
are chosen in some special way? Moreover, the formalisms of 
ZFC or PA are based, in fact, on the concept of a formal 
proof of a *feasible length*. (Otherwise we go into infinite 
regress.) Therefore the universe of sets or the "set" of 
natural numbers are inherently vague as well. As in the case 
of "vague" feasible numbers, certain questions are resolvable 
positively or negatively. If we will concentrate on such resolvable 
questions only then even feasible numbers will look as non-vague. 
The very possibility of undecidable questions in mathematics 
says about the vagueness of its most fundamental concepts. This 
vagueness may seem as not exactly of the same character as that 
of feasible numbers. But, philosophically, what is the difference 
(except that ZFC and PA are well developed, unlike new feasibility 
formalisms)?  

The "length" (or the borderline between feasible and non-feasible) 
of the row of feasible numbers is highly indefinite. 
Is the "length" of the row of the natural numbers (satisfying 
the axioms of PA or understood in terms of the abstraction of 
potential infinity/feasibility based on some strong "iteration" 
or extrapolation of the idea of feasibility) anything better? 

Let us ask ourselves what are provably existent (in PA?, ZFC?..., 
let even in PA only) natural numbers, and we will get the 
strongest feeling of vagueness. 


Vladimir Sazonov



----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.