Identifier
F:hall-matching-union-disjoint-images
Proof route
kernel-lean
External status
proved
Axiom footprint
Empty

Recorded description

Let nb be a family of finite sets of naturals, and let f be a system of distinct representatives for nb on the index set s1 and g one on s2 -- each picks a member of nb i for every index i in its own set, injectively. If the two images never meet (f a is never equal to g b for a in s1 and b in s2), then the function that takes f's value on s1 and g's value elsewhere is a system of distinct representatives for nb on the union of s1 and s2. The index sets need NOT be disjoint: the glued function reads s1 first, so a shared index takes f's value and the definition is unambiguous with no side condition. This is a kernel term with an empty axiom footprint.

Formal statement
theorem Nat.Hall.isMatching_union : ((x0 : AxNat.Finset) -> ((x1 : AxNat.Finset) -> ((x2 : ((x2 : AxNat) -> AxNat.Finset)) -> ((x3 : ((x3 : AxNat) -> AxNat)) -> ((x4 : ((x4 : AxNat) -> AxNat)) -> ((x5 : AxNat.Hall.IsMatching x0 x2 x3) -> ((x6 : AxNat.Hall.IsMatching x1 x2 x4) -> ((x7 : ((x7 : AxNat) -> ((x8 : AxNat) -> ((x9 : Eq.{1} Bool (AxNat.Finset.memB x0 x7) Bool.true) -> ((x10 : Eq.{1} Bool (AxNat.Finset.memB x1 x8) Bool.true) -> ((x11 : Eq.{1} AxNat (x3 x7) (x4 x8)) -> False)))))) -> AxNat.Hall.IsMatching (AxNat.Finset.union x0 x1) x2 (AxNat.Hall.glue x3 x4 x0)))))))))

Dependencies

The graph shows direct ledger edges. Follow a node to open its artifact page.

Direct dependencies appear to the left. The current fact is in the center. Facts that depend directly on it appear to the right. Cardinality of an injection bet Membership implies the index is Current fact Hall's condition survives on th Hall's marriage theorem: a fini
2 direct dependencies 2 direct dependents

Evidence

kernel-Nat.Hall.isMatching_union

Kind
kernel-term
Status
checked

Supports: two matchings with disjoint images glue into a matching on the union of their index sets

Checker command
cargo test --release -p axeyum-lean-kernel --lib nat_prelude::hall_tests -- --test-threads=4
Evidence notes

ADR-1614 expected Nat.Finset.card_le_of_injOn to be the tool. It is not: that lemma COUNTS an injection, and what is needed here is that the glued function IS one. The content is four branches, one per pair of decisions on `memB s1 i` and `memB s1 j`; the two diagonal ones are each matching's own injectivity and the two mixed ones are refuted by the disjointness hypothesis at exactly that pair, reached through memB_union_elim ('in the union but not in s1' gives 'in s2'). Requiring disjoint INDEX sets would have cost every consumer an obligation the argument never uses.

kernel-Nat.Finset.memB_union_elim

Kind
kernel-term
Status
checked

Supports: a member of a union of finite sets is a member of one of them

Checker command
cargo test --release -p axeyum-lean-kernel --lib nat_prelude::hall_tests -- --test-threads=4
Evidence notes

Produces an `Or` rather than a computed index deliberately: the two sides may overlap, and `setUnion` reads the left one first, so the decision on `memB s i` IS the disjunction. Its pointwise base `memB_union` costs one step more than the difference's, because `union` stores `bound s + bound t` and putting an index above it means putting it above EACH -- le_add_right on the left, the same lemma plus one add_comm on the right. `memB_union_right` needs a decision on `memB s i` where its `_left` twin needs none, for the same left-first reason.

eval-glue-convention

Kind
instance-pin
Status
checked

Supports: the glue takes f on the set and g off it, and not the other way round

Checker command
cargo test --release -p axeyum-lean-kernel --lib nat_prelude::hall_tests -- --test-threads=4
Evidence notes

Nat.Hall.glue is a Definition, so the trusted gate cannot tell you it is wrong -- a glue reading the selector the other way round has exactly the same type. It is reduced at concrete arguments with the wrong formula named: with f i = i + 10, g i = i + 20 and s = {1}, the glue is 11 at 1 and 22 at 2, and the swapped convention's answers 21 and 12 are named as the values it must NOT produce. A mutation exchanging the two branches WAS run: it killed all 18 tests in the module by making the shared prelude unbuildable, because the proof terms name the selector's branches positionally through select_nat_true/select_nat_false. So this test is the readable pin on the convention, not a load-bearing guard -- ADR-1623's mutation table records that this lane predicted otherwise and the measurement refuted it.

shape-Nat.Hall.isMatching_union

Kind
exhaustive-enumeration
Status
checked

Supports: the declarations exist under these exact names and are theorems

Checker command
cargo run --release -q -p axeyum-lean-kernel --example shape_search -- --name Nat.Hall.card_le_card_unionOver_sdiff_add --expect 1
Evidence notes

The presence check is not decoration: Kernel::axiom_footprint returns an EMPTY vector for a name that was never declared, so a footprint assertion alone passes vacuously on a typo'd or missing declaration. Environment::contains is what makes the exit status depend on the finding. The shape_search binary was rebuilt at this lane's HEAD (declarations=3017, up from 3000 at the base commit, the increment being exactly the seventeen new declarations), and the freshness control postdates every commit in the lane, so a stale index cannot pass.

Provenance

{
  "date": "2026-09-05",
  "established_by": "axeyum lane `hall-counting`, roadmap item W2-12 residue: `nat_prelude/hall.rs` gains `glue` and `isMatching_union`; `nat_prelude/finset.rs` gains the union's membership calculus (`memB_union`, `memB_union_left`, `memB_union_right`, `memB_union_elim`). ADR-1623.",
  "source": "The combining step of the standard inductive proof of Hall's marriage theorem, where two matchings produced by the inductive hypothesis on two smaller families are assembled into one.",
  "prior_art": [
    {
      "citation": "Mathlib, `Finset.piecewise` and the `Set.InjOn.union` family",
      "establishes": "the same gluing of two injective partial functions, stated over `Set`/`Finset` with decidable membership from a typeclass; that route requires the domains to be disjoint (or supplies an agreement hypothesis on the overlap), where this one reads the left set first and needs neither"
    }
  ]
}