Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

What is universal transitivity in logic?

Naima Ali

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

The rules of inference provide the guidelines for constructing valid arguments from the existing statements. Here, we’ll discuss an essential rule of inference for quantified statements, that is, universal transitivity.

Universal transitivity

Assume that we have three predicates PP, QQ, and RR for a certain domain, and we are given the following statements:

x(P(x)Q(x)).\forall x (P(x) \Rightarrow Q(x)).

x(Q(x)R(x)).\forall x (Q(x) \Rightarrow R(x)).

Then, we can conclude x(P(x)R(x))\forall x (P(x) \Rightarrow R(x)) by universal transitivity.

Let’s see how we reach this conclusion. First, we use universal instantiation to get the following statements:

P(c)Q(c).P(c) \Rightarrow Q(c).

Q(c)R(c).Q(c) \Rightarrow R(c).

Then, by using hypothetical syllogism, we get:

P(c)R(c).P(c) \Rightarrow R(c).

Finally, universal generalization gives us the following conclusion:

x(P(x)R(x)).\forall x (P(x) \Rightarrow R(x)).

Example

Let’s look at an example below. Consider the set of polygons as the domain:

Set of polygons

Define the following predicates:

  • P(x)P(x): xx is a regular polygon.
  • Q(x)Q(x): xx has all sides of equal length.
  • R(x)R(x): xx has all angles of equal measure.

Now, assume the following statements are true:

  • x(P(x)Q(x))\forall x (P(x) \Rightarrow Q(x)): Every regular polygon has all sides equal.

  • x(Q(x)R(x))\forall x (Q(x) \Rightarrow R(x)): Every regular polygon with all sides equal has all angles equal.

We can conclude the following statement by applying universal transitivity:

  • x(P(x)R(x))\forall x (P(x) \Rightarrow R(x)): Every regular polygon has equal angles.

RELATED TAGS

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring