AFTD Auto-Formalizing Theoretical Domains

mdfrbf_compression_card

theoremverified

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

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`.

  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.

    lines 4–5

    uses Fintype.card_coe, Finset.card_sdiff, Finset.card_univ, Fintype.card_fin, Finset.inter_univ

      rw [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

/-- 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]
See it in the graphDiscuss this resultChallenge it