[FOM] Tangential to Holmes/Slater exchange

[A.P. Hazen]

   The recent exchange between Randall Holmes and Hartley Slater (about
"numbers and sets") brings to mind a class of tecnical -- logical, maybe
even FoM-ical -- questions I think might be interesting to investigate.
   The "standard" formalism of First Order Logic (FOL) is a fine thing and
I won't say anything against it, but its WAY of representing various
concepts is (maybe importantly) different from the way natural languages
express them, and derivation in First Order formalisms can be
(surprisingly) different from intuitive reasoning.  Thus many philosophers
(and cognitive scientists? and artificial intelligentsia?) have been
attracted to non-standard formalisms which seem closer to "intuition" or
natural language.  I think the investigation of these formalisms can be
interesting/informative: perhaps, if one is found that is both expressive
and tractable, even *practically* important.

   Case in point:
	(A) Numerically definite quantifiers.  For any fixed n, FOL with
Identity can express "There are n things such that ...".  (Aside: the most
efficient way of doing this is apparently due to David Lewis.  To say
"There are at least n x such that Fx," start with (n-1) UNIVERSAL
quantifiers
	AyAz...Aw
then put in one EXISTENTIAL
	         Ex
then a conjunction of (n-1) negated identities saying that x is not one of
yz...w
		   (~x=y&...~x=w
and finally say that x is an F thing:
				 &Fx).
The length-increase of these formulas is linear as n increases, which is a
lot more user-friendly than other methods.)  PROBLEM: We humans tend to
think that it is EASY to see that 3+3=6, and so on.  But try to PROVE it
(in the form "If there are at least 3 A's and at least 3 B's, and no A is a
B, then there are at least 6 A-or-B's") using your favorite proof procedure
for FOL with I.  I have a feeling there is a problem in principle with
this: that the "logical" derivations of elementary facts about addition are
closely related to propositional logic proofs of cases of the Pigeon Hole
Principle, which seem to be intrinsically hard.
	I feel that there ought to be a philosophical moral here....

	(B) Now a formalism discussed by Holmes and Slater.  We can
ABBREVIATE the First Order version of "There are at least 3 Fs" to
something like
	E3x(Fx),
but the "3" here, like the subscripts on variables, is syncategorematic: a
logically inert part of the notation.  In particular, the "3" is not a
TERM, it cannot be replaced with a quantifiable variable.  So let's extend
the notation, and treat the numerical "subscripts" on quantifiers as terms,
at least to the extent of allowing them to to be substitution-instances of
quantifiable variables.
	For a start, do it in the most conservative way possible: the only
things that can be used as "subscripts" in numerically definite quantifiers
are actual numerals ("1", "2", "3", or maybe "1", "s1", "ss1"), numerical
variables, and terms formed  from one numeral or numerical variable by
prefixing the successor operator a number of times.  Still being
conservative, let the numerical and ordinary variables be of different
sorts (so questions about the identity of numbers with some objects
quantified over with ordinary variables don't arise).  We can readily think
of some BASIC things to include in the axiomatization: standard quantifier
logic for both sorts of variables, axioms of equivalence between
numerically definite quantifiers written with numerals and their pure
FOL-with-I definientia, maybe the scheme "If there are at least sn things,
x, such that Fx, then there is an x such that (Fx & there are at least n
things, y, such that (Fy & ~x=y))."
	QUESTION: How powerful (in terms of expressive power, or complexity
of an adequate deductive system) is this formalism?  One is tempted to
think, not very: it is just a hybrid of FOL-with-I (for the "ordinary"
variables) and the theory of successor (decidable!) for the numerical
variables.  Surprise: it's actually strong  enough to be non-axiomatizable.
(It can express "there are infinitely many F things" by "AnEnx(Fx)", and
this-- by Goedel's incompleteness theorem-- suffices to show
non-axiomatizability.)

	One philosophical moral seems to be that simple and
intuitive-seeming formalisms, even if close to natural language, can
conceal very great mathematical power.
	As I said at the outset, I think formalisms analogous to this may
be interesting to investigate.  What (weakish) set theory, for example,
does the simple theory of types (Russell-Ramsey) amount to if we allow the
type-subscripts to be quantifiable variables?

---

Allen Hazen
Philosophy Department
University of Melbourne