- 10 Dec '05 17:55 / 1 editDoctor Scribbles was talking about existence theorems yesterday. He showed how these can sometimes be proved constructively. Although many people find them annoying, my favourite existence theorems are those with non-constructive proofs, which guarantee that something with the properties under consideration exists, but leaves us no way of knowing what it might be.

As an exercise, prove the following statement: There exists a nonconstructive proof of the existence of irrational numbers. There's enough of a clue in the question so that all you really need to do is fill in the details. Of course, that's where the devil is, so if you're successful, an answer to the original poster's question will be a corollary. - 10 Dec '05 18:12

Where is the Doctor if you need him ....*Originally posted by royalchicken***Doctor Scribbles was talking about existence theorems yesterday. He showed how these can sometimes be proved constructively. Although many people find them annoying, my favourite existence theorems are those with non-constructive proofs, which guarantee that something with the properties under consideration exists, but leaves us no way of knowing what ...[text shortened]... is, so if you're successful, an answer to the original poster's question will be a corollary.** - 10 Dec '05 18:18

Can anyone solve my exercise nonconstructively, ie show that there is a nonconstructive proof of the irrationals' existence without actually formulating such a nonconstructive proof?*Originally posted by royalchicken***Doctor Scribbles was talking about existence theorems yesterday. He showed how these can sometimes be proved constructively. Although many people find them annoying, my favourite existence theorems are those with non-constructive proofs, which guarantee that something with the properties under consideration exists, but leaves us no way of knowing what ...[text shortened]... is, so if you're successful, an answer to the original poster's question will be a corollary.** - 10 Dec '05 19:28 / 4 edits

fugg it. Damn forum software.*Originally posted by royalchicken***Can anyone solve my exercise nonconstructively, ie show that there is a nonconstructive proof of the irrationals' existence without actually formulating such a nonconstructive proof?**

http://www.math.vanderbilt.edu/~schectex/papers/difficult.html - 10 Dec '05 23:29

That is a very interesting and slightly scary article. I'm preparing something of a response, which will be available at sonofhealfdane.blogspot.com in the next eight hours or so. I'm a second-year undergraduate, though, not a professional mathematician like Shcechter is, so I'm drawing on much less knowledge and experience and my response will reflect that. In particular, I didn't know that constructivism existed as a distinct mathematical approach before reading that article, but many thanks for the link; it's most interesting.*Originally posted by David C***fugg it. Damn forum software.**

http://www.math.vanderbilt.edu/~schectex/papers/difficult.html - 10 Dec '05 23:59

Claim: There exists a nonconstructive proof of the existence of irrational numbers.*Originally posted by royalchicken*

As an exercise, prove the following statement: There exists a nonconstructive proof of the existence of irrational numbers.

Proof by Construction:

Consider proof P: "Consider the set of real numbers R and the set of rational numbers Q. It can be shown via a diagonalization proof that the cardinality of R is greater than the cardinality of Q. Thus | |R| - |Q| | > 0, and thus R - Q is not the empty set, which is to say some reals exist and are not rational. Hence, some irrational numbers exist."

P is nonconstructive.

P proves the existence of irrational numbers.

Therefore, P is one nonconstructive proof of the existence of irrational numbers.

Hence, there exists a nonconstructive proof of the existence of irrational numbers, and the claim is true.

QED - 11 Dec '05 00:03

Actually, I'm using the same example, and argument, in my aforementioned critique. I'm sorry to say that, much like weak atheism, there might be a position of 'weak constructivism' other than the one outlined in Schechter's article (the link posted by David C).*Originally posted by DoctorScribbles***Claim: There exists a nonconstructive proof of the existence of irrational numbers.**

Proof by Construction:

Consider proof P: "Consider the set of real numbers R and the set of rational numbers Q. It can be shown via a diagonalization proof that the cardinality of R is greater than the cardinality of Q. Thus | |R| - |Q| | > 0, and thus R - Q ...[text shortened]... ts a nonconstructive proof of the existence of irrational numbers, and the claim is true.

QED

Can you think of a nonconstructive proof of the same claim? - 11 Dec '05 00:35 / 3 edits

Claim: There exists a nonconstructive proof of the existence of irrational numbers.*Originally posted by royalchicken***Can anyone solve my exercise nonconstructively, ie show that there is a nonconstructive proof of the irrationals' existence without actually formulating such a nonconstructive proof?**

Challenge: Prove the claim without formulating a nonconstructive proof of the existence of irrationals.

Direct Proof:

Consider the set T of all theorems in our axiom system.

T contains:

t1: "R - Q is not the empty set."

t2: "If R-Q is not the empty set, some irrationals exist."

There exists a proof of t1 that is nonconstructive.*

There exists a proof of t2 that is nonconstructive.*

Further, T must also contain:

t3: "Some irrationals exist."

which follows syllogistically from two theorems whose proofs are nonconstructive.

Hence, there exists a nonconstructive proof for t3, which must be a nonconstructive proof for the existence of irrationals.

QED

Dr. S

*If I can only demonstrate these two claims of existence by construction of the proofs, have I met the challenge? - 11 Dec '05 01:05

Dude dude dude dude dude. The answer to * is yes, but I also think the notion of constructivity is a bit weirder than it seems. In particular, I think:*Originally posted by DoctorScribbles***Claim: There exists a nonconstructive proof of the existence of irrational numbers.**

Challenge: Prove the claim without formulating a nonconstructive proof of the existence of irrationals.

Direct Proof:

Consider the set T of all theorems in our axiom system.

T contains:

t1: "R - Q is not the empty set."

t2: "If R-Q is not the empty ...[text shortened]... monstrate these two claims of existence by construction of the proofs, have I met the challenge?

'follows syllogistically from two theorems whose proofs are nonconstructive.'

is stronger than it needs to be in general. I'm still thinking about this, my conclusions, or explicit reasons for not having conclusions, will be available on my blog (address is in my profile), by dawn GMT. - 11 Dec '05 04:05

So far so good. I'll look forward to the meat tomorrow.*Originally posted by royalchicken***The first installment is now up. The actual interesting issues get started after I sleep/get out of the house for a few hours.**

"A final remark which will be useful later: an existence theorem with a constructive proof can be strengthened to a theorem which provides an example of the object whose existence it guarantees. Conversely, every theorem of the form '(specific) O has properties P' implies the existence theorem 'there exists and object with properties P', and this latter theorem has a constructive proof."

Interesting observation. Challenge for computer programmers: Name two concepts in Object Oriented Programming and one Design Pattern that mimics this observation. Responses are intended to be subjective. - 12 Dec '05 02:08

I see nobody accepted your challenge. I know essentially nothing about OOP or DP, so I'm not going to help the situation.*Originally posted by DoctorScribbles***So far so good. I'll look forward to the meat tomorrow.**

"A final remark which will be useful later: an existence theorem with a constructive proof can be strengthened to a theorem which provides an example of the object whose existence it guarantees. Conversely, every theorem of the form '(specific) O has properties P' implies the existence t ...[text shortened]... g and one Design Pattern that mimics this observation. Responses are intended to be subjective.

There will be more meat in an hour or two, with sporadic meat predicted for the rest of the week.