Author |
Topic: Pop Quiz Riddle (Read 78497 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Re: Pop Quiz Riddle
« Reply #175 on: Nov 20th, 2005, 7:11pm » |
 Quote  Modify
|
on Nov 19th, 2005, 3:22pm, towr wrote:If a statement has no counter example it must be true, and so it's negation must be false and thus have a counter example.
However, if the statement is undecidable, you can't know if the statement does or doesn't have a counter example. (Because that decides it) |
|
No - if a counter-example exists, the statement is false, whether or not anyone knows about it. If you just don't know about it, then the statement is merely undecided, not undecidable.
Undecidable statements are statements that can be neither proven nor disproven using the axioms and logic of the mathematical theory under consideration. As such, they cannot have counter-examples within that theory. An undecidable statement can be added to the axioms of the theory to create a new daughter theory in which the statement is true. And the negation of the statement can also be added to the axioms of the original theory to create a new daughter theory in which the statement is false. There are no counter-examples to either one.
on Nov 19th, 2005, 4:41pm, Eigenray wrote:| (although even if a universal statement has a counter-example, that doesn't mean it's provably false). |
|
 What definition of "universal" are you using that allows counter-examples?
Demonstrating the existance of counter-examples is exactly how you prove a universal statement is false!
|
|
 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
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pop Quiz Riddle
« Reply #176 on: Nov 20th, 2005, 8:58pm » |
Quote Modify
|
on Nov 20th, 2005, 7:11pm, Icarus wrote:| Demonstrating the existance of counter-examples is exactly how you prove a universal statement is false! |
|
Well, proving the existence of counter-examples, sure. But maybe x=17 is a counter-example to the (Pi4?) formula
For all x, Goldbach's conjecture is false.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pop Quiz Riddle
« Reply #177 on: Nov 21st, 2005, 5:10am » |
Quote Modify
|
on Nov 20th, 2005, 7:11pm, Icarus wrote:| No - if a counter-example exists, the statement is false, whether or not anyone knows about it. If you just don't know about it, then the statement is merely undecided, not undecidable. |
|
I'm pretty sure that's what I said..
Quote:| Undecidable statements are statements that can be neither proven nor disproven using the axioms and logic of the mathematical theory under consideration. |
|
I was under the impression that undecidability meant that there were true statements that could not be proven, and false statement that could not be disproven (by using axioms and applying rules).
Certainly there are numerous statements that trivially can't be proven, since they're contingent rather than tautological or contradictory. I wouldn't call those undecidable though.
Quote:| As such, they cannot have counter-examples within that theory. |
|
But then you're just looking at the syntactical side, not the semantical side. Undecidability only really means something when you look at both the model and theory; whether the theory is sound and complete with respect to the model.
Counter-examples are typically something found in a model (or at the very least corresponding to some entity in the model).
|
|
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: Pop Quiz Riddle
« Reply #178 on: Nov 21st, 2005, 4:48pm » |
Quote Modify
|
on Nov 20th, 2005, 8:58pm, Eigenray wrote:
Well, proving the existence of counter-examples, sure. But maybe x=17 is a counter-example to the (Pi4?) formula
For all x, Goldbach's conjecture is false. |
|
If you can't prove it, how is it a counter-example? Possibly the (Pi4?) formula is false for x=17, but for the formula to be false, you have to be able to show it. Otherwise the formula is undecidable or true, not false.
on Nov 21st, 2005, 5:10am, towr wrote:| I'm pretty sure that's what I said.. |
|
My point was in answer to this statement:
on Nov 19th, 2005, 3:22pm, towr wrote:| However, if the statement is undecidable, you can't know if the statement does or doesn't have a counter example. |
|
For a statement to be undecidable, it cannot have a counter-example. So if you know the statement is undecidable, you do know that is does not have a counter-example. If it has a counter-example, it is false, whether or not you know of the example.
on Nov 21st, 2005, 5:10am, towr wrote:| I was under the impression that undecidability meant that there were true statements that could not be proven, and false statement that could not be disproven (by using axioms and applying rules). |
|
If they cannot be proven, in what sense are they "true"? If a statement cannot be proven, then there exist completely consistent sub-theories in which the statement is true, and completely consistent sub-theories in which the statement is false. (I'm sure you understand what I mean, but for clarity's sake: a "sub-theory" of a mathematical theory is another theory containing all the axioms and primatives of the original, but with other axioms and primatives added.)
If the statement is somehow "true", how can I have a nice consistent sub-theory in which it is provably false?
Quote:| Certainly there are numerous statements that trivially can't be proven, since they're contingent rather than tautological or contradictory. I wouldn't call those undecidable though. |
|
I have no idea what you mean by "contingent".
Quote:But then you're just looking at the syntactical side, not the semantical side. Undecidability only really means something when you look at both the model and theory; whether the theory is sound and complete with respect to the model.
Counter-examples are typically something found in a model (or at the very least corresponding to some entity in the model). |
|
No - undecidability is often demonstrated by use of models, but it is only meaningful for the theory alone. It means exactly that neither the statement nor its negation can be proved within the theory. This is usually demonstrated by showing the existance of a model of the theory in which the statement is true, and of another model in which it is false.
Such statements are true or false in the model, but they are NOT true or false within the theory itself. There, "undecidable" is the most you can say. Models (there are many models of a theory) represent subtheories, with axioms beyond those of the theory modeled. So truth or falsity of a statement in the model does not imply the same for the theory.
A counter-example within some model is not a counter-example within the theory. Only when the counter-example exists within all models does it count as a counter-example within the theory itself.
________________________________________
To the particular point of nnahas' conundrum. His logic reduces to this:
(1) Conjecture is undecidable --> no counter-examples exist.
(2) No counter-examples exist --> Conjecture is provable.
(3) Conjecture is provable --> Conjecture is not undecidable, contradicting the assumption.
(4) Therefore, the conjecture must be decidable.
The downfall is step (2), which only holds for a different meaning of the terms than used in (1). To be more specific:
(1) Conjecture is undecidable --> no counter-examples within the theory exist.
For the conjecture to be truly undecidable, there must be models in which it is false (in particular, the theory with the negation of the conjecture added as an axiom is a model in which it is false). These models may have counter-examples within those models, but such counter-examples do not hold without the added axioms of the model.
(2) No counter-examples within any models--> conjecture is provable.
Stated as such, this is also true. If no model exists in which the statement is false, then in particular, the theory consisting of adding the negation of the conjecture as an axiom must not be a valid model. The only way it can not be a valid model is if it is contradictory. But if it is contradictory, then the conjecture must be provable in the original theory.
However, the weakness in the argument should be clear. The conclusion of (1) is not the same as the hypothesis of (2), and therefore the logic chain is broken.
|
|
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
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: Pop Quiz Riddle
« Reply #179 on: Nov 21st, 2005, 5:32pm » |
Quote Modify
|
OK, I'm not entirely sure about the mathematical expressions used, so this may have been said already in ways I didn't quite understand, but the way in which Kant expresses the nature of moral imperatives (following a logical structure) seems to be a good way of showing contingency:
An imperative should be considered contingent if you could will that it apply for everyone, and could also will the negation of the imperative to apply to everyone. (e.g. "The lucky number people should have is 7" would be contingent - unless you are somewhat zealous about your belief in lucky numbers, but then you're just strange  )
Contingency is also popular in possible world theories, where differences between worlds show what is contingent in a given world, while necessary things will remain constant in all possible worlds.
It seems that undecidability falls under the same kind of idea as contingency, in that just lacking a counter-example is not enough to prove a conjecture is true, as you also need to show that the negation of the conjecture has a counter-example. Otherwise, the conjecture is undecidable.
At least, that's how I understand contingency, and undecidability on the basis of this thread. Like I say, I could be wrong.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pop Quiz Riddle
« Reply #180 on: Nov 21st, 2005, 8:20pm » |
Quote Modify
|
on Nov 21st, 2005, 4:48pm, Icarus wrote:
If you can't prove it, how is it a counter-example? Possibly the (Pi4?) formula is false for x=17, but for the formula to be false, you have to be able to show it. Otherwise the formula is undecidable or true, not false. |
|
Oh. I thought we were talking about counter-examples in the standard model, i.e., if I say "for all x, phi(x)", and there's some x0 such that phi(x0) is false, then that would be a counter-example, even though I might not be able to prove phi(x0) is false.
For example, suppose for the sake of argument that Goldbach's conjecture is undecidable. In particular, it is not provably false, so there are no counter-examples (in the standard model) since in this case, any counter-example could easily be proved to be such. That means it's true. Now if I say "for all x, Goldbach's conjecture is false," then wouldn't x=17 be a counter-example to the latter statement?
On the other hand, for something like the continuum hypothesis, what exactly would a counter-example be? A set x, in some model of ZFC, with |N| < |x| < |R|? Or a proof in ZFC that there exists such an x? The former exists, assuming Con(ZF). The latter doesn't.
There's a standard model of arithmetic. Any statement in number theory is either true or false in this model, and that's what people usually mean. Especially if they distinguish between "true" and "provable". For example, Goodstein's Theorem is true, even though it's not provable in PA.
But there isn't even a standard set of axioms for set theory, let alone a standard model. So if someone asks "is foo true," you likely have to ask them what they mean by "true."
Does every field have an algebraic closure? When asked outside the context of logic, the answer is yes. Not because we write down a formal derivation from our favorite set of axioms, but because we just "prove" it, like any other theorem: it follows from other things that we know are "true". But of course, this discussion is specifically in the context of logic.
Is the axiom of choice true? Well, how did all the other axioms get in ZF? Because they're necessary for doing mathematics. A lot of mathematicians use AC (algebraic closures, maximal ideals, bases, ...), so they work in ZFC, where AC is true. It's so widely accepted because (0) Con(ZF) -> Con(ZFC); (1) it's, well, "true": if you take a bunch of nonempty sets, their product is non-empty; and (2) It's so damn useful. So yes, AC is true (in ZFC, which is usually assumed if no context is given). (A similar argument could be made for Foundation: it's consistent with ZF \ Foundation, and it should be true, but it's not really necessary, since most math is done in WF anyway.)
On the other hand, is there an uncountable set smaller than R? It's consistent either way, but (1) there's no intuitive answer, and (2) it doesn't really matter to most people, other than logicians. In this case, there's no answer to the question "is CH true," because when asked with no context, any answer would stay within ZFC, where it's undecidable. But if you were to ask, say, "is CH true in ZF+(V=L)", then the answer is yes.
Finally, it should be noted that I don't really know what I'm talking about, and I'm pretty much just rambling here.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pop Quiz Riddle
« Reply #181 on: Nov 22nd, 2005, 3:17am » |
Quote Modify
|
on Nov 21st, 2005, 4:48pm, Icarus wrote:| For a statement to be undecidable, it cannot have a counter-example. |
|
Not in the theory, no, but in a model yes. As you say yourself sometime later.
I think you're not understanding entirely where I'm coming from. I'm working a lot with modal logic at the moment, and the theories there are formed after the model, because meaning is important. And without a model you have no meaning; it'd just be symbol manipulation.
The theories there are proof systems to reason about the model. The same goes for most logics afaik.
Quote:| If they cannot be proven, in what sense are they "true"? |
|
They are true in they're meaning. If our 'world' (universe) contains God, then he's true, even though we can't proof him with all the laws and rules we created to reason about the world.
Quote:| I have no idea what you mean by "contingent". |
|
contradiction: A & ~A
tautology: A | ~A
contingency: A
Whether it's true or not depends on what value A gets.
Unlike the other two examples. It doesn't make sense to use the first two as axioms, because adding a tautology adds nothing, and adding a contradiction makes everything follow from the theory.
Adding a contigency as axiom can create a 'meaningfull' subtheory. (Although not really in this case)
|
| « Last Edit: Nov 22nd, 2005, 3:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nnahas
Newbie
Posts: 2
|
|
Re: Pop Quiz Riddle
« Reply #182 on: Nov 22nd, 2005, 12:21pm » |
Quote Modify
|
on Nov 21st, 2005, 4:48pm, Icarus wrote:
The downfall is step (2), which only holds for a different meaning of the terms than used in (1). . |
|
I fully agree with your point of view. Do you think some analogy can be drawn to different meanings of the word "Predict" in the pop quiz riddle ? I have a feeling that the meaning of the word Predict is changing as the pop quiz story develops, although I still can't pinpoint exactly what are the different meanings
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Pop Quiz Riddle
« Reply #183 on: Nov 22nd, 2005, 5:01pm » |
Quote Modify
|
So many controversies, so little time... 
Starting in order:
Three Hands, thank you for your comments. I don't want to appear to ignore them, but just as you have trouble understanding the deeper mathematics, I don't really follow your deeper philosophical statements, even if both are drawing on the common well of Aristotlean logic. The terminology is not completely co-incident.
_________________________________________
Eigenray - my comments to you have nothing to do with any model. I was speaking of matters strictly within the theory itself (I only included the model stuff as I came to realize what towr was refering to).
If it cannot be proven that 17 is a counter-example, then 17 is not a counter-example (this is of course a little more general than saying that you or I cannot prove it - I mean that a proof does not exist). But even if there are no counter-examples - or more generally, that a conjecture cannot be shown false, this does not mean the conjecture is true. To be true (within the theory), it must be provable. So a lack of counter-examples or counter-proofs just means the conjecture is either undecidable or true.
on Nov 21st, 2005, 8:20pm, Eigenray wrote:| There's a standard model of arithmetic. Any statement in number theory is either true or false in this model, and that's what people usually mean. Especially if they distinguish between "true" and "provable". For example, Goodstein's Theorem is true, even though it's not provable in PA. |
|
Really? Interesting that I have never heard of this model before. Obviously Godel never heard of it, either. Which is really too bad, since it would have stopped him from making a fool of himself by very famously proving that such a model is impossible. What is this model? How is it defined? How does it avoid the logic of Godel's incompleteness proof?
Also, what is "PA"?
_________________________________
towr - I don't know about the modal logic you are dealing with, but you have it completely backwards for how mathematics works.
Perhaps some definitions would help here. You surely know by now how much I love defining things! The definitions below are a simplified version of the formalist view.
A Mathematical Theory consists of:
- A list of symbols, called the "Primatives".
- Rules for constructing "Statements" and "Objects" from the primatives.
- A finite collection of rules for specifying certain statements. The rules are generally called by different names depending on the particular theory and their nature. Bourbaki refered to his as "Axiomatic Schemas". The statements specified by the rules are called "Axioms". The reason for schemas rather than simply a list of axioms is because the axioms cannot generally have statements as values for their variables, without running into problems with self-reference and inducing contradictions. So such "axioms" as (A implies (A or B)), must instead be stated as schemas, with all possible replacements for A and B providing different axioms.
The theory is developed by
- Adding "Definitions": additional symbols and statements relating them to the primatives, which can be thought of as more axioms, and
- Creating "Proofs", ordered lists of statements in which each entry is either an axiom, or is a statement B preceded by two other statements of the form "A" and "A implies B". A "Theorem" is any statement that occurs in one of these proof.
Proofs as we ordinarily think of them are, to the formalist, merely a "meta-argument" (one outside the theory, about the theory) that a formal proof as defined above exists. Statements are "true" in a theory if they are theorems (i.e., they occur in some formal proof). Statements are "false" if their negation is a theorem. If neither a statement nor its negation are theorems, then the statement is undecidable.
If T and T' are theories such that every primative in T corresponds to a primative, statement, or object in T', so that under this correspondence, every statement or object of T becomes a statement or object of T', and every axiom of T is a theorem of T' (note that all axioms are also theorems within their own theory), then T' is called a "subtheory" of T. If a statement is true in T, then its corresponding statement in T' is guaranteed to also be true. This is because the proof in T corresponds to a list of statements in T' that can be expanded to a full formal proof by preceding the list with proofs of all the theorems used in it without precedents.
T is called contradictory, or inconsistent, if there is a true (i.e., provable) statement within it whose negation is also true.
A "Model" of T is simply a subtheory of T. Usually the model is a construction within some other theory S, (of which it is necessarily also a subtheory). Models are most useful in demonstrating relative consistency, i.e. in showing that if S is consistent, then so is T.
|
|
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: Pop Quiz Riddle
« Reply #184 on: Nov 22nd, 2005, 5:30pm » |
Quote Modify
|
Continuing in a second post to sneak around the evil gremlin that limits vebosity... 
Note that from a mathematical point of view, the theory is where the essential meaning of what we are talking about is found. For instance, group theory consists of set theory (your pick which one) along with the added primative G (the group), * (the operation), and e (the identity), and the axioms:
(1) for all x in G, e*x = x*e = x
(2) for all x, y, z in G, x*(y*z) = (x*y)*z
(3) for all x in G, there exists y in G such that x*y = y*x = e.
The meaning of groups, all that we need to discuss and develop the idea of group, is found in these. Anything beyond is not about groups, but about specific groups or collections of groups.
In particular, models such as the integers, do not give any meaning to groups in general that is not already found in those axioms. The only thing that the existance of integers as a model for groups tells us is that our group theory is at least as consistent as arithmetic.
Your concept seems to be that you have one underlying model with many theories built off it. "True" and "False" are defined in terms of this model, and not by the theory. But in mathematics, this is not how we think of it. In fact, theories have many, many distinct models (even complete theories do, though they do not differ in any way discussable within the theory itself). What is true within one model, if not provable in the theory, will be false within other models.
This is why I do not, and cannot, define "true" in terms of what is true in some underlying model. Which model do I choose? Why should this model be chosen over others where the same statement is false? If we define true by some underlying model, then we are studying the model, and not the theory. It is fine to study the model, but we should not be tempted to think that results there always apply to the theory.
____________________________________
nnahas, the problem is indeed deeply rooted in semantics. I believe it has more to do with false assumptions the students develop from assuming the words have one meaning while the professor is interpreting them differently. I have explored this and posted it before, and am right now too involved mentally in other arguments ( ) to be motivated to delve back into it at this time. Alas, if you want my opinion, you will have to find it posted on previous pages.
|
|
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
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pop Quiz Riddle
« Reply #185 on: Nov 23rd, 2005, 4:33am » |
Quote Modify
|
on Nov 22nd, 2005, 5:30pm, Icarus wrote:| Your concept seems to be that you have one underlying model with many theories built off it. "True" and "False" are defined in terms of this model, and not by the theory. But in mathematics, this is not how we think of it. |
|
Then obviously we're simply talking about different things.
Apparantly it means something different in logic than it does in mathematics. Which is quite acceptable to me..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Pop Quiz Riddle
« Reply #186 on: Nov 23rd, 2005, 1:40pm » |
Quote Modify
|
on Nov 22nd, 2005, 5:01pm, Icarus wrote:
If it cannot be proven that 17 is a counter-example, then 17 is not a counter-example |
|
I guess I just don't like that terminology. A counterexample is an example, a specific element of some model which makes a given statement false in that model. A "counterexample in the theory" would be better called a "disproof".
The only misunderstanding here is that nobody bothered to define "counterexample" the first few times it came up (though in my opinion, the first time nnahas used it, he was clearly referring to a counterexample in the standard model of arithmetic).
Quote:
That's the million dollar question. There I meant Peano Arithmetic -- the first-order system of arithmetic where the axiom of induction is replaced by a schema: one axiom for each arithmetical formula.
On the other hand, the Peano Axioms is a second-order system: induction is taken care of by quantifying over properties.
The key difference here is that while there are nonstandard models of Peano Arithmetic, there is only one model for the Peano Axioms: the natural numbers. This is what I mean by the standard model. Even if you're talking about first-order logic, the natural numbers still exists as a model; it is the standard model because furthermore it satisfies the second-order induction axiom.
Quote:| A "Model" of T is simply a subtheory of T. |
|
A model is not a theory. A theory T is a set of sentences. A model M is a set (universe) together with an interpretation of the language L. Truth in M is defined recursively: k-ary predicate symbols of L are interpreted as subsets of Mk; function symbols are functions; logical connectives work as you'd expect; similarly for quantification: "for all x, phi(x)" is true in M iff for all s in M, the formula phi(x), with every (unbounded) x replaced by s, is true in M. (Part of the definition is that every sentence is either true or false in M: the theory of any model is complete.) M is a model for T iff every sentence of T is true in M.
For example, the theory of groups is not a group; its models are groups. Thus (G,*) is a group iff the axioms of group theory are true in G.
Quote:| For instance, group theory consists of set theory (your pick which one) along with the added primative G (the group), * (the operation), and e (the identity), and the axioms: |
|
You certainly don't need any of the usual axioms of set theory, or even the [in] predicate. It's just the first order language with a binary function symbol and 3 axioms (a constant symbol for the identity is not strictly necessary as it is definable).
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Pop Quiz Riddle
« Reply #187 on: Nov 23rd, 2005, 7:31pm » |
Quote Modify
|
Perhaps the terminology has changed from what I learned. For me, "The Natural numbers" are the theory, and are defined by the Peano Axioms or some equivalent formulation (whether first-order, second-order, or twenty-third order...). Models for the natural numbers are such constructions as the set { {}, {{}}, {{}, {{}}}, ... } (i.e., 0 = {}, 1={0}. 2={0,1}, etc), or certain equivalence classes of pairs of line segments (which is effectively how Euclid develops them). [Yes, I am including "0" in the natural numbers here. Call them the finite Cardinal numbers, or the Whole numbers, if you prefer.]
As a second example, "The smallest algebraicly and topologically complete field of characteristic 0" is the short description of the Theory of Complex Numbers. The most common Model of the complex numbers is R x R, along with the appropriate definitions of + and *. A second well-known model is the quotient R[x]/(x2+1).
Part of the problem may be that I am only interested in such things for their practical application to mathematics as a whole, and not for the sake of the thing itself (not that I disapprove of interest for the sake of it- I am a mathematician, after all - but I do not share it). This is why I take the theory of groups to be a subtheory of the theory of sets. Leaving set theory out makes Group theory tepid and difficult to talk about. Put set theory in, and suddenly Group theory is robust and full of examples.
As for counter-examples: For me, if it is not within the theory but only within some particular model, then it does not align with any concept of what is meant by "counter-example" that I normally encounter. For example (lets choose something a lot simpler here than obscure and difficult conjectures), a counter-example to the statement "For all x, x = 1" would be the value 2. A particular value well-defined in the theory (not just some model of the theory) which shows that the statement in question is false. On the other hand, the statement "For all natural numbers x, if x>0, then 0 c x." is true for the set-theoretic model of the natural numbers I gave above, but is false or even non-sensical for other models of the Natural numbers. In particular, the fact that it is not true for the equivalence classes used in the Geometry model does not count as a "counter-example" to me. (A bad example, I know, since the element operator c is not a part of of the theory of natural numbers, so the statement is not valid, but hopefully you follow my meaning.)
|
|
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
|
|
|
Alky
Newbie
Gender:
Posts: 5
|
|
Re: Pop Quiz Riddle
« Reply #188 on: Dec 6th, 2005, 11:41am » |
Quote Modify
|
I can't say I've read through this whole thread, but I have the solution to the riddle.
Essentially what the students have is an inductive proof. Each case obviously implies the next case as long as the base case is true.
It seems like everyone is focusin on the induction step (not friday gives not thursday) but ignoring the obvious fact that if the test happened on tuesday, the students wouldn't be able to know the test is on friday when thursday night arrived (because is happened on tuesday).
In short, the base case isn't proven.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: Pop Quiz Riddle
« Reply #189 on: Dec 7th, 2005, 8:53am » |
Quote Modify
|
on Dec 6th, 2005, 11:41am, Alky wrote:I can't say I've read through this whole thread, but I have the solution to the riddle.
Essentially what the students have is an inductive proof. Each case obviously implies the next case as long as the base case is true.
It seems like everyone is focusin on the induction step (not friday gives not thursday) but ignoring the obvious fact that if the test happened on tuesday, the students wouldn't be able to know the test is on friday when thursday night arrived (because is happened on tuesday).
In short, the base case isn't proven. |
|
What exactly do you think the base case is?
Not Friday is proved by conrtradiction - were it to be Friday, then the students would know on Thursday (because it wouldn't have been Tuesday or any other day)
|
|
IP Logged |
|
|
|
Alky
Newbie
Gender:
Posts: 5
|
|
Re: Pop Quiz Riddle
« Reply #190 on: Dec 7th, 2005, 2:11pm » |
Quote Modify
|
on Dec 7th, 2005, 8:53am, rmsgrey wrote:
What exactly do you think the base case is?
Not Friday is proved by conrtradiction - were it to be Friday, then the students would know on Thursday (because it wouldn't have been Tuesday or any other day) |
|
The base case for the induction is "the test won't happen on friday"
To know that the test won't happen on friday, you need to know it hasn't happened on monday, tuesday, wednesday or thursday. (This is made abundantly clear by the fact that it's thursday night and they would expect the test to be tomorrow)
The problem is that the logic goes something like this:
IF the test doesn't happen before friday
THEN the test can't be a surprise on friday
THEREFORE it won't happen on friday (IF the test doesn't happen before friday)
THEREFORE it won't be surprise on thursday (IF the test doesn't happen before friday)
THEREFORE it won't happen on thursday (IF the test doesn't happen before friday)
etc.
That's it. We assumed what we proved. Circular reasoning.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pop Quiz Riddle
« Reply #191 on: Dec 7th, 2005, 2:34pm » |
Quote Modify
|
No, the reasoning is
If the test doesn't happen before friday, it must be on friday
But if it is on friday, it won't have been a surprise ; which is a contradiction, the test is a surprise.
Therefore the test must happen before friday.
|
| « Last Edit: Dec 7th, 2005, 2:39pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Alky
Newbie
Gender:
Posts: 5
|
|
Re: Pop Quiz Riddle
« Reply #192 on: Dec 7th, 2005, 6:34pm » |
Quote Modify
|
on Dec 7th, 2005, 2:34pm, towr wrote:No, the reasoning is
If the test doesn't happen before friday, it must be on friday
But if it is on friday, it won't have been a surprise ; which is a contradiction, the test is a surprise.
Therefore the test must happen before friday. |
|
No, it wouldn't be a surpirse if the test was friday and the test already hadn't happened on monday, tuesday, wednesday and thursday. It would be a surprise UNTIL thursday night.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pop Quiz Riddle
« Reply #193 on: Dec 8th, 2005, 2:26am » |
Quote Modify
|
on Dec 7th, 2005, 6:34pm, Alky wrote:| It would be a surprise UNTIL thursday night. |
|
It would be a surprise until you know can't happen on thursday or before. I doubt they have classes thursday night.
If the test is on friday, they will know at the end of thursdays classes that it will be the next day, hence it's no surprise. Thus it can't be on friday.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Pop Quiz Riddle
« Reply #194 on: Dec 8th, 2005, 12:22pm » |
Quote Modify
|
on Dec 7th, 2005, 2:11pm, Alky wrote:The problem is that the logic goes something like this:
IF the test doesn't happen before friday
THEN the test can't be a surprise on friday
THEREFORE it won't happen on friday (IF the test doesn't happen before friday)
|
|
But if the test does happen before Friday, then it won't happen on Friday either.
Therefore the test won't happen on Friday (If the test doesn't happen before Friday or the test does happen before Friday)
So the only way the test can take place on Friday is if it neither takes place before Friday, nor fails to take place before Friday.
|
|
IP Logged |
|
|
|
Alky
Newbie
Gender:
Posts: 5
|
|
Re: Pop Quiz Riddle
« Reply #195 on: Dec 8th, 2005, 2:07pm » |
Quote Modify
|
Alright, I concede that point.
Just one thing to think about: We don't even need any of this "friday then thursday" stuff because we can just use the 'surprise' premise to disprove any day we choose.
Assume we figured out the test was on tuesday. But wait! The test is surprise so we can't figure out it will be on tuesday.
I think the problem comes because the day we expect the test to be is not equal to the day the test really is. Assume the test IS on friday. We go through the logic and expect it not to happen: surprise! it's on friday anyways.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pop Quiz Riddle
« Reply #196 on: Dec 8th, 2005, 2:50pm » |
Quote Modify
|
on Dec 8th, 2005, 2:07pm, Alky wrote:| Just one thing to think about: We don't even need any of this "friday then thursday" stuff because we can just use the 'surprise' premise to disprove any day we choose. |
|
Yes, that's the main problem. If you believe it will be a surprise, you cannot believe you know when it is.
If the Prof says: "There is a surprise test friday".
You can't believe that this is true, even if it is.
|
| « Last Edit: Dec 8th, 2005, 2:53pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Pop Quiz Riddle
« Reply #197 on: Feb 21st, 2006, 2:06am » |
Quote Modify
|
This statement of the problem is a little strange because you can take a guess and the professor won't hold the quiz if you're right. Fact is the professor took a risk: suppose the students play the strategy that they never guess until Thursday night rolls around, then if the quiz hasn't been given yet they guess that it is on Friday. In either case - if there is no quiz at all, or if it was planned for Friday, then the students know that there will be no quiz on Friday. So the professor should never put the quiz on Friday because the students might play this strategy. So in this version, the flaw involving not knowing that there will be a quiz at all, is not actually important; it seems to me that it all just boils down to the problem being a logical fallacy (If we can prove X, then not X).
|
| « Last Edit: Feb 21st, 2006, 2:08am by River Phoenix » |
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Pop Quiz Riddle
« Reply #198 on: Feb 21st, 2006, 2:17am » |
Quote Modify
|
Basically, there are number of assumptions that are taken as axioms. Together, they lead to a contradiction. If we continue to take all of what is in the problem as axioms, then we conclude that the problem is simply nonsense. Otherwise, we have to remove one of the axioms. There is no particular one of the axioms that is wrong, I just find it easiest to say that in fact it was the professors statements that were actually just assumptions.
In many statings of the paradox (in this one too if you disregard my previous post, which I'm not too sure on actually), you could simply say that the assumption that the test will be given in the week, is false. It's negation is that the test might not be given in the week. This suffices, since the test will always be a surprise, after all it might not be given at all. We simply can't assume that the test will both definitely be given and will definitely be a surprise, since this is obviously not true once Friday morning rolls around. So either the test won't necessarily be given, or the teacher was wrong and took a risk - meaning the test won't necessarily be a surprise. It's rather simple really; the problem contains a contradiction.
|
| « Last Edit: Feb 21st, 2006, 2:30am by River Phoenix » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pop Quiz Riddle
« Reply #199 on: Feb 21st, 2006, 3:28am » |
Quote Modify
|
on Feb 21st, 2006, 2:17am, River Phoenix wrote:| Basically, there are number of assumptions that are taken as axioms. Together, they lead to a contradiction. If we continue to take all of what is in the problem as axioms, then we conclude that the problem is simply nonsense. |
|
It isn't nonsense. It's actually a common problem you face in dynamic epistemic logic with an update operator. Certain updates don't lead to knowledge because believing the information leads to a contradiction. This is exactly what the students are facing.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print