[FOM] 456: The Quantifiers "majority/minority"

[Harvey Friedman]

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