[FOM] 568: Counting Equivalence Classes #2

Mon Jan 5 05:06:29 EST 2015

We restate http://www.cs.nyu.edu/pipermail/fom/2015-January/018485.html
with some additional results.

Section 1 remains unchanged.

The TEQ there is LEQ here.

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

We present some fundamental equivalence relations with finitely many
equivalence relations. We show that ZFC is not capable of counting the
number of equivalence classes. We also show this for the standard
extensions of ZFC and NBG with large cardinal hypotheses (for
whichever are consistent).

1. +,dot Equivalence Relations.
2. Polyvalue Equivalence Relations.
3. Locally Isomorphic Operations.

1. +,dot EQUIVALENCE RELATIONS

DEFINITION 1.1. x EQ(k,+,dot) y if and only if x,y in Z^k, and for all
1 <= i,j,r <= k,
i. x_i + x_j = x_r if and only if y_i + y_j = y_r.
ii. x_i dot x_j = x_r if and only if y_i dot y_j = y_r.

THEOREM 1.1. Each EQ(k,+,dot) is an equivalence relation with only
finitely many equivalence classes. EQ(1,+,dot) has 3 equivalence
classes. 0,1,2 forms a complete set of representatives.EQ(2,+,dot) has
18 equivalence classes. The following list of pairs forms a complete
set of representatives.
(0,0), (0,1), (0,2)
(1,-1), (1,0), (1,1), (1,2), (1,3)
(2,0), (2,1), (2,2), (2,4)
(-1,-2), (-1,1)
(4,1), (4,2)
(6,3), (16,4)

THEOREM 1.2. For all sufficiently large k, the number of equivalence
classes of EQ(k,+,dot) cannot be
counted in ZFC (assuming ZFC is consistent). I.e., there is no m such
that ZFC proves "the number of equivalence classes of EQ(k,+,dot) is
m". This result holds for any consistent formal system that interprets
EFA = exponential function arithmetic. Thus for all sufficiently large
k, EQ(k,+,dot) cannot be counted in any extension of ZFC and NBG by
standard large cardinal hypotheses that form a consistent system.

2. POLYVALUE EQUIVALENCE RELATIONS

DEFINITION 2.1. n PVEQ(k,d,c) m if and only if n,m are values of the
same polynomials in k integer variables, of degree at most d, with
coefficients from {-c,...,c}.

THEOREM 2.1. Each PVEQ(k,d,c) is an equivalence relation on Z with
finitely many equivalence classes.

THEOREM 2.2. For very small positive integers k,d,c, the number of
equivalence classes of PVEQ(k,d,c) cannot be
counted in ZFC (assuming ZFC is consistent). I.e., there is no m such
that ZFC proves "the number of equivalence classes of PVEQ(k,d,c) is
m". This result holds for any of the extensions of ZFC and NBG by
standard large cardinal hypotheses that form a consistent system.

How small can k,d,c be taken to be? I have a target of PVEQ(4,4,8).

3. LOCALLY ISOMORPHIC OPERATIONS

DEFINITION 3.1. f:A^2 into B and g:C^2 into D are isomorphic if and
only if there exists a bijection h:A union rng(f) onto C union rng(g)
such that f(x,y) = z iff g(hx,hy) = hz.

DEFINITION 3.2. LEQ(k) is the following equivalence relation on the
f:Z^2 into Z. f LEQ(k) g if and only if f,g:Z^2 into Z have the same
restrictions to sets A^2 containedin Z^2, |A| = k, up to isomorphism.

THEOREM 3.1. Each LEQ(k) is an equivalence relation with only finitely
many equivalence classes.

THEOREM 3.2. The number of equivalence classes in LEQ(8) cannot be
counted in ZFC (assuming ZFC is consistent). I.e., there is no m such
that ZFC proves "the number of equivalence classes of LEQ(8) is m".
This result holds for any extension of ZFC or NBG by standard large
cardinal hypotheses that form a consistent formal system.

More generally, we can define the equivalence relation LEQ(k;n,m) on
the f:Z^n into Z^m, where we use the restrictions to sets A^n, |A| =
k.  Thus LEQ(k) = LEQ(k;2,1). Then k can be pushed down from 8, even
for very small n,m.

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

Harvey Friedman