[FOM] 456: The Quantifiers "majority/minority"
Harvey Friedman
friedman at math.ohio-state.edu
Wed Feb 23 09:53:12 EST 2011
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
This is a continuation of http://www.cs.nyu.edu/pipermail/fom/2011-February/015305.html
What kind of conditions are we talking about, from a logical point of
view?
Let us use the majority/minority terminology. Thus "most" is
"majority", and "not most" is "minority".
Note that 1,2,3 are formulas with individual variables, equality,
monadic predicates, and the majority/minority quantifiers. In
particular, no ordinary quantifiers (however, free variables are
allowed, which are implicit outside ordinary universal quantifiers).
Note also that we do not allow compound majority/minority quantifiers.
CONJECTURE: The set of such sentences with "most" that hold in all
finite sets, or in all sufficiently large finite sets, is very
recursive.
I have not worked on this conjecture. This may fall out of work done
(or methods involved in work done) on the logic of 0,1-laws, even if
there is no restriction on the majority/minority quantifiers?
Note that axioms 1,2 clearly hold in all finite sets. However, axiom 3
does not hold in all finite sets. In fact, it holds in no finite sets.
The empty set is not allowed here.
There is a simple set of such sentences with "most", each of which
hold in all sufficiently large finite sets, but where there is no
reasonable interpretation in N (as in http://www.cs.nyu.edu/pipermail/fom/2011-February/015305.html)
.
1. It is not the case that a majority of numbers are in A intersect B
and a minority of numbers are in A union C.
2. Let k >= 1. If we partition N into three parts A,B,C, then at least
one of the following holds:
a. A majority of numbers are in A union B, and a minority of numbers
are in C union {x_1,...,x_k}.
b. A majority of numbers are in A union C, and a minority of numbers
are in B union {x_1,...,x_k}.
c. A majority of numbers are in B union C, and a minority of numbers
are in A union {x_1,...,x_k}.
THEOREM 1. There are predicates "majority/minority" on all subsets of
N for which 1,2 hold. In fact, we can use any finitely additive
probability measure on all subsets of N, where points have measure
zero, and take "majority" to mean measure > 1/2, "minority" to mean
measure < 1/2. The nonprincipal ultrafilters correspond to such
measures which are 0,1 valued. If we use a nonprincipal ultrafilter,
then we can strengthen these axioms very considerably. It is well
known that ZFC proves the existence of nonprincipal ultrafilters on
(the subsets of) N.
THEOREM 2. (well known). The existence of such measures in Theorem 1
is not provable in ZF. Furthermore, there is no set theoretic
definition which ZFC proves defines a finitely additive probability
measure on all subsets of N, where points have measure zero. In
addition, ZF proves that there is no Borel measurable such measure.
Theorem 2 indicates that there is no reasonable mathematical
construction of a specific finitely additive probability measure on
all subsets of N, where points have measure zero.
THEOREM 3. The existence of predicates "majority/minority" on all
subsets of N,
obeying conditions 1,2 above, is not provable in ZF. There is no set
theoretic definition which ZFC proves defines a predicate "most" on
all subsets of N, obeying conditions 1-3 above. Furthermore, ZF proves
that there is no Borel measurable predicate "most" on all subsets of N
obeying conditions 1,2.
Theorem 3 indicates that there is no reasonable mathematical
construction of a specific predicate on on all subsets of N, obeying
conditions 1,2.
The proof of this uses standard technology from forcing. For those
familiar with this technology, here is the core element of the proof.
LEMMA. There are two Cohen generic partitions (A,B,C), (D,E,A union B)
of N.
We can obviously weaken condition 1) by using partitions of N into
more than 3, but finitely many, sets. The same results hold.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 456th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-449 can be found
in the FOM archives at http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html
450: Maximal Sets and Large Cardinals II 12/6/10 12:48PM
451: Rational Graphs and Large Cardinals I 12/18/10 10:56PM
452: Rational Graphs and Large Cardinals II 1/9/11 1:36AM
453: 453: Rational Graphs and Large Cardinals III 1/20/11 2:33AM
454: Three Milestones in Incompleteness 2/7/11 12:05AM
455: The Quantifier "most" 2/22/11 4:47PM
Harvey Friedman
More information about the FOM
mailing list