Generalized Quantifiers
Dave L. Renfro
[sci.math Dec 20 2004 9:27:06:000PM]
http://mathforum.org/discuss/sci.math/m/664050/664484
wrote (in part):
> In the past few years I've grown fond of using the
> prefix "co" as in co-meagerly, co-measure zero,
> co-countable, etc. A lot of the kinds of results
> I'm interested in can be described nicely using
> quantifiers modulo some notion of smallness:
<snip rest>
I'm starting a new thread because there might be some
people interested in this who wouldn't see it if I
continued to post in the sci.math thread "What is meant
by a meager subset??".
Continuing this theme, and because it will give me
an excuse to continue putting off grading final exams
for my remaining class, let
v-oo mean "there exists infinitely many"
and
^-oo mean "for all but finitely many"
In non-ASCII writing the generally accepted notation
is to superscript with the "infinity" symbol oo the
usual symbols for "there exists" (backwards capital E)
and "for all" (upside down capital A).
These are the "there exists" and "for all" quantifiers
(which I'll use 'v' and '^' for) modulo the smallness
notion "finite".
Note that negation ~ distributes through these new
quantifiers the same way it distributes through v and ^:
(~)(v-oo) is the same as (^-oo)(~)
and
(~)(^-oo) is the same as (v-oo)(~)
It follows that the negation of a sequence of
such quantifiers can be rewritten the same way
that the negation of a sequence of ordinary
quantifiers can be rewritten, namely switch all
the v's to ^'s and all the ^'s to v's and then
take the negation of the right-most expression.
We can often use these new quantifiers to give
shorter definitions, such as
"x_n converges to L" can be expressed as
(^ e>0)(^-oo n)(|x_n - L| < e).
The negation of this can be carried out formally
in the way I described above to get
"x_n does not converge to L" expressed as
(v e>0)(v-oo n)(|x_n - L| \geq e).
For another example, the lim-inf of a sequence {A_n}
of sets is {x: (^-oo n)(x in A_n)} and the lim-sup of
the sequence {A_n} is {x: (v-oo n)(x in A_n)}.
In these and in other ways, I found the v-oo and ^-oo
quantifiers quite useful in a graduate real analysis
class I taught three years ago.
For the ordinary quantifiers we have the following
logical strength chart (no implication can be
reversed in general):
(^)(^) ==> (v)(^) ==> (^)(v) ==> (v)(v)
The analogous chart also holds for v-oo and ^-oo.
I haven't investigated the logical relationships for
sequences involving these four quantifier types, but I
have noticed that ^-oo doesn't commute with ^ (and hence
by considering negations, v-oo doesn't commute with v).
In particular, (^-oo)(^) is strictly stronger logically
than (^)(^-oo). For example, note that "for all real numbers
x we have for all but finitely many integers n that x < n
holds" is true, but "for all but finitely many integers
n we have for all real numbers x that x < n holds" is false.
The issue is that in order for (^-oo r)(^ s) to be true,
we need the existence of a co-finite collection of r's
that uniformly works for each s. In fact, the distinction
between (^-oo)(^) and (^)(^-oo) is really a (v)(^) verses
(^)(v) distinction (see [*]) if you look at things the
right way. Let 'C' be a variable that runs over the set
of co-finite collections of r's. Then (^-oo r)(^ s)
becomes (v C)(^ r in C)(^ s), which is equivalent to
(v C)(^ s)(^ r in C) (see [#]), while (^ s)(^-oo r) becomes
(^ s)(v C)(^ r in C).
[*] Note that (v)(^) verses (^)(v) is what makes uniform
continuity and uniform convergence (of functions)
different from continuity and pointwise convergence.
The distinction is also important if you want to
correctly state the identity and inverse axioms
for a group.
[#] Recall that ordinary ^'s (and v's as well) commute
among themselves. That is, (^ P)(^ Q) is logically
the same as (^ Q)(^ P).
I haven't tried to develop these ideas into a general
framework (quantifiers modulo various notions of smallness,
and how they logically relate to each other relative
to how the various notions of smallness relate to each
other, besides trivial things like the larger the notion
of smallness, the stronger and weaker the corresponding
versions of v and ^ are, respectively, with no difference
between them at all when the set being quantified over is
"small"), nor do I expect to in the future. However, below
are a few literature references I've come across that seem
as if they might be relevant if anyone wants to look into
these ideas further.
[1] Jon Barwise, "An introduction to first-order logic",
pp. 5-46 in Jon Barwise (editor), HANDBOOK OF
MATHEMATICAL LOGIC, Studies in Logic and the
Foundations of Mathematics #90, North-Holland, 1977.
[See Section 5.5 ("Logic with new quantifiers") on
pp. 44-45.]
[2] Johan van Benthem, "Questions about quantifiers",
Journal of Symbolic Logic 49 (1984), 443-466.
[3] Alexander S. Kechris, CLASSICAL DESCRIPTIVE SET
THEORY, Graduate Texts in Mathematics #156,
Springer-Verlag, 1995. [See p. 53 (meager versions)
and p. 114 (measure zero versions).]
[4] H. Jerome Keisler, "Logic with the quantifier 'there
exist uncountably many'", Annals of Mathematical
Logic 1 (1970), 1-93.
[5] Andrzej Mostowski, "On a generalization of quantifiers",
Fundamenta Mathematicae 44 (1957), 12-36.
[6] Dag Westerstahl, "Self-commuting quantifiers", Journal
of Symbolic Logic 61 (1996), 212-224.
http://www.google.com/search?as_epq=generalized+quantifiers
http://scholar.google.com/scholar?as_epq=generalized+quantifiers
http://www.maths.usyd.edu.au:8000/s/search/p?p1=generalized+quantifiers
http://groups-beta.google.com/groups?as_epq=generalized+quantifiers
Dave L. Renfro