2 views

Skip to first unread message

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.

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?

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?

> 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

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).

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.

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)

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

> 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.

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).

> 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

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.

> 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

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]

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...

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.

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

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> 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.

>

> 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.

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

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.

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....)

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

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.

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.

> 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.

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.

> 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?

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)

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)

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> 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

>

>

> > --

> > hz

>

> >

>

> 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)

> > 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.

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:

> 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.

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?

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.

--------------------------------------------

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.

> --------------------------------------------

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.

>

> --------------------------------------------

> --------------------------------------------

> The intuitionist conflates existence with construction.

> The Platonist conflates existence with consistency.

> --------------------------------------------

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

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

to

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

Never mind.

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.

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

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".

>

> 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.

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?

> 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.

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.

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.

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.

> 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.

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?

-----------------------------------------------------

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!

--

--

--

--

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

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?

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.

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.

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?

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?

prove, for example, that an equation has no solutions by assuming it

has a solution and deriving a contradiction?

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

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...> 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

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

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?

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

to

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

ideas.

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