Intuitionistic Arithmetic

2 views
Skip to first unread message

kleptoma...@hotmail.com

unread,
Nov 8, 2007, 3:53:54 PM11/8/07
to
My knowledge here is quite limited, so please bear with me. I have
some questions about how in first order arithmetic, the axiomatic
systems using classical logic and intuitionistic logic are related. I
have read about systems of intuitionistic analysis where every
function is continuous, but for now I want to ask only about
arithmetic, systems like PA and its intuitionistic counterpart. I will
try and articulate the questions and I hope they make sense.

1) Given a fixed list of axioms or axiom schemata (it could be the
axioms used in PA, or whatever), do the theorems that one can prove
change according to whether one uses classical or intuitionistic
logic?

2) Would two people using the two logics ever contradict each other?
Are there theorems that can be proved in arithmetic using classical
logic which are proved false when using intuitionistic logic, or vice
versa?

MoeBlee

unread,
Nov 8, 2007, 4:17:20 PM11/8/07
to
On Nov 8, 12:53 pm, kleptomaniac6...@hotmail.com wrote:
> My knowledge here is quite limited, so please bear with me. I have
> some questions about how in first order arithmetic, the axiomatic
> systems using classical logic and intuitionistic logic are related. I
> have read about systems of intuitionistic analysis where every
> function is continuous, but for now I want to ask only about
> arithmetic, systems like PA and its intuitionistic counterpart. I will
> try and articulate the questions and I hope they make sense.
>
> 1) Given a fixed list of axioms or axiom schemata (it could be the
> axioms used in PA, or whatever), do the theorems that one can prove
> change according to whether one uses classical or intuitionistic
> logic?

Intuitionisitic arithmetic may be understood to be Heyting arithmetic
(HA), which is the first order theory in intuitionisitic first order
logic with identity and with all the non-logical axioms of PA.

In what follows, I'm referring to first order. And in my answers
below, take it as an assumption (or proven, or whatever basis you
prefer) that PA is consistent.

HA is a proper subset of PA. I.e., every theorem of HA is a theorem of
PA, but not every theorem of PA is a theorem of HA.

> 2) Would two people using the two logics ever contradict each other?

No. Every theorem of HA is a theorem of PA, so HA cannot contradict
PA.

> Are there theorems that can be proved in arithmetic using classical
> logic which are proved false when using intuitionistic logic, or vice
> versa?

No. If a sentence P is a theorem of PA and also ~P were a theorem of
HA, then ~P would be a theorem of PA, so both P and ~P would be
theorems of PA, which contradicts that PA is consistent. And if a
sentence of the form ~P is a theorem of HA then ~P is a theorem of PA,
so, since PA is consistent, P is not a theorem of PA.

MoeBlee


kleptoma...@hotmail.com

unread,
Nov 8, 2007, 4:31:40 PM11/8/07
to
OK, thanks. So there are some theorems of PA, for which if one went to
HA, one would have to add more axioms to HA in order to prove them. So
I guess that means, trying to prove arithmetical facts without the law
of excluded middle would genuinely be harder than with the law of
excluded middle, in the sense that you would need more axioms, not
just more patience (longer proofs).

I guess the same goes for any classical axiomatic system for
arithmetic - that the theorems you can prove with that are a (not
necessarily proper) superset of the theorems you can prove with its
intuitionistic counterpart.

Does this differ from the situation for analysis? I mean, with systems
of intuitionistic analysis that prove "every function is continuous"
whereas in classical analysis you prove "not every function is
continuous". That seems pretty inconsistent to me.


translogi

unread,
Nov 8, 2007, 4:33:12 PM11/8/07
to

Also a very limited reply (After my last misknowledge on
intuitionistic logic)

) Given a fixed list of axioms or axiom schemata (it could be the
axioms used in PA, or whatever), do the theorems that one can prove
change according to whether one uses classical or intuitionistic
logic?

Yes in Classical logic you can prove more.
In intuitionistic logic you can only prove if you have seen it.
The famous example is is there a devil in pi? (the devil meaning the
decimal sequence 666)
In classical logic you can argue pi has an infinite number of
decimals, the changeof 666 NOT in it is zero (because it is an
infinite non repeating sequence) so there must be a devilin pi.

In intuitionistic logic for a proof you will have to construct PI so
that you can say something like the first six is the ???? decimal and
the next two decimals are also 6 es.
(does anybody know where the devil in Pi is?)

2) Would two people using the two logics ever contradict each other?
Are there theorems that can be proved in arithmetic using classical
logic which are proved false when using intuitionistic logic, or vice
versa?

NO they do not contradict eachother but in classical logic more is
provable than in intuitionistic logic.

Intuitionistic logic needs a constructive proof, while for classical
logic a reductio ad absurdum counts as a proof.

an example
(bit overthe top maybe)
that every even number bigger than 2 is the sum of 3 squares is not
proven to be true nor proven to be false

Is it therefore either true or false?
Classial logic says yes it is true or false
Intuitionistic logic say I don't know maybe there are other
possibilities

.
Hope this helps
(and that i am correct)

kleptoma...@hotmail.com

unread,
Nov 8, 2007, 4:39:25 PM11/8/07
to
On Nov 8, 9:33 pm, translogi <wilem...@googlemail.com> wrote:
> an example
> (bit overthe top maybe)
> that every even number bigger than 2 is the sum of 3 squares is not
> proven to be true nor proven to be false
>
> Is it therefore either true or false?
> Classial logic says yes it is true or false
> Intuitionistic logic say I don't know maybe there are other
> possibilities

Well a number is the sum of 3 squares iff it is not of the form 4^m(8k
+7). So 60 is not the sum of three squares. Out of interest does
anyone know where to find a proof of this? A bit off topic but I know
a proof for sums of two squares and sums of four squares, but not for
sums of three squares. It seems that it would be quite difficult,
because sums of two squares and sums of four squares form
multiplicative domains (if you multiply two, you get another). Whereas
sums of three squares do not have this property.

MoeBlee

unread,
Nov 8, 2007, 4:50:52 PM11/8/07
to
On Nov 8, 1:31 pm, kleptomaniac6...@hotmail.com wrote:
> OK, thanks. So there are some theorems of PA, for which if one went to
> HA, one would have to add more axioms to HA in order to prove them. So
> I guess that means, trying to prove arithmetical facts without the law
> of excluded middle would genuinely be harder than with the law of
> excluded middle, in the sense that you would need more axioms, not
> just more patience (longer proofs).

Say S is a theorem of PA but not of HA, then to make S a theorem of
HA, then you'd have to add some axiom(s) or inference rule(s) to HA.
Of course, to do that on a sweeping basis, you could just add whatever
axiom of inference rules to the LOGICAL axioms of HA to make the logic
into classical logic which would put you in PA.

> I guess the same goes for any classical axiomatic system for
> arithmetic - that the theorems you can prove with that are a (not
> necessarily proper) superset of the theorems you can prove with its
> intuitionistic counterpart.

Yes. If you can prove S from a set of non-logical axioms G with
intuitionistic logic, then you prove S from G with classical logic.

> Does this differ from the situation for analysis? I mean, with systems
> of intuitionistic analysis that prove "every function is continuous"
> whereas in classical analysis you prove "not every function is
> continuous". That seems pretty inconsistent to me.

But the non-logical axioms don't match, so this is not an exception to
what we were talking about. Indeed, the language itself might not
match, and the constructivist analysis might or might not even be
formally axiomatized.

MoeBlee


Pierre Asselin

unread,
Nov 8, 2007, 9:26:28 PM11/8/07
to
kleptoma...@hotmail.com wrote:
> OK, thanks. So there are some theorems of PA, for which if one went to
> HA, one would have to add more axioms to HA in order to prove them.

In the other direction, Goedel found a an embedding of PA into HA.
He transforms each arithmetical statement s to a new statement
G(s), classically but not intuitionistically equivalent to s, such
that if s is a theorem of PA then G(s) is a theorem of HA.

This translation opens up another point of view: that intuitionist
arithmetic is a *refinement* of classical arithmetic, because the
latter identifies propositions that to an intuitionist are distinct.

--
pa at panix dot com

Gc

unread,
Nov 8, 2007, 9:46:47 PM11/8/07
to
On 8 marras, 23:33, translogi <wilem...@googlemail.com> wrote:

> The famous example is is there a devil in pi? (the devil meaning the
> decimal sequence 666)
> In classical logic you can argue pi has an infinite number of
> decimals, the changeof 666 NOT in it is zero (because it is an
> infinite non repeating sequence) so there must be a devilin pi.

How it is certain? Even if the probability of its negation is 0. For
example if you choose a random real from [1,0], then the probability
of getting a 1/2 is zero, but it is still a possibility.

[added sci.math]

guyont...@yahoo.com

unread,
Nov 9, 2007, 1:03:51 AM11/9/07
to

There is no argument like this in classical logic.

You need to fill in the gap between

"because it is an infinite non repeating sequence ..."

and

"... the chance of 666 not occurring in the expansion is zero"

In the meantime consider the following decimal expansion

.0100100001000000001...

Gc

unread,
Nov 9, 2007, 1:12:21 AM11/9/07
to

Is the chance of this decimal expansion suppose to be anything but
zero? Let`s suppose towards a contradiction that the chance for each
decimal-expansions of the reals is a positive constant k, so that
each decimal expansion is equally likely. What you get from "the
cardinality of the reals" times constant k? This should be the whole
probability mass namely it`s value should be 1, if k is non zero
positive.

Proginoskes

unread,
Nov 9, 2007, 1:55:04 AM11/9/07
to

Actually, if you go to http://zenwerx.com/pi.php (which has the first
4 million+ digits of pi) and then use your browser to find 666, it
will show up fairly early (in the first screen, at the 2440th place).
In fact, a string of 6 6's in a row shows up in the first four million
places.

--- Christopher Heckman

Gc

unread,
Nov 9, 2007, 2:09:56 AM11/9/07
to
On 9 marras, 08:55, Proginoskes <CCHeck...@gmail.com> wrote:
> On Nov 8, 7:46 pm, Gc <Gcut...@hotmail.com> wrote:
>
> > On 8 marras, 23:33, translogi <wilem...@googlemail.com> wrote:
>
> > > The famous example is is there a devil in pi? (the devil meaning the
> > > decimal sequence 666)
> > > In classical logic you can argue pi has an infinite number of
> > > decimals, the changeof 666 NOT in it is zero (because it is an
> > > infinite non repeating sequence) so there must be a devilin pi.
>
> > How it is certain? Even if the probability of its negation is 0. For
> > example if you choose a random real from [1,0], then the probability
> > of getting a 1/2 is zero, but it is still a possibility.
>
> Actually, if you go tohttp://zenwerx.com/pi.php(which has the first

> 4 million+ digits of pi) and then use your browser to find 666, it
> will show up fairly early (in the first screen, at the 2440th place).
> In fact, a string of 6 6's in a row shows up in the first four million
> places.
>
> --- Christopher Heckman

OK. That`s nice to know.

herbzet

unread,
Nov 9, 2007, 2:27:27 AM11/9/07
to

translogi wrote:

> The famous example is is there a devil in pi? (the devil meaning the
> decimal sequence 666)

The string 666 occurs at position 2,440 counting from the first digit after
the decimal point. The 3. is not counted.

The string and surrounding digits:

78895252138522549954 666 72782398645659611635

from http://www.angio.net/pi/piquery#find

--
hz

guyont...@yahoo.com

unread,
Nov 9, 2007, 4:57:56 AM11/9/07
to


The sequence of partial sums is increasing and bounded below
by 1/100 so it won't converge to zero. If you just pick
epsilon = one of the partial sums, it should be clear why not.

translogi

unread,
Nov 9, 2007, 6:50:32 AM11/9/07
to

OOPS again gave the wrong example

the real proposition should have been : even number greater than 2 is
the sum of two primes. That happens when you write without first
checking your sourses. (But my books are at home and i am at the
uni....)

Alan Smaill

unread,
Nov 9, 2007, 7:11:56 AM11/9/07
to
p...@see.signature.invalid (Pierre Asselin) writes:

and another possibility is that an axiomatisation is inconsistent
classically (so nonsense), yet intuitionistically consistent and a
fine theory from that point of view -- but contradicting any consistent
classical axiomatisation in that language.

> --
> pa at panix dot com

--
Alan Smaill

Gc

unread,
Nov 9, 2007, 7:28:33 AM11/9/07
to

I don`t understand what your point is. The real number that this
decimal expansion represents is not zero. So what? It is still true
that any set that contains some decimal expansion of the reals, which
do not contain some particular finite strings, are of measure zero. So
the chance of those reals is 0. But in infinite case this doesn`t mean
that they couldn`t occur.


Frederick Williams

unread,
Nov 9, 2007, 7:33:46 AM11/9/07
to
kleptoma...@hotmail.com wrote:

> Does this differ from the situation for analysis? I mean, with systems
> of intuitionistic analysis that prove "every function is continuous"
> whereas in classical analysis you prove "not every function is
> continuous". That seems pretty inconsistent to me.

Two different senses of the words are used; therefore there is no
inconsistency.

--
Remove "antispam" and ".invalid" for e-mail address.
"He that giveth to the poor lendeth to the Lord, and shall be repaid,"
said Mrs Fairchild, hastily slipping a shilling into the poor woman's
hand.

kleptoma...@hotmail.com

unread,
Nov 9, 2007, 10:51:22 AM11/9/07
to
On Nov 8, 9:17 pm, MoeBlee <jazzm...@hotmail.com> wrote:
> HA is a proper subset of PA. I.e., every theorem of HA is a theorem of
> PA, but not every theorem of PA is a theorem of HA.

Is there anything one can say about the nature of the theorems which
can be proved in PA but not HA? Is it the case that every such theorem
is classically equivalent to some theorem which can be proved in
both?

Jan Burse

unread,
Nov 9, 2007, 12:40:16 PM11/9/07
to
herbzet schrieb:

21041974 does not occure in the first 2*10^8 digits.
Will it occure somewhere, yes or no?

I guess it should be possible to formulate the
problem either in intuitionistic logic or in
classical logic, because:

Proposition logic: Glivenko's Theorem
|-classical A <-> |-intutionistic ~~A

Predicate logic: negative translation by Gödel/Gentzen
|-classical A <-> |-intutionistic g(A)

Therefore the following statement being more a phantasie
of the author, than a hard existing limitation/contrast
of intuitionistic versus classical logic:

> > translogi wrote:
> Yes in Classical logic you can prove more.
> In intuitionistic logic you can only prove if you have seen it.

> The famous example is is there a devil in pi? (the devil meaning the
> decimal sequence 666)

Jan Burse

unread,
Nov 9, 2007, 12:45:16 PM11/9/07
to
Jan Burse schrieb:

> 21041974 does not occure in the first 2*10^8 digits.
> Will it occure somewhere, yes or no?
>
> I guess it should be possible to formulate the
> problem either in intuitionistic logic or in
> classical logic, because:
>
> Proposition logic: Glivenko's Theorem
> |-classical A <-> |-intutionistic ~~A
>
> Predicate logic: negative translation by Gödel/Gentzen
> |-classical A <-> |-intutionistic g(A)
>

Maybe this article could be helpful:
http://www.mathematik.tu-darmstadt.de/~kohlenbach/GKSmlq.pdf

(Didn't verify that)

translogi

unread,
Nov 9, 2007, 1:32:30 PM11/9/07
to
On Nov 9, 5:40 pm, Jan Burse <janbu...@fastmail.fm> wrote:
> herbzet schrieb:
>
>
>
>
>
> > translogi wrote:
>
> >> The famous example is is there a devil in pi? (the devil meaning the
> >> decimal sequence 666)
>
> > The string 666 occurs at position 2,440 counting from the first digit after
> > the decimal point. The 3. is not counted.
>
> > The string and surrounding digits:
>
> > 78895252138522549954 666 72782398645659611635
>
> > fromhttp://www.angio.net/pi/piquery#find

>
> > --
> > hz
>
> >
>
> 21041974 does not occure in the first 2*10^8 digits.
> Will it occure somewhere, yes or no?
>
started a new tread for this

> I guess it should be possible to formulate the
> problem either in intuitionistic logic or in
> classical logic, because:
>
> Proposition logic: Glivenko's Theorem
> |-classical A <-> |-intutionistic ~~A
>
> Predicate logic: negative translation by Gödel/Gentzen
> |-classical A <-> |-intutionistic g(A)
>
> Therefore the following statement being more a phantasie
> of the author, than a hard existing limitation/contrast
> of intuitionistic versus classical logic:
>
> > > translogi wrote:
> > Yes in Classical logic you can prove more.
> > In intuitionistic logic you can only prove if you have seen it.
> > The famous example is is there a devil in pi? (the devil meaning the
> > decimal sequence 666)
> > In classical logic you can argue pi has an infinite number of
> > decimals, the changeof 666 NOT in it is zero (because it is an
> > infinite non repeating sequence) so there must be a devilin pi.
> >
> > In intuitionistic logic for a proof you will have to construct PI so
> > that you can say something like the first six is the ???? decimal and
> > the next two decimals are also 6 es.

> > (does anybody know where the devil in Pi is?)- Hide quoted text -
>
I remember reading this example somewhere in Brouwer/ Heyting or
Dummett.

shall try to find the reference to it.


And it is a question what does ~~A intuitionisticly mean?
(Or (A -> _|_)-> _|_ if you prefer)

it is something other than A what does mean that A is constructable.

Pierre Asselin

unread,
Nov 9, 2007, 8:15:39 PM11/9/07
to
Alan Smaill <sma...@spaminf.ed.ac.uk> wrote:
> p...@see.signature.invalid (Pierre Asselin) writes:

> > In the other direction, Goedel found a an embedding of PA into HA.
> > He transforms each arithmetical statement s to a new statement
> > G(s), classically but not intuitionistically equivalent to s, such
> > that if s is a theorem of PA then G(s) is a theorem of HA.
> >
> > This translation opens up another point of view: that intuitionist
> > arithmetic is a *refinement* of classical arithmetic, because the
> > latter identifies propositions that to an intuitionist are distinct.

> and another possibility is that an axiomatisation is inconsistent
> classically (so nonsense), yet intuitionistically consistent and a
> fine theory from that point of view -- but contradicting any consistent
> classical axiomatisation in that language.

In the case at hand, no. The translation of "1=0" is "1=0", from which
it follows that PA and HA are equiconsistent.

kleptoma...@hotmail.com

unread,
Nov 11, 2007, 9:25:08 AM11/11/07
to

Does this question make sense? There are several examples known of
statements unprovable in PA e.g. Goodstein's theorem. Are there any
examples known of theorems provable in PA but not HA?

Bill Taylor

unread,
Nov 11, 2007, 11:35:32 PM11/11/07
to
> Are there any examples known of theorems provable in PA but not HA?

Sure, tons.

An oft-mentioned example is:-

Every multinomial with integer coefficients takes on a minimum
absolute value for some arguments.

--------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
--------------------------------------------
The intuitionist conflates existence with construction.
The Platonist conflates existence with consistency.
--------------------------------------------

kleptoma...@hotmail.com

unread,
Nov 12, 2007, 8:40:59 AM11/12/07
to
On Nov 12, 4:35 am, Bill Taylor <w.tay...@math.canterbury.ac.nz>
wrote:

> > Are there any examples known of theorems provable in PA but not HA?
>
> Sure, tons.
>
> An oft-mentioned example is:-
>
> Every multinomial with integer coefficients takes on a minimum
> absolute value for some arguments.
>
> --------------------------------------------
> Bill Taylor W.Tay...@math.canterbury.ac.nz

> --------------------------------------------
> The intuitionist conflates existence with construction.
> The Platonist conflates existence with consistency.
> --------------------------------------------

Weird. Is that not provable by induction/well ordering?

kleptoma...@hotmail.com

unread,
Nov 13, 2007, 7:31:11 PM11/13/07
to

Oh, well. It seems there are plenty of other examples, no shortage.
Never mind.

Bill Taylor

unread,
Nov 15, 2007, 3:15:57 AM11/15/07
to
Frederick Williams wrote:

> > of intuitionistic analysis that prove "every function is continuous"
> > whereas in classical analysis you prove "not every function is
> > continuous". That seems pretty inconsistent to me.
>
> Two different senses of the words are used; therefore there is no
> inconsistency.

Just in case of confusion, he means - two meanings of "function".

For the classicist a function is any set of ordered pairs.

For the intuitionist, the pairs must be related by a "constructive"
means of getting from input to output. Brouwer took this as
meaning: "If you want to get n dec-places of output, you must
be able to specify in advance m (dependent on n), such that
if you input the first m places of your input-number, you can
get at least n places of your output-number".
(Ignoring double-representation technicalities.)

This is what a classicist would call "a uniformly computable"
function, or some similar term. So Brouwer's theorem becomes,
"Every uniformly computable function is uniformly continuous",
which is not completely trivial but hardly earth-shattering.

[RANT MODE ON]

Which brings me to one of my perpetual gripes, in which
I'm sure I'm not alone. Constructivists generally, make it
a pugnacious point of principle to use the SAME terms as
the classicist, even though they know it is for different concepts.
They claim an "equal right" to use any (pre-schism) math term
as they please. And in practise this leads to all sorts of
absurdities and confusions, like the uniform continuity result,
and their nonsense claim to be able to prove the axiom of choice
(a constructivist set is a wizened imitation of a classical one!)
and so on.

I hate it! They could perfectly well use alternative terms,
admitting that the orthodox line has (for now at least)
"won the battle" of converts and terminology. As indeed they
HAVE done with certain terms such as "apart from" and
"inhabited set". This contiunued insistence on using
regular terms in a non-orthodox manner is very irksome
and (I'm sure) detrimental to their ultimate cause.

I hereby formally taint them!!

[RANT OVER]

Bill of Attainder.

Herman Jurjus

unread,
Nov 15, 2007, 6:58:47 AM11/15/07
to

Despite the seemingly later appearance of intuitionism, there are
indications that constructivism has always been part of the mathematical
thinking culture througout history.

It would be more fair to rant against the qualification 'classical
mathematics' being used for something that made no sense at all to most
people prior to 1874.

--
Cheers,
Herman Jurjus

Frederick Williams

unread,
Nov 15, 2007, 9:08:24 AM11/15/07
to
Bill Taylor wrote:
>
> Frederick Williams wrote:
>
> > > of intuitionistic analysis that prove "every function is continuous"
> > > whereas in classical analysis you prove "not every function is
> > > continuous". That seems pretty inconsistent to me.
> >
> > Two different senses of the words are used; therefore there is no
> > inconsistency.
>
> Just in case of confusion, he means - two meanings of "function".

You've got to go owwwwwwwwww!

Sorry wrong newsgroup.

--
How unlike the home life of our own dear Queen.

John Jones

unread,
Nov 15, 2007, 2:52:17 PM11/15/07
to
On Nov 8, 8:53�pm, kleptomaniac6...@hotmail.com wrote:
> My knowledge here is quite limited, so please bear with me. I have
> some questions about how in first order arithmetic, the axiomatic
> systems using classical logic and intuitionistic logic are related. I
> have read about systems of intuitionistic analysis where every
> function is continuous, but for now I want to ask only about
> arithmetic, systems like PA and its intuitionistic counterpart. I will
> try and articulate the questions and I hope they make sense.
>
> 1) Given a fixed list of axioms or axiom schemata (it could be the
> axioms used in PA, or whatever), do the theorems that one can prove
> change according to whether one uses classical or intuitionistic
> logic?
>
> 2) Would two people using the two logics ever contradict each other?
> Are there theorems that can be proved in arithmetic using classical
> logic which are proved false when using intuitionistic logic, or vice
> versa?

2) Two logics contradict each other when they represent objects in the
same system. Two logics do not contradict each other if their objects
are supported by systems where each system is incommensurable with the
other. Thus, it is not a contradiction to say that objects vanish and
objects do not vanish.

kleptoma...@hotmail.com

unread,
Nov 15, 2007, 3:14:28 PM11/15/07
to
Haha I really like Bill Taylor's rant.

But anyway I thought of a famous example that might be an example of a
theorem provable in PA but noone has yet found a proof in HA. In PA
one can prove (I presume! I have never actually tried to prove
anything in PA!) that for any natural number n the quantity of primes
is not n. If one could prove the same in HA, it would be a fairly
monumental achievement, unless I am very much mistaken.

I surely think for such matters (the theory of numbers) the classicist
will in the end derive more joy than the intuitionist or more
generally constructivist (are there any intuitionist or constructivist
number theorists?), for he will take joy in an existential proof and
he will take joy in a constructive proof even if the existential proof
has already been found, while the intuitionist will only take joy at
the constructive proof which is much harder to come by.

kleptoma...@hotmail.com

unread,
Nov 15, 2007, 4:12:18 PM11/15/07
to

That said, I found the following quote from Stanford Encyclopaedia:
"¬ (not): to prove ¬P we must show that P implies 0 = 1."

Does that not mean that one could use, for instance, infinite descent
or some other proof by contradiction to prove that two squares cannot
have their sum and difference both a square, or some other Diophantine
fact?

Or prove that there does not exist an n such that the quantity of
primes is equal to n. But that hardly seems like a constructive proof
of the infinitude of primes. When I think of "constructive proof of
the infinitude of primes" I think of proving that for some particular
list of primes, you can generate another prime not on that list, and
then generate another prime not on that list, and so on
indefinitely.

guyont...@yahoo.com

unread,
Nov 15, 2007, 4:52:22 PM11/15/07
to
On Nov 15, 3:14 pm, kleptomaniac6...@hotmail.com wrote:
> Haha I really like Bill Taylor's rant.
>
> But anyway I thought of a famous example that might be an example of a
> theorem provable in PA but noone has yet found a proof in HA. In PA
> one can prove (I presume! I have never actually tried to prove
> anything in PA!) that for any natural number n the quantity of primes
> is not n. If one could prove the same in HA, it would be a fairly
> monumental achievement, unless I am very much mistaken.

I think this argument is formalizable in HA.

Consider any list of primes p_1, p_2, ..., p_n

let N = p_1 * p_2 * ... * p_n + 1

If an integer divides N-1 and N it must be either
1 or -1 so none of the p_i where (1 <= i <= n) divide N.

Because N has no prime divisors in the list p_1, ..., p_n
either N itself is prime or there exists a prime p not
in the list that divides N.

In either case there are at least n+1 primes.

Bill Taylor

unread,
Nov 15, 2007, 11:50:46 PM11/15/07
to
Herman Jurjus <hjur...@hetnet.nl> wrote:

> > [RANT MODE ON]
>
> > Which brings me to one of my perpetual gripes, in which
> > I'm sure I'm not alone. Constructivists generally, make it
> > a pugnacious point of principle to use the SAME terms as
> > the classicist, even though they know it is for different concepts.

> Despite the seemingly later appearance of intuitionism, there are


> indications that constructivism has always been part of the mathematical
> thinking culture througout history.

There may well be something in what you say. It is a large debate.
However, the fact remains that (as I said, for the moment)
the orthodox has won the battle against the constructive.
So they should be allowed first pick at terms.

> It would be more fair to rant against the qualification 'classical
> mathematics' being used for something that made no sense at all
> to most people prior to 1874.

Hmmmmm. I suspect it would've, had they had 40 minutes to consider
it.

However, that is bye the bye. And it is also why I prefer to use
the term "orthodox" rather than "classical".

-----------------------------------------------------
Bill Taylor
W.Ta...@math.canterbury.ac.nz
-----------------------------------------------------
If writers go on strike, do they carry blank picket placards?
-----------------------------------------------------

Bill Taylor

unread,
Nov 15, 2007, 11:51:48 PM11/15/07
to
Frederick Williams

> > Just in case of confusion, he means - two meanings of "function".
>
> You've got to go owwwwwwwwww!
>
> Sorry wrong newsgroup.

NOW GET OUT!

--

--

--

--

Alan Smaill

unread,
Nov 16, 2007, 7:25:57 AM11/16/07
to
John Jones <jonesc...@aol.com> writes:

I'm afraid you are still trapped in the framework of
substantial nonsense; with time you may achieve truly
austere nonsense, but you have a way to go.

And only then may you wither into truth.

--
Alan Smaill

kleptoma...@hotmail.com

unread,
Nov 16, 2007, 10:31:08 AM11/16/07
to

Actually you're right, that does prove that given n primes we have an n
+1th prime.

In any case, the proof you posted, is that not nonconstructive? You
said N is a multiple of a prime not on the original list, but that
doesn't tell by itself how to find that prime. Does this not mean that
one could prove something using intuitionistic logic, yet not
constructively? Or is it the case that it is nonconstructive to say "N
is a multiple of some prime p that is not on the original list,
therefore there is a prime p which is not on the original list"?

Because I think when the word "constructive" is used to refer to
constructive existence of numbers satisfying certain conditions, for
example, it is fairly clear what it means. It means that one has
explicitly found an example of such a number. But when it refers to
constructively proving that the set of the numbers satisfying certain
conditions is infinite, I would have thought that it means finding
explicit examples of numbers in the set, and then providing an
algorithm, that given n numbers in the set tells you how to find
another number in the set, different from each of the original n
numbers.

Actually, we could make an algorithm: Take any n primes. Multiply them
together and add one. Resolve the resulting number into it's prime
factors. We have proved that this factorisation will contain at least
one prime that is not amongst our original n primes. Take the least
such prime. Then you have n+1 primes.

Is that not a constructive proof of prime infinity? Given n primes, it
tells you how to find a new prime. It doesn't give a formula for what
the new prime will be that you manufacture from the original n primes,
but it tells you how to find one, does it not? It gives you an
algorithm, that unless I am very much mistaken, if you follow it you
will find the new prime.

I don't know where to look to find an account of elementary number
theory developed using purely constructive methods. So it leads me to
think have I misunderstood the meaning of the word "constructive"?
Does it even have a precise unambiguous meaning? I think Davenport
said something like "A construction often gives greater mental
satisfaction than a mere proof of existence, although the distinction
between the two is not always a clear cut one". It seems that if
construction does have a clear unambiguous meaning, he must be
mistaken?

guyont...@yahoo.com

unread,
Nov 16, 2007, 3:49:48 PM11/16/07
to

The challenge was to give a proof that is formalizable into HA not
to write a proof that "tells you" how to do something, however I
thought it was clear that if you wanted to find a prime not on
the original list that you would factor N.


Neil W Rickert

unread,
Nov 16, 2007, 7:14:25 PM11/16/07
to
Bill Taylor <w.ta...@math.canterbury.ac.nz> writes:

>[RANT MODE ON]

>Which brings me to one of my perpetual gripes, in which
>I'm sure I'm not alone. Constructivists generally, make it
>a pugnacious point of principle to use the SAME terms as
>the classicist, even though they know it is for different concepts.

While I enjoyed the rant, I think it appropiate to recognize that
this is just the way language works. The Einsteinians didn't choose
new words when they changed the Newtonian concepts. The Copernicans
didn't choose new words when they changed the Ptolemaic concepts.
And AI folk drive traditional philosophers up the wall by talking
about computers having beliefs.

Let's face it - coming up with completely new words, and getting
everybody to adopt that new vocabulary, is very difficult to do.

Besides, it does little harm. Mathematicians can easily switch
between the different sets of concepts. The people mainly confused
are those who would be confused anyway.

kleptoma...@hotmail.com

unread,
Nov 17, 2007, 8:55:29 AM11/17/07
to
On Nov 16, 8:49 pm, guyonthei...@yahoo.com wrote:

>
> The challenge was to give a proof that is formalizable into HA not
> to write a proof that "tells you" how to do something, however I
> thought it was clear that if you wanted to find a prime not on
> the original list that you would factor N.

So I guess the challenge that is really unsolved is to find a
construction for finding every prime, not just an infinite set of
primes. We have a way of constructing an infinite set of primes, but
we have no way, as far as I know, of specifying what the nth prime
is.

In fact, if we start with 2,3,5 say, we get 31, then we get 7, then we
get 17, I wonder what primes the algorithm I gave will miss?

kleptoma...@hotmail.com

unread,
Nov 17, 2007, 9:03:49 AM11/17/07
to
Another thing was, is it not acceptable in intuitionistic reasoning to
prove, for example, that an equation has no solutions by assuming it
has a solution and deriving a contradiction?

Alan Smaill

unread,
Nov 17, 2007, 10:45:07 AM11/17/07
to
kleptoma...@hotmail.com writes:

That's fine;
the problem arises if you claim there *is* a solution, and prove it by
assuming that there is no solution and deriving a contradiction.

--
Alan Smaill

cbr...@cbrownsystems.com

unread,
Nov 18, 2007, 5:08:20 PM11/18/07
to
On Nov 17, 5:55 am, kleptomaniac6...@hotmail.com wrote:
> On Nov 16, 8:49 pm, guyonthei...@yahoo.com wrote:
>
>
>
> > The challenge was to give a proof that is formalizable into HA not
> > to write a proof that "tells you" how to do something, however I
> > thought it was clear that if you wanted to find a prime not on
> > the original list that you would factor N.
>
> So I guess the challenge that is really unsolved is to find a
> construction for finding every prime, not just an infinite set of
> primes. We have a way of constructing an infinite set of primes...

To be pedantic: This depends on how we strictly state things.

We might simply have a predicate A and a proof of "exists z s.t. A(z);
and forall x, if A(x) then x is a prime and there exists y s.t. y > x
and A(y)"; without any sort of reference to "sets", "members of sets",
and "infinite sets" at all.

That's not the same claim as "there exists an infinite set S of primes
satisfying A"; although usually we are working in some sort of set
theory that lets us talk about the set N of all naturals, and allows
us to talk about and prove the existence of sets such as S = {x | x in
N and A(x)}.

However, we might have instead a set theory that only says something
like (where x, m, and n are all assumed to have the property "is a
natural"):

if
forall x, exists m such that m = f(x)
then
forall n exists S such that
S = {f(x) | x <= n }

and that wouldn't /require/ us to include any infinite sets at all;
only finite ones. For example, if f(x) is the xth prime, this would
only imply that every finite set of primes exists, not that an
infinite set of primes exists.

>..., but


> we have no way, as far as I know, of specifying what the nth prime
> is.
>

Sure we do; inductively. The first prime is 2. The (n+1)th prime is
the smallest natural which is greater than the nth prime, and which is
not divisible by any of the first n primes.

What's important to note in the case of /finding/ the nth prime
constructive/ly/ is that given the first n primes, we have explicit
lower and upper bounds on the value of the (n+1)th prime : the
previously given proof implies that the (n+1)th prime exists and is
greater than the nth prime and less than or equal to the product of
the first n primes + 1.

So there are only a finite range of candidates to check, and /at
least/ one of the candidates is indeed not divisible by any of the
first n primes; and every finite range of naturals that contains at
least one natural not divisible by the first n primes also contains a
unique smallest such natural.

Induction turns out to be a very powerful constructive tool.

> In fact, if we start with 2,3,5 say, we get 31, then we get 7, then we
> get 17, I wonder what primes the algorithm I gave will miss?

Not sure what algorithm you're talking about here; certainly 2*3*5*31
+ 1 is not equal to 7...

If your algorithm proceeds as: given the first 3 primes 2,3,5 find the
smallest natural k > 5 and <= 2*3*5 + 1 = 31 such that k is prime in
order to get the 4th prime = 7, and so on with 2,3,5,7 to get the 5th,
etc.; then I don't see why you might be worried that there is any
chance of missing a prime at all for any /given/ natural n.

Whether that constitutes "constructing an infinite set of primes" is a
different matter, as I noted above.

Cheers - Chas

kleptoma...@hotmail.com

unread,
Nov 20, 2007, 7:41:11 PM11/20/07
to
On Nov 18, 10:08 pm, "cbr...@cbrownsystems.com"

Oh yeah, doh. One can compute the nth prime inductively by boundedness
of the nth prime. The nth prime has to be less than 2^(2^(n-1)). So
you have a mindless procedure for computing the nth prime.

As for my algorithm, I may not have been explicit enough. Start with
some list of primes, say 2,3,5 or whatever, then multiply them
together and add 1, split the result into its prime factors and take
the least, add that to the list, then multiply and add 1 and do the
same again, ad infinitum. For the starting list 2,3,5, we get
2,3,5,31,7,17,91,... and the calculations get large. Clearly the
primes you generate depends on the starting list, but is it the case
that you can choose a starting list that generates every prime at some
point? Is it the case that every starting list will generate every
prime at some point?

kleptoma...@hotmail.com

unread,
Nov 20, 2007, 8:16:07 PM11/20/07
to

Actually that's more number theory than anything. But hey, I get
ideas.

herbzet

unread,
Nov 23, 2007, 2:07:50 AM11/23/07
to

kleptoma...@hotmail.com wrote:

> As for my algorithm, I may not have been explicit enough. Start with
> some list of primes, say 2,3,5 or whatever, then multiply them
> together and add 1, split the result into its prime factors

How do you propose to do that, when none of the primes that you
already have on the list will divide it?

I'm not saying it can't be done, but it's not simple.

> and take
> the least, add that to the list,

Why not add them all to the list, not just the least? None of them
are already on the list.

> then multiply and add 1 and do the
> same again, ad infinitum. For the starting list 2,3,5, we get
> 2,3,5,31,7,17,91,... and the calculations get large. Clearly the
> primes you generate depends on the starting list,

Maybe or maybe not; but clearly the _order_ of the primes generated
depends on the starting list.

> but is it the case
> that you can choose a starting list that generates every prime at some
> point? Is it the case that every starting list will generate every
> prime at some point?

These are two interesting questions, and my guess is that the answers
are not known.

What's wrong with a straightforward brute-force search for primes:
start with the number 2 on the list, then check each successive number
to see if it divides by a number on the list. If not, add it to the list.

There's a godawful amount of literature on prime-representing formulae
and efficient searching for primes. Plenty of fun there, if you like
that sort of thing.

--
hz

Reply all
Reply to author
Forward
0 new messages