Lecture
Transitivity — a property of a binary relation: a binary relation on a set is transitive if, for any three elements of the set, , , the relations and holding implies that the relation :
.One of the most important properties of binary relations; by definition, equivalence relations are transitive (in particular, equality), as are order relations (for example, the set inclusion relation), implication, the reachability relation between vertices of a directed graph, and the parallelism relation for lines (from 
and 
it follows that 
). In number theory, divisibility is transitive (if 
is divisible by 
, and is divisible by 
, then is divisible by ) and so is congruence modulo a number.
Transitive closure — the intersection of all transitive relations containing a given one — the smallest transitive relation that contains it.
Non-transitivity — the absence of transitivity, when the fact that 
and 
hold does not imply that 
holds. For example, the adjacency relation of vertices in a graph is non-transitive (a vertex adjacent to an adjacent vertex may or may not be adjacent to the original one). A tolerance relation is a reflexive and symmetric relation that may be non-transitive. If, on the other hand, the fact that and implies that does not hold, the relation is called antitransitive.
A simple idea
If some set x lies inside a set A, then all the elements of that x must also lie in A.
That is, A in a sense «contains not only sets, but their insides as well».
Example 1: a transitive set
Let:
A = { ∅, {∅} }
Let us check.
The elements of A:
∅
{∅}
Now we look at the elements of those elements:
∅ contains no elements
{∅} contains ∅
And ∅ really is in A.
So:
A = { ∅, {∅} }
is a transitive set.
Example 2: a non-transitive set
Let:
B = { {∅} }
The element of the set B:
{∅}
But inside {∅} lies:
∅
And ∅ does not lie in B.
That is:
{∅} ∈ B
∅ ∈ {∅}
but ∅ ∉ B
So B is not transitive.
Example 3: an ordinary set of numbers
Let:
C = {1, 2, 3}
In ordinary school mathematics the numbers 1, 2, 3 are not treated as sets. That is why the question of transitivity is usually not applied here directly.
But if we understand numbers as von Neumann sets:
1 = {0}
2 = {0, 1}
3 = {0, 1, 2}
then the set:
C = {1, 2, 3}
is not transitive, because:
1 ∈ C 0 ∈ 1 but 0 ∉ C
To make it transitive, we need to add 0:
{0, 1, 2, 3}
An intuitive scheme
A is transitive: if x ∈ A and y ∈ x then y ∈ A
Example:
A = { ∅, {∅} }
{∅} ∈ A
∅ ∈ {∅}
∅ ∈ A
Everything is fine.
But here:
B = { {∅} }
{∅} ∈ B
∅ ∈ {∅}
∅ ∉ B
So there is no transitivity.
It is important not to confuse:
Transitivity of a relation:
a R b and b R c ⇒ a R c
For example:
if a > b and b > c, then a > c
Transitivity of a set:
x ∈ A and y ∈ x ⇒ y ∈ A
That is, here we are talking not about a relation between arbitrary objects, but about the nesting structure of the elements inside a set.
in summary
A set A is transitive if it contains the elements of its own elements.
if x lies in A, then everything that lies inside x must also lie in A.
An example of a transitive set:
{ ∅, {∅} }
An example of a non-transitive set:
{ {∅} }
Surjection, injection and bijection are not direct kinds of transitivity. They are notions from the theory of mappings / functions, whereas transitivity of a set is a property of the nesting of a set's elements.
But they are connected through a more general idea:
how the elements of one set relate to the elements of another set.
A set A is transitive if:
That is:
if an element x lies in A, and y lies inside x, then y must lie in A as well.
Example:
A = { ∅, {∅} }
Here:
{∅} ∈ A
∅ ∈ {∅}
∅ ∈ A
That is why A is transitive.
An injection is a function in which different elements map to different elements.
A function is injective if:
More simply:
different inputs → different outputs
Example:
A = {1, 2, 3}
B = {a, b, c, d}
f(1) = a
f(2) = b
f(3) = c
This is an injection, because no two elements of A land on one and the same element of B.
Scheme:
1 → a 2 → b 3 → c d was left unused
A surjection is a function that covers the entire target set.
f:A→BA function is surjective if every element of B has a preimage in A.
More simply:
every element of B is reached by something from A
Example:
A = {1, 2, 3, 4}
B = {a, b, c}
f(1) = a
f(2) = b
f(3) = c
f(4) = c
This is a surjection, because a, b, c are all covered.
Scheme:
1 → a 2 → b 3 → c 4 → c
A bijection is a function that is at the same time:
injective + surjective
That is:
every element of A corresponds to exactly one element of B, and every element of B is used exactly once.
Example:
A = {1, 2, 3}
B = {a, b, c}
f(1) = a
f(2) = b
f(3) = c
Scheme:
1 → a 2 → b 3 → c
This is a bijection: there are no repetitions and no unused elements in B.
- A mapping f:x->y is called a SURJECTION if ∀y∈Y ∃ x∈X:y=f(x). Then y is the image and x is a preimage of y.
- A mapping f:x->y is called an INJECTION if x1 ≠ x2 => f(x1)≠f(x2), i.e. different elements of the set X are taken to different elements of the set Y.
or f(x1)≠f(x2) => x1=x2
- A mapping f:x->y is called a BIJECTION if it is surjective and injective at the same time. Under a bijective mapping, every element of one set corresponds to exactly one element of the other set, and an inverse mapping is defined which has the same properties.
Transitivity of a set speaks about the connection:
element → element of an element
Injection, surjection and bijection speak about the connection:
element of one set → element of another set
That is:
Transitivity: x ∈ A, y ∈ x Functions: f(x) = y
A function can be regarded as a relation between the elements of two sets.
For example:
f(1) = a
can be represented as the pair:
(1, a)
Then a function is a set of pairs:
f = { (1, a), (2, b), (3, c) }
And transitivity is also often studied through relations.
For example, the relation > is transitive:
5 > 3 3 > 1 so 5 > 1
That is, for relations transitivity means:
A function can be:
injective, but not related to a transitive set surjective, but not transitive bijective, but not transitive
For example:
f: {1, 2, 3} → {a, b, c}
f(1)=a, f(2)=b, f(3)=c
This is a bijection, but nothing at all is said here about the fact that:
if y ∈ x, then y ∈ A
So transitivity of a set is not involved here.
The natural numbers can be built as transitive sets:
0 = ∅
1 = {0}
2 = {0, 1}
3 = {0, 1, 2}
Then every number is a transitive set.
For example:
3 = {0, 1, 2}
If:
2 ∈ 3 1 ∈ 2
then:
1 ∈ 3
And functions between such numbers can be injections, surjections or bijections.
For example:
A = 3 = {0, 1, 2}
B = 3 = {0, 1, 2}
The function:
f(0)=1 f(1)=2 f(2)=0
is a bijection between two transitive sets.
That is:
sets can be transitive, and functions between them can be injective, surjective or bijective.
But these are different properties.
If we have an order relation, for example:
≤
it is transitive:
a ≤ b and b ≤ c ⇒ a ≤ c
And functions can preserve this order.
For example:
f(a)≤f(b)if:
a≤bSuch functions are called monotone.
Here they already appear together:
a transitive order relation + a function between sets + properties of the function
But injection/surjection/bijection are still responsible for something else: how the function covers elements and whether it glues them together.
| Notion | What it is about | A simple idea |
|---|---|---|
| Transitivity of a set | About the nesting of elements | The elements of elements are inside the set too |
| Transitivity of a relation | About a chain of connections | If aRb and bRc, then aRc |
| Injection | About a function | Different inputs give different outputs |
| Surjection | About a function | The whole target set is covered |
| Bijection | About a function | One-to-one and everything covered |
Transitivity is about a chain: A contains x, x contains y ⇒ A contains y Injection/surjection/bijection are about a mapping: the elements of A go to the elements of B
They can be used within one theory, but they describe different aspects of the structure of sets.
In programming, transitivity usually means:
if there is a connection A → B, and there is a connection B → C, then the connection A → C can be inferred.
That is, the connection is passed along the chain.
A is related to B B is related to C so A is related to C
A transitive relation is a relation that is preserved when passing through an intermediate element.
Formally:
if a R b and b R c, then a R c
where R is some relation.
10 > 5 5 > 2 so 10 > 2
The relation > is transitive.
Suppose we have a hierarchy of roles:
admin > manager manager > user
Then, transitively:
admin > user
That is, if admin inherits the permissions of manager, and manager inherits the permissions of user, then admin also gets the permissions of user.
$roles = [
'admin' => ['manager'],
'manager' => ['user'],
'user' => [],
];
function hasRoleAccess(array $roles, string $from, string $target): bool
{
if ($from === $target) {
return true;
}
foreach ($roles[$from] ?? [] as $childRole) {
if (hasRoleAccess($roles, $childRole, $target)) {
return true;
}
}
return false;
}
var_dump(hasRoleAccess($roles, 'admin', 'user')); // true
Here the connection is as follows:
admin → manager → user
And the function returns:
admin → user
A transitive dependency is a dependency through an intermediate object.
A depends on B B depends on C so A transitively depends on C
Suppose your project depends on package A:
project → package-a
And package-a depends on package-b:
package-a → package-b
Then your project transitively depends on package-b:
project → package-a → package-b
That is, package-b may end up in the project even though you did not install it directly.
Your project:
{
"require": {
"monolog/monolog": "^3.0"
}
}
monolog/monolog may depend on other packages, for example on psr/log.
Then it turns out that:
your-project → monolog/monolog → psr/log
psr/log is a transitive dependency of your project.
You did not declare it explicitly, but it is needed by the package you use.
You use the package directly:
Project → Laravel
For example:
{
"require": {
"laravel/framework": "^11.0"
}
}
laravel/framework is a direct dependency.
Internally, Laravel depends on other packages:
Project → Laravel → Symfony Console
Then symfony/console is a transitive dependency of the project.
Suppose:
class PaymentController
{
public function __construct(
private PaymentService $paymentService
) {}
}
class PaymentService
{
public function __construct(
private CheckoutClient $checkoutClient
) {}
}
class CheckoutClient
{
public function request(): void
{
// HTTP request to the payment system
}
}
Dependencies:
PaymentController → PaymentService PaymentService → CheckoutClient
So:
PaymentController → CheckoutClient
But an important point: PaymentController depends on CheckoutClient not directly, but transitively.
Scheme:
PaymentController
↓
PaymentService
↓
CheckoutClient
Transitive dependencies can create hidden coupling.
For example, this is bad:
class PaymentController
{
public function pay(): void
{
$client = new CheckoutClient();
$client->request();
}
}
Here the controller knows directly about the low-level client.
Better:
interface PaymentGatewayInterface
{
public function charge(int $amount): void;
}
class CheckoutPaymentGateway implements PaymentGatewayInterface
{
public function charge(int $amount): void
{
// working with Checkout.com
}
}
class PaymentService
{
public function __construct(
private PaymentGatewayInterface $gateway
) {}
public function pay(int $amount): void
{
$this->gateway->charge($amount);
}
}
Now PaymentService depends not on the concrete CheckoutPaymentGateway, but on the interface:
PaymentService → PaymentGatewayInterface CheckoutPaymentGateway → PaymentGatewayInterface
This reduces tight coupling.
In database normalization there is the notion of a transitive dependency between attributes.
For example, a table:
orders ------------------------------------------------ order_id | customer_id | customer_name | city ------------------------------------------------ 1 | 10 | Ivan | Kyiv 2 | 10 | Ivan | Kyiv
Dependencies:
order_id → customer_id customer_id → customer_name customer_id → city
So:
order_id → customer_name order_id → city
But this is a transitive dependency through customer_id.
The problem: the customer's data is duplicated across orders.
It is better to split it:
orders ----------------------- order_id | customer_id ----------------------- 1 | 10 2 | 10 customers ------------------------------ customer_id | customer_name | city ------------------------------ 10 | Ivan | Kyiv
This way we remove the transitive dependency from the orders table.
Many connections in programming are conveniently represented as a graph:
A → B → C
If we care not only about the direct connection but also about reachability, we build the transitive closure.
The transitive closure shows all the vertices that can be reached.
For example:
A → B B → C C → D
Then, transitively:
A → C A → D B → D
AuthModule → UserModule UserModule → DatabaseModule DatabaseModule → ConfigModule
Then:
AuthModule transitively depends on DatabaseModule AuthModule transitively depends on ConfigModule UserModule transitively depends on ConfigModule
const deps = {
app: ['auth'],
auth: ['user'],
user: ['db'],
db: ['config'],
config: []
};
function collectDeps(module, visited = new Set()) {
for (const dep of deps[module] || []) {
if (!visited.has(dep)) {
visited.add(dep);
collectDeps(dep, visited);
}
}
return visited;
}
console.log([...collectDeps('app')]);
// ['auth', 'user', 'db', 'config']
Here:
app depends directly on auth app transitively depends on user, db, config
In OOP, inheritance is also transitive.
class Animal {}
class Mammal extends Animal {}
class Dog extends Mammal {}
The connection:
Dog → Mammal Mammal → Animal
So:
Dog → Animal
That is, a Dog object is also an Animal.
$dog = new Dog(); var_dump($dog instanceof Dog); // true var_dump($dog instanceof Mammal); // true var_dump($dog instanceof Animal); // true
Example:
your-app image → php:8.3-fpm image php:8.3-fpm image → debian base image debian base image → system libraries
Your Docker image transitively depends on the system libraries of the base image.
If the base image has a vulnerability, it can affect your image too, even if you did not install it directly.
This is very important in supply chain security.
For example:
your-project → package-a → package-b → vulnerable-package
You did not install vulnerable-package directly, but it got into the project through a chain of dependencies.
That is why commands such as:
composer audit npm audit
check not only direct dependencies, but transitive ones as well.
In DDD, transitive dependencies often appear when one layer starts dragging along too many details.
A bad chain:
Controller → Service → Repository → ORM Model → Database
If the controller starts knowing about the ORM model or SQL details, the transitive dependency effectively becomes a direct one.
It is better to keep the boundaries:
Controller → Application Service → Domain Interface Infrastructure Repository → Domain Interface
That is, the upper layers must not depend on the details of the lower layers directly.
Imagine:
The project depends on Laravel. Laravel depends on Symfony. Symfony depends on a polyfill package.
Then:
The project transitively depends on Symfony and on the polyfill package.
Even though in composer.json you may have written only Laravel.
Transitivity of relations:
A is related to B B is related to C so A is related to C
Transitivity of dependencies:
A depends on B B depends on C so A depends on C
In programming this shows up in:
Composer/npm packages classes and services OOP inheritance databases modules Docker images access permissions dependency graphs security application architecture
The main idea:
a transitive dependency is a hidden dependency that appears through a chain of other dependencies.
Transitivity of dependencies is directly related to the Law of Demeter.
The Law of Demeter says:
an object should talk only to its “closest friends”, and not to objects that are hidden inside them.
More simply:
Do not reach through a chain: A → B → C → D Work only with the nearest object: A → B
If:
A depends on B B depends on C
then:
A transitively depends on C
That is, A does not seem to use C directly, yet it still becomes coupled to it through B.
Example:
class OrderController
{
public function show(Order $order): string
{
return $order->getCustomer()->getAddress()->getCity();
}
}
Here is the chain:
OrderController → Order → Customer → Address → City
OrderController directly calls only $order, but in fact it knows the internal structure:
Order has a Customer Customer has an Address Address has a City
This is exactly the problem with transitive dependencies.
The Law of Demeter does not like such chains:
$order->getCustomer()->getAddress()->getCity();
Because the OrderController object now depends not only on Order, but on the internal structure of Customer and Address.
If tomorrow the structure changes:
Customer no longer stores Address directly Address is renamed to Location City is now stored as a CityName object
then the code in the controller may break, even though formally the controller was only working with the order.
class OrderController
{
public function show(Order $order): string
{
$city = $order
->getCustomer()
->getAddress()
->getCity();
return 'City: ' . $city;
}
}
The problem:
OrderController knows too much: - that Order has a Customer - that Customer has an Address - that Address has a City
That is, the controller depends on a chain of objects.
Instead of having the controller reach inside the object, we can give the object a more expressive method:
class Order
{
public function __construct(
private Customer $customer
) {}
public function getCustomerCity(): string
{
return $this->customer->getCity();
}
}
class Customer
{
public function __construct(
private Address $address
) {}
public function getCity(): string
{
return $this->address->getCity();
}
}
Now the controller:
class OrderController
{
public function show(Order $order): string
{
return 'City: ' . $order->getCustomerCity();
}
}
The connection has become shorter:
OrderController → Order
And the details:
Order → Customer → Address
are hidden inside the domain model.
A transitive dependency reveals a problem:
A depends on B B depends on C so A indirectly depends on C
The Law of Demeter tries to reduce this problem:
A must not access C directly through B
That is, the Law of Demeter restricts access to transitive dependencies.
The bad option:
class PaymentController
{
public function pay(PaymentService $paymentService): void
{
$paymentService
->getGateway()
->getHttpClient()
->post('/payments');
}
}
The chain:
PaymentController → PaymentService → Gateway → HttpClient
The controller now knows that PaymentService contains a Gateway, and that Gateway contains an HttpClient.
This is a violation of the Law of Demeter.
class PaymentController
{
public function pay(PaymentService $paymentService): void
{
$paymentService->pay(1000);
}
}
class PaymentService
{
public function __construct(
private PaymentGatewayInterface $gateway
) {}
public function pay(int $amount): void
{
$this->gateway->charge($amount);
}
}
Now the controller knows only:
PaymentController → PaymentService
and not the whole internal chain:
Gateway → HttpClient → API
An important point: not every method chain is bad.
For example, this is usually fine:
$query->where('status', 'paid')
->orderBy('id', 'desc')
->limit(10);
Why?
Because this is a fluent interface: the methods return the same query object or a special builder.
There is no traversal into internal objects here:
QueryBuilder → QueryBuilder → QueryBuilder
But this is more dangerous:
$order->getCustomer()->getAddress()->getCity();
Because every call returns a new internal object:
Order → Customer → Address → City
Signs of a Law of Demeter violation:
$a->getB()->getC()->getD();
or:
$service->repository()->connection()->query();
or:
$user->getProfile()->getSettings()->getTimezone();
The essence of the problem:
the current object knows too much about the internal structure of other objects
It can be remembered like this:
Transitive dependency: A → B → C Violation of the Law of Demeter: A reaches C itself through B The fix: A asks B to perform the required action
That is, instead of:
$a->getB()->getC()->doSomething();
it is better to write:
$a->askBToDoSomething();
or:
$b->doSomethingForA();
In object-oriented style this is often called:
Tell, Don’t Ask
That is:
do not ask an object about its insides, tell it what needs to be done
The bad option:
$total = $cart
->getItems()
->first()
->getProduct()
->getPrice()
->getAmount();
The code knows too much:
Cart contains Items Item contains a Product Product contains a Price Price contains an Amount
Better:
$total = $cart->calculateTotal();
And inside:
class Cart
{
private array $items = [];
public function calculateTotal(): int
{
$total = 0;
foreach ($this->items as $item) {
$total += $item->totalPrice();
}
return $total;
}
}
class CartItem
{
public function __construct(
private Product $product,
private int $quantity
) {}
public function totalPrice(): int
{
return $this->product->priceAmount() * $this->quantity;
}
}
Now the outer code depends only on Cart, and not on the whole chain of objects.
The Law of Demeter helps to preserve encapsulation.
Without it:
an object exposes its internal structure to the outside
With it:
an object manages its own internal objects itself
Bad style:
$order->getCustomer()->getAddress()->getCity();
Better style:
$order->deliveryCity();
or:
$order->shippingAddressCity();
Sometimes getters are fine.
For example, a DTO:
class UserDTO
{
public function __construct(
public string $name,
public string $email
) {}
}
For a DTO it is normal to read data:
$userDto->email;
But for domain objects and services, long chains often mean poor encapsulation.
The connection is as follows:
A transitive dependency shows: A indirectly depends on C through B. The Law of Demeter says: A must not reach C through B.
That is, the Law of Demeter is needed in order to reduce the harm from transitive dependencies.
The main bad sign:
$a->getB()->getC()->getD();
Better:
$a->doWhatINeed();
or:
$b->doItForMe();
The main idea:
do not walk along a chain of internal objects; ask the nearest object to perform the required action.
Yes, on the whole the idea of the table is correct, but I would refine the wording:
| Context | Example | Is there transitivity? | Law of Demeter | Assessment |
|---|---|---|---|---|
| Classes: architectural level | Controller → Service → Repository → DB | Yes | Usually not violated, if each layer talks only to the next layer | Good — a normal architectural chain |
| Classes: object level | $service->getRepo()->getDb()->query() | Yes | Violated: the object accesses “a friend of a friend” | Bad — excessive coupling appears |
| Java modules | requires transitive some.module; | Yes | Not directly related to the Law of Demeter | Good for public API dependencies, but bad if it exposes too much |
| Databases: FK chain | orders → customers → countries | Yes | Not directly related to the Law of Demeter | Fine if the relations are controlled; bad with excessive nesting and complex JOINs |
| Databases: transitive functional dependency | order_id → customer_id → customer_name in a single orders table | Yes | Not directly related to the Law of Demeter | Bad for normalization — a sign of a 3NF violation |
| Maven / Gradle / Composer / npm | project → package-a → package-b | Yes | Not violated, this is the level of package dependencies | Fine as a mechanism, but dangerous with version conflicts, vulnerabilities and hidden dependencies |
| Game logic | A beat B, B beat C, so A beat C | Not always | Not applicable | Bad if the result is inferred mechanically — it can break the business logic |
| Access permissions / roles | Admin → Manager → User | Yes | Usually not violated | Good if the role hierarchy is defined explicitly |
| OOP inheritance | Dog extends Mammal, Mammal extends Animal | Yes | Not violated in itself | Fine if the inheritance reflects a real is-a relationship |
| A long chain of getters | $order->getCustomer()->getAddress()->getCity() | Yes | Violated | Bad for the domain model; $order->deliveryCity() is better |
It is better to put it not like this:
architectural transitivity = good object-level transitivity = bad
but like this:
Transitivity at the architectural level is acceptable if it is hidden behind the boundaries of layers and interfaces. Transitivity at the object level is dangerous if the code starts walking through internal objects via call chains.
| Type | Example | Verdict |
|---|---|---|
| Architectural chain | Controller → Service → Repository | Fine |
| Violation of Demeter | $controller->getService()->getRepo()->getDb() | Bad |
| Package dependency | project → framework → library | Fine, but it has to be kept under control |
| Business logic | A > B, B > C, so A > C | Not always true |
The most important thing: transitivity in itself is neither good nor bad. It becomes bad when it creates hidden coupling, leaking implementation details or incorrect business conclusions.
Comments