[FOM] 292: Concept Calculus 1

Harvey Friedman friedman at math.ohio-state.edu
Sat Jun 17 17:26:36 EDT 2006


We first make a correction in section 3 of 291: Independently Free
Minds/Collectively Random Agents/more.

We wrote

AXIOM SCHEME 5. TRANSITION HORIZON EFFECT. Any true statement about any
given time remains true if we hypothetically restrict the transitions to
those that are at least any given transition after the given time.

This should be 

AXIOM SCHEME 5. TRANSITION HORIZON EFFECT. Any true statement about any
given time remains true if we hypothetically restrict the transitions to
those that are at most the given time or at least any given transition after
the given time. 

AXIOM SCHEME 5. TRANSITION HORIZON EFFECT. t1 < t implies (phi implies
phi[>=t]), where phi is any formula in the language of IFM/CRA with eternal
transitions, with at most the free variable t1, in which t1,t are not bound.
Here phi[<=t1,>=t] is the result of replacing each T[ti] by (T[ti] and (ti
<= t1 or t <= ti). 

##########################################

CONCEPT CALCULUS 1
by
Harvey M. Friedman 
June 17, 2006

Introduction.
1. Varying Quantity, Common Scale.
2. Varying Quantity, Common Scale, Transitions.
3. To be continued.

INTRODUCTION.

This new development is an improved reworking of the previous two part
series http://www.cs.nyu.edu/pipermail/fom/2006-June/010611.html
and its successor, #291. We do not rely on these earlier postings.

We present various basic theories involving fundamental concepts of naïve
thinking, of the sort that were common in "natural philosophy"  before the
dawn of substantial physical science.

Substantial physical science, as we know it, is based on the usual real
numbers.

Here we instead use linear orderings, and formulate principles that are
incompatible with identifying these linear orderings with the real numbers,
or segments thereof. The principles have a clear conceptual meaning to any
naïve thinker.  

We are nowhere near the stage in this development to seriously contemplate
the overthrow of the real number orthodoxy in physical science. That would
be grossly premature, and may never be appropriate.

Our aims are quite different and more philosophical:

i. We show how a complex of very simple intuitive ideas that can be absorbed
and reasoned with by naïve thinkers, leads surprisingly quickly and
naturally to a consistency proof for mathematics (ZFC, even with large
cardinals). Thus these naïve ideas are surprisingly powerful in light of the
fact that mathematics itself is not sufficient to prove its own consistency
(in the sense of Godel's second incompleteness theorem).

ii. Armed with this array of very powerful naïve principles, we can search
for entirely new contexts in which principles of a similar nature arise with
similar results. There may be more richly philosophical or theological
contexts in which these emerging naïve principles are particularly
compelling, and relevant to ordinary thinking and life experiences.

iii. In particular, there may be contexts in which there are orderings but
where the very idea of quantitative measurement (as presently construed) is
inappropriate or even absurd, and so there will not be or cannot be any
associated real number orthodoxy. For example, "x is more beautiful than y".
Or "idea x is more interesting than idea y". Or "act x is morally preferable
to act y". Or "agent x is morally superior to agent y". Or "outcome x is
more just than outcome y". Or "act x is more pleasurable than act y." Or
"activity x is preferable to activity y" or "state of affairs x is
preferable to sate of affairs y".

iv. What is emerging is a true calculus of conceptual principles, whose
"logical strengths" is being "calculated". There is already an entirely
solid mathematical basis for the comparison of theories formulated in first
order predicate calculus. This is through the fundamental notion of
*interpretation* or *interpretability* due to Alfred Tarski.

v. We call this prospective calculus of conceptual principles,

the CONCEPT CALCULUS.

vi. What is the methodology of the Concept Calculus? We identify fundamental
informal notions from ordinary thinking, particularly from philosophical
subjects where there is a rich literature of discussion going back for long
periods of time (e.g., several centuries or millennia).

We then consider various combinations of fundamental principles capable of
clear and concise formulation.

We then experiment with appropriate combinations of such principles. Some of
these first order theories may of course be incompatible with others.

We then "calculate" the logical strengths of these theories.

Here logical strength has come to mean "interpretation power". Calculating
logical strength has come to mean

a) an identification of a theory among the robust linearly ordered hierarchy
of set theories, arising out of the foundations of mathematics.

b) the verification that the theory in question is mutually interpretable
with the identified set theory.

Thus the "measuring tool" is the robust hierarchy of set theories developed
already in the foundations of mathematics.

vii. This measuring tool is the appropriate tool needed to compare the
logical strengths of two interesting theories arising in Concept Calculus.
For, let S and T be two theories arising in Concept Calculus. To compare S
and T, we first calculate the logical strengths of S,t in the sense above -
through identifying the appropriate two levels of set theory. Then we can
merely note the comparison of these two levels of set theory.

viii. This is directly analogous to the measurement of, say, the height of
buildings. First they are measured in, say, meters  - as, say, a base 10
rational. Then the two base 10 rationals are compared. Generally, one may
only commit to an interval and not a single number, where the intervals are
both small enough that the comparison can be made.

ix. We are at the very beginning of the development of Concept Calculus, and
here great experience with set theories and various techniques developed
from mathematical logic are needed to obtain the first significant results.
In particular, one has to be facile with how to interpret set theories and
interpret into set theories in a wide variety of contexts.

x. However, at some point, basic tools will develop that will make the
development of Concept Calculus more amenable to more scholars. In
particular, what I want to do now is to develop an array of most basic
theories for which I can calculate - or approximately calculate - their
logical strength. Then, scholars can work with these basic theories - which
should be more 'friendly' than set theories - in order to make calculations,
or at least the interpretations needed for approximate calculations.

We will make a number of calculations in Concept Calculus. For a while, we
will not try to operate fully systematically, as our main interest at the
moment is in showing how naturally one obtains theories that are at least as
strong, logically, as mathematics - as identified with ZFC.

1. VARYING QUANTITY, COMMON SCALE.

This is a particularly basic context. We have a quantity that varies over
time. We will operate under the assumption that the time scale and the
quantity scale are identical. In section 2, when we add Transitions, we will
obtain strength far beyond that of ZFC - and in particular provide a
consistency proof for mathematics.

If we are doing normal mathematical science, then the time scale might
typically be [0,infinity) in the usual mathematical real line, and the
quantity scale would also be the same [0,infinity). The system would be
described mathematically by a function

f:[0,infinity) into [0,infinity)

the idea being that the quantity in question at time t has value f(t).

Here we take a naïve approach. We view [0,infinity) as simply some
unspecified linear ordering representing time (since the big bang or
creation), without identifying it with the nonnegative real numbers. We also
view [0,infinity) as the range of values of a quantity that varies over
time. We will not be committed to having a first time.

We introduce various axioms formulated in the usual first order predicate
calculus with equality, based on the following:

1. The binary relation symbol <.
2. The constant symbol 0.
3. The unary function symbol F.

We refer to this language as LOF(0) = linearly ordered function with 0.

We begin with the fundamental basis of everything that we do.

LINEARITY. < is a strict linear ordering, with the left endpoint 0, and no
right endpoint. 

The first major idea that drives this development is

*time is so vast, that any possibility will eventually occur*

The most primitive and obvious way of saying this is simply

ARBITRARY VALUES. Every value is achieved.

ARBITRARY VALUES. (therexists x)(F(x) = y).

This is of course inherent in everything that we do, but it is far too weak
to be breaking any new ground.

Let us refine * as follows.

**time is so vast, that any possible behavior over intervals eventually
occurs**

For our purposes, intervals are of the following forms:

[q,b].
(a,b).
[a,b).
(a,b].
[a,infinity).
(a,infinity).

where a,b are points. The bounded intervals are the intervals of the first
four forms. We allow a = b and a > b, thus incorporating degenerate
intervals. 

We will freely use interval notation in the formal presentation of various
axioms.

Now, in our very primitive language, we are of course limited in just what
"any possibilities" covers.

In light of our minimalistic first order approach, it is natural to fix on
the range of values in an interval. More general aspects of behavior can
also be handled in our minimalistic first order approach, and we will take
some preliminary steps in this direction later in this section.

ARBITRARY RANGES. Every range of values is realized over some interval.

There is a kind of Cantor diagonal argument or Russell paradox inherent in
Arbitrary Ranges, as we shall see.

The really appropriate principle is

ARBITRARY BOUNDED RANGES. Every bounded range of values is realized over
some bounded interval.

We view Arbitrary Bounded Ranges as formulating a kind of "randomness" or
"creativity". It does not correspond to any existing such notions, but we
claim that it has a kind of naïve conceptual clarity.
 
Here are the formal statements. We use the usual abbreviations <=, >, >=.

LINEARITY. not x < x, (x < y and y < z) implies x < z ,x <= y or y <= x, 0
<= x, (therexists y)(x < y).

ARBITRARY RANGES. (therexists an interval J)(forall x)((therexists y in
J)(F(y) = x) iff phi), where phi is a formula in LOF in which y and the
variables used to present J are not free.

THEOREM 1.1. Linearity + Arbitrary Ranges is inconsistent.

ARBITRARY BOUNDED RANGES. (therexists a bounded interval J)(forall
x)((therexists y in J)(F(y) = x) iff (phi and x <= z)), where phi is a
formula in LOF in which y and the variables used to present J are not free.

THEOREM 1.2.  Linearity + Arbitrary Bounded Ranges is mutually interpretable
with finite set theory (e.g., PA = Peano Arithmetic, and ZFC\I = ZFC without
infinity). This is provable in EFA = exponential function arithmetic.

Let us return to the idea behind Arbitrary Bounded Ranges - that any
behavior over intervals is realized.

We can consider the behavior on the interval [0,infinity), and say that it
is emulated on some bounded interval J. Note that the interval J must be of
the form [x,y), since [0,infinity) has a least but no greatest element.

But how do we formulate this? Certainly not in terms of having the same
range of values.

REMARK: In this development, we very strongly have a unique direction of
time. END.

GLOBAL/LOCAL. Any true statement remains true when the quantifiers are
relativized to some bounded interval.

GLOBAL/LOCAL. (therexists x,y)(phi implies phi|[x,y)), where phi is a
sentence in LOF(0) and | indicates the relativization of all quantifiers to
the displayed interval.

It is also very natural to insist that the left endpoint of J be 0.

GLOBAL/LOCAL (0). (therexists x)(phi implies (phi|[0,x)), where phi is a
sentence in LOF(0) and | indicates relativization of all quantifiers to the
displayed interval.

Furthermore, it is entirely natural to emulate the behavior on intervals
[x,infinity). 

GLOBAL/LOCAL (initial). Any true statement over [x,infinity) remains true
over some [x,y). 

THEOREM 1.3. The following theories are mutually interpretable with
countable set theory (e.g., Z_2, and ZFC\P = ZFC without the power set
axiom). This is provable in EFA.
i. Linearity + Arbitrary Bounded Ranges + Global/Local.
ii. Linearity + Arbitrary Bounded Ranges + Global/Local (initial).

It is natural to strengthen GLOBAL/LOCAL by introducing constant symbols to
LOF which provide a single fixed interval for Global/Local. In fact, we can
introduce a single constant c for this purpose, and use [0,c), as in
Global/Local (0). Theorem 1.3 will still hold.

We can also take this step for Global/Local (initial), by adding a unary
function symbol, and use the expanded language for Arbitrary Bounded Ranges.
Theorem 1.3 will still hold.

2. VARYING QUANTITY, COMMON SCALE, TRANSITIONS.

To make further progress in terms of logical strength, in the most natural
way, we introduce transitions. Transitions are certain special points.

We can think of transitions as marking the beginnings of new epochs. In
particular, the idea is that any two transitions are unimaginably far apart,
so as to support certain alternate formulations of Arbitrary Bounded Ranges.

Later, we will make use of a second idea about transitions. Namely, that
transitions all look the same in various senses.

Thus in this section, we work with the language LOF(0,T), which expands
LOF(0) with the unary predicate symbol T. I.e., T(x) means "x is a
transition". 

Now that we have introduced the crucial concept of transitions, we start
over. Again, we begin with

LINEARITY. < is a strict linear ordering, with the left endpoint 0, and no
right endpoint. 

TRANSITIONS. Every point is less than some transition.

A particularly fundamental idea about transitions is that any prospective
behavior of an interval that involves only points at or before a given
transition can be realized by some interval bounded by any later transition.

DOUBLE TRANSITION RANGES. Every range of values bounded by a given
transition is realized over some interval bounded by any later transition.

DOUBLE TRANSITION RANGES. (x < y and T(x) and T(y)) implies (therexists J
containedin [0,y])(forall z)((therexists w in J)(F(w) = z) iff (phi and z <=
x)), where phi is a formula in LOF(0,T) in which y and the variables used to
present J are not free.

There is an important strengthening of Double Transition Ranges.

SINGLE TRANSITION RANGES. Every range of values bounded by a given point
before a given transition is realized over some interval whose right
endpoint is also before the given transition.

SINGLE TRANSITION RANGES. (x < y and T(y)) implies (therexists J,z)(z < y
and J containedin [0,z] and (forall w)((therexists u in J)(F(u) = w) iff
(phi and w <= x))), where phi is a formula in LOF(0,T) in which y and the
variables used to present J are not free.

THEOREM 2.1. Linearity + Double Transition Ranges is mutually interpretable
with finite set theory (e.g., PA, and ZFC\Inf). This is provable in EFA.

THEOREM 2.2. Linearity + Single Transition Ranges is mutually interpretable
with ZC + "for all n, V(omega x n) exists". This is provable in EFA.

We now consider principles of similarity of transitions.

TRANSITION INTERVAL SIMILARITY. Any statement true over any interval whose
left endpoint is before its right endpoint, and whose right endpoint is a
transition, remains true if the right endpoint is changed to any later
transition. 

TRANSITION INTERVAL SIMILARITY. (x < y < z and T(y) and T(z) and phi[(x,y)])
implies phi[(x,z)], (x < y < z and T(y) and T(z) and phi[[x,y]]) implies
phi[[x,z]], (x < y < z and T(y) and T(z) and phi[(x,y]]) implies phi[(x,z]],
(x < y < z and T(y) and T(z) and phi[[x,y)]) implies phi[[x,z)], where phi
is a formula in LOF(0) in which z does not appear.

TRANSITION SIMILARITY. Any true statement involving a given point and some
later transition is also true of the given point and any later transition.

TRANSITION SIMILARITY. (x < y < z and T(y) and T(z) and phi) implies
phi[y/z], where phi is a formula in LOF(0) in which z does not occur.

WEAK TRANSITION SIMILARITY. Any true statement involving a given point and
some transition that is later than some transition later than the given
point, is also true of the given point and any later transition that is
later than some transition later than the given point.

WEAK TRANSITION SIMILARITY. (x < y < z < w and T(y) and T(z) and T(w) and
phi) implies phi[z/w], where phi is a formula in LOF(0) in which y.w do not
occur. 

THEOREM 2.3. The following theories are mutually interpretable with ZFC.
This is provable in EFA.
i. Linearity + Transitions + Double Transition Ranges + Transition Interval
Similarity.
ii. Linearity + Transitions + Double Transition Ranges + Weak Transition
Similarity.  
iii. Linearity + Transitions + Single Transition Ranges + Transition
Interval Similarity.
iv. Linearity + Transitions + Single Transition Ranges + Weak Transition
Similarity. 

THEOREM 2.4. The following theories interpret ZFC + "there exists a subtle
cardinal" and are interpretable in ZFC + "there exists an almost ineffable
cardinal". This is provable in EFA.
i. Linearity + Transitions + Double Transition Ranges + Transition
similarity.
ii. Linearity + Transitions + Single Transition Ranges + Transition
Similarity. 

We single out the following Corollary to Theorem 2.3.

COROLLARY 2.5. The following is provable in EFA.  Each of the four theories
in Theorem 2.3 is consistent if and only if ZFC is consistent.

We now consider a very strong form of Transition Similarity.

TAIL TRANSITION SIMILARITY. Any true statement about a point remains true if
we hypothetically restrict the transitions to those that are <= x together
with those that are at least any given transition after x.

TAIL TRANSITION SIMILARITY. (x < y and T(y) and phi) implies phi[<=x,>=y],
where phi is a formula of LOF with at most the free variable x, in which x
does not appear bound, y does not appear, and phi[<=x,>=y]  is the result of
replacing each T(v) by (T(v) and (v <= x or y <= v)).

THEOREM 2.6. The following theories interpret ZFC + "for all x containedin
omega, x# exists" and are interpretable in ZFC + "there exists a measurable
cardinal". This is provable in ZFC.
i. Linearity + Transitions + Double Transition Ranges + Tail Transition
Similarity.
ii. Linearity + Transitions + Single Transition Ranges + Tail Transition
Similarity.  

Hence the two theories in Theorem 2.6 have consdierably more strength than

ZFC + "there exists a cardinal that arrows every countable ordinal".

In order to get past measurable cardinals, we add the following.

WEAK TRANSITION ACCUMULATION. There is a point which has a transition before
it, but no last transition before it.

WEAK TRANSITION ACCUMULATION. (therexists x < y)(T(x) and (forall x <
y)(T(x) and (therexists z)(x < z < y and T(z)))).

We can also use

TRANSITION ACCUMULATION. There is a point which is the limit of earlier
transitions.  

TRANSITION ACCUMULATION. (therexists x < y)(T(x) and (forall x <
y)(therexists z)(x < z < x and T(z))).

THEOREM 2.7. The following theories interpret ZFC + "there exists a
measurable cardinal kappa with kappa many measurable cardinals below kappa"
and are interpretable in ZFC + "there exists a measurable cardinal kappa
with normal measure 1 measurable cardinals below kappa". This is provable in
EFA.
i. Linearity + Transitions + Double Transition Ranges + Tail Transition
Similarity + Weak Transition Accumulation.
ii. Linearity + Transitions + Double Transition Ranges + Tail Transition
Similarity + Transition Accumulation.
iii. Linearity + Transitions + Single Transition Ranges + Tail Transition
Similarity + Weak Transition Accumulation.
iv. Linearity + Transitions + Single Transition Ranges + Tail Transition
Similarity + Transition Accumulation.

We get into the concentrator measurable hierarchy if we use the following.

STRONG TRANSITION ACCUMULATION. There is a transition which is the limit of
earlier transitions.

STRONG TRANSITION ACCUMULATION. (therexists x < y)(T(x) and T(y) and (forall
x < y)(therexists z)(x < z < x and T(z))).

THEOREM 2.8. The following theories interpret ZFC + "there exists a
measurable cardinal kappa with normal measure 1 measurable cardinals below
kappa (order >= 2)" and are interpretable in ZFC + "there exists a
measurable cardinal kappa of order >= 3". This is provable in EFA.
i. Linearity + Transitions + Double Transition Ranges + Tail Transition
Similarity + Strong Transition Accumulation.
ii. Linearity + Transitions + Single Transition Ranges + Tail Transition
Similarity + Strong Transition Accumulation.

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

I use http://www.math.ohio-state.edu/%7Efriedman/ for downloadable
manuscripts. This is the 292nd 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-249 can be found at
http://www.cs.nyu.edu/pipermail/fom/2005-June/008999.html in the FOM
archives, 6/15/05, 9:18PM. NOTE: The title of #269 has been corrected from
the original.

250. Extreme Cardinals/Pi01  7/31/05  8:34PM
251. Embedding Axioms  8/1/05  10:40AM
252. Pi01 Revisited  10/25/05  10:35PM
253. Pi01 Progress  10/26/05  6:32AM
254. Pi01 Progress/more  11/10/05  4:37AM
255. Controlling Pi01  11/12  5:10PM
256. NAME:finite inclusion theory  11/21/05  2:34AM
257. FIT/more  11/22/05  5:34AM
258. Pi01/Simplification/Restatement  11/27/05  2:12AM
259. Pi01 pointer  11/30/05  10:36AM
260. Pi01/simplification  12/3/05  3:11PM
261. Pi01/nicer  12/5/05  2:26AM
262. Correction/Restatement  12/9/05  10:13AM
263. Pi01/digraphs 1  1/13/06  1:11AM
264. Pi01/digraphs 2  1/27/06  11:34AM
265. Pi01/digraphs 2/more  1/28/06  2:46PM
266. Pi01/digraphs/unifying 2/4/06  5:27AM
267. Pi01/digraphs/progress  2/8/06  2:44AM
268. Finite to Infinite 1  2/22/06  9:01AM
269. Pi01,Pi00/digraphs  2/25/06  3:09AM
270. Finite to Infinite/Restatement  2/25/06  8:25PM
271. Clarification of Smith Article  3/22/06  5:58PM
272. Sigma01/optimal  3/24/06  1:45PM
273: Sigma01/optimal/size  3/28/06  12:57PM
274: Subcubic Graph Numbers  4/1/06  11:23AM
275: Kruskal Theorem/Impredicativity  4/2/06  12:16PM
276: Higman/Kruskal/impredicativity  4/4/06  6:31AM
277: Strict Predicativity  4/5/06  1:58PM
278: Ultra/Strict/Predicativity/Higman  4/8/06  1:33AM
279: Subcubic graph numbers/restated  4/8/06  3:14AN
280: Generating large caridnals/self embedding axioms  5/2/06  4:55AM
281: Linear Self Embedding Axioms  5/5/06  2:32AM
282: Adventures in Pi01 Independence  5/7/06
283: A theory of indiscernibles  5/7/06  6:42PM
284: Godel's Second  5/9/06  10:02AM
285: Godel's Second/more  5/10/06  5:55PM
286: Godel's Second/still more  5/11/06  2:05PM
287: More Pi01 adventures  5/18/06  9:19AM
288: Discrete ordered rings and large cardinals  6/1/06  11:28AM
289: Integer Thresholds in FFF  6/6/06  10:23PM
290: Independently Free Minds/Collectively Random Agents  6/12/06  11:01AM
291: Independently Free Minds/Collectively Random Agents (more)  6/13/06
5:01PM 

Harvey Friedman  












 



















 




More information about the FOM mailing list