Generative Structural Theory v1.22 — Closure-Preserving Sub-relations: Essential Pairs, Inclusion-Minimal Members, and Minimum Cardinality
- 1SD Lab LLC
Abstract
GST v1.21 characterised, for a finite loop-free relation z, the family H_le(z) of sub-relations w of z that keep the reflexive transitive closure of z: w is strongly connected inside each strongly connected component of z and keeps at least one pair of z on each link of the transitive reduction of the condensation (v1.21 Theorem A2). This manuscript studies the smallest members of that family and keeps two notions apart: inclusion-minimal (no pair can be removed) and of minimum cardinality (fewest pairs).
A pair is essential when it lies in every member. The family is an up-set, so its maximal proper members are the relations z - {e} with e not essential (Proposition B1), and a pair a>b is essential if and only if there is no path from a to b in z - {a>b} (Proposition B2). A pair inside a component is essential if and only if its removal breaks the strong connectivity of that component (these are the strong bridges), and a pair between components if and only if it is the only pair on a link of the transitive reduction (Proposition B3).
The inclusion-minimal members correspond one to one to the choices of an inclusion-minimal strongly connected spanning sub-relation for each component and of one pair for each link of the transitive reduction, which gives their number as a product (Theorem B4). The least number of pairs is the sum of the least numbers for the components plus the number of links of the transitive reduction; a member of minimum cardinality is inclusion-minimal, but not conversely in general (Proposition B5).
For the fixed cut z_t of twelve pairs, the essential pairs are five and do not themselves keep the closure; H_lt(z_t) has seven maximal members, H_le(z_t) has four inclusion-minimal members, of 7, 7, 8 and 8 pairs, and the minimum is 7; inside the component {0, 2, 3, 4} one inclusion-minimal sub-relation has six pairs while the minimum there is five. The stored answer y = z_t - {1>3} is one of the seven maximal proper members and is not inclusion-minimal; this places y in the structure and does not explain the procedure that stored it.
The general statements are related to known results of graph theory, and no novelty is claimed for B1-B5; the specific correspondence with the known decomposition by components is stated in §A8. All results are argued; no new machine enumeration or graph computation was made for v1.22. Nothing is claimed about other particular cuts, the member list of the class C evaluation, acceptance at a root, or why y was stored.
Related
- Generative Structural Theory v1.21 — Closure-Preserving Sub-relations: Structural Conditions and Counting
- Generative Structural Theory v1.20 — Where the 59 Cuts Come From: The Closure-Preserving Sub-relations of z_t, a Finite Machine Check of Their Characterisation, and a Conditional Connection with C_2
- Generative Structural Theory v1.23 — Connecting the Class C Evaluation with Closure-Preserving Sub-relations
- Generative Structural Theory v1.27 — Theta Relations with One-Way Edges: Exact Counting and Minimality
- Generative Structural Theory v1.30 — K4-Supported Relations with One-Way Edges: Exact Counting and Minimality
BibTeX
@misc{okino2026generative,
title = {{Generative Structural Theory v1.22 — Closure-Preserving Sub-relations: Essential Pairs, Inclusion-Minimal Members, and Minimum Cardinality}},
author = {Koji Okino},
howpublished = {Zenodo},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23450445},
url = {https://zenodo.org/records/23450445},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Generative Structural Theory v1.22 — Closure-Preserving Sub-relations: Essential Pairs, Inclusion-Minimal Members, and Minimum Cardinality
AU - Koji Okino
PY - 2026
DA - 2026/10/18
PB - Zenodo
DO - 10.5281/zenodo.23450445
UR - https://zenodo.org/records/23450445
AB - GST v1.21 characterised, for a finite loop-free relation z, the family H_le(z) of sub-relations w of z that keep the reflexive transitive closure of z: w is strongly connected inside each strongly connected component of z and keeps at least one pair of z on each link of the transitive reduction of the condensation (v1.21 Theorem A2). This manuscript studies the smallest members of that family and keeps two notions apart: inclusion-minimal (no pair can be removed) and of minimum cardinality (fewest pairs). A pair is essential when it lies in every member. The family is an up-set, so its maximal proper members are the relations z - {e} with e not essential (Proposition B1), and a pair a>b is essential if and only if there is no path from a to b in z - {a>b} (Proposition B2). A pair inside a component is essential if and only if its removal breaks the strong connectivity of that component (these are the strong bridges), and a pair between components if and only if it is the only pair on a link of the transitive reduction (Proposition B3). The inclusion-minimal members correspond one to one to the choices of an inclusion-minimal strongly connected spanning sub-relation for each component and of one pair for each link of the transitive reduction, which gives their number as a product (Theorem B4). The least number of pairs is the sum of the least numbers for the components plus the number of links of the transitive reduction; a member of minimum cardinality is inclusion-minimal, but not conversely in general (Proposition B5). For the fixed cut z_t of twelve pairs, the essential pairs are five and do not themselves keep the closure; H_lt(z_t) has seven maximal members, H_le(z_t) has four inclusion-minimal members, of 7, 7, 8 and 8 pairs, and the minimum is 7; inside the component {0, 2, 3, 4} one inclusion-minimal sub-relation has six pairs while the minimum there is five. The stored answer y = z_t - {1>3} is one of the seven maximal proper members and is not inclusion-minimal; this places y in the structure and does not explain the procedure that stored it. The general statements are related to known results of graph theory, and no novelty is claimed for B1-B5; the specific correspondence with the known decomposition by components is stated in §A8. All results are argued; no new machine enumeration or graph computation was made for v1.22. Nothing is claimed about other particular cuts, the member list of the class C evaluation, acceptance at a root, or why y was stored.
ER -