mdfrbf_compression_card
If W is a set of j-1 points of Fin d (j ≥ 2), then the complement of W has exactly d - (j-1) elements, so it can be reindexed by Fin (d - (j-1)).
Statement
theorem mdfrbf_compression_card (j d : ℕ) (hj : 2 ≤ j) (W : Finset (Fin d)) (hW : W.card = j - 1) :
Fintype.card ↥(Finset.univ \ W) = d - (j - 1)- Source
- step towards mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- mixed_diamond_fan_ramsey_bound_all_singletons_fan_coloursCase b ≥ 2 with every singleton fan-coloured: if d ≥ j*a + (j-1)*b + 1 and the statement holds at (a, b-1) in dimension d-(j-1), then χ…
The proof, explained
The proof computes the cardinality of the complement `Finset.univ \\ W` in `Fin d` via a sequence of algebraic rewrites. It converts the subtype cardinality to a finset difference, expands the difference as `|univ| - |W ∩ univ|`, simplifies `|univ|` to `d` and `W ∩ univ` to `W`, and substitutes the given size `|W| = j - 1`.
The subtype corresponding to the complement `univ \\ W` has cardinality `d - (j - 1)`.
We compute the cardinality directly by rewriting: the subtype cardinality `Fintype.card ↥(univ \\ W)` equals the finset cardinality `(univ \\ W).card` (`Fintype.card_coe`). The cardinality of the set difference `univ \\ W` is `univ.card - (W ∩ univ).card` (`Finset.card_sdiff`). The size of the universe of `Fin d` is `Fintype.card (Fin d) = d` (`Finset.card_univ`, `Fintype.card_fin`), and intersecting `W` with `univ` leaves `W` unchanged (`Finset.inter_univ`). Finally, substituting the hypothesis `hW` that `W.card = j - 1` yields `d - (j - 1) = d - (j - 1)`, closing the goal.
uses
Fintype.card_coe,Finset.card_sdiff,Finset.card_univ,Fintype.card_fin,Finset.inter_univrw [Fintype.card_coe, Finset.card_sdiff, Finset.card_univ, Fintype.card_fin, Finset.inter_univ, hW]
Fintype.card_coe- The cardinality of a finset coerced to a subtype equals the cardinality of the finset itself.
Finset.card_sdiff- The cardinality of the difference of two finsets `t \\ s` is `t.card - (s ∩ t).card`.
Finset.card_univ- The cardinality of the universal finset `univ` of a finite type `α` is `Fintype.card α`.
Fintype.card_fin- The cardinality of the standard finite type `Fin n` is `n`.
Finset.inter_univ- The intersection of any finset with the universal finset is the finset itself.
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.
/-- The complement of the compressed block has the cardinality used to reindex Fin (d - (j-1)). -/theorem mdfrbf_compression_card (j d : ℕ) (hj : 2 ≤ j) (W : Finset (Fin d)) (hW : W.card = j - 1) : Fintype.card ↥(Finset.univ \ W) = d - (j - 1) := by rw [Fintype.card_coe, Finset.card_sdiff, Finset.card_univ, Fintype.card_fin, Finset.inter_univ, hW]