bibd_isomorphic_of_block_clique_graph_iso
OP-1148: if two BIBDs D₁, D₂ with the same parameters (v, b, r, k, λ) on finite block sets have isomorphic modified block-clique graphs (bibd_block_clique_graph), then the designs are isomorphic (bibd_isomorphic), for every block size k.
Statement
theorem bibd_isomorphic_of_block_clique_graph_iso {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂] {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (h : Nonempty (bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂)) : bibd_isomorphic D₁ D₂
- Related work
- arXiv:2611.05762, Conjecture 6.30.1 (Sec. 6.30, Algebraic Recoverability), for the construction of Sec. 6.9. Stated for every block size k; finiteness of the block sets is added because Nat.card gives no information on infinite types.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- bibd_isomorphic_of_block_clique_graph_iso_of_three_leRecoverability of a BIBD from its modified block-clique graph when the block size k is at least 3: if two BIBDs D₁, D₂ with the same…
- bibd_block_clique_graphThe modified block-clique graph K_v^*(D) of a balanced incomplete block design D with parameters (v, b, r, k, λ) is the simple graph on…
- bibd_isomorphicTwo balanced incomplete block designs D₁ and D₂ with parameters (v, b, r, k, λ) are isomorphic if there exist a bijection f between their…
- BIBDA structure BIBD parameterized by types X and B and natural numbers v, b, r, k, lam, with fields: card_points asserting Nat.card X = v;…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
Let $X_1, B_1, X_2, B_2$ be types with $B_1$ and $B_2$ finite, and let $v, b, r, k, \lambda$ be natural numbers. Let $D_1$ and $D_2$ be balanced incomplete block designs (BIBDs) on point sets $X_1, X_2$ and block sets $B_1, B_2$, respectively, both having parameters $(v, b, r, k, \lambda)$. If there exists a graph isomorphism between the block-clique graph of $D_1$ and the block-clique graph of $D_2$, then $D_1$ and $D_2$ are isomorphic as block designs.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is established by case analysis on the block size k. For k ≥ 3, design isomorphism follows from graph isomorphism by the reconstruction theorem for block-clique graphs (bibd_isomorphic_of_block_clique_graph_iso_of_three_le). For small block sizes k ∈ {0, 1, 2}, the design is completely characterized up to isomorphism by its parameters alone without using the graph isomorphism: for k = 0 block incidence is vacuously false, for k = 1 blocks are singletons with point fibers of uniform size r, and for k = 2 blocks are pairs with pair fibers of uniform size λ, allowing explicit construction of the block bijection by fiber decomposition.
The point sets and block sets of the two designs are finite with equal cardinalities, providing bijections between points and between blocks.
Since k = 0 < v by the incomplete design axiom, the number of points v is non-zero. By Nat.finite_of_card_ne_zero, both point sets are finite. Because the designs share parameters v and b, Finite.card_eq.mp yields bijections f between the point sets and g between the block sets.
uses
Nat.finite_of_card_ne_zero,Finite.card_eq.mphave hv : v ≠ 0 := by have := D₁.incomplete omega have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv) have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv) have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points]) have hB : Nonempty (B₁ ≃ B₂) := Finite.card_eq.mp (by rw [D₁.card_blocks, D₂.card_blocks]) rcases hX with ⟨f⟩ rcases hB with ⟨g⟩
The chosen bijections f and g form an isomorphism between the designs for k = 0.
For block size 0, the incidence condition between blocks and points asserts the existence of an index in Fin 0, which is vacuously false on both sides using Fin.elim0.
uses
Fin.elim0refine ⟨f, g, fun b₁ x => ?_⟩ constructor · rintro ⟨j, _⟩; exact Fin.elim0 j · rintro ⟨j', _⟩; exact Fin.elim0 j'
The point sets are finite and there is a bijection f between them for k = 1.
Since 1 = k < v, v is positive. Therefore both point sets have non-zero cardinality and are finite by Nat.finite_of_card_ne_zero. Since both have v points, Finite.card_eq.mp yields a bijection f between them.
uses
Nat.finite_of_card_ne_zero,Finite.card_eq.mphave hv : v ≠ 0 := by have := D₁.incomplete omega have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv) have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv) have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points]) rcases hX with ⟨f⟩
For each point, the fibers of blocks containing that point have cardinality r in both designs, giving fiberwise bijections.
When k = 1, the unique block index is j0 = 0 (since any index equals j0 by Subsingleton.elim). Through Equiv.subtypeEquivRight and Nat.card_congr, the fiber of blocks mapping to a given point is equivalent to the replication set, which has cardinality r by the design replication axiom. Since every fiber has size r, Finite.card_eq.mp provides a bijection between the fiber over x in D₁ and the fiber over f(x) in D₂.
uses
Nat.zero_lt_one,Equiv.subtypeEquivRight,Subsingleton.elim,Nat.card_congr,Finite.card_eq.mplet j0 : Fin 1 := ⟨0, Nat.zero_lt_one⟩ let pt₁ : B₁ → X₁ := fun β => D₁.block_pts β j0 let pt₂ : B₂ → X₂ := fun β => D₂.block_pts β j0 have h_fib₁ : ∀ x : X₁, Nat.card { β : B₁ // pt₁ β = x } = r := by intro x have hr := D₁.replication x have heq : { β : B₁ // pt₁ β = x } ≃ { β : B₁ // ∃ j, D₁.block_pts β j = x } := Equiv.subtypeEquivRight (fun β => by constructor · intro h; exact ⟨j0, h⟩ · rintro ⟨j, hj⟩ have : j = j0 := Subsingleton.elim j j0 subst this exact hj) rw [Nat.card_congr heq] exact hr have h_fib₂ : ∀ y : X₂, Nat.card { β : B₂ // pt₂ β = y } = r := by intro y have hr := D₂.replication y have heq : { β : B₂ // pt₂ β = y } ≃ { β : B₂ // ∃ j, D₂.block_pts β j = y } := Equiv.subtypeEquivRight (fun β => by constructor · intro h; exact ⟨j0, h⟩ · rintro ⟨j, hj⟩ have : j = j0 := Subsingleton.elim j j0 subst this exact hj) rw [Nat.card_congr heq] exact hr have h_fib_iso : ∀ x : X₁, Nonempty ({ β : B₁ // pt₁ β = x } ≃ { β : B₂ // pt₂ β = f x }) := by intro x exact Finite.card_eq.mp (by rw [h_fib₁, h_fib₂])
Gluing the fiber bijections over all points produces a bijection g between the block sets for k = 1.
Decomposing each block set into a dependent sum of fibers over points gives canonical equivalences e₁ and e₂. Combining the point bijection f with the fiber bijections using Equiv.sigmaCongr yields an equivalence of sigma types, which when composed with e₁ and the inverse of e₂ gives a bijection g between the block sets.
uses
Equiv.sigmaCongrlet e₁ : B₁ ≃ (x : X₁) × { β : B₁ // pt₁ β = x } := { toFun := fun β => ⟨pt₁ β, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨x, β, hβ⟩ => by dsimp subst hβ rfl } let e₂ : B₂ ≃ (y : X₂) × { β : B₂ // pt₂ β = y } := { toFun := fun β => ⟨pt₂ β, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨y, β, hβ⟩ => by dsimp subst hβ rfl } let e_sigma : ((x : X₁) × { β : B₁ // pt₁ β = x }) ≃ ((y : X₂) × { β : B₂ // pt₂ β = y }) := Equiv.sigmaCongr f (fun x => (h_fib_iso x).some) let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm)
The bijections f and g constitute a design isomorphism for k = 1.
By construction, the point of block g(β) is f applied to the point of block β. Since any index in Fin 1 is j0 by Subsingleton.elim, block incidence reduces to point equality, which is preserved and reflected by f using congr_arg and injectivity of f.
uses
Subsingleton.elim,congr_argrefine ⟨f, g, fun β x => ?_⟩ have hg_pt : pt₂ (g β) = f (pt₁ β) := by have this1 : (e_sigma (e₁ β)).1 = f (pt₁ β) := rfl have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1 rw [e₂.apply_symm_apply] exact he2.trans this1 constructor · rintro ⟨j, hj⟩ have hj0 : j = j0 := Subsingleton.elim j j0 subst hj0 refine ⟨j0, ?_⟩ change pt₂ (g β) = f x rw [hg_pt] exact congr_arg f hj · rintro ⟨j', hj'⟩ have hj0 : j' = j0 := Subsingleton.elim j' j0 subst hj0 refine ⟨j0, ?_⟩ change pt₁ β = x change pt₂ (g β) = f x at hj' rw [hg_pt] at hj' exact f.injective hj'
A point belongs to a block of size 2 if and only if it equals the block's point at index 0 or at index 1.
Since any index in Fin 2 is either 0 or 1 by case exhaustion, the existential quantifier over Fin 2 is logically equivalent to the disjunction of equalities at index 0 and index 1.
let j0 : Fin 2 := ⟨0, by omega⟩ let j1 : Fin 2 := ⟨1, by omega⟩ have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by intro ⟨val, hval⟩ interval_cases val · left; rfl · right; rfl constructor · rintro ⟨j, hjx⟩ rcases hj j with rfl | rfl · left; exact hjx · right; exact hjx · rintro (h | h) · exact ⟨j0, h⟩ · exact ⟨j1, h⟩
Equality of unordered pairs under a bijection f preserves and reflects membership.
Unordered pair equality expands via Sym2.eq_iff to matching coordinates in forward or swapped order. Applying injectivity of f via EmbeddingLike.apply_eq_iff_eq and disjunction commutativity or_comm shows that membership in the image pair is equivalent to membership in the source pair.
uses
Sym2.eq_iff,EmbeddingLike.apply_eq_iff_eq,or_commsimp only [Sym2.eq_iff] at h rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · simp only [EmbeddingLike.apply_eq_iff_eq] · simp only [EmbeddingLike.apply_eq_iff_eq, or_comm]
The point sets are finite and admit a bijection f between them for k = 2.
From 2 = k < v, v is non-zero, making both point sets finite by Nat.finite_of_card_ne_zero. Since both have cardinality v, Finite.card_eq.mp gives a bijection f between them.
uses
Nat.finite_of_card_ne_zero,Finite.card_eq.mphave hv : v ≠ 0 := by have := D₁.incomplete omega have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv) have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv) have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points]) rcases hX with ⟨f⟩
Each block determines an unordered pair of points, and for distinct points x ≠ y, the block's pair equals s(x, y) if and only if both x and y belong to the block.
Using Sym2.eq_iff, equality of the block pair with s(x, y) is equivalent to the two points matching in either order. Because the block indices are restricted to 0 and 1 and x ≠ y prevents both indices from taking the same value, this is equivalent to both x and y being incident with the block.
uses
Sym2.eq_ifflet j0 : Fin 2 := ⟨0, by omega⟩ let j1 : Fin 2 := ⟨1, by omega⟩ let pair₁ : B₁ → Sym2 X₁ := fun β => s(D₁.block_pts β j0, D₁.block_pts β j1) let pair₂ : B₂ → Sym2 X₂ := fun β => s(D₂.block_pts β j0, D₂.block_pts β j1) have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by intro ⟨val, hval⟩ interval_cases val · left; rfl · right; rfl have h_fib_eq₁ : ∀ (β : B₁) (x y : X₁), x ≠ y → (pair₁ β = s(x, y) ↔ (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y) := by intro β x y hxy simp only [pair₁, Sym2.eq_iff] constructor · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩) · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩ · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩ · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩ rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl · subst hjx hj'y; exact (hxy rfl).elim · left; exact ⟨hjx, hj'y⟩ · right; exact ⟨hj'y, hjx⟩ · subst hjx hj'y; exact (hxy rfl).elim have h_fib_eq₂ : ∀ (β : B₂) (x y : X₂), x ≠ y → (pair₂ β = s(x, y) ↔ (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y) := by intro β x y hxy simp only [pair₂, Sym2.eq_iff] constructor · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩) · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩ · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩ · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩ rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl · subst hjx hj'y; exact (hxy rfl).elim · left; exact ⟨hjx, hj'y⟩ · right; exact ⟨hj'y, hjx⟩ · subst hjx hj'y; exact (hxy rfl).elim
Block pairs are never diagonal, and each off-diagonal pair appears in exactly λ blocks.
Because the points of any block are distinct by injectivity of block_pts, Sym2.mk_isDiag_iff shows no block pair is diagonal. For any off-diagonal pair s(x, y) (analyzed using Sym2.ind and Sym2.mk_isDiag_iff), the fiber of blocks having this pair is equivalent via Equiv.subtypeEquivRight to the set of blocks containing both x and y, which has cardinality λ by Nat.card_congr and the design balance axiom.
uses
Sym2.mk_isDiag_iff,Sym2.ind,Equiv.subtypeEquivRight,Nat.card_congrhave pair_not_diag₁ : ∀ β : B₁, ¬ (pair₁ β).IsDiag := by intro β rw [Sym2.mk_isDiag_iff] intro h have := D₁.block_inj β h revert this decide have pair_not_diag₂ : ∀ β : B₂, ¬ (pair₂ β).IsDiag := by intro β rw [Sym2.mk_isDiag_iff] intro h have := D₂.block_inj β h revert this decide have card_fib₁ : ∀ (p : Sym2 X₁), ¬ p.IsDiag → Nat.card { β : B₁ // pair₁ β = p } = lam := by intro p hp induction' p using Sym2.ind with x y rw [Sym2.mk_isDiag_iff] at hp have heq : { β : B₁ // pair₁ β = s(x, y) } ≃ { β : B₁ // (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y } := Equiv.subtypeEquivRight (fun β => h_fib_eq₁ β x y hp) rw [Nat.card_congr heq] exact D₁.balance hp have card_fib₂ : ∀ (p : Sym2 X₂), ¬ p.IsDiag → Nat.card { β : B₂ // pair₂ β = p } = lam := by intro p hp induction' p using Sym2.ind with x y rw [Sym2.mk_isDiag_iff] at hp have heq : { β : B₂ // pair₂ β = s(x, y) } ≃ { β : B₂ // (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y } := Equiv.subtypeEquivRight (fun β => h_fib_eq₂ β x y hp) rw [Nat.card_congr heq] exact D₂.balance hp
The point bijection f induces an equivalence on non-diagonal unordered pairs, and corresponding fibers are isomorphic.
The bijection f maps unordered pairs via Sym2.map, preserving non-diagonality by Sym2.ind and Sym2.mk_isDiag_iff, which yields an equivalence pair_equiv on non-diagonal pairs using Subtype.ext. Since every non-diagonal pair has fiber size λ in both designs, Finite.card_eq.mp provides a bijection between the fibers over corresponding pairs.
uses
Sym2.map,Sym2.ind,Sym2.mk_isDiag_iff,Subtype.ext,Finite.card_eq.mplet sym2_f : Sym2 X₁ ≃ Sym2 X₂ := { toFun := Sym2.map f invFun := Sym2.map f.symm left_inv := fun p => by induction' p using Sym2.ind with x y; simp right_inv := fun p => by induction' p using Sym2.ind with x y; simp } have sym2_f_isDiag : ∀ p : Sym2 X₁, (sym2_f p).IsDiag ↔ p.IsDiag := by intro p induction' p using Sym2.ind with x y simp [sym2_f, Sym2.mk_isDiag_iff] have sym2_f_symm_isDiag : ∀ p : Sym2 X₂, (sym2_f.symm p).IsDiag ↔ p.IsDiag := by intro p have := sym2_f_isDiag (sym2_f.symm p) rw [sym2_f.apply_symm_apply] at this exact this.symm let pair_equiv : { p : Sym2 X₁ // ¬ p.IsDiag } ≃ { p : Sym2 X₂ // ¬ p.IsDiag } := { toFun := fun ⟨p, hp⟩ => ⟨sym2_f p, by rwa [sym2_f_isDiag]⟩ invFun := fun ⟨p, hp⟩ => ⟨sym2_f.symm p, by rwa [sym2_f_symm_isDiag]⟩ left_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.symm_apply_apply p) right_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.apply_symm_apply p) } have fib_iso : ∀ P : { p : Sym2 X₁ // ¬ p.IsDiag }, Nonempty ({ β : B₁ // pair₁ β = P.1 } ≃ { β : B₂ // pair₂ β = (pair_equiv P).1 }) := by intro P apply Finite.card_eq.mp rw [card_fib₁ P.1 P.2, card_fib₂ (pair_equiv P).1 (pair_equiv P).2]
Gluing the fiber bijections over all non-diagonal pairs gives a bijection g between the block sets for k = 2.
Decomposing each block set into a dependent sum over non-diagonal pairs yields equivalences e₁ and e₂. Combining the pair equivalence with the fiberwise isomorphisms using Equiv.sigmaCongr gives an equivalence of sigma types, which with e₁ and the inverse of e₂ yields a bijection g between block sets.
uses
Equiv.sigmaCongrlet e₁ : B₁ ≃ (P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 } := { toFun := fun β => ⟨⟨pair₁ β, pair_not_diag₁ β⟩, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by dsimp at hβ subst hβ rfl } let e₂ : B₂ ≃ (P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 } := { toFun := fun β => ⟨⟨pair₂ β, pair_not_diag₂ β⟩, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by dsimp at hβ subst hβ rfl } let e_sigma : ((P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 }) ≃ ((P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 }) := Equiv.sigmaCongr pair_equiv (fun P => (fib_iso P).some) let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm)
The bijections f and g form a design isomorphism for k = 2.
The construction of g ensures that the pair of block g(β) is the image under f of the pair of block β using congr_arg and Subtype.val. Applying bibd_fin2_exists_iff reduces block incidence to membership in the 2-element set, which transfers across f by bibd_sym2_mem_iff_f.
uses
congr_arg,Subtype.val,bibd_fin2_exists_iff,bibd_sym2_mem_iff_fhave hg_pair : ∀ β : B₁, pair₂ (g β) = sym2_f (pair₁ β) := by intro β have this1 : (e_sigma (e₁ β)).1 = pair_equiv ⟨pair₁ β, pair_not_diag₁ β⟩ := rfl have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1 rw [e₂.apply_symm_apply] have := he2.trans this1 exact congr_arg Subtype.val this refine ⟨f, g, fun β x => ?_⟩ have hp : pair₂ (g β) = s(f (D₁.block_pts β j0), f (D₁.block_pts β j1)) := by rw [hg_pair β] rfl rw [bibd_fin2_exists_iff, bibd_fin2_exists_iff] exact (bibd_sym2_mem_iff_f f (D₁.block_pts β j0) (D₁.block_pts β j1) x (D₂.block_pts (g β) j0) (D₂.block_pts (g β) j1) hp).symm
If two designs have isomorphic block-clique graphs, they are isomorphic as designs for every block size k.
We split into cases on the block size k. When k is 0, 1, or 2, the designs are isomorphic by bibd_isomorphic_of_k_zero, bibd_isomorphic_of_k_one, and bibd_isomorphic_of_k_two respectively, whose proofs do not need the graph isomorphism. When k ≥ 3, the result follows from bibd_isomorphic_of_block_clique_graph_iso_of_three_le using the assumed graph isomorphism.
uses
bibd_isomorphic_of_k_zero,bibd_isomorphic_of_k_one,bibd_isomorphic_of_k_two,bibd_isomorphic_of_block_clique_graph_iso_of_three_lercases k with _ | _ | _ | k · exact bibd_isomorphic_of_k_zero D₁ D₂ · exact bibd_isomorphic_of_k_one D₁ D₂ · exact bibd_isomorphic_of_k_two D₁ D₂ · exact bibd_isomorphic_of_block_clique_graph_iso_of_three_le D₁ D₂ (by omega) h
Nat.finite_of_card_ne_zero- A type with non-zero cardinality is finite.
Finite.card_eq.mp- Two finite types with equal cardinality admit a bijection between them.
Fin.elim0- An element of the empty type Fin 0 produces a value in any type by vacuous elimination.
Nat.zero_lt_one- Zero is strictly less than one.
Equiv.subtypeEquivRight- Subtypes defined by logically equivalent predicates on the same domain are naturally equivalent.
Subsingleton.elim- Any two terms of a subsingleton type are equal.
Nat.card_congr- Equivalent types have the same cardinality.
Equiv.sigmaCongr- An equivalence between index types together with fiberwise equivalences yields an equivalence of sigma types.
congr_arg- Equal arguments applied to a function yield equal results.
Sym2.eq_iff- Two unordered pairs are equal if and only if their elements match in the same or opposite order.
EmbeddingLike.apply_eq_iff_eq- Applying an injective map preserves and reflects equality.
or_comm- Disjunction is commutative.
Sym2.mk_isDiag_iff- An unordered pair lies on the diagonal if and only if its two coordinates are equal.
Sym2.ind- Any property of unordered pairs holds if it holds for all canonical representatives s(x, y).
Sym2.map- Functorial action mapping a function over an unordered pair.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Subtype.val- The projection that extracts the underlying value from a subtype.
bibd_fin2_exists_iff- An element lies in the range of a function on Fin 2 if and only if it equals the value at index 0 or index 1.
bibd_sym2_mem_iff_f- Given equality of unordered pairs under a bijection f, membership in the target pair corresponds to membership in the source pair.
bibd_isomorphic_of_k_zero- Any two balanced incomplete block designs with block size 0 on finite block sets and matching parameters are isomorphic.
bibd_isomorphic_of_k_one- Any two balanced incomplete block designs with block size 1 on finite block sets and matching parameters are isomorphic.
bibd_isomorphic_of_k_two- Any two balanced incomplete block designs with block size 2 on finite block sets and matching parameters are isomorphic.
bibd_isomorphic_of_block_clique_graph_iso_of_three_le- Two balanced incomplete block designs with block size at least 3 and isomorphic block-clique graphs are isomorphic.
- Unresolved check: no step explains line(s) 106 -- every tactic of the proof has to belong to some step
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Classicaltheorem bibd_isomorphic_of_k_zero {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂] {v b r lam : ℕ} (D₁ : BIBD X₁ B₁ v b r 0 lam) (D₂ : BIBD X₂ B₂ v b r 0 lam) : bibd_isomorphic D₁ D₂ := by have hv : v ≠ 0 := by have := D₁.incomplete omega have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv) have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv) have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points]) have hB : Nonempty (B₁ ≃ B₂) := Finite.card_eq.mp (by rw [D₁.card_blocks, D₂.card_blocks]) rcases hX with ⟨f⟩ rcases hB with ⟨g⟩ refine ⟨f, g, fun b₁ x => ?_⟩ constructor · rintro ⟨j, _⟩; exact Fin.elim0 j · rintro ⟨j', _⟩; exact Fin.elim0 j'theorem bibd_isomorphic_of_k_one {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂] {v b r lam : ℕ} (D₁ : BIBD X₁ B₁ v b r 1 lam) (D₂ : BIBD X₂ B₂ v b r 1 lam) : bibd_isomorphic D₁ D₂ := by have hv : v ≠ 0 := by have := D₁.incomplete omega have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv) have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv) have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points]) rcases hX with ⟨f⟩ let j0 : Fin 1 := ⟨0, Nat.zero_lt_one⟩ let pt₁ : B₁ → X₁ := fun β => D₁.block_pts β j0 let pt₂ : B₂ → X₂ := fun β => D₂.block_pts β j0 have h_fib₁ : ∀ x : X₁, Nat.card { β : B₁ // pt₁ β = x } = r := by intro x have hr := D₁.replication x have heq : { β : B₁ // pt₁ β = x } ≃ { β : B₁ // ∃ j, D₁.block_pts β j = x } := Equiv.subtypeEquivRight (fun β => by constructor · intro h; exact ⟨j0, h⟩ · rintro ⟨j, hj⟩ have : j = j0 := Subsingleton.elim j j0 subst this exact hj) rw [Nat.card_congr heq] exact hr have h_fib₂ : ∀ y : X₂, Nat.card { β : B₂ // pt₂ β = y } = r := by intro y have hr := D₂.replication y have heq : { β : B₂ // pt₂ β = y } ≃ { β : B₂ // ∃ j, D₂.block_pts β j = y } := Equiv.subtypeEquivRight (fun β => by constructor · intro h; exact ⟨j0, h⟩ · rintro ⟨j, hj⟩ have : j = j0 := Subsingleton.elim j j0 subst this exact hj) rw [Nat.card_congr heq] exact hr have h_fib_iso : ∀ x : X₁, Nonempty ({ β : B₁ // pt₁ β = x } ≃ { β : B₂ // pt₂ β = f x }) := by intro x exact Finite.card_eq.mp (by rw [h_fib₁, h_fib₂]) let e₁ : B₁ ≃ (x : X₁) × { β : B₁ // pt₁ β = x } := { toFun := fun β => ⟨pt₁ β, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨x, β, hβ⟩ => by dsimp subst hβ rfl } let e₂ : B₂ ≃ (y : X₂) × { β : B₂ // pt₂ β = y } := { toFun := fun β => ⟨pt₂ β, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨y, β, hβ⟩ => by dsimp subst hβ rfl } let e_sigma : ((x : X₁) × { β : B₁ // pt₁ β = x }) ≃ ((y : X₂) × { β : B₂ // pt₂ β = y }) := Equiv.sigmaCongr f (fun x => (h_fib_iso x).some) let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm) refine ⟨f, g, fun β x => ?_⟩ have hg_pt : pt₂ (g β) = f (pt₁ β) := by have this1 : (e_sigma (e₁ β)).1 = f (pt₁ β) := rfl have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1 rw [e₂.apply_symm_apply] exact he2.trans this1 constructor · rintro ⟨j, hj⟩ have hj0 : j = j0 := Subsingleton.elim j j0 subst hj0 refine ⟨j0, ?_⟩ change pt₂ (g β) = f x rw [hg_pt] exact congr_arg f hj · rintro ⟨j', hj'⟩ have hj0 : j' = j0 := Subsingleton.elim j' j0 subst hj0 refine ⟨j0, ?_⟩ change pt₁ β = x change pt₂ (g β) = f x at hj' rw [hg_pt] at hj' exact f.injective hj'theorem bibd_fin2_exists_iff {α : Type*} (p : Fin 2 → α) (x : α) : (∃ j, p j = x) ↔ p ⟨0, by omega⟩ = x ∨ p ⟨1, by omega⟩ = x := by let j0 : Fin 2 := ⟨0, by omega⟩ let j1 : Fin 2 := ⟨1, by omega⟩ have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by intro ⟨val, hval⟩ interval_cases val · left; rfl · right; rfl constructor · rintro ⟨j, hjx⟩ rcases hj j with rfl | rfl · left; exact hjx · right; exact hjx · rintro (h | h) · exact ⟨j0, h⟩ · exact ⟨j1, h⟩theorem bibd_sym2_mem_iff_f {α β : Type*} (f : α ≃ β) (a₁ b₁ x : α) (a₂ b₂ : β) (h : s(a₂, b₂) = s(f a₁, f b₁)) : (a₂ = f x ∨ b₂ = f x) ↔ (a₁ = x ∨ b₁ = x) := by simp only [Sym2.eq_iff] at h rcases h with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · simp only [EmbeddingLike.apply_eq_iff_eq] · simp only [EmbeddingLike.apply_eq_iff_eq, or_comm]theorem bibd_isomorphic_of_k_two {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂] {v b r lam : ℕ} (D₁ : BIBD X₁ B₁ v b r 2 lam) (D₂ : BIBD X₂ B₂ v b r 2 lam) : bibd_isomorphic D₁ D₂ := by have hv : v ≠ 0 := by have := D₁.incomplete omega have fx1 : Finite X₁ := Nat.finite_of_card_ne_zero (by rw [D₁.card_points]; exact hv) have fx2 : Finite X₂ := Nat.finite_of_card_ne_zero (by rw [D₂.card_points]; exact hv) have hX : Nonempty (X₁ ≃ X₂) := Finite.card_eq.mp (by rw [D₁.card_points, D₂.card_points]) rcases hX with ⟨f⟩ let j0 : Fin 2 := ⟨0, by omega⟩ let j1 : Fin 2 := ⟨1, by omega⟩ let pair₁ : B₁ → Sym2 X₁ := fun β => s(D₁.block_pts β j0, D₁.block_pts β j1) let pair₂ : B₂ → Sym2 X₂ := fun β => s(D₂.block_pts β j0, D₂.block_pts β j1) have hj : ∀ j : Fin 2, j = j0 ∨ j = j1 := by intro ⟨val, hval⟩ interval_cases val · left; rfl · right; rfl have h_fib_eq₁ : ∀ (β : B₁) (x y : X₁), x ≠ y → (pair₁ β = s(x, y) ↔ (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y) := by intro β x y hxy simp only [pair₁, Sym2.eq_iff] constructor · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩) · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩ · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩ · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩ rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl · subst hjx hj'y; exact (hxy rfl).elim · left; exact ⟨hjx, hj'y⟩ · right; exact ⟨hj'y, hjx⟩ · subst hjx hj'y; exact (hxy rfl).elim have h_fib_eq₂ : ∀ (β : B₂) (x y : X₂), x ≠ y → (pair₂ β = s(x, y) ↔ (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y) := by intro β x y hxy simp only [pair₂, Sym2.eq_iff] constructor · rintro (⟨h0, h1⟩ | ⟨h0, h1⟩) · refine ⟨⟨j0, h0⟩, ⟨j1, h1⟩⟩ · refine ⟨⟨j1, h1⟩, ⟨j0, h0⟩⟩ · rintro ⟨⟨j, hjx⟩, ⟨j', hj'y⟩⟩ rcases hj j with rfl | rfl <;> rcases hj j' with rfl | rfl · subst hjx hj'y; exact (hxy rfl).elim · left; exact ⟨hjx, hj'y⟩ · right; exact ⟨hj'y, hjx⟩ · subst hjx hj'y; exact (hxy rfl).elim have pair_not_diag₁ : ∀ β : B₁, ¬ (pair₁ β).IsDiag := by intro β rw [Sym2.mk_isDiag_iff] intro h have := D₁.block_inj β h revert this decide have pair_not_diag₂ : ∀ β : B₂, ¬ (pair₂ β).IsDiag := by intro β rw [Sym2.mk_isDiag_iff] intro h have := D₂.block_inj β h revert this decide have card_fib₁ : ∀ (p : Sym2 X₁), ¬ p.IsDiag → Nat.card { β : B₁ // pair₁ β = p } = lam := by intro p hp induction' p using Sym2.ind with x y rw [Sym2.mk_isDiag_iff] at hp have heq : { β : B₁ // pair₁ β = s(x, y) } ≃ { β : B₁ // (∃ j, D₁.block_pts β j = x) ∧ ∃ j', D₁.block_pts β j' = y } := Equiv.subtypeEquivRight (fun β => h_fib_eq₁ β x y hp) rw [Nat.card_congr heq] exact D₁.balance hp have card_fib₂ : ∀ (p : Sym2 X₂), ¬ p.IsDiag → Nat.card { β : B₂ // pair₂ β = p } = lam := by intro p hp induction' p using Sym2.ind with x y rw [Sym2.mk_isDiag_iff] at hp have heq : { β : B₂ // pair₂ β = s(x, y) } ≃ { β : B₂ // (∃ j, D₂.block_pts β j = x) ∧ ∃ j', D₂.block_pts β j' = y } := Equiv.subtypeEquivRight (fun β => h_fib_eq₂ β x y hp) rw [Nat.card_congr heq] exact D₂.balance hp let sym2_f : Sym2 X₁ ≃ Sym2 X₂ := { toFun := Sym2.map f invFun := Sym2.map f.symm left_inv := fun p => by induction' p using Sym2.ind with x y; simp right_inv := fun p => by induction' p using Sym2.ind with x y; simp } have sym2_f_isDiag : ∀ p : Sym2 X₁, (sym2_f p).IsDiag ↔ p.IsDiag := by intro p induction' p using Sym2.ind with x y simp [sym2_f, Sym2.mk_isDiag_iff] have sym2_f_symm_isDiag : ∀ p : Sym2 X₂, (sym2_f.symm p).IsDiag ↔ p.IsDiag := by intro p have := sym2_f_isDiag (sym2_f.symm p) rw [sym2_f.apply_symm_apply] at this exact this.symm let pair_equiv : { p : Sym2 X₁ // ¬ p.IsDiag } ≃ { p : Sym2 X₂ // ¬ p.IsDiag } := { toFun := fun ⟨p, hp⟩ => ⟨sym2_f p, by rwa [sym2_f_isDiag]⟩ invFun := fun ⟨p, hp⟩ => ⟨sym2_f.symm p, by rwa [sym2_f_symm_isDiag]⟩ left_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.symm_apply_apply p) right_inv := fun ⟨p, hp⟩ => Subtype.ext (sym2_f.apply_symm_apply p) } have fib_iso : ∀ P : { p : Sym2 X₁ // ¬ p.IsDiag }, Nonempty ({ β : B₁ // pair₁ β = P.1 } ≃ { β : B₂ // pair₂ β = (pair_equiv P).1 }) := by intro P apply Finite.card_eq.mp rw [card_fib₁ P.1 P.2, card_fib₂ (pair_equiv P).1 (pair_equiv P).2] let e₁ : B₁ ≃ (P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 } := { toFun := fun β => ⟨⟨pair₁ β, pair_not_diag₁ β⟩, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by dsimp at hβ subst hβ rfl } let e₂ : B₂ ≃ (P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 } := { toFun := fun β => ⟨⟨pair₂ β, pair_not_diag₂ β⟩, ⟨β, rfl⟩⟩ invFun := fun p => p.2.1 left_inv := fun β => rfl right_inv := fun ⟨⟨p, hp⟩, ⟨β, hβ⟩⟩ => by dsimp at hβ subst hβ rfl } let e_sigma : ((P : { p : Sym2 X₁ // ¬ p.IsDiag }) × { β : B₁ // pair₁ β = P.1 }) ≃ ((P : { p : Sym2 X₂ // ¬ p.IsDiag }) × { β : B₂ // pair₂ β = P.1 }) := Equiv.sigmaCongr pair_equiv (fun P => (fib_iso P).some) let g : B₁ ≃ B₂ := e₁.trans (e_sigma.trans e₂.symm) have hg_pair : ∀ β : B₁, pair₂ (g β) = sym2_f (pair₁ β) := by intro β have this1 : (e_sigma (e₁ β)).1 = pair_equiv ⟨pair₁ β, pair_not_diag₁ β⟩ := rfl have he2 : (e₂ (g β)).1 = (e_sigma (e₁ β)).1 := by change (e₂ (e₂.symm (e_sigma (e₁ β)))).1 = (e_sigma (e₁ β)).1 rw [e₂.apply_symm_apply] have := he2.trans this1 exact congr_arg Subtype.val this refine ⟨f, g, fun β x => ?_⟩ have hp : pair₂ (g β) = s(f (D₁.block_pts β j0), f (D₁.block_pts β j1)) := by rw [hg_pair β] rfl rw [bibd_fin2_exists_iff, bibd_fin2_exists_iff] exact (bibd_sym2_mem_iff_f f (D₁.block_pts β j0) (D₁.block_pts β j1) x (D₂.block_pts (g β) j0) (D₂.block_pts (g β) j1) hp).symmtheorem bibd_isomorphic_of_block_clique_graph_iso {X₁ B₁ X₂ B₂ : Type*} [Finite B₁] [Finite B₂] {v b r k lam : ℕ} (D₁ : BIBD X₁ B₁ v b r k lam) (D₂ : BIBD X₂ B₂ v b r k lam) (h : Nonempty (bibd_block_clique_graph D₁ ≃g bibd_block_clique_graph D₂)) : bibd_isomorphic D₁ D₂ := by rcases k with _ | _ | _ | k · exact bibd_isomorphic_of_k_zero D₁ D₂ · exact bibd_isomorphic_of_k_one D₁ D₂ · exact bibd_isomorphic_of_k_two D₁ D₂ · exact bibd_isomorphic_of_block_clique_graph_iso_of_three_le D₁ D₂ (by omega) h