“It’s all Greek to me”– on the pre-history of categorical logic
Peter M. Hines — University of York

Computational Logic & Applications

Krakòw, Dec. 2023

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

1 / 31

A puzzle from antiquity . . .
The Logician/Philosopher vs. the Astronomer/Mathematician :“Chrysippus says that the number of conjunctionsa [constructible] fromonly ten assertibles exceeds one hundred myriads [i.e. 106 ]. However, Hipparchus refuted this, demonstrating that the affirmative encompasses 103049
conjoined assertibles and the negative 310952.”— Plutarch, Quæstiones Convivales (2nd C. AD)a ‘combinations’ in some documents . . .

This was reported as common knowledge,“Chrysippus is refuted by all the arithmeticians, among them Hipparchus
himself who proves that his error in calculation is enormous”.
— Plutarch, De Stoicorum Repugnantiis (2nd C. AD)
but the precise meaning was lost.
“Since the exact terms of the problem are not stated, it is difficult to interpret the numerical answers . . . The Greeks took no interest in these matters”.
— N. L. Biggs The Roots of Combinatorics 1979
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

2 / 31Interpretation and Composition
The significance of 103049 was realised in 1994 by Daniel Hough :Hipparchus, Plutarch, Schröder, and Hough— R. Stanley, American Mathematical Monthly (1997)
It is simply the 10th little Schröder number, counting (amongst other things1 ) the
number of distinct Rooted Planar Trees with ten leaves.
A natural (too easy?) interpretation
We may view :1Each branching as a logical operation (conjunction?)

2

Each leaf as a simple assertible (variable?)

Building larger trees from smaller trees : Substituting a tree for a given leaf.

1 e.g. the number of facets of the tenth associahedron
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

3 / 31

Replacing simple assertibles by non-simple composites
Operadic Composition :
v22
v2

v3

v1

and

v11

˝2

v21

v5

and

v32

v42

and

v52

v4
v31

“

v12

v62

and

and
v72

and
and
and

Provided we
Avoid clashes of free variable names, & identify α-equivalent trees,
Identify up to (half-planar) topological equivalence,
we arrive at the non-symmetric operad RPT of rooted planar trees.
This is freely generated by one tree of each arity (number of leaves).
"
,
,
,
, ...
‚

‚

peter.hines@york.ac.uk

‚

‚

‚

‚

‚

‚

‚

01232 457964

‚

‚

‚

*

‚

‚

nihil sub sōle novum

4 / 31Counting Conjunctions ...
How did Hipparchus (and “all the arithmeticians”) calculate Schröder numbers??
On the Shoulders of Hipparchus:
A Reappraisal of Ancient Greek Combinatorics.
— F. Acerbi (2004)
Why should we be interested?
Chrysippus’ main achievement is the development of a propositional logic& deductive system2 . He was innovative in topics central to contemporary
formal and philosophical logic. The many close similarities with Gottlob Frege
are especially striking.
— Stanford Encyclopedia of Philosophy
How & why did Chrysippus & Hipparchus come up with such different values?
Combinatorics for Stoic Conjunction:
Chrysippus Vindicated, Hipparchus Refuted.
Oxford Studies in Ancient Philosophy, S. Bobzien (2011)

2 best understood as a substructural backwards-working Gentzen-style natural-deduction
system — S.E.P.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

5 / 31Counting Conjunctions ...
How did Hipparchus (and “all the arithmeticians”) calculate Schröder numbers??
On the Shoulders of Hipparchus:
A Reappraisal of Ancient Greek Combinatorics.
— F. Acerbi (2004)
Why should we be interested?
Chrysippus’ main achievement is the development of a propositional logic& deductive system2 . He was innovative in topics central to contemporary
formal and philosophical logic. The many close similarities with Gottlob Frege
are especially striking.
— Stanford Encyclopedia of Philosophy
How & why did Chrysippus & Hipparchus come up with such different values?
Combinatorics for Stoic Conjunction:
Chrysippus Vindicated, Hipparchus Refuted.
Oxford Studies in Ancient Philosophy, S. Bobzien (2011)

2 best understood as a substructural backwards-working Gentzen-style natural-deduction
system — S.E.P.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

5 / 31Counting Conjunctions ...
How did Hipparchus (and “all the arithmeticians”) calculate Schröder numbers??
On the Shoulders of Hipparchus:
A Reappraisal of Ancient Greek Combinatorics.
— F. Acerbi (2004)
Why should we be interested?
Chrysippus’ main achievement is the development of a propositional logic& deductive system2 . He was innovative in topics central to contemporary
formal and philosophical logic. The many close similarities with Gottlob Frege
are especially striking.
— Stanford Encyclopedia of Philosophy
How & why did Chrysippus & Hipparchus come up with such different values?
Combinatorics for Stoic Conjunction:
Chrysippus Vindicated, Hipparchus Refuted.
Oxford Studies in Ancient Philosophy, S. Bobzien (2011)

2 best understood as a substructural backwards-working Gentzen-style natural-deduction
system — S.E.P.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

5 / 31Counting Conjunctions ...
How did Hipparchus (and “all the arithmeticians”) calculate Schröder numbers??
On the Shoulders of Hipparchus:
A Reappraisal of Ancient Greek Combinatorics.
— F. Acerbi (2004)
Why should we be interested?
Chrysippus’ main achievement is the development of a propositional logic& deductive system2 . He was innovative in topics central to contemporary
formal and philosophical logic. The many close similarities with Gottlob Frege
are especially striking.
— Stanford Encyclopedia of Philosophy
How & why did Chrysippus & Hipparchus come up with such different values?
Combinatorics for Stoic Conjunction:
Chrysippus Vindicated, Hipparchus Refuted.
Oxford Studies in Ancient Philosophy, S. Bobzien (2011)

2 best understood as a substructural backwards-working Gentzen-style natural-deduction
system — S.E.P.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

5 / 31Counting Conjunctions ...
How did Hipparchus (and “all the arithmeticians”) calculate Schröder numbers??
On the Shoulders of Hipparchus:
A Reappraisal of Ancient Greek Combinatorics.
— F. Acerbi (2004)
Why should we be interested?
Chrysippus’ main achievement is the development of a propositional logic& deductive system2 . He was innovative in topics central to contemporary
formal and philosophical logic. The many close similarities with Gottlob Frege
are especially striking.
— Stanford Encyclopedia of Philosophy
How & why did Chrysippus & Hipparchus come up with such different values?
Combinatorics for Stoic Conjunction:
Chrysippus Vindicated, Hipparchus Refuted.
Oxford Studies in Ancient Philosophy, S. Bobzien (2011)

2 best understood as a substructural backwards-working Gentzen-style natural-deduction
system — S.E.P.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

5 / 31

A misunderstanding of logic?

Bobzien’s claim is that, “Hipparchus, it seems, got his mathematics right. What I
suggest in this paper is that he got his Stoic logic wrong.”
Where it starts going wrong :“He counts the same sequence of conjuncts but with different bracketing as different
conjunctions . . . He counts
rP ^ Qs ^ R

P ^Q^RP ^ rQ ^ Rs

as different assertibles. Unlike modern propositional logic, Hipparchus assumes that a[elementary] conjunction can consist of two or more conjuncts.
In order to get to [the little Schröder number 103049], Hipparchus also had to take theorder of the ten atomic assertibles as fixed.‘” – S. B.

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

6 / 31

A synthesis via category theory
Between ‘equal’ and ‘not equal’ lies a compromise :equal up to

The Same

unique isomorphism

DifferentThis should be understood at the level of semantic models.
What might we need ?
A family of k -ary elementary conjunctions
p ‹ q

,

p ‹ ‹ q,p ‹ ‹ ‹ q,...

(presumably, functors . . . )Under substitution / operadic composition these should freely generate an operad
isomorphic to RPT.
A notion of ‘equivalence up to natural isomorphism’ that uniquely relates any two
composites of the same arity.

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

7 / 31

A substructural / relevance logic ! ?
We need to take into account (lack of) structural rules :Stoic Sequent Logic and Proof Theory History & Philosophy of Logic (2019)“Much of Stoic logic appears surprisingly modern: a recursively formulated syntax. . . analogues to cut rules, axiom schemata and Gentzen’s negation-introduction
rules. . . a deliberate rejection of Thinning [Weakening]”

What about contraction / idempotency of conjunction?
“Non-simple [assertibles] are those that are, as it were, double pδιπλαq – put together
by means of a connecting particle from two different assertibles, or an assertiblethat is taken twice pδιζq.” — Sextus Empiricus (M8), quoted in S. B.
For convenience, we will :borrow & generalise a model of conjunction from Linear Logic.
(As a bonus!) Everything is based on Euclidean division.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

8 / 31

A substructural / relevance logic ! ?
We need to take into account (lack of) structural rules :Stoic Sequent Logic and Proof Theory History & Philosophy of Logic (2019)“Much of Stoic logic appears surprisingly modern: a recursively formulated syntax. . . analogues to cut rules, axiom schemata and Gentzen’s negation-introduction
rules. . . a deliberate rejection of Thinning [Weakening]”

What about contraction / idempotency of conjunction?
“Non-simple [assertibles] are those that are, as it were, double pδιπλαq – put together
by means of a connecting particle from two different assertibles, or an assertiblethat is taken twice pδιζq.” — Sextus Empiricus (M8), quoted in S. B.
For convenience, we will :borrow & generalise a model of conjunction from Linear Logic.
(As a bonus!) Everything is based on Euclidean division.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

8 / 31

A substructural / relevance logic ! ?
We need to take into account (lack of) structural rules :Stoic Sequent Logic and Proof Theory History & Philosophy of Logic (2019)“Much of Stoic logic appears surprisingly modern: a recursively formulated syntax. . . analogues to cut rules, axiom schemata and Gentzen’s negation-introduction
rules. . . a deliberate rejection of Thinning [Weakening]”

What about contraction / idempotency of conjunction?
“Non-simple [assertibles] are those that are, as it were, double pδιπλαq – put together
by means of a connecting particle from two different assertibles, or an assertiblethat is taken twice pδιζq.” — Sextus Empiricus (M8), quoted in S. B.
For convenience, we will :borrow & generalise a model of conjunction from Linear Logic.
(As a bonus!) Everything is based on Euclidean division.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

8 / 31

“Everything is [in the endomorphism monoid of] Numbers”
In J.-Y. Girard’s Geometry of Interaction system (Parts 0 – 2) :Propositions are modelled by functions on N.
Bijections in the symmetric group SpNq for MLL
Partial injections in the symmetric inverse monoid IpNq for MELL
Conjunction is modelled by the following operation :pf ‹ gqp2nq“

2.f pnqpf ‹ gqp2n ` 1q“

2.gpnq ` 1

A simple description, based on Hilbert’s Grand HotelThis “writes two functions as a single function”, byreplicating their behaviour on the even and odd numbers respectively.
This is an injective homomorphism SpNq ˆ SpNq ãÑ SpNq, and indeed acategorical (semi-monoidal) tensor
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

9 / 31

Potential vs. actual infinity
The Greeks feared infinity and tried to avoid it . . . According to tradition,
they were frightened off by the paradoxes of Zeno. . . . Until the late C 19th ,mathematicians were reluctant to accept infinity as more than “potential”.
— J. Stillwell, Mathematics and Its History 2012
Not Euclid There exists an infinite number of primes.
Euclid The prime numbers are more numerous
than any proposed multitude of prime numbers.
Actual infinity was eventually forced by the requirements of medieval theology:
Duns Scotus on God (R. Cross, 2005)
John Duns Scotus (1266-1308) [ontological] argument may be summarised as,“If God is composed of parts, then each part must be finite or infinite. . . . If any given
part is infinite, then it is equal to the whole, which is absurd”
John Duns’ absurdity was was (mostly!) stripped of theological interpretations,and taken as a definition by G. Cantor.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

10 / 31

Not strictly the same . . .
In general :pP ‹ Qq ‹ R ‰ P ‹ pQ ‹ Rq

No faithful tensor on a non-abelian monoid can be strictly associative.
Coherence & Strictification for Self-Similarity
Journal Homotopy & Related Structures (P.M.H. 2016)

There is a non-trivial natural isomorphism p ‹ p ‹ qq ñ pp ‹ q ‹ q@ a, b, c P SpNq$
2nn ” 0 mod 2,’&n`1n ” 1 mod 4,
whose unique component (the associator) αpnq “’% n´1n ” 3 mod 4,
αpa ‹ pb ‹ cqq “ ppa ‹ bq ‹ cqα2satisfies MacLane’s pentagon condition
α2 “ pα ‹ Idq α pId ‹ αqpeter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

11 / 31

A Hipparchus-style generalisation
Girard gave a binary model of conjunction p ‹ q : SpNq ˆ SpNq ãÑ SpNq.
“pa ‹ bq replicates a, b on the modulo classes 2N, 2N ` 1 respectively”.
‚‚

We draw this as‚

There is an obvious ternary analogue, p ‹ ‹ q : SpNq ˆ SpNq ˆ SpNq ãÑ SpNq$i “0& 3.apnq
3.bpnq ` 1
i “1
pa ‹ b ‹ cqp3n ` iq “%
3.cpnq ` 2
i “2“Replicate a, b, c on the modulo classes 3N , 3N ` 1 , 3N ` 2 respectively”.
‚‚‚

We draw this as‚

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

12 / 31The general case :For any k ě 1, we form the k th elementary conjunction by :pf0 ‹ . . . fk ´1 qpkn ` iq “ k .fi pnq ` i where i “ 0, 1, 2, . . . , k ´ 1
Alternatively & equivalently,ˆ
pf0 ‹ . . . fk´1 qpxq “ k .fi

˙

x ´i
k

` i where x ” imod kThis gives, for any k ą 0, an injective group homomorphism SpNqˆk ãÑ SpNq that :“replicates the action of f0 , f1 , . . . , fk´1 on the modulo
classes kN , k N ` 1 , . . . , k N ` pk ´ 1q respectively.
For k “ 1, 2, 3, 4, . . ., we draw these as
"
,
,
‚

‚

‚

‚

‚

peter.hines@york.ac.uk

‚

*
‚

‚

‚

01232 457964

,

‚

‚

‚

‚

,

...

‚

nihil sub sōle novum

13 / 31Composing elementary conjunctions
These ‘compose by substitution’ to give an operad Hipp of generalised
conjunctions. Each k -leaf tree determines an injective hom. SpNqˆk ãÑ SpNq.
¨
¨

¨

¨

¨
¨

: SpNqˆ5 ãÑ SpNq¨¨
pf0 , f1 , f2 , f3 , f4 q

ÞÑ ppf0 ‹ pf1 ‹ f2 ‹ f3 qq ‹ f4 q

More formally :We have one operation of each arity ą 0 in the (non-symmetric) endomorphism
operad of SpNq within the category pGrp, ˆq of groups / homomorphisms with
Cartesian product.
These generate the sub-operad Hipp.

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

14 / 31

An operad for Hipparchus

Claim :The operad Hipp of generalised conjunctions extends Girard’s operationfrom the Geometry of Interaction, to provide a semantic model for
Hipparchus’ (mis-)understanding of Chrysippus’ Stoic Logic.

More concisely(!)
Hipp – RPT, so each tree determines a distinct homomorphism SpNqˆk ãÑ SpNq.
Proof?
Proving this requires a concept the Greeks (notoriously) did not have3 :The greatest calamity in the history of science was the failure ofArchimedes to invent positional notation. – C. F. Gauss
3 . . . but may (occasionally) have borrowed from their neighbours
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

15 / 31

Let me see you counting like they do in Babylon
¨

¨

¨

¨

¨
¨

defines a homomorphism : SpNqˆ5 ãÑ SpNq¨¨In the operadic composite pf0 , f1 , f2 , f3 , f4 q ÞÑ ppf0 ‹ pf1 ‹ f2 ‹ f3 qq ‹ f4 q, the action of eachfj is mapped :from The whole of the natural numbers N
to Some modulo class Aj N ` Bj .
For example : f3 is translated onto 12N ` 10.
Question:
How do we derive these coefficients from the tree?
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

16 / 31

Leaves as modulo classes

The Fifth Associahedron K5

label the leaves of a chosen edgeof K5 by modulo classes(Diagram “borrowed” from Tai-Danae
Bradley’s www.math3ma.com blog.)

12N ` 2

12N ` 64N

12N ` 10¨
2N ` 1¨¨

All modulo classes are disjoint. Their union is the whole of N.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

17 / 31The multiplicative coefficients

Multiplicative coefficients

12N ` 24N ` 012N ` 6In leaf-traversal ordering
4

“

2ˆ2

12

“

2ˆ2ˆ3

12

“

2ˆ2ˆ3

12

“

2ˆ2ˆ3

2

“

2 (!)

12N ` 103-fold2-fold2N ` 12-foldTo find multiplicative parts . . .
Multiply the arities of each branching, from root to leaf.

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

18 / 31

Counting paths
Additive coefficients

12N ` 2

12N ` 60

4N ` 0

1

Path from leaf to root
Base 20Base 20Base 30Base 2
1

Base 20“Base 31

Base 2
1

Base 20

10“Base 32

Base 2
1

Base 2
0

1

“

0

“

2

“

6

12N ` 1023-fold012-fold2N ` 10

12-foldBase 2
1

To find additive parts . . .
Write down the ‘address’ of each leafa& treat it as a number in a mixed-radix counting system(with bases determined by the number of branchings).
a in leaf-to-root order!

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

19 / 31

A Root & Branch approach

Rooted Planar Trees are uniquely determined by the “addresses” of their leaves,which uniquely determine (ordered) exact covering systems.
Heavily studied by P. Erdös (1950s)
Sets of pairwise-disjoint modulo classes, whose union is the whole of N
This is based on mixed-radix counting systems
First formal study by G. Cantor, Über einfache Zahlensysteme (1869)(Corol: Distinct trees determine distinct homomorphisms).

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

20 / 31

Mappings between between gen. conjunctions
Given generalised conjunctions T , U : SpNqˆk ãÑ SpNq, can we find a (well-behaved)
natural isomorphism between them?
T

SpNqˆk)??

5 SpNqU

A simplification : As generalised conjunctions are monoid homomorphisms,
natural transformations have a single component.
We identify nat. iso.s with their unique components in SpNq.

A fuller analysis of natural transformations in the single object setting :“Monoidal Categories — a unifying concept in math., physics, & C.S.”
Noson Yanofsky (M.I.T. Press appearing shortly )peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

21 / 31

Congruential functions as natural isomorphisms
Consider the generalised conjunctions4 T , U : SpNqˆ5 ãÑ SpNq
¨

¨

¨
¨

¨
T “

¨

¨
¨

U“

¨

¨
¨

¨
¨

¨
¨
¨

We build a natural isomorphism ηT ,U : T ñ U by monotonically mapping between theirrespective ordered covering systems :leaf 0leaf 1
leaf 2leaf 3leaf 44N
12N ` 2
12N ` 6
12N ` 102N ` 1

ÞÑ
Þ
Ñ
ÞÑ
ÞÑ
ÞÑ

6N
6N ` 33N ` 1
6N ` 2
6N ` 4This gives, as desired,ηT ,U .ppa ‹ pb ‹ c ‹ dqq ‹ eq “ ppa ‹ bq ‹ c ‹ pd ‹ eqq.ηT ,U
4 edges of the fifth associahedron K
peter.hines@york.ac.uk

501232 457964

nihil sub sōle novum

22 / 31

A category for Chrysippus

Observe that :ηT ,T “ Id P SpNq
ηT ,U ηS,T “ ηS,U
ηT´1
,U “ ηU,T
We have a posetal groupoid Chrys of functors / natural iso.s, given by :Objects Generalised conjunctions (operations of Hipp)$
T , U have the same arity,& tηT ,U u
Arrows ChryspT , Uq “%Hotherwise.

As this groupoid is posetal, all diagrams commute.

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

23 / 31

Unbiased tensors on a posetal groupoid
We may equip Chrys with a family of unbiased tensors, one of each arity :Given homomorphisms T0 , . . . , Tx P ObpChrysq, we define
T0

T1

Tx

def .

pT0 b . . . b Tx q “...

¨Rather neatly (but entirely expectedly) :The unique arrow T0 b . . . b Tx ñ U0 b . . . b Ux is given by
ηpT0 b...bTx q,pU0 b...bUx q “ pηT0 ,U0 ‹ . . . ‹ ηTx ,Ux q

Generalised conjunction defines N` -indexed family of functors on a posetal groupoid :#+ź
p b ... b q :Chrys Ñ ChryskkPN`

Very special case: Chrys contains a copy of (a unitless version of) MacLane’s posetal monoidal groupoid pW, l q.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

24 / 31

Concrete formulæ for arrows of Chrys
Given two ordered exact covering systems, determined by k-ary generalised
conjunctions T , U
leaf 0A0 N ` B0ÞÑ

C0 N ` D0

leaf 1A1 N ` B1

ÞÑC1 N ` D1

..
.

..
.

leaf k ´ 1

Ak ´1 N ` Bk´1

..
.
ÞÑ

Ck ´1 N ` Dk´1

The natural isomorphism ηT ,U is the bijectionˇˇ˙ˆˇ A Bj ˇ1ˇ where x ” Bj
ηT ,U pxq “Cj x ` ˇˇ j
Cj Dj ˇAj

mod AjWe arrive at congruential functions, introduced in“Unpredictable Iterations” — J. Conway (1972)
to demonstrate undecidability in elementary arithmetic.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

25 / 31Bobzien’s ‘three simple assertibles’ example
pp ‹ q ‹ q ks

α

ai

γ5

$ 4n
’
& 3
γ5 pnq “
’
%

4n`2
3
2n´1
3

p ‹ p ‹ qq

6>p ‹ ‹ qn ” 0 mod 3,
n ” 1 mod 3,

γ

$ 2n
’
& 3

n ” 0 mod 3,’%

n ” 2 mod 3.

γpnq “n ” 2 mod 3.

4n´1
3
4n`1
3

$
2n
’
&
n`1
αpnq “’% n´1
2n ” 1 mod 3,

n ” 0 mod 2,
n ” 1 mod 4,
n ” 3 mod 4,

These are familiar from other areas :α : the associator for the conjunction from G.O.I.
γ : the amusical permutation from a (unresolved) conjecture of Collatz.
γ5 : the flattened permutation, defined by 1 ` γ5 pnq “ γpn ` 1q.
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

26 / 31

From the third to the fourth associahedron
We can label (most of) K4 using conjunctions / composites of labels from K3 .
αpp ‹ q ‹ q ‹p ‹ q‹p ‹ q

γ ´1

γ5
γ5 ‹
Id

γ5
pp ‹ q ‹ ‹ q

qγ 5
Id
1 ‹

α ‹ Id

γ ´1
γ5

´

pγ 5
pp ‹ ‹ q ‹ q

γq

d

qγ 5
p ‹p ‹ q‹ qγ5p ‹ p ‹ ‹ qq

γ ´1 pId ‹ γ5 q

‹ p ‹ p ‹ qq

Id ‹ γ ´1

α

γ ´1

Id ‹

γ5

p ‹ p ‹ qq ‹

γ ´1

γ ´1
pId ‹

´1 ‹ Id‹Ip ‹ ‹ p ‹ qq

pγ

1
´

γ

α

Id ‹ αp ‹ pp ‹ q ‹ qpeter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

27 / 31

Context for the “amusical permutation”

Conway’s classic Unpredictable Iterations (1972) paper5 exhibited
undecidability of iterative problems on congruential functions.
He discussed his motivation in (among other places) :Unsettleable Arithmetic Problems – J. Conway 2012

“What is the simplest Collatz-style game that we can expect to be
undecidable? I think I have an answer!” — J. C.

5 See also Sergei Maslov, On E. L. Post’s Tag Problem (1964)
peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

28 / 31

What is this “simplest undecidable game”?

The 3x ` 1 problem & its generalisations – Jeffrey Lagarias (1985)
Writing about L. Collatz : ”In his notebook dated July 1, 1932, he considered thefunction
$ 2
’
’ 3n
’
’
&
4
γpnq “n ´ 13
3
’
’
’
’
% 4
n ` 13
3

if n ” 0 pmod 3q
if n ” 1 pmod 3q
if n ” 2 pmod 3q

He posed the problem of whether the cycle containing 8 is finite or infinite. I will callthis the Original Collatz Conjecture. His original question has never been answered.

John Conway called this bijection the Amusical Permutation & claimed the OCC as“The simplest undecidable (& therefore ‘true’) arithmetic statement.”

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

29 / 31

Melodic Conjectures?
A “probvious” conjecture!
“The proportion of fallacies in published proofs is far greater than the small
positive probability that [this conjecture is false]”– J.C., Unsettleable Algebraic Problems (2012)
A plot of n : log pγ n pkqq, for k “ 8, 14, 40, 64, 80, 82

γ 200000 p8q « 105000

peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

30 / 31

It goes like this, the fourth, the fifth ...
“There are twelve notes per octave, which represents a doublingof frequency, just as twelve steps [of γ or γ ´1 ] approximately
doubles a number, on average.” — J.C. (2012)
This average-case doubling is not exact :12[The amusical permutation] doubles by a factor of 2318 « 2
20[Its inverse] doubles by a factor of 2312 « 2
12“A frequency ratio of 3219 is called the Pythagorean comma
and is the difference between enharmonically equivalent
notes (e.g. A7 and B 5 ). So there really is a connection withmusic.”b
Exact doubling / the octave is given by their geometric mean

312 220.
218 312“ 2.

The amusing musical permutation“Since the series always ascends by a fifth, modulo octaves, it does not sound very
musical. It has always amused me to call it amusical.”peter.hines@york.ac.uk

01232 457964

nihil sub sōle novum

31 / 31