The limits of logic

April 5, 2006 12:11 AM

I've read that Gödel's incompleteness theorem shows that there are definite limits to what logic, mathematics and by extension computers can do. This seems to be unknown among humanists such as myself. What are the things logic cannot do? Earlier AskMe questions about Gödel here and here (this answer is especially good).
posted by Termite to religion & philosophy (50 comments total)

Logic can't make a decent cup of coffee, for a start.

What the incompleteness theorem demonstrates is that any formal system (loosely, any system that involves symbol manipulation according to fixed rules) which is powerful enough to be considered complete (that is, is capable in principle of expressing any truth) is also capable of expressing statements whose truth or otherwise is undecidable.

Statements in this class are easy to generate in English. For example: "This statement is not true".

What Gödel devised was a general method for producing statements with this quality using the notation of any sufficiently powerful formal system, which includes systems like arithmetic and logic.

The best way I can think of for non-technical folk to get the gist of the thing is to read Douglas Hofstadter's wonderful book.
posted by flabdablet at 12:30 AM on April 5, 2006

Very few things in mathematics have been shown to be undecidable. As was mentioned in an answer to one of your links the Continuum Hypothesis has been shown to be undecideable given 'the usual' axioms in mathematics. You can build in at the foundations an axiom so that it's true, or that it's false.

There's also the Halting Problem. Is that the kind of thing you're thinking about?
posted by edd at 12:32 AM on April 5, 2006

Re: Godel, check out two of my posts: 1, 2 and the latest tribute issue to Godel by the American Mathematical Society.
posted by Gyan at 12:42 AM on April 5, 2006

Well.."things logic cannot do" is an odd way of putting it. Its more that, given a set of axioms, there will be propositions which cannot be proven to be true (or proven to be not true) with those axioms.

So, given Zermelo-Fraenkel (+axiom of choice) as your axioms, yes, there are undecidable propositions within ZFC. So, what logic cannot do, in this example, is tell us whether those statements are true or not true. They are independent of the axioms. Is this what you were asking? ZFC is fairly strong so the types of things which are outside its reach (undecidable) are fairly exotic, not things you are likely to encounter doing everyday mathematics or logic. In fact, most mathematicians get along just fine without considering undecidable propositions.
posted by vacapinta at 12:46 AM on April 5, 2006

Keep in mind I'm not good at math:

"This sentence cannot be proven true."

You cannot prove it true, because then it would be false.

But it is true, because you cannot prove it true.

Godel's proof involves first contemplating the possible properties of any consistent system. Then he pretty much shows that the system must include a way to construct the above sentence in mathematical terms.

I believe you can also construct a sentence which is false, but cannot be proven false. Try it.
posted by TheOnlyCoolTim at 1:01 AM on April 5, 2006

But I wouldn't worry about encountering such things in "meaningful" logical discourse.
posted by TheOnlyCoolTim at 1:04 AM on April 5, 2006

how about the following- can g d create a rock that he can't move?
posted by Izzmeister at 1:11 AM on April 5, 2006

how about the following- can g d create a rock that he can't move?

I think that's a different kind of thing. The quick answer being: no - as it's not logically possibly.
posted by ed\26h at 1:45 AM on April 5, 2006

I wonder what happens with Gödels theorem if you state that self-reference is not allowed. I.e. that "This sentence cannot be proven true" is of the type 'meta-sentence' while the phrase 'this sentence' is of the type sentence.
I think this is what Russell devised as a kind of solution; type theory.
(Russells paradox on the web)
posted by jouke at 2:00 AM on April 5, 2006

Re: the rock that god can't move
As this cartoon(annoying ad first) illustrates that god is on a different plane (i.e. 'is a different type') from man and his logic.
posted by jouke at 2:07 AM on April 5, 2006

"If there a magic unknowable thing that defies all logic that we can't perceive?"

I think this might be kind of a start. But that's just a quick guess. I'm sure someone can pick it apart.
posted by cellphone at 2:52 AM on April 5, 2006

Just to pick up on flabdablet - completeness is the converse of consistency. That is a complete system is one where anything true is provable. There are mathematical theories that are both consistent and complete (eg group theory).

One thing that Godel's theorem does tell you about logic, is that a consistent logical system that's strong enough to express arithmetic (roughly speaking) can't prove it's own consistency. ie, you can't hope to bootstrap yourself into a situation where you have a system that you can use to prove all the theorems you want and also have a proof within that system that it is consistent (ie won't let you prove any false statements).

Another way of thinking about this is that when you choose a logical system you have to make a decision about how powerful you want it to be vs how sure you are that the logic itself is consistent and complete. First order logic as a theory is provably consistent and complete. Mathematicians like it for that reason. You have to add in a whole bunch of axioms for arithmetic before you arrive at something incomplete.

Conversely, second order logic, which has several benefits in terms of expressiveness (eg you can refer to all axioms in your theory, which you can't in FOL), and being able to define categorical models, is inherently incomplete.

Basically, when it comes to logic, you can't have everything.
posted by crocomancer at 2:59 AM on April 5, 2006

God could most certainly create a rock He couldn't move, and do so without causing any kind of logical paradox. He'd simply have to relinquish His own omnipotence in the process.

(this insight is not original - I'm pretty sure I first saw it pointed out on MeFi, though).

As for the whole types vs meta-types thing: Gödel's construction doesn't actually involve self-reference, so it escapes through the cracks.

The closest thing in English is probably Hofstadter's:

"yields falsehood when preceded by its quotation." yields falsehood when preceded by its quotation.

Even this doesn't quite capture the flavour of the thing, though, because it invokes an explicit quotation mechanism that's already present in English. The really cool part of Gödel's construction is that he shows how to implement a similar quoting mechanism within any sufficiently powerful formal system. Basically, he beats the use-mention distinction about the head with a great big stick until it gives in.
posted by flabdablet at 3:27 AM on April 5, 2006

My (possibly unfounded) reading of Godel is that while a system may be incomplete, you can always add more axioms which will allow you to prove previously unprovable theorems. The catch being, of course, that this is a new system with unprovable theorems of its own.

For example, the continuum hypothesis (CH) is undecidable in ZFC, but trivially true in the extended system ZFC+CH.

So although any given system is either incomplete or inconsistent, there exists something like a flowering tree of logical systems which get bigger and bigger, and never allow you to prove everything, but which do allow you prove any arbitrary theorem providing you are willing to move up the tree.
posted by hoverboards don't work on water at 4:19 AM on April 5, 2006

Termite -- If you haven't already, I think you might enjoy Thomas Kuhn's book called The Structure of Scientific Revolutions. Check it out. It's an important book.
posted by bim at 6:45 AM on April 5, 2006

God could most certainly create a rock He couldn't move, and do so without causing any kind of logical paradox. He'd simply have to relinquish His own omnipotence in the process.

I'm in two minds about responding to this. On the one hand, I don't think the God/rock thing belongs in this thread, because it's unrelated to Godel. On the other hand, I find the above "logic" so absurd, I can't resist responding. Feel free to flag.

In the God/rock paradox, "God" is taken to mean an all-powerful being. If He's not all powerful, then there's no paradox. (Can He make a rock so heavy He can't lift it? No.)

According to your cheat, flabdablet, God makes himself NOT all-powerful. But at this point, he ceases to be God (as God is defined in the paradox).

Perhaps the paradox would be clearer if it were worded as follows (but I think this meaning is already implicit in the paradox as it stands).

Can an all-powerful being make a rock so heavy that an all-powerful being can't lift it?

If he's all-powerful, he should able to lift ANY rock; If he's all-powerful, he should be able to make a rock so heavy that an all-powerful being can't lift it. But both can't be true.

You can refute this by pointing out that the paradox is gibberish. There can be no meaning to "a rock so heavy that an all-powerful being can't lift it." It's semantically equal to "Can God djsosjhjchxierieuriekjdhx2334?"

Sophomoric people have been trying to trap theists with this conundrum for eons. But religious philosophers have dismissed it. Most intelligent theists interpret "all-powerful" as the ability to do anything logically consistent. If you'd asked St. Augustan if God could make a rock so heavy He couldn't lift it, he (Augustan) would have answered, "No."
posted by grumblebee at 6:56 AM on April 5, 2006

I've read that Gödel's incompleteness theorem shows that there are definite limits to what logic, mathematics and by extension computers can do. This seems to be unknown among humanists such as myself.

Your reference to humanism makes me think that you're trying to apply Gödel's theorem to life. I don't think it really has such relevance. Like the uncertainty principle, it's often used in bad analogies to make questionable arguments about life. The theorem doesn't say anything about whether we'll succeed in creating artificial intelligence that's smarter than us, for example. So in the philosophical sense, I'm not sure it has any important implications for real life.
posted by callmejay at 6:57 AM on April 5, 2006

Very few things in mathematics have been shown to be undecidable.

I'm sorry, this is incorrect. Rice's Theorem (roughly equivalent to Goedel's) states that any interesting property of programs is undecidable in the general case. (Also check out Lob's Theorem.)

So, given an arbitrary program p(x), we'd like to know if it computes the input x plus 5. There is NO function f that returns true if and only if p(x)=x+5. The only things we can consistently determine about programs in general are trivial properties like length.

(Note that it is possible to construct a program from the ground up using types, and the type system will ensure that if p compiles, p(x)=p+5. Those kinds of sophisticated type systems are only getting used in production fairly recently, say in Haskell. Also note that there is no way to take an untyped program and figure out the types post facto as above.)

Further, Gregory Chaitin has shown that not only are there lots of mathematical facts that cannot be proven, the number of mathematical facts that can be proven given any consistent axiomatic system is vanishingly small. That is to say, there are an unimaginably larger number of unprovable propositions than provable ones.

There has been a lot of interesting stuff in "paraconsistent logics," logics in which it is possible to prove a contradiction, but also do not suffer from the incompleteness property. You will observe that since we must handle even paraconsistent logics in a consistent manner (to do anything at all) that the incompleteness still creeps in at the meta-level.

A nice introductory book is Goedel's Proof by Nagel and Newman. This is a favorite book of Hofstadter's.

What does all this mean for non-math folks? It is still a topic of hot debate in the logic community. At minimum, it indicates that there are certain things that cannot be reached by language, since even if language is paraconsistent, there exists some consistent formal language that simulates it and is incomplete. This is why people often connect Goedel and Wittgenstein, and there are some similarities in their arguments.
posted by sonofsamiam at 7:18 AM on April 5, 2006

The halting problem is much easier to understand, IMO, and explains about the same thing. (Partly because we work with computers every day).
posted by delmoi at 7:36 AM on April 5, 2006

how about the following- can g d create a rock that he can't move?

I think that's a different kind of thing. The quick answer being: no - as it's not logically possibly.

I always thought the answer was "yes, he just dosn't want to".
posted by delmoi at 7:38 AM on April 5, 2006

I wonder what happens with Gödels theorem if you state that self-reference is not allowed.

Well, you lose a lot of mathematical power. Calculating interest rates, for example:

"The amount of money you have is the amount of money you had last year times 1.1. The amount of money you had last year can be calculated by this sentence, by substituting the year before that, and so on, until you get to the first year you invested."

You can derive an equation, but the equation is based on the original self-refrence. There are a lot of problems that require self reference, including pretty much anything involving computer science.
posted by delmoi at 7:43 AM on April 5, 2006

grumblebee: Basically it boils down to "can god commit suicide". I honestly don't see why not. Yes, he ceases to be come all powerful if he creates the rock, but that's not inconsistent at all. First he's all powerful, and then he's not. He's only defined as being all powerful, for the terms of the question, at the beginning.

If you asked "is there a being with property P that can create a rock so heavy it can't lift it, with P omnipotence so long as they don't create anything to heavy to lift?" I think the answer is clearly yes.
posted by delmoi at 7:51 AM on April 5, 2006

The theorem doesn't say anything about whether we'll succeed in creating artificial intelligence that's smarter than us, for example. So in the philosophical sense, I'm not sure it has any important implications for real life.

It really only effects the lives of early 20th century mathematicians who found out all the work they were doing had been hopeless from the start. For everyone else, it's not really a big deal, but it is kind of annoying that there are questions that can't be answered.
posted by delmoi at 7:53 AM on April 5, 2006

I wonder what happens with Gödels theorem if you state that self-reference is not allowed.

That's the thing: if you can, at minimum, represent the natural numbers in your system, then you cannot escape self-reference. You don't have to include it explicitly, it is a (surprising) property of the natural numbers that they can always be used to reference themselves.
posted by sonofsamiam at 7:54 AM on April 5, 2006

I think (from what I remember from sitting in on one advanced logic seminar several years ago) the upshot of Gödel, from a layman's perspective, is that logic simply isn't as powerful as one might imagine it is; more specifically, that logic isn't some super-optimalized, purified language that still does everything English does, only better and more reliably. It also means that a perfect logical system would fail to be a reflection of the world in some way, because completeness and consistency can never simultaneoulsy be acheived without constraints. On the contrary, logic will never "express the world", or perform many of the functions we take natural language to achieve. There is a tension between the requirements for completeness and consistency, and formal logic lacks the tools we have for dealing with similar problems in natural language (cf. Saussure & co).

Naive philosophy 101 students (myself included at the time) often start with the impression that logic is the "language of truth", and that if we could translate all our premises (beliefs or scientific knowledge) into formal logic and parse them out completely, our work would be done. Wittgenstein believed something approximately like this at one time, but also ran up against the completeness and consistency problem as well: certain topics - metaphysics, God - are necessarily outside the capacity of logical representation, because introducing axioms that let them in (adding completeness) lets the system expand beyond the bounds of certainty (sacrificing consistency). Famously, he concluded his Tractatus with the words, "whereof one cannot speak, one must remain silent." He eventually changed his mind the nature of language and the relationship between logic and metaphysics, as many logicians and philosophers did after Gödel.

Sorry if I'm being entirely too pedantic and/or shouldn't be talking about this in the first place; I just wanted to say something from an angle that hadn't been taken yet.
posted by xanthippe at 8:06 AM on April 5, 2006

it's nowhere near as bad as some people make out.

the proof of godel's theorem requires "the law of the excluded middle" (that something is either true or false). that sounds obvious, but in maths you typically have to assume things about infinite collections of values to use it (there are an infinite number of numbers, so to say a formula is true or false you have to somehow consider all possible numbers...).

now it turns out that there's a relatively obscure branch of maths called constructivism, which has had a resurgence in recent years because constructive proofs are very similar to computer programs (a program describes how to do something, so it's a proof by showing that something can be done, rather than by making logical arguments that include infinity).

mathematicians don't like constructivism much, because it makes things harder. but it turns out that most of the useful stuff in maths can be proved in this way. and, because it avoids infinities, it is unaffected by godel's theorem.

so, in fact, it appears that godel's theorem has very little importance. even though it is amazingly cool.

disclaimer: i am no expert and i had to read a lot of stuff i only partially understood to work this out (your first link was the start of this process); it's pretty obscure and many mathematicians have little idea about it. but i believe that whati have said above is roughly correct.
posted by andrew cooke at 8:19 AM on April 5, 2006

oops. you can read the above as if i had discovered what i said, which is completely misleading - see your first link for someone much smarter than me saying the same thing. when i said "to work this out" i meant "to understand this personally"; it is not my work or my idea.
posted by andrew cooke at 8:22 AM on April 5, 2006

delmoi, we're basically in agreement, except that I think the paradox is uninteresting and trivial if interpreted your way. Your way, it becomes:

1) Can a rock be so heavy that a person (a NON all-powerful being) can't lift it? Yes.

2) Can God make a rock so heavy that a person can't lift it? Yes.

2) Can God turn Himself into a person. Yes.

3) Without making himself into a person, could God make a rock so heavy He couldn't lift it? No.

God can't STAY God (all powerful -- he might still be God in some other ways) and make a rock so heavy He can't lift it.

True, but boring and trivial. As you suggested (re: suicide), the only interesting question here is whether or not God can limit His powers. (God is a fictional being to me, so the answer is yes or no, depending on the story we're telling.) If he CAN'T limit his powers (which I guess would itself BE a limit), then He can't ever become a person, so then He can't ever make a rock so heavy He can't lift it.

Since the answers here are so obvious, I don't think most people who ask this question are framing it your way. I think most people mean, "Can God retain all his powers and STILL make a rock so heavy he can't lift it." As I stated in the paragraph, above, the answer must be no.

Which means that God isn't literally ALL-powerful. His powers are limited by what's logically consistent.
posted by grumblebee at 9:17 AM on April 5, 2006

I don't know, that "rock so heavy he can't lift it" thing is pretty much the same as asking "Can God make a triangle with 2 sides?" or "Can God make water that isn't wet?" I don't think it has anything useful to tell us.
posted by ludwig_van at 9:31 AM on April 5, 2006

if you can, at minimum, represent the natural numbers in your system

if you can get by with just as many as you'll ever need, then there is no problem. it's only when you push to "all" natural numbers that you have problems (without that, no diagonalisation)

answering the orignal question - in my experience "godel escher and bach" leaves a lot of people cold/confused (i have a science background and it really annoyed me; i've leant it to friends from the humanities and they often end up lost).

i have seen various people mention this book which you might find preferable. i've not read it myself, but it seems to be considered a standard popular introduction.
posted by andrew cooke at 9:33 AM on April 5, 2006

If you want to understand the theorem itself, rather than the history surrounding it, I suggest you find a copy of the "Puzzle Guide to Goedel" by Rayond Smullyan.
posted by gd779 at 9:45 AM on April 5, 2006

Restricting the domain of inquiry to a finite subset is certainly possible. It's kind of cheating, though, ultimately, there is a meta-system (which can always be explicitly constructed) which cannot be restricted in such a way.

If we wanted to restrict the meta-system to a finite one, we can always identify interesting questions which will not fit in the proof-space of the finitary meta-system, too.

The central issue is that we, as humans, can always explicitly present an unresolvable problem relative to some system. So, while it's possible to do constructivist mathematics, there is no hope of constructivist mathematics accurately reflecting what a human mathematician does. Remember, mathematics is an exteriorization of interior thought. We can do practical math forever without running into incompleteness, but if our hope is to accurately reflect human thought in a formal system (i.e. in any form), Goedel showed it is not possible.

That is to say, if it is meaningless to induct to infinity, i.e. to use recursive functions, why is it so natural and fruitful?

It is about the mismatch of our interior intellectual life and our tools for representing it.
posted by sonofsamiam at 9:53 AM on April 5, 2006

For instance, ML type theory is constructivist mathematics in that you construct programs only according to certain meta-rules, the type system. Only type-correct programs are allowed, so the type system can enforce certain invariants.

But could anyone say that untyped programs are meaningless?

This is more than an analogy, it is an exact analogue by the Curry-Howard isomorphism. Disallowing use of the Law of the Excluded Middle is a type constraint. It is a meta-rule that restricts what would otherwise be valid inferences in the axiomatic system.
posted by sonofsamiam at 10:02 AM on April 5, 2006

It is exceedingly dangerous to rely on colloquial English summations of things like the Gödel theorem or the laws of thermodynamics or the Heisenberg principle.

These things are very rigorously described, but in mathematical terms. Pat descriptions like "You can't observe something without affecting it" (a popular summation of one aspect of the Heisenberg principle) or "order always degrades into chaos" (a popular summation of the Second Law of Thermodynamics) have caused more harm than good because they result in confusion and misapplication.

That's also the case for Turing's Stopping Problem. The popularization of that is "computers can't solve some problems" -- and it's true, as far as it goes. Problem is, it's also false, as far as it goes. The difficulty is the word "computer" in there; not all computers are "computers" within the realm of Turing's proof.

Any computer which is isomorphic to a Turing Machine cannot guarantee to solve the arbitrary Stopping Problem, or any other problem which is isomorphic to the Stopping Problem, in finite time. It happens that all computers in common use now are indeed isomorphic to the Turing machine, so that's of more than intellectual interest. But we know ways of designing computers which are not (e.g. dataflow systems, including analog computers), and working prototypes exist of such machines. Turing's proof doesn't apply to them.

It also turns out that biological computers (brains) are not isomorphic to the Turing Machine, and Turing's proof doesn't apply to them.

That doesn't mean those other systems can solve those problems; it just means that we can't prove whether they can or cannot. They might or they might not; Turing's proof offers no guidance.

"There are limits to what mathematics can prove" is a facile summary of Gödel -- but no mathematician ever claimed that math was universally applicable to all problems. Just as with Turing, Gödel's theory is of more than intellectual interest, but if you try to apply it broadly based on a colloquial description of the result, you're likely to get into trouble. It's better to try to understand it by studying the rigorous description of the result in order to understand what it does -- and more importantly, what it does not -- apply to.

Meanwhile, I would like to state that one can be a Humanist and still understand mathematics well enough to understand the true nature of these principles without having to rely on precariously inaccurate English language popularizations of them. A lot of scientists and engineers are Humanists, which word is not a synonym for "Humanities major".
posted by Steven C. Den Beste at 10:17 AM on April 5, 2006

Bertrand Russell has many essays, most of which are small-book length, that address topics along these lines and which are accessible to the non-mathematician. He certainly qualifies as a humanist, and is one of the more interesting people of the last century, to boot. (For instance, he both sat upon the lap of Queen Victoria as a child AND lived long enough to see humans on the moon.) Along with Alfred North Whitehead, the two of the penned their Principia Mathematica, which attempts to reduce just about everything to logic. It took them a few hundred pages, as I recall, to prove that 1+1=2, a seemingly simple rule rife with many implications. (Prinicipia is not all that accessible to non-mathemeticians. Russell's essays are.)



If you want a wonderful exploration of a variety of accessible math topics with implications over much of human activity, I recommend a series called 'The World of Mathematics', a compilation of 133 original papers with commentary by J. R. Newman:

THE WORLD OF MATHEMATICS (4 vols., 2479 pages)
A Small Library of the Literature of Mathematics from A'h-mose' the Scribe to Albert Einstein Presented with Commentaries and Notes by James R. Newman
Forward by Philip and Phylis Morrison
Tempus Books of Microsoft Corporation, Redmond, Washington 1988
QA3.W67 1988 510 88-20040
ISBN 1-55615-149-7 (cloth)
ISBN 1-55615-148-9 (paper)


Find it. Read it. You'll fall in love with the subject and find yourself very informed vis a vis your fellow humanists. Good luck!
posted by FauxScot at 12:20 PM on April 5, 2006

Blah blah logic, blah blah God, blah blah rock.

Shakespeare had it years ago.

HORATIO
O day and night, but this is wondrous strange!

HAMLET
And therefore as a stranger give it welcome.
There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy.
posted by frogan at 1:25 PM on April 5, 2006

sofs - i'm not sure i understand the point you're trying to make. if you use lem you're breaking the rules and you can't rely on the results. you can wax lyrical about how wonderful it is to break the rules, just as people wax lyrical about dynamic languages, but no matter how lyrical, they can't prove that their programs have consistent types.

i have no idea why inducting to infinity is so useful (well, see below), but that doesn't mean it's correct, any more than stealing sweeties from the shop is ok because they're such nice sweeties.

you're response to all that seems to be "but we lose xxx". but i'm not sure what it is exactly that you think we do lose. constructivist maths can do one heck of a lot, and could probably do another couple of hecks more if it were given more weight. saying "ooo but it's ugly" seems like a pretty pathetic excuse when the alternative is, as godel showed, that you are truly borked.

another way of looking at the same thing: induction is useful because it closely corresponds to the correct way to do maths. just like newtonian mechanics is pretty close to relativistic mechanics in a lot of cases. what boggles me is why physicists are quite happy about that, but mathematicians feel they have some kind of direct line to god that means, apparently, that they don't make mistakes and so are forced to arrive at the conclusion that proof that they've screwed is not, in fact, proof that they've screwed up, but some "deep" result that tells us wacka wacka wacka....meaningless philosophical evasion of the obvious: if soemthing breaks your axioms aren't right. if lem is a family friend, do you have a different candidate?

[ok, so i'm having rhetorical fun, and i may be wrong, but the above seems moderately reasonable to me - i honestly do not understand why constructivism hasn't come to dominate maths in the latter half of the last century. is it really just because it's hard? sheesh.]
posted by andrew cooke at 3:22 PM on April 5, 2006

Nice meta-philosophy you and Hamlet have going there :)
posted by flabdablet at 3:26 PM on April 5, 2006

By the way, it's possible to create a mathematically rigorous version of "Can God create a rock He cannot lift?" which avoids all the easy outs. Instead of talking about rocks, you describe it in terms of set theory.

Define the universe set V to be all actions. (Note that this particular set is not vulnerable to Russell's Paradox; it is possible for it to be complete.) Within that we define two subsets G representing all the actions God is capable of, and G' representing all actions God is not capable of. (G' is defined as being everything which is in V which is not in G.) The hypothesis is that G' is empty, because God is omnipotent and thus is capable of doing everything. (Thus the hypothesis is that G is equal to V.) There is no act that God cannot do, and therefore G' is the null set.

Let us define act A to be identify a member of G'. A is an action and therefore a member of V, so which subset is it a member of? In other words, can God identify an act that God cannot accomplish?

If A is a member of G, which means that God is capable of doing A, then it means that God can identify a member of G', and thus we know that G' is not empty (even though we may not know what it contains).

But if God cannot do A, then A is itself a member of G' (by the definition of G' as the set of all acts that God cannot accomplish), and G' is still not empty because it must contain A. Either way, G' cannot be empty, and thus we have proved that there must be something God cannot do.
posted by Steven C. Den Beste at 4:26 PM on April 5, 2006

Steven C. Den Beste : "If A is a member of G, which means that God is capable of doing A, then it means that God can identify a member of G', and thus we know that G' is not empty"

Why can't the result of A be 'none'?
posted by Gyan at 4:38 PM on April 5, 2006

Because that's not how A is defined. To accomplish A, it's necessary for God to identify a member of G', which is to say to show that G' is not the null set. If the answer is "none" then A is not accomplished. (And thus A is a member of G', which still proves that G' is not the null set.)
posted by Steven C. Den Beste at 5:03 PM on April 5, 2006

Steven C. Den Beste : "Because that's not how A is defined."

Then your setup presumes that there's a member: "can God identify an act that God cannot accomplish?". If there are no such acts, then God can't identify them because they don't exist, but this is not a lack of knowledge/power, but the idiosyncrasy of the linguistic expression that represents both possibilities: 1)can't identify acts because of lack of knowledge, and 2)can't identify acts because there aren't any. The second isn't a lack of ability, but the use of "can't" makes it seem that way.
posted by Gyan at 5:17 PM on April 5, 2006

I'm afraid not. Acts (members of G) are stated as imperatives, not as questions. And this is not a question of "idiosyncrasies of linguistic expression" because your subsidiary bifurcation is uninteresting. It doesn't matter why God can't do it; what's important is that He cannot.
posted by Steven C. Den Beste at 5:24 PM on April 5, 2006

Steven C. Den Beste : "It doesn't matter why God can't do it"

Like I said, saying God "cannot do" it (when G' is a null set) is an idiosyncrasy of language, not an expression of impotence, just like asking a childless guy whether he knows the names of all his children.
posted by Gyan at 5:31 PM on April 5, 2006

I can't believe this thread devolved into the elementary school conundrum of God and lifting rocks.

Gyan: All he's trying to say is that:

If God cannot name something he cannot do then that is one thing that God cannot do.

Although, in this case, God can name something he cannot do (namely, that he cannot name something he cannot do) and thus he can do that after all! :)
posted by vacapinta at 7:13 PM on April 5, 2006

vacapinta : "If God cannot name something he cannot do then that is one thing that God cannot do."

All I'm trying to say is that the third 'cannot' in your example means the same as the first, only if there is something that God is unable to do, else the third 'cannot' is an overloaded linguistic mutant. The 'cannot' in nonreferent claims is not equivalent i.e. "God cannot kill the bald king of France".
posted by Gyan at 8:30 PM on April 5, 2006

Thanks for your answers!

"Your reference to humanism makes me think that you're trying to apply Gödel's theorem to life."

The reason I'm asking this is because I'm reading Ray Kurzweil's "The Singularity is near" where he writes that Gödel's incompleteness theorem is "a proof demonstrating that there are definite limits to what logic, mathematics, and by extension computation can do".

I didn't know this, and had always assumed that logic/mathematics were perfect, consistent and completely provable. This made me want to learn more about the implications of Gödel's theorem. It seemed to me that humanists/intellectuals discuss logics without mentioning/knowledge of Gödel.

That "the number of mathematical facts that can be proven --- is vanishingly small" is interesting to learn, even though it has little relevance to daily life.

Kuhn's "Structure of scientific revolutions" has been on my reading list for a long time. Also, this "people often connect Goedel and Wittgenstein, and there are some similarities in their arguments" is interesting and worth exploring. I wish I had the time.
posted by Termite at 12:09 AM on April 6, 2006

I want to second the recommendations for The World of Mathematics and Goedel's Proof (Nagel and Newman). The first made me want to become a mathematician and the second made me glad I'd studied enough math to enjoy the thrill of the proof.

I used to enjoy baffling my fellow fifth-graders with that God/rock thing, but why are we talking about it here?
posted by languagehat at 6:53 AM on April 6, 2006

andrew cooke: is constructivist mathematics the correct way to do mathematics? It depends on what you want to do.

I tend towards formalism, I see no problem with exploring untyped or inconsistent axiomatic systems. They can only be judged "incorrect" relative to some type restrictions.

How do we decide which type restrictions are correct (i.e. no lem)? We can only decide relative to some higher-order conception of correctness, that is, some metatype regimen, for instance, no infinities. Like in Haskell, "kinds" are the metatype of types.

How did we decide to to use this particular metatype (kind) regimen? There is no bottom to this inquiry, and no good reason to suppose this inquiry is meaningless, other than the fact it may make us uncomfortable.

There can never be a solid foundation for mathematics, we can only provisionally restrict ourselves to one context or another.
posted by sonofsamiam at 9:14 AM on April 6, 2006

"Correct" isn't a meaningful concept applied to math. There are only two questions that matter.

1. Does a given kind of mathematics embody contradictions? I.e. is there any statement that the system can prove both to be true and to be false? If so, it's useless and should be tossed in the ashcan.

2. Is a given kind of mathematics isomorphic to a problem we are trying to solve? If so, it can be used to solve the problem. (You can't use plane geometry to navigate on the Earth because the surface of the earth is not a plane.) If not, it should be put on the shelf until the next problem comes along, which it might well be able to solve.
posted by Steven C. Den Beste at 9:16 PM on April 6, 2006