gpa_path3_indep
lemmaverified
In the path 0 - 2 - 1, {0, 1} is a maximum independent set.
Statement
open Finset in lemma gpa_path3_indep : gpa_indep gpa_path3 {0, 1} ∧ ∀ S, gpa_indep gpa_path3 S → S.card ≤ ({0, 1} : Finset (Fin 3)).card
- Source
- step towards gpa_eq54_false / gpa_eq54_fails_of_indep (Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Sec. 5.3, Eq. (5.4))
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Used by 2
- gpa_eq54_falseEq. (5.4) in the proof of Theorem 5 (hardness of costly information acquisition) of arXiv:2209.01146 is false: it is not true that for…
- gpa_cube_max_le_one_falseThe auxiliary claim max_{x ∈ [0,1]^k} u*(x) ≤ 1 used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three…
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 Finset in/-- In the path `0 - 2 - 1`, `{0, 1}` is a maximum independent set. -/lemma gpa_path3_indep : gpa_indep gpa_path3 {0, 1} ∧ ∀ S, gpa_indep gpa_path3 S → S.card ≤ ({0, 1} : Finset (Fin 3)).card := by refine ⟨by unfold gpa_indep gpa_path3; decide, ?_⟩ intro S hS have : S ≠ Finset.univ := by rintro rfl exact hS 0 (Finset.mem_univ _) 2 (Finset.mem_univ _) (by unfold gpa_path3; decide) have hlt : S.card < 3 := by have := Finset.card_lt_card (Finset.ssubset_univ_iff.2 this) simpa using this have : ({0, 1} : Finset (Fin 3)).card = 2 := by decide omega