[FOM] 576: Game Correction/Simplicity Theory 1

Tue Jan 27 10:39:49 EST 2015

CORRECTION to http://www.cs.nyu.edu/pipermail/fom/2015-January/018512.html

In the description of the finite game G(R,k,t), I wrote

Alice wins iff none of Bob's plays is an R reduction of any of Bob's plays.

I meant to write

Bob wins iff none of Bob's plays is an R reduction of any of Bob's plays.

***************

SIMPLICITY THEORY 1

I want to try some systematic development of a theory of Simplicity. I
expect a delicious combination of theory and computer investigations.

The, or a, basic aim of Simplicity Theory is to calculate upper and
lower bounds on how complicated the definitions of fundamental notions
in mathematics must be. Of course, we generally aim at exact
calculations, and in simple cases, that's exactly what we expect.
However, we probably will find that that is not going to be something
that we are able to do, perhaps even with computers.

So let's start with easy examples, which I am going to throw out
without even working them out. Perhaps the FOM followers will enjoy
this, and I expect to see postings describing solutions.

COMPLEXITY DEFINITION. Let M be a relational structure. We use and,
or, not, if then, iff, formal, therexists, =, together with the
relation, constant, and function symbols interpreted by M. The
complexity of a formula in L(M) is the total number of relation,
constant, and function symbols appearing in the formula.

I "know" that this is definitely worth pursuing, but I don't know how
to prove this at this point. I "know" that interesting fundamental
phenomena "will" arise when trying to get exact calculations here,
with new little combinatorial subjects arising as spin offs. Also, it
will be interesting to see if the usual definitions normally given are
close to optimal, complexity wise.

1. What is the least complexity for equivalence relations?
2. For strict partial orderings?
3. For strict linear orderings?
4. For strict dense linear orderings?
5. For strict linear orderings with no endpoints?
6. For strict linear orderings with both endpoints?
7. For the myriad of widely used kinds of binary relations?
8. What is the least complexity for semigroups?
9. For Abelian semigroups?
10. For groups?
11. For Abelian groups?
12. For divisible groups?
13. For rings?
14. For commutative rings?
15. For integral domains?
16. For fields?
17. For ordered groups?
18. For ordered rings?
19. For ordered fields?

Often there are a few closely related formulations that are each
interesting. E.g., for groups, there is (G,dot), (G,dot,1), (G,dot,-),
(G,dot,-,1). We learn that adding structure like this is a good idea,
partly because it reduces complexity. This can be systematically
investigated under the above complexity measure. However, we may find
that it is a good idea to consider a few different complexity
measures, reflecting different aspects of complexity. Or we may simply
want to restrict the kind of definitions being considered such as
"purely universal definitions". Of course, with that approach, some of
the notions don't even have purely universal definitions, something
that is often easy to prove.

That ought to keep you busy and out of trouble.

************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 576th 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-527 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2014-August/018092.html

528: More Perfect Pi01  8/16/14  5:19AM
529: Yet more Perfect Pi01 8/18/14  5:50AM
530: Friendlier Perfect Pi01
531: General Theory/Perfect Pi01  8/22/14  5:16PM
532: More General Theory/Perfect Pi01  8/23/14  7:32AM
533: Progress - General Theory/Perfect Pi01 8/25/14  1:17AM
534: Perfect Explicitly Pi01  8/27/14  10:40AM
535: Updated Perfect Explicitly Pi01  8/30/14  2:39PM
536: Pi01 Progress  9/1/14 11:31AM
537: Pi01/Flat Pics/Testing  9/6/14  12:49AM
538: Progress Pi01 9/6/14  11:31PM
539: Absolute Perfect Naturalness 9/7/14  9:00PM
540: SRM/Comparability  9/8/14  12:03AM
541: Master Templates  9/9/14  12:41AM
542: Templates/LC shadow  9/10/14  12:44AM
543: New Explicitly Pi01  9/10/14  11:17PM
544: Initial Maximality/HUGE  9/12/14  8:07PM
545: Set Theoretic Consistency/SRM/SRP  9/14/14  10:06PM
546: New Pi01/solving CH  9/26/14  12:05AM
547: Conservative Growth - Triples  9/29/14  11:34PM
548: New Explicitly Pi01  10/4/14  8:45PM
549: Conservative Growth - beyond triples  10/6/14  1:31AM
550: Foundational Methodology 1/Maximality  10/17/14  5:43AM
551: Foundational Methodology 2/Maximality  10/19/14 3:06AM
552: Foundational Methodology 3/Maximality  10/21/14 9:59AM
553: Foundational Methodology 4/Maximality  10/21/14 11:57AM
554: Foundational Methodology 5/Maximality  10/26/14 3:17AM
555: Foundational Methodology 6/Maximality  10/29/14 12:32PM
556: Flat Foundations 1  10/29/14  4:07PM
557: New Pi01  10/30/14  2:05PM
558: New Pi01/more  10/31/14 10:01PM
559: Foundational Methodology 7/Maximality  11/214  10:35PM
560: New Pi01/better  11/314  7:45PM
561: New Pi01/HUGE  11/5/14  3:34PM
562: Perfectly Natural Review #1  11/19/14  7:40PM
563: Perfectly Natural Review #2  11/22/14  4:56PM
564: Perfectly Natural Review #3  11/24/14  1:19AM
565: Perfectly Natural Review #4  12/25/14  6:29PM
566: Bridge/Chess/Ultrafinitism 12/25/14  10:46AM
567: Counting Equivalence Classes  1/2/15  10:38AM
568: Counting Equivalence Classes #2  1/5/15  5:06AM
569: Finite Integer Sums and Incompleteness  1/515  8:04PM
570: Philosophy of Incompleteness 1  1/8/15 2:58AM
571: Philosophy of Incompleteness 2  1/8/15  11:30AM
572: Philosophy of Incompleteness 3  1/12/15  6:29PM
573: Philosophy of Incompleteness 4  1/17/15  1:44PM
574: Characterization Theory 1  1/17/15  1:44AM
575: Finite Games and Incompleteness  1/23/15  10:42AM

Harvey Friedman