[Tccc] Jackson Network and Queueing Theory
Prof. Victor Li
vli
Fri Nov 25 06:26:28 EST 2011
Dear Lachlan,
It seems that you have misunderstood
what the example illustrates.
Refer to the following implication
as Theorem 0.
Theorem 0
If m is divisible by 6 then m is divisible by 2.
Theorem 0 always holds. In any case in which
the assumption is false, the implication as a whole,
i.e., Theorem 0, is considered true, by applying
V(F, T) = V(F, F) = T in its intended meaning
(if the assumption of Theorem 0 is false
then Theorem 0 is true).
The basic idea here is
this. When arguing for or against an implication,
one should adopt the assumption of the
implication, i.e., one should only consider
cases in which the assumption is true.
For example, in proving Theorem 0, by the
intended meaning of V(F, T) = V(F, F) = T,
it is unnecessary to consider any m which is
indivisible by 6. One needs only to
verify whether the implied proposition
follows from the assumption.
But you argue against an implication by
considering cases in which the assumption of the
implication is false. Such argument is invalid
by the intended meaning of V(F, T) = V(F, F) = T.
For example, no M/M/1 queue satisfies the
assumption of the implication you have been
arguing against. But you keep on using
such queues in your argument.
By the intended meaning of
V(F, T) = V(F, F) = T, your argument is
invalid.
If one were allowed to argue against
an implication by considering
cases in which the assumption of the
implication is false, then one might have
disproved Theorem 0 by claiming that
Theorem 0 does not hold for all m since
there exist numbers (such as 17)
that do not satisfy
the assumption of Theorem 0.
Such arguments are prohibited
by the intended meaning of V(F, T) = F(F, F) = T.
Theorem 0 still holds for any m.
Similarly, in your attempt to disprove the
implication you have been arguing against,
you should consider those queues that satisfy
the assumption of the implication.
Best regards,
Guang-Liang and Victor
-----Original Message-----
From: Lachlan Andrew
Sent: Friday, November 25, 2011 3:43 AM
To: Prof. Victor Li
Cc: tccc at lists.cs.columbia.edu
Subject: Re: [Tccc] Jackson Network and Queueing Theory
Greetings Victor,
I assume you are talking about example 1. This is consistent with my
understanding of implication. I'll explain in detail below. First
let me clarify something:
I'm *not* arguing that the statement "bounded implies unstable" is
true in general. That seems to be what you assume I am saying. That
would be saying "For all queues, V(X,Y) = T", which is what is
generally meant when someone says "X implies Y".
Instead, I am pointing out that the flow your logic is "(for all
queues, V(X,Y)=T) is false, therefore (for all queues, V(X,Y)=F) is
true". (Correct me if I'm wrong.) That statement isn't true. The
correct logic is "(for all queues, V(X,Y)=T) is false, therefore (for
some queues, V(X,Y)=F) is true". (See again the fourth relation at
<http://en.wikipedia.org/w/index.php?title=Quantification&oldid=457601452#Equivalent_Expressions>.)
What I am saying is there also exist some queues Q for which V(X
restricted to Q,Y restricted to Q)=T, simply because X(restricted to
Q) is false.
For an analogy of why quantifiers are important, consider the
implication (B): "If A is odd then A is prime". That is not true in
general, but if it is restricted to 2 <= A <= 7 then it is true. That
means we can't say "(For all A, (B) is true) is false, therefore (for
all A, (B) is false) is true". There exists some A's (like some Q's)
for which (B) is true. In particular, it is true for A=2 ((F,T),
analogous to an unstable M/M/1) and A=4 ((F,F), analogous to a stable
M/M/1).
Now consider the example in the book.
The implication is "(m is divisible by 6) implies (m is divisible by 2)"
To paraphrase your "option 1" and "option 2" for this example, we get:
>> Option 1 There is a queue with X := [m is divisible by 6] and
>> Y := [m is divisible by 2] such that V(F, T) = T
>> (meaning "if m is indivisible by 6 then the m is divisible by 2").
(Recall that you negated the "if" part, just because we are
considering a case where the "if" part is false.)
Now clearly, for m=4, we get V(X,Y) = V(F,T) = T, but we don't get
the statement "(For all m) if m is indivisible by 6 then m is
divisible by 2".
Similarly
>> Option 2 There is a queue with X := [m is divisible by 6] and
>> Y := [m is indivisible by 2] such that V(F, F) = T
>> (meaning "if m is indivisible by 6 then m is indivisible by 2").
Clearly, for m=1 we get V(X,Y) = V(F,F) = 1, but we don't get the
statement "(For all m), if m is indivisible by 6 then m is indivisible
by 2".
My claim is that an unstable and a stable M/M/1 queue are analogous to
m=4 and m=1 (respectively).
The analogy isn't perfect, because the example given in the book is an
implication which is true *for all* m.
Again, if you think I am mistaken, please tell me what error you think
I am making. Statements such as "contradicts the intended meaning of"
aren't very precise. I'm stubborn enough to keep this up for weeks,
but progress will be much faster if you point out flaws in my
argument, instead of just saying "your argument is flawed".
On 24 November 2011 21:46, Prof. Victor Li <vli at eee.hku.hk> wrote:
> 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: tccc at lists.cs.columbia.edu
> 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.
> Tccc at lists.cs.columbia.edu
> https://lists.cs.columbia.edu/cucslists/listinfo/tccc
--
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
More information about the TCCC
mailing list