1

Consider a relation $R$ = {$(a, b), (c, d)$}.
This relation is transitive.
Since transitive pair $(a, b)$ and $(b, c)$ is absent, We cannot prove that this relation is TRANSITIVE or NOT TRANSITIVE.
What we say is that it is transitive "by vacuity“ or "vacuously true".
My questions are:-

  1. Why did we define vacuous statements as true rather than false?
  2. Cannot we say that there are not enough facts available to determine the transitivity of the relation? Is it necessary that a relation must be called either TRANSITIVE or NOT TRANSITIVE?

Thanks.

Edit(added 11:27 PM, 23 March 20): I know that the relation in my question is transitive and I also know how. That is not my question. My question is, here we have an if-then statement, $P⇒Q$, (the condition of transitivity), now when the transitive pair (a, b) and (b, c) is absent, P becomes false, then it implies every Q statement. It means that this implies (i) relation is transitive, as well as (ii) relation is not transitive. Then why do we define this type of relation as transitive (vacuously true) rather than not transitive (vacuously false)?

Edit: I am surprised, why this question is marked as duplicate. I saw the mentioned question and observed that they are different. The mentioned question is interested in whether the relation is transitive or not, whereas in my question I have admitted from the beginning that the relation is transitive and questioned the logic behind it. Do you people think they are same?

Shekhar Malhotra
  • 157
  • @Matteo OP is specifying the relation as a set, i.e. under $R$, we have $a \sim b$ and $c \sim d$. – gt6989b Mar 23 '20 at 15:32
  • @abiessu: No. I have modified my question. – Shekhar Malhotra Mar 23 '20 at 18:00
  • The answer to your updated question is that is how we always use vacuous truth. A relation has a property until it doesn't. This relation can be categorized as transitive right next to any other transitive relation and anything that is true for all transitive relations must also be true for this one. – abiessu Mar 23 '20 at 18:44
  • 1
    We are not determining the truth of Q. We are determining the truth of $P\to Q$ which is always true when $P$ is false. Review the truth table for $P\to Q$. It is only false when P is true$, but Q is false. Otherwise it is true. So if the conditions in P do not hold, it doesn't matter whether or not Q holds. The Implication is nonetheless true. – amWhy Mar 23 '20 at 23:33
  • @amWhy: My question is about the truth table. When P doesn’t exist, we are actually clueless and what we did was that we have arbitrarily chosen P⟹Q always holds. Is it a chosen convention or a logical conclusion? – Shekhar Malhotra Mar 24 '20 at 04:41
  • @abiessu: "A relation has a property until it doesn't.": Can we say that 'A relation is transitive until it is proven wrong.'? – Shekhar Malhotra Mar 28 '20 at 04:52
  • Look at it another way: "every time $A$ happens, $B$ must happen." "Look, $B$ happened, that means $A$ must have happened!" "No, $B$ can also happen on its own." The only reverse implication that works is that $B$ not happening means that $A$ cannot have happened. – abiessu Mar 28 '20 at 05:04
  • If some condition happens $n$ times, and every time that condition occurs another condition also occurs, then we can make the full inference, even if $n=0$. – abiessu Mar 28 '20 at 05:07

4 Answers4

3

A relation R on a set S is transitive IF whenever there are pairs $(x, y), (y, z)\in R$, THEN $(x, z)\in R$. It doesn't disqualify a relation from being transitive in cases where there ARE no pairs for which $(x, y), (y, z) \in R$.

Put differently, relation $R$ on a set $S$ is transitive, unless there are elements such that $(x, y) \in S$ AND $(y, z)\in S$ but $(x, z) \notin S$.

In your example, $(a, b) \in S$, but $(b, c) \notin X$, and $(c, d) \in S$, but $(d, a) \notin S$, and $(a, c)\notin S,$ even though $(c, d)\in S$. So it is transitive trivially, because there are no pairs $(x, y)\in S$ AND $(y, z)\in S$, where $(x, z) \notin S$.

amWhy
  • 209,954
  • 1
    By definition a relation R is transitive if we can find pairs (x,y),(y,z)∈R such that (x,z)∈ R. But, such pairs cannot be found in the above relation. So, by this logic the relation is proved to be not transitive (trivially). Why it is called trivially transitive whereas it may also be called trivially not transitive? – Shekhar Malhotra Mar 23 '20 at 15:49
  • No, please reread the answers. – amWhy Mar 23 '20 at 16:30
3

The answer to your question has roots in mathematical logic. The statement of the form you are referring here is a conditional statement where you must have a certain hypothesis to check for the conclusion. Mathematically, it is $P\implies Q$ form where $P$ is antecedent (hypothesis) and $Q$ is consequent (conclusion). The truth value of $P\implies Q$ is $T$ (true) in the following cases:

$(1)$ when both $P$ and $Q$ are true

$(2)$when $P$ is false (irrespective of the truth value of $Q$)

Case (2) says that whenever the hypothesis is false (doesn't hold),the conditional $P\implies Q$ always holds.

Nitin Uniyal
  • 7,946
  • Consider the relation given in original post. Let us define P: If (a, b), (b, c)∈R ⇒ (a, c)∈R; and Q: Relation is transitive; Now, we don’t have (a, b) and (b, c), this implies that P doesn’t exist. So, we cannot prove whether the relation is transitive or not. What this MATHEMATICAL LOGIC {case (2)} is doing, is fixing a convention that in this condition we will go with the statement P⟹Q always holds. We could also go with the statement that P⟹Q does not hold without any problem.Is Case (2) a logical conclusion or a chosen convention? – Shekhar Malhotra Mar 24 '20 at 04:25
  • @ShekharMalhotra Do you agree if it is said that a statement $p\to q$ is false if and only if statement $p$ is true and statement $q$ is false? – drhab Mar 24 '20 at 12:54
  • @drhab: Yes. (1) P is true, Q is true: P→Q is TRUE. (2) P is true, Q is false: P→Q is FALSE. (3) P is false: Information missing. We cannot decide whether P→Q is true or false. We can draw more than one conclusions as in case of your frog example. – Shekhar Malhotra Mar 24 '20 at 15:59
  • In case of transitivity. (1) (a, b), (b, c) ∈ R⇒ (a, c) ∈ R {Relation is transitive} (2) (a, b), (b, c) ∈ R⇒ (a, c) ∉ R {Relation is not transitive} (3) (a, b), (b, c) ∉ R {Not enough facts available to determine the transitivity of the relation?}. Is it necessary that a relation must be called either TRANSITIVE or NOT TRANSITIVE? – Shekhar Malhotra Mar 24 '20 at 16:15
  • 1
    @ShekharMalhotra So $p\to q$ is false iff $p$ is true or $q$ is false. That means that $p\to q$ is true iff at least one of two conditions ($p$ is true, $q$ false) fails and this is evidently the case if $p$ is false. Conclusion: if $p$ is false (or if $q$ is true) then $p\to q$ is true. Every statement is true or false (law of excluded middle). If info lacks then we might not know (true? false?) but it stays a fact that the statement is true or false. – drhab Mar 24 '20 at 16:16
  • 1
    @ShekharMalhotra Every relation is transitive or is not transitive. No relation is both. Again: the law of the excluded middle. – drhab Mar 24 '20 at 16:22
  • @drhab: OK. I got the point. – Shekhar Malhotra Mar 24 '20 at 16:33
  • @drhab: “No relation is both. Again: the law of the excluded middle. “ : I was not saying that the given relation is both TRANSITIVE and at the same time NOT TRANSITIVE. I was just asking that is it not OK to say that we cannot determine the transitivity of the relation. – Shekhar Malhotra Mar 25 '20 at 03:11
  • @ShekharMalhotra Is there in this context a difference then between "the transitivity of the relation is not determined" and "we cannot determine the transitivity of the relation"?... – drhab Mar 25 '20 at 14:06
2

By definition a relation $R$ is not transitive if we can find pairs $(x,y),(y,z)\in R$ such that $(x,z)\notin R$.

Looking at the relation in your question we observe that such pairs cannot be found.

Conclusion: the relation is not not transitive, or equivalently is transitive.

Edit (concerning your second question):

In logic where "excluded middle" is absent a statement is true or false. Applying that to the statement "$R$ is transitive" we find that this is a true statement ($R$ is transitive) or a false statement ($R$ is not transitive).

drhab
  • 151,093
  • Consider this statement.
    By definition a relation R is transitive if we can find pairs (x,y),(y,z)∈R such that (x,z)∈R.
    Looking at the relation in my question we observe that such pairs also cannot be found.
    Conclusion: the relation is not transitive.
    Am I wrong?     – Shekhar Malhotra Mar 23 '20 at 15:43
  • That is not the definition of a transitive relation. Rather a relation R on a set S is transitive IF whenever there are pairs $(x, y), (y, z)\in R$, THEN $(x, z)\in R$. It doesn't disqualify a relation from being transitive in cases where there ARE no pairs for which $(x, y), (y, z) \in R$. – amWhy Mar 23 '20 at 15:47
  • 1
    Your definition of transitive is not correct. It should be: $R$ is transitive if for every pair of pairs $(x,y),(y,z)\in R$ we also have $(x,z)\in R$. So it is not demanded that such pairs $(x,y),(y,z)\in R$ exist. Actually if they don't exist then we can immediately conclude that $R$ is transitive. If you have a box with no frogs in it then the statement: "every frog in that box is yellow" is a true statement. This because in the box no frogs can be found that are not yellow. – drhab Mar 23 '20 at 15:48
  • 1
    @amWhy I am not giving a definition of a relation that is transitive but of a relation that is not transitive. This in an effort to broaden the view of the OP. – drhab Mar 23 '20 at 15:52
  • @drhab I'm sorry I wasn't criticizing your post; I meant only to address the OP's first comment to you. I'm sorry I did not explicitly address Shekhar. I certainly was not at all faulting your answer. It is fine, and I upvoted it! – amWhy Mar 23 '20 at 15:56
  • @amWhy Oh, I see. Thank you. – drhab Mar 23 '20 at 15:56
  • @drhab “If you have a box with no frogs in it then the statement: "every frog in that box is yellow" is a true statement. This because in the box no frogs can be found that are not yellow. “
    : In this case, the statement “No frog in that box is yellow” is also a true statement because you cannot find a frog in that box which is yellow. That is exactly my question, why are we insisting on labeling it as true statement whereas the opposite of it is also true at the same time?     – Shekhar Malhotra Mar 23 '20 at 16:11
  • What your stating is not in general the opposite of the statement. The statements "every frog in that box is yellow" and "every frog in that box is not yellow" (or equivalently "no frog in that box is yellow") are not opposite statements in general. They are only opposite statements if there are indeed frogs in the box. In the case of an empty box both statements are true. – drhab Mar 23 '20 at 16:22
  • Let $X$ be a set and $A\subseteq X$. Then the statements $\varnothing\subseteq A$ and $\varnothing\subseteq A^{\complement}$ are both true statements. They can be translated/worded into: "every element of $X$ that is an element of the empty set is an element of $A$" and "every element of $X$ that is an element of the empty set is not an element of $A$". – drhab Mar 23 '20 at 16:32
  • @drhab The point is that “No frog in that box is yellow” is also a true statement. Why are we insisting on positive statements whereas negative statements are equally true? If A is true, B is true, C is also true, then how can we say that A is true is the right statement?
    Basically my question was “”Why did we define vacuous statements as true rather than false?     – Shekhar Malhotra Mar 23 '20 at 16:38
  • Do you agree that implication $p\to q$ is false if and only if $p$ is true and $q$ is false? If you do then be aware that the implication is true whenever $p$ is false. "Ex falso sequitur quodlibet" they say in logic. A false statement $p$ (like $x\in\varnothing$) implies every statement $q$. You speak of "positive statements" and "negative statements". A bit tricky because positive and negative exclude eachother. This is not so for the statements we handled here. – drhab Mar 23 '20 at 16:40
  • “A false statement p (like x∈∅) implies every statement q.” : When the transitive pair (a, b) and (b, c) is absent (as mentioned in the question), p becomes false, then it implies every q. Does not it mean that this imply (i) relation is transitive, as well as (ii) relation is not transitive? – Shekhar Malhotra Mar 23 '20 at 17:26
  • Tell me explicitly which statement $p$ you have in mind in your former comment. Anyhow, if $p$ is a false statement then $p\to q$ is a true statement for every $q$. But that does not mean that every statement $q$ is true. – drhab Mar 23 '20 at 18:40
  • “Anyhow, if p is a false statement then p→q is a true statement for every q.“ : It is just a convention. Isn’t it? – Shekhar Malhotra Mar 24 '20 at 05:25
  • 1
    More than that I would say. Ask yourself: under what condition is a statement of the form $p\to q$ false?... Well, I can find only one answer to that: if $p $ is true and - in spite of that - $q $ is false. Now what is the negation of this? Of course that $p$ is false or $q $ is true. This shows that the being false of $p $ is sufficient for being true of $p\to q $. – drhab Mar 24 '20 at 09:28
0
  • If a person is not in a situation falling under the conditions of a rule, vacuously, this person is OK with this rule, and what this person does is vacuously right ( as to this rule).

Suppose I define the property " safe driver" as

" ($x$ is a safedriver) iff ( if $x$ is driving a car at time $t$ , then $x$ is not drunk at time $t$)".

Is my friend Peter, who has no car licence and has never driven a car, a " safe driver"?

Yes he is, vacuously.

The reason is that the condition of the rule " $x$ is driving a car at time $t$ " is always false when applied to Peter. So Peter can never be in a situation where (1) the condition of the rule holds and (2) Peter does not obey what the rule commands in that situation.

  • In the same way, the condition of the rule defining a " transitive relation " is false for the relation you are considering. The condition is : having ( at least) two ordered pairs such that the second element of one pair is also the first element of the other.

  • So, this relation cannot possibly violate the rule, and, therefore, is " transitive" vacuously.