Mathematical Terms

Binary classification

A classification that places every record into one of exactly two labeled groups, such as covered and not-covered.

Block

One group within a partition.

Records in the same block are treated as equivalent under the relation being modeled. For example, the partition

{A, B} {C} {D}

contains three blocks.

Covered Set

The set of records for which a directional coverage predicate evaluates to true.

For example, if A and B are covered and C and D are not, the covered set is:

{A, B}

This can be lifted, or transformed into a representation suitable for partition analysis, as the labeled binary classification:

covered = {A, B}

not-covered = {C, D}

Directional Relation

A relationship for which order matters.

If A relates to B, it does not necessarily follow that B relates to A.

A more general identifier may match a more specific identifier without implying that the more specific identifier matches the more general one. Contrast with a symmetric relation.

For example, suppose:

A = pkg:oci/example@sha256:123

and:

B = pkg:oci/example@sha256:123?repository_url=registry.example.com/example

A matching rule may allow the more general identifier A to match the more specific identifier B, because B adds a qualifier.

But that does not imply that the more specific identifier B must match the more general identifier A.

So the relation has a direction: A -> B

where the arrow means: A is permitted by the matching rule to match, cover, or apply to B.

This does not necessarily imply: B -> A

because the reverse match may not be permitted by the rule.

Another example: dog -> mammal

where the arrow means: dog is a more specific category that belongs within the broader category mammal.

But this does not imply: mammal -> dog

because not every mammal is a dog.

Likewise: dog -> animal

does not imply: animal -> dog.

The relationship is directional because one category is contained within another, but the reverse containment does not hold.

Equivalence Relation

A relation representing a consistent notion of "the same."

An equivalence relation is reflexive, symmetric, and transitive. Equivalence relations naturally divide a finite set into partitions called equivalence classes.

Finite Domain

The complete finite set of records being analyzed.

For example:

D = {A, B, C, D}

A partition assigns every member of the finite domain to exactly one block.

Identity Commitment

An identity commitment is an explicit rule stating when two records, identifiers, or representations should be treated as referring to the same thing for a particular purpose.

The commitment must identify the relevant notion of sameness.

For example, a commitment might state that two package representations identify the same software package when their canonical package identifiers are equal.

In this study, an identity commitment must be grounded in an external source such as a standard, specification, documented contract, or established ecosystem convention rather than inferred from the implementation being tested.

Identity Commitment, Multi-Class

A multi-class identity commitment is an identity commitment that divides the examined finite domain into three or more identity classes.

For example, suppose six records describe three software packages:

A1, A2 describe package A.

B1, B2 describe package B.

C1, C2 describe package C.

The identity commitment induces the partition:

{A1, A2} {B1, B2} {C1, C2}

This is a multi-class identity commitment because the declared identity relation produces three distinct blocks.

Multi-class commitments are important in this study because they allow the partition analysis to express merge, split, refinement, and incomparability relationships that cannot arise fully in a simple two-block covered / not-covered classification.

Incomparable Partitions

Two partitions are incomparable when neither is a refinement of the other.

For example:

P1 = {A, B} {C, D}

P2 = {A, C} {B, D}

P1 groups A with B, while P2 separates them.

P2 groups A with C, while P1 separates them.

Neither partition can be obtained from the other simply by splitting existing blocks.

Each makes distinctions that the other does not, so neither partition is strictly finer or coarser than the other.

Labeled Partition

A partition whose blocks have explicit semantic meanings.

For example:

covered = {A, B}

not-covered = {C, D}

The labels matter because the unlabeled partition

{A, B} {C, D}

does not by itself indicate which block represents covered.

Lifted

A rule or relation is lifted when it is transformed into another representation so that it can be analyzed by a different mathematical framework while preserving the original meaning as faithfully as possible.

In this study, a directional coverage predicate such as:

covered(x)

can be lifted into a labeled binary classification:

covered = {A, B}

not-covered = {C, D}

That classification can then be represented as a two-block partition.

The important question is whether the lifting preserves the semantics of the original rule.

For example, if the original rule is directional, the lifted representation must not silently turn it into a symmetric notion of identity.

A lifting is useful only when the transformation preserves the distinctions that matter for the analysis.

Partition

A division of a set into non-overlapping groups, called blocks, such that every element appears in exactly one block.

For example:

{A, B} {C} {D}

is a partition of:

{A, B, C, D}

In this study, partitions represent how an identity rule or implementation groups records according to a particular notion of sameness.

Predicate

A rule that evaluates to either true or false for a given record or relationship.

For example:

covered(x)

may be true when identifier x is covered by another identifier and false otherwise.

A predicate can produce a binary classification, but the predicate itself is not necessarily an identity relation.

Proper Refinement

A refinement in which one partition is strictly finer than another rather than identical to it.

For example:

{A} {B} {C}

properly refines:

{A, B} {C}

because the first partition makes an additional distinction between A and B.

Refinement

A relationship between partitions describing whether one classification makes at least all the distinctions made by another.

Partition P1 refines partition P2 when every block of P1 is completely contained within some block of P2.

For example:

P1 = {A} {B} {C}

refines:

P2 = {A, B} {C}

The finer partition distinguishes A from B; the coarser partition treats them as the same.

Symmetric Relation

A relationship for which direction does not matter.

If A relates to B, then B must also relate to A.

Ordinary equality and equivalence-like notions of sameness are symmetric.

A directional matching or coverage rule must not be modeled as symmetric unless independent justification supports doing so.

Two-Block Partition

A partition containing exactly two blocks.

A binary predicate such as covered / not-covered can be represented as a two-block partition.

Two distinct two-block partitions cannot stand in a proper refinement relation: they are either equal or incomparable. This limits how much partition structure a binary classification can expose.

Witness

A concrete finite example demonstrating that a declared relation and an implemented relation do not conform.

A witness identifies the particular records responsible for the mismatch rather than reporting only that a disagreement exists.