I have removed the attached page as it is too big to be broadcasted by TCCC, but the book should be readily available in most libraries. The example referred to is on p. 875 of Oxford Users' Guide to Mathematics, edited by E. Zeidler, English Translation (translated by B. Hunt), Oxford University Press, New York, 2004.
-----Original Message----- From: Prof. Victor Li Sent: Thursday, November 24, 2011 6:46 PM To: Lachlan Andrew Cc: [email protected] Subject: Re: [Tccc] Jackson Network and Queueing Theory Dear Lachlan, The key issue to be resolved in this discussion is the meaning of V(F, T) = V(F, F) = T. Your understanding of V(F, T) = V(F, F) = T contradicts the intended meaning of V(F, T) = V(F, F) = T given by logicians. So your use of V(F, T) = V(F, F) = T contradicts the intended use of V(F, T) = V(F, F) = T in mathematics. For your convenience, we have attached a copy of the page from the book mentioned in our previous e-mail. The example given on that page illustrates clearly the intended use of V(F, T) = V(F, F) = T according to its intended meaning given by logicians. Hopefully the example will convince you that neither your understanding nor your use of V(F, T) = V(F, F) = T is correct. Best Regards, Guang-Liang and Victor -----Original Message----- From: Lachlan Andrew Sent: Wednesday, November 23, 2011 10:48 AM To: Prof. Victor Li Cc: [email protected] Subject: Re: [Tccc] Jackson Network and Queueing Theory Greetings Victor, > Option 1 There is a queue with X := [P(B) = 1] and > Y := [P(S) = 0] such that V(F, T) = T > (meaning "if a queue is unbounded then the queue is unstable"). > > Option 2 There is a queue with X := [P(B) = 1] and > Y := [P(S) = 0] such that V(F, F) = T > (meaning "if a queue is unbounded then the queue is stable"). > > The above interpretation is the basis of your argument. > But such an interpretation is wrong. > The contrapositive of the implication in your option 1 > is "if a queue is stable then the queue is bounded", > which is the result you have been arguing against. > As shown in our response below, your option 2 leads > to a contradiction. This is why we consider your argument > incorrect To show the flaw, it is enough to show that either option 1 or option 2 is possible. I will now show that both are. Option 1. Part of the problem with your argument against option 1 is with the implicit quantifiers. I'm arguing against the claim that " *for all* queues, if the queue is unbounded then it is unstable", (or the contrapositive formulation "for all queues, if the queue is stable then it is bounded"). I'm not arguing that there is no queue such that, if it is unbounded then it is unstable. Also, the English paraphrase you gave changes the definition of V. What you did was negate the hypothesis of the implication, just because it is being evaluated for a value that is false. That means you changed the logical statement. The correct logical paraphrase for option 1 is "if a queue is bounded (which it isn't) then the queue is unstable", which says nothing about what happens if the queue is unbounded. If we have an M/M/1 queue A with rho > 1, then that particular queue satisfies option 1. I claim it is unbounded, and unstable, so we get " P(B) = 1 implies P(S) = 0" <=> V(A is bounded, A is unstable) <=> V(F,T) <=> T If we accept that the probabilities are both either 0 or 1, then the contrapositive of this is "P(S) != 0 implies P(B) != 1" <=> V(A is stable, A is unbounded) <=> V(F,T) <=> T Option 2. Consider this time an M/M/1 queue C with rho < 1. Then I claim it is unbounded and stable, so we get "P(B)=1 implies P(S)=0" <=> V(C is bounded, C is unstable) <=> V(F,F) (* see below) <=> T The contrapositive is again V(C is stable, C is unbounded) <=> V(T,T) <=> T Again, the correct paraphrase doesn't say what happens if C is unbounded. It is "If C is bounded (which it isn't) then C is unstable (which it isn't)" The contrapositive of this is "If C is stable (which it is) then C is unbounded (which it is)". This is not a contradiction (even though not all stable queues have unbounded delay). First, the apparent contradiction only arises because your paraphrase has a different logical meaning from the original statement. Second, there is actually no contradiction to the (logical) statement "if the queue is unstable then the queue is bounded" in this case, because the queue is not in fact unstable. That statement is simply V(F,F) (although the propositions are different from the one at (*) above, because your paraphrase simply negated both the hypothesis and conclusion of the implication). The third part of your email is again confusing the concepts of logical implication and sufficient conditions. It is impossible to "prove" V(T,T)=T, because that is simply the definition of the "implication" operator in logic. I don't have the text you mentioned, and so can't comment on that specifically. Remember the difference between the logical statement "X implies Y" and the English statement "X is a sufficient condition for Y"; if X is false then the former is always true even if the latter is not. Being unbounded need not a sufficient condition for being unstable, just because there exists a queue that is unbounded and unstable. I'm not sure what you mean when you say that my "understanding of V(F, T) = V(F, F) = T appears to be incorrect". These are definitions, not concepts. If you mean that my understanding of implication is incorrect, then please tell me what is wrong with it. I have pointed out several places where our usage seems to differ, but I believe that my usage is standard. Now consider the issue of notation. You wrote: >>> Does this mean that you are using the queue specified >>> in c) as a counterexample to >>> V(T, F) = F where X : = [P(B) = 1], Y: = [P(S) = 0]? >> >> No. Re-read what you wrote. The expression "V(T, F) = F where X : >> = [P(B) = 1], Y: = [P(S) = 0]" is not useful, because X and Y are >> never used. > > Why do you say so? The use of X and Y is clear as shown > by X : = [P(B) = 1], Y: = [P(S) = 0] , and with V(T, F) = F > it is clear X = T and Y = F. It is clear that you are *intending* to write X=T and Y=F. However, you have *defined* X to be a propositional statement, which can be false. Either you are *assuming* X=T, or *redefining* X=T. It is not clear which, which makes discussion hard. If you are assuming it, then your proof is flawed because what you are trying to prove is that X=T (see "Thus P(B)=1" on line 3 of page 5). If you are redefining X=T, then your proof is flawed the second definition is inconsistent with the first one when (P(B)=1) is false. At the risk of getting distracted, here is an analogous example. Assume I want to show that "Your argument is valid implies your conclusion is valid" is false. We have agreed that this can be written: V(your argument is valid, your conclusion is valid)=F. You claim that this can be rewritten V(T,F)=F X := "your argument is valid" and Y := "your conclusion is valid". We have agreed that V(T,F)=F, and so (if we allowed to rewrite things this way) the claim has been proven. If you think "but you are assuming my conclusion is not valid", then you may see my point. We can't define a propositional variable to be the truth of a particular statement, and then arbitrarily assume it has a particular value. -- Lachlan Andrew Centre for Advanced Internet Architectures (CAIA) Swinburne University of Technology, Melbourne, Australia <http://caia.swin.edu.au/cv/landrew> Ph +61 3 9214 4837 _______________________________________________ IEEE Communications Society Tech. Committee on Computer Communications (TCCC) - for discussions on computer networking and communication. [email protected] https://lists.cs.columbia.edu/cucslists/listinfo/tccc _______________________________________________ IEEE Communications Society Tech. Committee on Computer Communications (TCCC) - for discussions on computer networking and communication. [email protected] https://lists.cs.columbia.edu/cucslists/listinfo/tccc
