Is license compatibility a partial order?

Question

When we say that some license X is (one-way) compatible with another license Y, I gather that we often intend for compatibility to be transitive; that is, given some other license W which is compatible with X, W is also compatible with Y.

This happens to be the key property of partial orders. A partial order has two other properties which seem trivial to establish. First, any license is trivially compatible with itself. Second, if two licenses are each compatible with each other, then the licensed software can be offered equivalently under both licenses simultaneously; this equivalence is antisymmetry.

So, to detail my question, I think that in an ideal world, yes, license compatibility is a partial order. But that's not the world that we find ourselves inhabiting today. What counterexamples show that license compatibility is not a partial order?

The main pragmatic purpose of this question is to establish the degree to which we are allowed to use Boolean algebra (AND, OR, NOT, etc.) to compose many licenses together. Given how often folks informally do this, I would not be surprised to learn that I am not the first person to ask this question. Prior questions have involved informally considering unions of single licenses or unions of license families.

Answer 1

No, license compatibility is generally transitive but does not quite form a partial order in the mathematical sense.

Viewing license compatibility as a partial order makes sense in the context of copyleft licenses like the GPL. These require that the software as a whole must be available as the same license. Thus, if we include compatibly-licensed software into a GPL-covered program, the entire program is effectively licensed under GPL. And any GPL software can also be used in an AGPL-covered program.

This view stops making sense with more permissive licenses. Here, the licenses do not impose any requirements on the program as a whole, but can freely provide permissions and impose conditions. The licensee will then effectively have the intersection of permissions, and the union of conditions to comply with.

As an abstract example, consider the following made-up licenses:

• Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, subject to the following condition:
  This notice shall be included in all copies or substantial portions of the Software.

  (X-Attribution, a made-up combination of 0BSD + MIT)

• Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, subject to the following condition: If the software is modified, the modified version shall only be distributed (a) under any OSI-approved license, or (b) in a manner that doesn't prevent installation of the unmodified version.

  (X-Compat, a made-up combination of 0BSD with a core feature of the Artistic License)

A software that combines software under these two licenses is licensed under neither of these alone, but under both in combination. The relicensing mechanism of X-Compat clause (a) cannot be used to switch to X-Attribution because X-Attribution is not OSI-approved. However, the licenses are clearly compatible: nothing prevents a licensee from complying with both license conditions.

So we might say that “X-Attribution is-compatible-with X-Compat” and “X-Compat is-compatible-with X-Attribution”, but the licenses are not equal. This violates the antisymmetric condition you propose.

I think it would be possible to find a practical example of this issue with more exotic permissive licenses, e.g. involving the Artistic License, Attribution Assurance License, or SIL Open Font License. But I haven't checked this in detail.

A more rigorous definition would consider that the compatibility relation should not consider compatibility between two “input” licenses, but possible changes to licensing that a covered software can undergo. Here, it would be more precise to say:

• X-Compat is-compatible-with (X-Compat AND X-Attribution)
• X-Attribution is-compatible-with (X-Compat AND X-Attribution)

In contrast, we can say for some licenses with explicit relicensing provisions there wouldn't be an AND operator on the right side:

• GPL-2.0+ is-compatible-with GPL-2.0
• GPL-2.0+ is-compatible-with GPL-3.0
• LGPL-3.0 is-compatible-with GPL-3.0

This post uses the AND operator as defined in SPDX license expressions.