[Tccc] Jackson Network and Queueing Theory
Prof. Victor Li
vli
Tue Nov 22 06:28:27 EST 2011
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" <lachlan.andrew at gmail.com>
To: "Prof. Victor Li" <vli at eee.hku.hk>
Cc: <tccc at lists.cs.columbia.edu>
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 <vli at eee.hku.hk> 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.
> Tccc at lists.cs.columbia.edu
> 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
More information about the TCCC
mailing list