Dear Lachlan, This e-mail consists of three parts. The first part below is a brief explanation on why we consider your argument incorrect. Following the first part, the second part is a detailed response to your previous e-mail. The third part is a remark on V(F, T) = V(F, F) = T. (Those readers not interested in reading the point-by-point response can go to the third part after reading the first part.)
For a general mathematical statement H(X, Y) with two propositional variables X and Y, denote by H(A, B) the truth value of H(X, Y) with (X, Y) = (A, B), where A and B are truth values. For a given truth value C, we say "H(A, B) = C holds" if the truth value of H(A, B) is C, and "H(A, B) = C does not hold" if the truth value of H(A, B) is not C. For convenience of discussion, we use (Q) to represent the following implication. (Q) V(T, F) = F where X := [P(B) = 1], and Y := [P(S) = 0]. In (Q), V(T, F) = F holds for any queue. For otherwise there is a queue such that V(T, F) is not F, which implies V(T, F) = T. With classical logic, one cannot understand the existence of a queue such that V(T, F) = T, as this contradicts the truth table. You use two options to interpret "the implication given by (Q) does not hold for all queues" differently. 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. In the following we respond to your previous e-mail. We mark our responses with Rn where n is a number. ----- Original Message ----- From: "Lachlan Andrew" <[email protected]> To: "Prof. Victor Li" <[email protected]> Cc: <[email protected]> Sent: Thursday, November 17, 2011 9:01 PM Subject: Re: [Tccc] Jackson Network and Queueing Theory > Greetings Victor, > > I'll try again. The flaw in your logic is as follows: > You show (in the second half of the first sentence of your proof, and > explicitly stated in the second sentence) that X and Y are not *both* > true. > You incorrectly state (by using the word "since" at the end of the > first line of the proof) that this implies V(X,Y) is false. That is > not correct. As we have agreed, V(F,F)=V(F,T)=T. Neither of these > cases requires X=Y=T. > R0 You have misunderstood the reason why V(T, F) = F with specified X and Y. In this implication, X = T is the assumption, and Y = F is the consequence of the assumption. So from X = T and Y = F, we have V(T, F) = F. In your argument there is a confusion between the two cases below. Case 1 (X, Y) = (T, F). Case 2 (X, Y) = (T, F), (X, Y) = (F, F) , (X, Y) = (F, T). Although in both cases above, the values of X and Y are not both T, V(T, F) = F holds only when (X, Y) = (T, F). There is no such confusion in the proof of Theorem 1. In other words, in the proof of Theorem 1, V(T, F) = F only when (X, Y) = (T, F). As to V(F, T) = V(F, F) = T, see our remark in the third part of this e-mail. > Below, I respond to your previous reply. > > On 17 November 2011 22:48, Prof. Victor Li <[email protected]> wrote: >> in the following discussion we shall use X : = [p] to mean >> "X represents p" where p is a proposition. For example, >> X : = [P(B) = 1] means "X represents P(B) = 1". >>> >>> My argument again is: >>> a) For some queues in G, (P(B)=1)=F. >>> b) if X=F then V(X,F)=V(X,T)=T. >>> c) Hence, there exists a queue in G, such that V(P(B)=1, P(S)=0) = T. >>> d) Hence, it is not true that for all queues in G, V(P(B)=1, P(S)=0) = >>> F. >>> >>> Please tell me which step you disagree with. >> >>To avoid any confusion, let us follow the conventions below. >>i) To determine the value >>of V(X, Y), we must first specify X and Y. >>ii) In any expression of the form V(A, B) = C, >>A, B, and C must be truth values, rather than propositional variables. >>For example, V(X, F) = F is not allowed because X is a propositional >>variable. > > The second proposal gets in the way of communication. See (*) below. > >> In your argument, suppose that you mean >> in a), b) , and c), X : = [P(B) = 1] and X = F; >> in b), Y: = [P(S) = 0] and Y = T or F; >> in c), for X : = [P(B) = 1] and Y: = [P(S) = 0]. V(F, T) = T and >> V(F, F) = T; >> in d) X : = [P(B) = 1], Y: = [P(S) = 0], X = T, Y = F and >> V(T, F) = F. > > OK. > >> You say that for X and Y as specified in d), >> V(T, F) = F is not true for all the queues in G because >> for X and Y as specified in c) V(F, T) = V(F, F) = T. > > No. V(T,F)=F is always true. This is (*), the point it is not > convenient to express the ideas we are discussing without using > propositional variables. > What I am saying is that V(P(B)=1, Y)=F is not (always) true, > because P(B)=1 is not (always) T. This statement has nothing to do > with the value of V(T,F). R1 By saying so you are not talking about the same queue. To avoid any confusion so caused, let us follow both conventions i) and ii) as we proposed. > >> 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. R2 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. > I am not saying anything at all about the truth or otherwise of > V(T,F). I am talking about the truth of V(X,Y), which, in this > case, is V(F, Y) [either V(F,T) or V(F,F), if you want to avoid > propositional variables]. R3 V(F, F) = T corresponds to option 2 in your interpretation of "the implication given by (Q) does not hold for all queues" (see the first part of this e-mail). For a queue, say, an M/M/1 queue, set X := [P(B) = 1], Y := [P(S) = 0], For X and Y specified above, you claim V(F, F)= T, meaning "if the queue is unbounded then the queue is stable". Its contrapositive is "if the queue is unstable then the queue is bounded". This is a contradiction. V(F, T) = T corresponds to option 1 of your interpretation. We have already discussed this option in the first part of this e-mail. Please also see our remark on V(F, T) = V(F, F) = T in the third part of this e-mail. > >> If the answer is yes, then such a counterexample is invalid >> as explained below. >> >> Implications (such as V(T, F) = F with X and Y we specified) >> are typically used to express mathematical statements. >> If one says "there is a counterexample to an implication" then the >> counterexample must satisfy the assumption of the implication for >> the counterexample to make sense. If an example does not >> satisfy the assumption of an implication, then the example fails to be >> a counterexample to the implication, and hence does not make >> the implication invalid. It seems that you are using a false >> counterexample to argue against an implication. > > I am not saying the queue is a counter-example to the implication. > I am saying it is a counter-example to the statement "For all queues, > the implication is false". If there is one queue for which the > implication is true, it is a valid counter-example to that statement. > The step from (c) to (d) is the fourth equivalence listed at > <http://en.wikipedia.org/w/index.php?title=Quantification&oldid=457601452#Equivalent_Expressions>. R4 Why do you claim that such a queue exists? Please see R3 and the first part of this e-mail. > >> If you are not using the >> queue as a counterexample, >> then your argument is irrelevant to V(T, F) = F >> with X : = [P(B) = 1], Y: = [P(S) = 0]. > > Yes, V(T,F)=F is irrelevant to what I wrote. Please respond to what I > wrote. R5 We have responded to it. Please see R3. Please also see our explanation given in the first part and our remark in the third part of this e-mail. > >> Return to your conclusion given in d). >> You say that it is not true for all queues in G, V(T, F) = F >> with X : = [P(B) = 1], Y: = [P(S) = 0]. >> Based on our explanation above, >> your conclusion appears to be incorrect. The fact is, >> there are queues in G that do not satisfy the assumption >> X = T with X : = [P(B) = 1] of V(T, F) = F >> where Y: = [P(S) = 0] with Y = F. This does not necessarily >> mean that V(T, F) = F with X : = [P(B) = 1], Y: = [P(S) = 0] >> is incorrect. > > It does not mean that the statement "V(P(B)=1, P(S)=0) = F" is > necessarily incorrect. > It does mean that the statement "For all queues, V(P(B)=1, P(S)=0) = > F" (the first statement in your proof) is incorrect. R6 Again, please see R3 and R0. Please also see our explanation in the first part of this e-mail. > >> Suppose that one wants to >> use a theorem to solve a problem. But the >> problem does not satisfy the assumption of the theorem. >> Does this mean that the theorem is flawed? Clearly not. >> The theorem is still true. > > Are you suggesting that "P(B)=1" is a hypothesis of your Theorem 1? > It is not listed in the statement of the theorem. R7 No. You have mistaken the context of the example for the context of Theorem 1. > If not, what exact assumption does my argument not satisfy? R8 You use X : = [P(B) = 1] and X = F in your argument. It is the assumption X = T with X : = [P(B) = 1] of V(T, F) = F where Y: = [P(S) = 0] with Y = F that your argument does not satisfy. > > In your reply, please do not tell me that I'm trying to deny that > "true implies false" is false. > R9 Please see the first part of this e-mail where we have explained why we consider your argument is incorrect. Your understanding of V(F, T) = V(F, F) = T appears to be incorrect, as shown by R3 and the first part of this e-mail. The use of V(F, T) = V(F, F) = T in your argument leads to either a contradiction or a result you are arguing against. Please also see our remark below. > Cheers, > Lachlan > > -- > 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 > To conclude, we would like to make the following remark. V(F, T) = V(F, F) = T is a convention to formulate and prove mathematical statements expressed by implications. By this convention, one usually focuses on whether the implied proposition Y follows from the assumption X. To this end, one begins naturally with X = T, and then verifies whether Y = T or Y = F follows from X = T. If Y = T follows from X = T, then one has correctly formulated or proved V(T, T) = T for the propositions X and Y. If Y = F follows from X = T, then one has correctly formulated or proved V(T, F) = F for the propositions. Once the implication in the form of either V(T, T) = T or V(T, F) = F has been correctly formulated or proved for the specified propositions, any other case in which the assumption does not hold (i.e., X = F) will not change the correctness of the implication. A simple example illustrating the use of V(F, T) = V(F, F) = T can be found 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. Best regards, Guang-Liang and Victor _______________________________________________ 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
