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

Thu Mar 3 13:06:16 EST 2011

Dear  FOMers:

on what concerns Harvey Friedman's post about quantifiers
"majority/minority", it may be of interest to know that Paulo Veloso,
Mário Sette and I have worked since 1997 on this topic. The main papers
are the following (and Veloso has subsequently  written other  papers):

P.A.S. Veloso and W. A. Carnieli.  Ultrafilter logic and generic
reasoning, in Computational Logic and Proof Theory. In: CARNIELLI, W.
A.. (Org.). Lecture Notes in Comput. Sci.. Berlin: Springer, 1997, v.
1289, p. 34-53.

P.A.S. Veloso and W. A. Carnieli. Logics for qualitative reasoning.
In: Shahid Rahman; John Symons. (Org.). Logic, Epistemology and the
Unity of Science. Amsterdam: Kluwer Academic Publishers, 2004, p.
487-526.

W. A. Carnielli  and  M. C. C. Gracio. Modulated Logics and Flexible
Reasoning. Logic and Logical Philosophy, v. 17, p. 211-249, 2008.

Best regards,

Walter Carnielli

> De: Harvey Friedman <friedman at math.ohio-state.edu>
> Data: 23 de fevereiro de 2011 11h53min12s BRT
> Para: fom <fom at cs.nyu.edu>
> Assunto: [FOM] 456: The Quantifiers "majority/minority"
> Responder A: Foundations of Mathematics <fom at cs.nyu.edu>
>
> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>

--
++++++++++++++++++++++++++++
Prof. Dr. Walter Carnielli
Director
Centre for Logic, Epistemology and the History of Science – CLE
State University of Campinas –UNICAMP
13083-859 Campinas -SP, Brazil
Phone: (+55) (19) 3521-6517
Fax: (+55) (19) 3289-3269
e-mail: walter.carnielli at cle.unicamp.br
Website: http://www.cle.unicamp.br/prof/carnielli