Re: semantics of "most"

[cbmvax!uunet!PRC.Unisys.COM!dave]

> First, to restate the claim in a more formal way:
>  no quantifier with the same meaning as the English word "most" can be
> defined in first order logic, i.e. a logic in which there is
> quantification over individuals drawn from some (finite or infinite)
> universe.

Let me begin by saying that I will pretty much take your word on this.
While I am a comfortable user of formal logic, I make no claims to be
a logician myself.  So I don't disagree, but I do have some comments
and questions.

The first comment/question is, does this really cause any problems for
Lojban?  In other words, though Lojban certainly tries to be logical,
I don't believe it tries to mirror first order logic, does it?  FOL is
certainly powerful, but equally certainly it is provably inadequate
for many tasks.

For example, I would expect (in my role of looking in at Lojban from
the outside) that notions of possibility, necessity, and logical
entailment would be expressible in any usable human language, Lojban
included; these notions cannot be expressed in FOL either, but
require extensions such as modal logic.

> As an aside, it is a standard result that if a quantifier can be
> defined in first order logic, then it is reducible to some combination
> of "All" and "Exists" (which I will write here as A and E). For
> example, the derived quantifier "two x" can be reduced to "Ex.Ey.x /=
> y" (where /= is "not equal").  So we can translate "Two men walk" as
> "two x.(man(x) & walk(x))", i.e.  "Ex.Ey.(x /= y & man(x) & man(y) &
> walk(x) & walk(y))".

This is a little puzzling; it sounds more like this is a definition of
what FOL is.  You seem to be saying that if a quantifier can be
defined in FOL, then it can be defined in terms of the concepts
already in FOL.  This seems more of a truism than a "result" (which
implies to me that it is somehow provable).

For example, if we add a quantifier "Most" to FOL, then either (1) it
is reducible to "All" and "Exists," in which case it is merely
shorthand, and we haven't really extended the logic any, or (2) it is
not reducible to "All" and "Exists," in which case we have added new
expressive power and extended the logic, in which case we should call
it something other than FOL.

So is this result provable in some way?

> Secondly, I should make it clear what I mean by "most". A paraphrase
> is "more than half of", i.e. "Most men walk" is equivalent to
> (1) "more than half of the individuals who are men are individuals who
> walk."

I tried to put "Most men walk" into FOL, and it's certainly hairy
enough.  I was a little surprised at where the problem was, though.
My basic approach was to partition the set of men into men who walk
and men who don't walk, then to form a 1-1 mapping between men who
don't walk and an arbitrary subset of men who walk.  Then it would be
a simple matter of asserting there is a man who walks but is not in
this subset.

My problem came in attempting to show that two sets were equal in size
by forming a 1-1 mapping between them (the rest is pretty easy).  So
if you are correct that "Most men walk" cannot be put into FOL, then
it appears to be because there is no way in FOL to say that two sets
have equal cardinality.  This seems reasonable, since to state that a
mapping between two sets is 1-1 is to make a statement about the
mapping, which takes you out of first order.  Is this basically what
the proof is about?

> One solution which is widely used is to adopt what are called
> "generalized quantifiers". Now, instead of translating a sentence into
> a quantifier over a variable, and a formula which uses that variable,
> we express the quantifier as a relation between two sets. Thus
> ...
> English	Most men walk.
> GQ	The intersection of the set of men and the set of walkers contains at
> 	least half as many members as the set of men.

While I like the notion of generalized quantifiers, I still don't see
how things like "at least half" can be expressed without bringing in
the same sorts of problems.

In other words, if FOL quits being FOL when we introduce quantifiers
like "most" or "same number of," then neither can we arbitrarily throw
in new generalized quantifiers.  So:  there must be a "standard set"
of generalized quantifiers.  What is it?


-- Dave Matuszek (dave@prc.unisys.com)  I don't speak for my employer. --
-------------------------------------------------------------------------
|   When I was young, my family bought a color TV.  Our neigbors, who   |
| were poorer, had only a black-and-white set.  They bought a piece of  |
| cellophane, red on top, yellow in the middle, and blue on the bottom, |
| and taped it over their screen, so they could claim that they had a   |
| color TV, too.                                                        |
|   Now there's Windows 3.0.                                            |
-------------------------------------------------------------------------