[FOM] 574: Characterization Theory 1

Mon Jan 19 14:10:45 EST 2015

CORRECTION TO http://www.cs.nyu.edu/pipermail/fom/2015-January/018506.html

In the description of G(R,k,t), in the last line I wrote "max(x) <
max(y) and x R y". This should be "max(y) < max(x) and x R y". In
Theorem 1.1.1, I wrote G(R,k). This should be G(R,k,t).

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

I now want to start discussion of a systematic project based on the
following thesis.

CHARACTERIZATION THESIS. All of the most important mathematical
structures have informative characterizations that uniquely
characterize them up to isomorphism. There are many opportunities for
new kinds of fundamentally important characterizations. These
characterizations are not only important in their own right, but also
lead to various logical investigations.

I want to emphasize that this is meant to be a systematic
investigation. This means that the results will range from the utterly
trivial to the quite involved, and just about everything in between.
Settings and results are chosen for their fundamental illuminating
character, rather than for novel difficulties. Novel difficulties may
episodically arise.

I will start the discussion with the set Z of integers with various
structure. This is an example of a fundamental triviality.

THEOREM 1. Z with no structure is characterized up to isomorphism as
an infinite set with no structure which is isomorphic to all of its
infinite subsets.

But there is a more interesting characterization.

THEOREM 2. Z with no structure is characterized up to isomorphism as
an infinite D with some f:D into D that generates D from some element
of D. Also as an infinite D with some k and f:D^k into D that
generates D from finitely many elements of D.

THEOREM 3. Let k >= 1 and 1 <= n <= infinity. There exists f:Z^k into
Z which generates Z from n elements of Z and no fewer.

PROBLEM. In Theorem 3, what happens if we require that f is a
polynomial of degree d?

Next, let's look at (Z,S), where S(x) = x+1.

THEOREM 4. (Z,S) is characterized up to isomorphism as a permutation
on an infinite set that does not map any nonempty proper subset into
itself.

Now let's look at (Z,<).

THEOREM 5. (Z,<) is characterized up to isomorphism as a nonempty
linear ordering without endpoints where every bounded set is finite.

We now come to (Z,+).

THEOREM 6. (Z,+) is characterized up to isomorphism as an infinite
group whose nonzero elements form the orbit of some element.

Now (Z,+,dot).

THEOREM 7. (Z,+,dot) is characterized up to isomorphism as a
commutative ring with unit of characteristic 0, with no proper subring
with unit.

THEOREM 8. (Z^+,dot) is characterized up to isomorphism as a
commutative semigroup with unit with a countably infinite set of free
generators.

PROBLEM. Find a striking characterizations of (Z,dot), (Z,<,dot) up to
isomorphism.

Now (Q,<).

THEOREM 8. (Q,<) is characterized up to isomorphism as a dense linear
ordering without endpoints that is isomorphic to all of its
restrictions that are dense linear orderings without endpoints.

Next (Q,+). Divisible Abelian groups are required to have at least two
elements. Torsion free means every element has infinite order.

THEOREM 9. (Q,+) is characterized up to isomorphism as a torsion free
divisible Abelian group with no proper divisible subgroup.

Now for (Q,<,+).

THEOREM 10. (Q,<,+) is characterized up to isomorphism as a divisible
ordered Abelian group with no proper divisible subgroup.

PROBLEM. Find striking characterizations up to isomorphism of (Q,dot),
(Q^+,dot), (Q,<,dot), (Q^+,<,dot).

And (Q,+,dot).

THEOREM 11. (Q,+,dot) is characterized up to isomorphism as a field
with no proper subfield.

Now (Q,<,+,dot).

THEOREM 12.  (Q,<,+,dot) is characterized up to isomorphism as an
ordered field with no proper subfield.

In the next in this series, we delve into the complete dense linear
orderings, where we see some much more striking phenomena.

************************************************************
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 574th 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

Harvey Friedman