Author |
Topic: All Sigs. are false (Read 4820 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: PUZZLE: All Sigs. are false
« Reply #25 on: Nov 10th, 2002, 7:45am » |
 Quote  Modify
|
"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  )
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..
|
|
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: PUZZLE: All Sigs. are false
« Reply #26 on: Nov 10th, 2002, 2:04pm » |
Quote Modify
|
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!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: All Sigs. are false
« Reply #27 on: Nov 11th, 2002, 4:45pm » |
Quote Modify
|
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? 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: All Sigs. are false
« Reply #28 on: Nov 11th, 2002, 10:18pm » |
Quote Modify
|
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?
|
| « Last Edit: Nov 11th, 2002, 10:22pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: All Sigs. are false
« Reply #29 on: Nov 12th, 2002, 3:59am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: All Sigs. are false
« Reply #30 on: Nov 12th, 2002, 9:21am » |
Quote Modify
|
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...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: All Sigs. are false
« Reply #31 on: Nov 12th, 2002, 3:59pm » |
Quote Modify
|
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! 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: All Sigs. are false
« Reply #32 on: Nov 12th, 2002, 6:51pm » |
Quote Modify
|
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.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: All Sigs. are false
« Reply #33 on: Nov 13th, 2002, 5:51am » |
Quote Modify
|
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 ...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: All Sigs. are false
« Reply #34 on: Nov 13th, 2002, 1:32pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: All Sigs. are false
« Reply #35 on: Nov 13th, 2002, 3:54pm » |
Quote Modify
|
on Nov 13th, 2002, 5:51am, 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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print