[FOM] Finite Set Theory

[Vladimir Sazonov]

Quoting Harvey Friedman <friedman at math.ohio-state.edu> Sun, 19 Feb 2006:

> I have had several occasions to explain what set theory is to "ordinary
> people" of a variety of age groups.
>
> I have found it very useful and effective to start with finite set theory
> only - restriction attention to very small sets.
>
> It works very well, and everybody is quite satisfied. Nobody feels confused
> or uneasy.
>

........

> 17. Again, this goes over reasonably well. And then I say that we can rework
> all of the above even allowing such infinite sets.
>
> Now, where would FOM subscribers have issues with this development?

I would say that everything is quite clear and *sufficiently* 
convincing, at least on that level of consideration based on the common 
sense of "people from the street" or even those mathematically trained 
or just the ordinary professional mathematicians. In fact, I think that 
the problem of set-theoretic paradoxes has been successfully resolved 
by mathematical practice - virtually everybody work in the framework of 
ZFC and are quite happy.

Another story - people concerned with more subtle foundational 
questions. Say, for me, the meaning of powerset operation even for the 
case of HF (hereditarily finite sets) and even for not so huge concrete 
finite sets is doubtful. But I would like to stress that these my 
doubts do not mean any pretension on imposing restrictions to 
mathematical practice (which generally consists in developing 
*arbitrary formalisms as "tools of thought"*). Rather, I hope on some 
extension of this practice by new ideas and formalisms around the 
(vague) concept of feasibility as reflecting practical (say, 
computational) reality where these imaginary powersets are not 
realisable.

In particular, a feasibly finite set theory could be in principle 
developed where the powerset 2^1000 would not exist (or would be an 
infinite class). Here 1000 is understood as a set consisting of one 
thousand elements. (Also note that a set x could be quite small, but 
yet non-feasible because of the cardinality of its transitive closure 
TC(x).)

This approach is like the complexity theory, but with declaring 
something too complex (like the exponential time or space) as a kind of 
infinity, thereby moving complexity problems to the foundations of 
mathematics. Of course, mathematics here is understood wider than just 
ZFC. What should not be changed, at least in the ideal, is the highest 
standard of mathematical rigour - its main and distinguishing, even the 
definitive feature.

A preliminary example of considerations in this direction is done, for 
example, in my paper "On bounded set theory" 
http://www.csc.liv.ac.uk/~sazonov/papers/cong-fin.ps where, in 
particular, a BST is considered whose definable operations = provably 
recursive operations = exactly PTime computable ones over HF. Recall 
that PTime is also considered as a version of feasible computability. 
But I discussed above on feasibility and typically use this term in a 
much more strong sense.


Vladimir Sazonov






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