wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> All Sigs. are false
        
(Message started by: Icarus on Nov 3^rd, 2002, 7:59pm)

Title: All Sigs. are false
Post by Icarus on Nov 3^rd, 2002, 7:59pm

A certain UberPuzzler in a certain puzzle forum uses the signature "All signatures are false". What is the most that can be deduced from this alone (i.e. without any knowledge of other signatures)?

With apologies to J.F.

Title: Re: NEW PUZZLE: All Sigs. are false
Post by TimMann on Nov 4^th, 2002, 12:14am

Nothing -- the self-referential statement is meaningless.

Suppose one tries to go along with the gag and assign a truth value to the statement. If you pick "true," you have a contradiction: a true statement saying that it itself is false. If you pick "false," you don't have an immediate contradiction, so you conclude that the statement must be false. That is, "not all signatures are false". But this signature is false, so some other signature must be true.

But that conclusion is unjustified. The mere existence of a signature that says "All signatures are false" does not guarantee that someone else's signature is true. Nothing is stopping everyone else from signing their messages with false statements.

Title: Re: NEW PUZZLE: All Sigs. are false
Post by James Fingas on Nov 4^th, 2002, 8:47am

All conclusions about self-referential statements are false. 8)Especially the conclusion that they neccessarily have no meaning.

Title: Re: NEW PUZZLE: All Sigs. are false
Post by TimMann on Nov 4^th, 2002, 2:40pm

Is that statement itself a conclusion about self-referential statements? :o

Title: Re: NEW PUZZLE: All Sigs. are false
Post by Chronos on Nov 4^th, 2002, 11:50pm

I disagree with TimMann: One may at least conclude that there is at least one sig which is not true.

Title: Re: NEW PUZZLE: All Sigs. are false
Post by James Fingas on Nov 5^th, 2002, 6:37am

Since the statement is a conclusion about conclusions about self-referential statements, then it only becomes a conclusion about self-referential statements if there is a self-referential conclusion about self-referential statements, like this one:

It can be proven that not all logical deductions made from self-referential statements can be true.

Chronos,
That is only true if we know that there is more than a single signature. The question doesn't allow us to make that assumption.

Title: Re: NEW PUZZLE: All Sigs. are false
Post by towr on Nov 5^th, 2002, 8:30am

on 11/05/02 at 06:37:20, James Fingas wrote:

Chronos,
That is only true if we know that there is more than a single signature. The question doesn't allow us to make that assumption.

If there is no other signature the one above still can not be true, which makes at least one. (It would be a contradiction if it were true). Which is not to say it's false.. Something may conceivably be neither true nor false..

Title: Re: PUZZLE: All Sigs. are false
Post by Icarus on Nov 5^th, 2002, 4:43pm

This is generating more interest from the Forum regulars than I expected! I figured it to be more of a "newbie" puzzle.

Still, a stronger statement than Chronos' can be made, despite Tim's and James' objections. Towr has indicated part of it.

Title: Re: PUZZLE: All Sigs. are false
Post by Jeremy on Nov 6^th, 2002, 5:22pm

i agree with chronos.
"there is at least one non-true signature"
can you say there is at least one false signature?

Title: Re: PUZZLE: All Sigs. are false
Post by TimMann on Nov 6^th, 2002, 5:29pm

I guess we are working in something other than 2-valued logic here?

Title: Re: PUZZLE: All Sigs. are false
Post by Icarus on Nov 6^th, 2002, 7:03pm

on 11/06/02 at 17:29:56, TimMann wrote:

I guess we are working in something other than 2-valued logic here?

Yes and no. 2-valued logic has more than two values.

Title: Re: PUZZLE: All Sigs. are false
Post by towr on Nov 7^th, 2002, 5:35am

Not really, that would make it three-valued at the least..
'Unknown' or 'undetermined' is a value in its own right..
There's no good way to handle it though.. Even-numbered logics make more sense.. (imo)

Title: Re: PUZZLE: All Sigs. are false
Post by Jonathan_the_Red on Nov 7^th, 2002, 11:32am

Tim's got it right; you can't deduce a damned thing.

Smullyan touches on this issue. Suppose you've got two boxes, and you're told that there is gold in one of them. The boxes are labeled:

A: Both of the statements on these boxes are false.
B: The gold is in Box A

Using a little rudimentary logic, you deduce that the gold must be in box A. Right?

Well, shoot, there's nothing out there that would stop me from taking two boxes, writing the above statements on them, and then sticking the gold in Box B. The universe will not implode if I do so. Heck, I just now said "This sentence is false" out loud, and no bolt of lightning from the heavens struck me down.

So, suppose there are a total of three puzzlers in the universe, each with his own signature. Suppose they are:

1. All signatures are false.
2. 2+2=5.
3. Carrot Top is funny.

What can you deduce from #1? Absolutely nothing.

Title: Re: PUZZLE: All Sigs. are false
Post by TimMann on Nov 7^th, 2002, 12:38pm

I suppose it depends on how we go about deducing. If our method is to translate the sigs into 2-valued predicate logic or the like, take them as axioms, and see what theorems follow, then we can't even get started, because "this statement is false" has no translation into predicate logic.

If we work in a larger system, we can deduce various things. For instance, we can deduce that at least one uberpuzzler has a sig that does not translate into predicate logic. That's what I meant by calling it meaningless, by the way. You could say I deduced that, if you want to use the word "deduced" that way.

Title: Re: PUZZLE: All Sigs. are false
Post by James Fingas on Nov 7^th, 2002, 1:48pm

I hereby christen this thread with the dual names 101 Ways to Beat a Dead Horse, and The Definitive Guide on Semantic Quibbling

I would also like to point out that "you can't deduce a darned thing" is, technically, a deduction--proving itself false ;D

Title: Re: PUZZLE: All Sigs. are false
Post by Icarus on Nov 7^th, 2002, 3:31pm

How about this then,

The signature "all signatures are false" is either false, or a contradiction.

It's stronger than Chronos' statement in two ways. It tells you what signature is not true, instead of just saying that one exists. It also specifies the value of the signature more tightly than "not true".

And it is logically deducible from the existance of the signature "all signatures are false."

As for logic values, 2-valued logic divides well-defined statements into 4 or 5 classes, depending on how you count them. They are:

1) Truths
2) Falsehoods
3) Contradictions (e.g. "This sentence is false".)
4) Indeterminants (e.g. "This sentence is true".)
5) Undecidables (Which statements are undecidable depends on the axioms one starts with, but by Goedel we know that any useful logic system has them.)

You can view the indeterminants as being part of the undecidables, or count them separately.

Title: Re: PUZZLE: All Sigs. are false
Post by TimMann on Nov 7^th, 2002, 6:33pm

A statement that is Godel-undecidable is either true or false. We just can't prove either from the axioms of the system in question.

Contradictions and indeterminates come in if you admit self-referential statements as well-formed formulas in your logic. Simpler logics such as predicate calculus don't have any way to generate self-referential statements.

The proof of Godel's incompleteness theorem can be seen as a clever way to sneak self-reference into a system that doesn't appear to have it. You need a system at least as powerful as arithmetic for it to work, though.

Title: Re: PUZZLE: All Sigs. are false
Post by Icarus on Nov 8^th, 2002, 3:04pm

on 11/07/02 at 18:33:26, TimMann wrote:

A statement that is Godel-undecidable is either true or false. We just can't prove either from the axioms of the system in question.

A statement is true if it can be proved. A statement is false if its negation can be proved. A statement that is undecidable is neither true nor false. We may establish subsystems with added axioms which decide it either way. In those systems it is true or false, but not in the original.

Quote:

Contradictions and indeterminates come in if you admit self-referential statements as well-formed formulas in your logic. Simpler logics such as predicate calculus don't have any way to generate self-referential statements.

True (though only of the simplist logic systems), but not applicable here, as the logic in question certainly does admit self-referential formulas. The whole puzzle is about one!

Quote:

The proof of Godel's incompleteness theorem can be seen as a clever way to sneak self-reference into a system that doesn't appear to have it. You need a system at least as powerful as arithmetic for it to work, though.

For the proof of Goedel's theorem to work, you need a system with the ability to create statements equivalent to arithmetical statements. (Which any truly useful logic system has. Predicate calculus cannot take you very far on its own.)

Certainly this is true for the logic system under discussion in this puzzle. But even if you dispute this, we still have undecidability, as the statement "This sentence is true" is undecidable.

One possible complaint that I am compelled to bow to is that indeterminants are not a well-defined class. I have realized that I do not have a good way of defining which undecidable statements are indeterminant. I think it can be (and has been) done, but I do not recall one, so I will retract the "indeterminant" value, and say that "2-valued" logic systems have 4 classes of statements: Truths, Falsehoods, Contradictions, and Undecidables.

The fact that a few highly restricted logic systems have no contradictions or undecidables does not disprove this general statement about "2-valued" logic systems. Most systems that have been formulated have statements in all 4 classes.

Title: Re: PUZZLE: All Sigs. are false
Post by TimMann on Nov 8^th, 2002, 7:05pm

You don't say what system we're actually talking about. Natural language, I guess. Natural language is not a formal system, and it of course has all kinds of odd things in it, including ambiguous statements, questions, meaningless sentences, etc.

I still don't agree with this part:

Quote:

A statement is true if it can be proved. A statement is false if its negation can be proved. A statement that is undecidable is neither true nor false.

I suppose you can define true and false this way, but it's not conventional as far as I know.

The sentence that Godel's incompleteness proof actually generates amounts to "there does not exist a proof for this statement". Suppose a logic is expressive enough to let you write that statement. Then either the statement has a proof or it does not. If it does, the logic is inconsistent. If it does not, then the statement is true but not provable. So actually, Godel's proof doesn't generate a statement that's neither true nor false; it generates a statement that's true but not provable.

Title: Re: PUZZLE: All Sigs. are false
Post by Icarus on Nov 9^th, 2002, 11:35am

The system in the puzzle is evidently a standard logical system with the single additional axiom

The statement "All signatures are false" is a signature.

In order to interpret this, obviously some relations (the signatures) must be quantizable, but any other assumptions are precluded by the "deduced from this alone" clause.

Quote:

I still don't agree with this part:
Quote:A statement is true if it can be proved. A statement is false if its negation can be proved. A statement that is undecidable is neither true nor false.

I suppose you can define true and false this way, but it's not conventional as far as I know.

So then, tell me which is true?

The sum of the angles of a triangle add up to two right angles.

The sum of the angles of a triangle add up to less than two right angles.

By your reasoning, and accepting the rest of the postulates of geometry, one of these is true, and the other false. So who was blowing wind? Was it Euclid, Archimedes, and Pythagorus, or was it Gauss, Boylai, and Lobatchevsky?

The truth is, in the logical system whose axioms are the remaining postulates of geometry, neither statement can be viewed as either true or false. In the geometry each produces, it is possible to build a model of the other geometry. Hence to declare one of them true (even if unprovable), and thus the other false, leads to a contradiction in the metamathematics.

The definition I gave for true and false is conventional. Indeed, it is the only consistent definition I have ever heard.

I do not have a full answer to your remaining points yet. It's been too long since I last looked at Goedel's theorem. I believe the problem with "there is no proof of this statement" is a mixing of logic and metalogic (logic about logical systems), but I will need more thought on the matter.

This is getting really deep (however you want to interpret that! :D) for what I thought of a quick little puzzle. Does anyone else want to get into a discussion on the meaning of truth?

One last side matter. Some people may be wondering why I keep spelling the name as Goedel, while Tim uses Godel. The actual spelling of the name is G o-umlaut d e l. O-umlaut is an o with the two little dots above it, and has the alternative form of oe run together into a single character. I was taught that when neither is available, "oe" is the accepted way of representing it. However, it is also quite common simply to use "o" and ignore the umlaut. I suppose you can use which ever you prefer, and I will keep doing as I have until Wowbagger, Towr, or some other native German speaker weighs in on the subject.

Title: Re: PUZZLE: All Sigs. are false
Post by Chronos on Nov 9^th, 2002, 2:02pm

One can solve that triangle problem in at least two different ways. First, one can restrict the definition of a triangle in such a way as to specify the curvature of the space in which it is found. Second, one can allow figures of either sort to be considered "triangles", and then say that one of the statements is true, depending on the triangle.

To put it another way: Which of the following statements is true?

A rectangle has length equal to its width
A rectangle has length unequal to its width

The answer, of course, is that it depends on the rectangle. For some rectangles, the first is true, and for some, the second is true. Or, we could specify that a rectangle is an equiangular quadrilateral which is not a square, and then the second is true and the first is false.

Title: Re: PUZZLE: All Sigs. are false
Post by TimMann on Nov 9^th, 2002, 5:43pm

Hi, Icarus. We're definitely talking past each other. Perhaps it's been too long since both of us studied formal logic. I've pulled out my old metalogic textbook to review. I'm guessing that part of the problem may also be that you learned different terminology than I did. Forgive me if I assume that the terminology I know is standard. Where I had any doubt, I've been looking things up on MathWorld -- maybe not the world's most authoritative reference, but the best one I have handy.

I'll ask you questions about some things and try to clear up some things.

Quote:

A standard logical system with the single additional axiom: The statement "All signatures are false" is a signature.

How do you translate this axiom from English into the formal notation of a standard logical system? I can't apply any rules of inference to a string of English words. I'm not being willfully obtuse here. I don't know how to write a self-referential statement in any of the standard logical systems I'm familiar with, so I don't know what I can deduce from it.

Also, I have to ask what you mean by "some relations must be quantizable". I don't see how a signature is a relation, so you must be using that term in a different sense than I'm familiar with. And the term "quantizable" isn't familar to me at all.

* * *

You bring up the issue of Euclidean vs. non-Euclidean geometry to refute what I said about truth vs. falsity, but it's not relevant; I wasn't saying what you thought I was saying. Let me clarify that.

Formal systems have a model theory and a proof theory.

The model theory of a system deals with interpretations, where every wff of the system is assigned a truth value. In 2-valued logic, this truth value must be either true or false, nothing else. There are some wffs that are true under all interpretations; these are called logically valid.

The proof theory of a system deals with axioms and rules of inference. In the proof theory, there can certainly exist a wff A such that neither A nor ~A is a theorem. In that case the system is said to be incomplete.

One is often interested in choosing axioms and rules of inference such that the proof-theoretic concepts of theorem and non-theorem match up with the model-theoretic concept of logical validity. That is, we would like statements that are true under all assignments of truth values to atomic variables to also be theorems, and other statements not to be theorems.

For example, in propositional logic, whether "p" is true depends on the interpretation, but "p OR ~p" is true under all interpretations, and hence logically valid. In propositional logic with the usual proof theory, a statement is logically valid iff it is a theorem. However, in other systems you can have a logically valid statement A where neither A nor ~A is a theorem. Such a statement can be called undecidable, although this can be a bit confusing because "undecidable" also has another completely different meaning: if there is no effective method (finite-time algorithm) to determine whether something is in a set, the set is said to be undecidable.

Although it doesn't make an issue of it, the logic text I'm rereading is careful not to use the words "true" or "false" for either logical validity or theoremhood. It uses them only in the concept of "true relative to an interpretation I". That's why I objected when you said that "true" means "provable" and "false" means "the negation is provable." (Though my memory was a bit fuzzy on that point. I was thinking that "true", unqualified by "relative to an interpretation", was conventionally used to mean "true under any interpretation" -- i.e., logically valid.)

Despite the logic textbook usage, though, I'll concede that it's reasonable to use "A is true" and "A is false" to mean "A is a theorem" and "~A is a theorem" when you're dealing with mathematics in a broader context and not just chopping formal logic. In fact, I'm sure that is conventional among most mathematicians, because they're mostly concerned with working with a standard set of axioms and finding whether something can be proved or disproved. I assumed we weren't doing that here because this is a logic puzzle, but that was a bit rash.

Using the words this way can lead to confusion at times. The statement that Gödel's incompleteness theorem constructs is not provable within the system under consideration, but it must be true under any interpretation. So the Gödel sentence is neither true nor false if by "true" you mean syntactically provable within the system, but it is true if by "true" you mean that the sentence must be semantically true under any interpretation.

* * *

The example of Euclidean vs. non-Euclidean geometry is fairly trivial, of course. I'm sure you brought it up only because you thought I was saying that every statement is "really" true or false in some universal way, which was not what I was saying at all. But I'll say a bit about it anyway.

The axioms of geometry without Euclid's parallel postulate are not sufficient to either prove or disprove every geometrical statement. Thus the parallel postulate is independent of the other axioms: we can obtain a consistent formal system by either affirming it or adopting one of two other axioms that contradict it. It's also cool that we can find a model of each system within the others. (Hmm, is that true for all six possibilities? I don't know.) It was surprising to mathematicians at the time that the parallel postulate was independent, and also surprising that such nice models could be found for the two non-Euclidean geometries.

Working in the system where none of these axioms is adopted is interesting too; I've read that one of the founders of non-Euclidean geometry (I forget which) called this "absolute geometry" and proved a number of theorems in it. Such theorems are correct in both Euclidean and non-Euclidean geometry, of course. This system is definitely incomplete; there are many statements A for which neither A nor ~A is a theorem, or as you'd say, A is neither true nor false -- in particular, the parallel postulate itself! That doesn't stop the system from being useful and interesting.

The Continuum Hypothesis has also been shown to be independent of the rest of mathematics, by the way. This is an interesting case because I believe it's customary neither to adopt it as an axiom nor to adopt something that contradicts it. I suppose this is because the truth or falsity of this statement doesn't matter for any of the applications of mathematics (i.e., models) that we've thought of, unlike the parallel postulate, which makes a difference when trying to apply mathematics to the physical world. So here we have a case where it's standard to knowingly work in an incomplete formal system.

* * *

(By the way, I speak some German and I know how to spell Gödel correctly. I was just being lazy about not looking for my compose key to get the umlaut there, and not sticking in the e to compensate.)

* * *

Edit: rewrote some paragraphs to correct errors, one rather serious. Apologies to those who may have read this before I corrected it, but I thought it would work better to correct it with an edit than to post again.

Title: Re: PUZZLE: All Sigs. are false
Post by Icarus on Nov 9^th, 2002, 10:01pm

Chronos: There is no problem to solve. This was a response to Tim's earlier statement
Quote:

A statement that is Godel-undecidable is either true or false. We just can't prove either from the axioms of the system in question.

, which I had interpreted as meaning that every statement was in some way either true or false, and that undecidability (actually independence) merely meant we could not figure it out. The example amply demonstrates the flaw of such a position. In Absolute Geometry (I had forgotten that term), neither statement is provable, and more to the point, neither can be viewed in absolute geometry as either true or false. If you set things up so that one is true, you can also model the geometry with it false, disputing it's absolute truth! It was this discovery of a model for Hyperbolic geometry within Euclidean geometry (sort of) that lead mathematicians to finally accept Hyperbolic geometry as legit. Apparently though, this interpretation of Tim's comment was not what he meant.

Tim:
It's definitely been way too long since I studied symbolic logic anyway. I had completely forgotten about atoms, etc. By "Quantization" I meant "quantification", which I assume you now recognize. For those who might not, it refers to the "for all" and "there exists" operators. Attaching one of them to a statement is called "quantifying it". Formal logics usually do not include variables for "statements", "relations", "wffs", or whatever else you want to call them, for the very good reason that they allow self-reference and the horrible quagmire that comes with it. So this puzzle must extend beyond the normal course of formal logics to even exist. However we can formalize it as follows:

Add relational variables: we can say "P is a relation" in the system, not just in the metalogic.

Add a new primative relation (I've forgotten the proper terminology and am to lazy to look it up): "P is a signature".

The sig in question formalizes to:

For all P, P is signature ==> NOT P.

As an axiom, we have the statement

"For all P, P is signature ==> NOT P" is a signature.

My claim is that in any system with this, you can prove:

(NOT X) or ( X <==> NOT X)

where X is "For all P, P is signature ==> NOT P"

Note that any actual interpretation of "is a signature" is not needed for this. It is merely a condition on statements for which we know only one statement for which it is true.

I am a mathematician, so that is the way I invariably approach anything. This means that strict logical concepts have long since faded from my memory, replaced by the more robust (for my purposes) mathematical concepts that I actually use. Pardon me for misinterpreting your remarks.

Side point: In your comments you mentioned replacing the parallel postulate with two others. Were you refering to Spherical geometry? If so, I have to point out that in Absolute geometry, the spherical case is excluded, so you have to weaken the other axioms to obtain it.

Side point 2: I did not know if you were aware of the correct spelling of Goedel or not. But I figured that someone along the line almost certainly would not know, and think I was misspelling since they were not used to seeing the "e". While I have to accept my mistakes with grace, to be thought mistaken when I was not is something not to be borne! ;)

Edited to add---
I'll have to rethink the formalized version of my "Sig is false or a contradiction" statement. The one I gave is formally equivalent to NOT X, which is stronger than what can actually by shown.

Title: Re: PUZZLE: All Sigs. are false
Post by TimMann on Nov 9^th, 2002, 10:37pm

Icarus, thanks for your gracious response. I was editing my last message while you were posting yours, so you might want to look back at mine.

About "quantize"; the word for that that I'm familiar with is "quantify", but maybe "quantize" is common too. I thought you might mean "quantify", but I still didn't get your meaning from that when I first read your post. I also didn't realize that "relation" could be another word for statement or wff. Thanks.

Also, I didn't know that absolute geometry excludes spherical geometry. Thanks.

I'll await the re-formalized version of the puzzle. I think ZF set theory might be handy as another way to formalize it. Unfortunately I don't own a text on that and my memory of it is way too fuzzy.

I can't call myself a mathematician; I'm at best twice removed from one, as my Ph.D. is in computer science -- not even theoretical computer science, which is basically a form of applied mathematics, but operating systems. Logic has always been an interest of mine, though, and I had lots of chances to learn about it, between doing a B.S. in mathematics, taking the generally required C.S. Ph.D. courses, and hanging out with some logicians at the research lab where I worked after graduation and trying to read books they recommended. It's nice to have an occasion to go back and review it and improve my understanding.

Title: Re: PUZZLE: All Sigs. are false
Post by towr on Nov 10^th, 2002, 7:19am

on 11/09/02 at 11:35:00, Icarus wrote:

However, it is also quite common simply to use "o" and ignore the umlaut. I suppose you can use which ever you prefer, and I will keep doing as I have until Wowbagger, Towr, or some other native German speaker weighs in on the subject.

I'm _not_ a native german speaker.. I'm not a German, and don't live in Germany.. Quite frankly I hate the language..
The Netherlands is the small country next to Germany, above Belgium, another small country next to germany, half of which speaks Dutch like we do in the Netherlands, which is not German.. I'm also a native Frisian speaker, the second state-language of the Netherlands, which is also not like German (actually it's a close relative to English, which is also not German)

anyway.. internet convention is to ignore accents, umlauts etc, while it's also acceptable to use oe for ö, ae for ä or ue for ü, since that's the more like the sound it is.. as far as I know :p
(but we don't really have any accents or umlauts in Frisian nor in Dutch )

Title: Re: PUZZLE: All Sigs. are false
Post by towr on Nov 10^th, 2002, 7:45am

"All signatures are false" isn't undecidable.. once you have any signature that is true it's decidably false..
So one thing you could deduce is that if you ever find a signature that is true you can decide on the problem..

While you've only found false signatures it will still be consistent that "All signatures are false" is false, since it is consistent that you will find a true signature one day. (Consistent means you can't prove the opposite.)

Proving a universally quantified statement true is impossible if the domain isn't closed (which holds for real world systems, or at least that's consitent). But proving it false only need one counterexample.

It's not a tautology (always true) or contradiction (always false), so you can't prove it generally true or false, it depends on the world you're possibly in (possible worlds-model).
I'm not really sure what happens when you eliminated all worlds with more that one signature as possible.. (Luckily in a real-world situation that's impossible :P )

Maybe the statement can be formalized in lambda-calculus.. Any other logic system I'm familiar with certainly can't handle the self-reference.. But lambda-calculus does have unprovable (undecidable) statements.. Unless it's typed lambda-calculus, but then you can't make self-references..

Title: Re: PUZZLE: All Sigs. are false
Post by Icarus on Nov 10^th, 2002, 2:04pm

Towr: First, my deepest apologies for thinking you were a native German speaker. I knew you were from the Netherlands, but was under the false impression that German was the native language there. Thank you for setting me straight.

I never agued that "All sigs are false" is undecidable. Indeed my argument is that it is decidable, and in fact decides to either being false, or contradictory. By "contradictory" I mean that assigning a value of "true" leads to a proof that it is false, and assigning it a value of "false" leads to a proof that it is true. Such a statement cannot be assigned a value of either "true" or "false", but only makes a system inconsistent if the system demands it is either "true" or "false".

The sentence I claim is undecidable unless one specifically makes it or it's negation an axiom is "This sentence is true."

Tim:

Quote:

About "quantize"; the word for that that I'm familiar with is "quantify", but maybe "quantize" is common too.

No, "quantize" was just me grabbing the wrong word. I meant "quantify".

Quote:

I'll await the re-formalized version of the puzzle.

Groan... Why do I get myself into these things. Now I'm going to have to sit down and create/recreate a logical system with logical variables that does not immediately run into a variant of Russell's paradox!

Title: Re: All Sigs. are false
Post by Icarus on Nov 11^th, 2002, 4:45pm

Okay, this is what I have figured out: A soon as you add the ability for self-reference into a 2-valued model theory, it becomes inconsistant. The reason is simply what I stated in my last post. 2-valued model theories demand that all statements have a value of true or false. But assigning either value to a contradictory statement leads to a contradiction. So with 2-valued model theories, you either have to totally exclude self-reference or else introduce complicated rules for constructing wwfs so that no contradictory statements can be constructed in the first place (similar to the Russell-Whitehead approach to solving Russell's paradox).

This was fairly obvious, but I thought that a 2-valued proof theory would work, since proof theories do not demand a truth value for every statement. Unfortunately, in any 2-valued system where the statements make sense, the statement "All sigs all false" implies the statement " "All sigs are false" is not a sig". Thus, this whole puzzle cannot exist in a 2-valued logic without being inconsistent! Regardless of whether one uses a model theory or a proof theory.

In my defense, I will say that the multi-valued nature of the problem is implicit in its statement. And it is still wrong to say that "All sigs are false" is meaningless even in a 2-valued logic. Inconsistencies are full of meaning, all of it bad.

So, introduce a third truth value (C="Contradictory"), and a new logical operator CON. Our tables are:

CON T = F
CON F = F
CON C = T

NOT C = C

T OR C = T
F OR C = C
C OR C = C

T AND C = C
F AND C = F
C AND C = C

T => C = C
F => C = T
C => T = T
C => F = C
C => C = C

The equivalences A AND B = NOT ( NOT A OR NOT B) and ( A => B) = (NOT A OR B) still hold.

The strongest statement derivable from ' "All sigs are false"
is a signature ' is then

NOT X OR CON X

where X is the statement "All sigs are false" (i.e. FOR ALL P, P is a signature => NOT P).

Does this pass muster, Tim? :D

Title: Re: All Sigs. are false
Post by TimMann on Nov 11^th, 2002, 10:18pm

I definitely agree with the model theory part.

I think I agree with the proof theory part, but it's still confusing me a little, so I'm going to think about it some more and see if I can explain why I believe it.

I know very little about non-2-valued logic, but the 3-valued logic solution looks good to me. You can also conclude that NOT x implies that there is more than one sig, though, can't you?

Title: Re: All Sigs. are false
Post by towr on Nov 12^th, 2002, 3:59am

well, NOT(x) would expand to
NOT(FORALL(x; SIG(x) => NOT(x)))
which is equivalent with
THEREIS(x; SIG(x) AND x)
So it's equivalent in saying that there is another (true) signature if the statement isn't contradictory..

Title: Re: All Sigs. are false
Post by James Fingas on Nov 12^th, 2002, 9:21am

From a more philosophical point of view, do you suppose the author of this quote could have been trying to caution fellow forum-goers that:

Not all sigs are true--and not all sigs are false.
Some sigs may be meaningless, but don't jump to conclusions.

Or maybe the author was just trying to be funny...

Title: Re: All Sigs. are false
Post by Icarus on Nov 12^th, 2002, 3:59pm

My knowledge of multi-valued logics is pretty shaky as well. Fuzzy logic is the only one I have given more than a cursory glance to.

NOT X does indeed imply a second signature, but NOT X is not implied by NOT X OR CON X

As to why in a 2-valued proof theory provides a proof that ' "all sigs are false" is not a sig ', letting X="all sigs are false", Assume X is a sig. Then X => NOT X, that is: NOT X OR NOT X, which is equivalent to NOT X. Which as Towr points out is THERE EXISTS (P: SIG(P) AND P). Hmmm, I guess I overshot. The statement that can be proven in a 2-valued system is: There is a true signature, or X is not a signature.

So either there is a true signature or the 2-valued puzzle is inconsistent. (There is no reason to assume that it isn't inconsistent.)

James: Yes, I apologize for hijacking your signature and flying off with it to places you never intended for it to go. But I'm not sorry I did. I have brushed off concepts I haven't used in years, clarified (at least to me) my thinking, and learned a few things in the process. If that doesn't make for a good puzzle, I don't know what does! ::)

Title: Re: All Sigs. are false
Post by TimMann on Nov 12^th, 2002, 6:51pm

Cool, sounds like we have converged.

On the 3-valued logic formulation, all I meant to say was that you can deduce (NOT X AND EXISTS P in Sigs: P) OR CON X. I don't suppose that's really deducing "more" than NOT X OR CON X, though. "What's the most you can deduce?" is a somewhat fuzzy question.

I basically agree about the proof theory too, now that you've slightly revised what you said. As far as I can see, one can't construct a syntactic inconsistency (i.e., you can't prove both A and ~A as theorems for any A). But the results of reasoning about whether or not X can be a sig are still unsatisfactory, because they don't agree with our intended model. That is, we can prove a theorem that we don't want to have as a theorem, namely "There is a true signature (!= X), or X is not a signature." We don't like this theorem because it seems to constrain what elements the set of sigs can have in a strange way. We naively expect to be able to include X in the set of sigs, and we don't expect this to require us to include something else in the set too.

I think (based on vague memory) that this problem is closely related to one that's dealt with in ZF set theory, where one needs to make a rule about what conditions define a set and what conditions do not. In particular, to avoid Russell's paradox, you have to say that "the set of all sets that do not contain themselves" is not a condition that defines a set. In fact, I think ZF probably tells us that if we say that X must be in the set of sigs, we're failing to define a set.

Title: Re: All Sigs. are false
Post by James Fingas on Nov 13^th, 2002, 5:51am

We can say that in 2-valued logic, then either X is not a sig or there is another true sig (that isn't X) with perfect validity. All we are really saying is that at least one of the following is true:

1) X is not a sig (this is obviously not true, because X is a sig according to the question)

2) There is a true signature out there, and the sig stating X is not it. This may or may not be true, and of course, this is where the "no knowledge of any other signatures" comes in.

3) The veracity of X cannot be stated in 2-valued logic. This is the key, because of course when you work the problem out in 2-valued logic you are making the implicit assumption that it can be worked out in 2-valued logic.

I don't see any logical inconsitencies here ...

Title: Re: All Sigs. are false
Post by Chronos on Nov 13^th, 2002, 1:32pm

Quoth TimMann:
Quote:

Working in the system where none of these axioms is adopted is interesting too; I've read that one of the founders of non-Euclidean geometry (I forget which) called this "absolute geometry" and proved a number of theorems in it.

I'm not sure who the fellow is you're referring to, but the first person to attempt something like this was Euclid himself. Read through the Elements sometime: His first 30 or so propositions are all things which don't require the P. P., and after that, there's only one (fairly minor) theorem which does not. He wasn't all that comfortable with the Parallel Postulate, either, so he wanted to at least lay a foundation which future mathematicians might use to try to prove it.

Title: Re: All Sigs. are false
Post by Icarus on Nov 13^th, 2002, 3:54pm

on 11/13/02 at 05:51:23, James Fingas wrote:

I don't see any logical inconsitencies here ...

You will notice that I said the 2-valued puzzle is inconsistent if there are no true signatures. This disallows your cases 2 and 3, leaving 1 as the only possibility. But it too is contradicted by the statement of the puzzle. Hence the inconsistency. The point was, in a system with no true signatures, 2-valued logic must be abandoned for this puzzle to make sense.