/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ import FormalConjecturesUtil

Optimal monotone families for the discrete isoperimetric inequality

References:

namespace Mathoverflow10799 open Finset Real

Start with a set $X={1,2,...,n}$ of $n$ elements and the family $2^X$ of all subsets of $X$. For a real number $p$ between zero and one, we consider a probability distribution $\mu_p$ on $2^X$ where the probability that $i \in S$ is $p$, independently for different $i$'s. Thus for $p=1/2$ we get the uniform probability distribution.

For $S \subseteq {0, \ldots, n-1}$, its probability is $p^{|S|} (1-p)^{n - |S|}$.

noncomputable def μ {n : } (p : ) (S : Finset (Fin n)) : := p ^ #S * (1 - p) ^ (n - #S)

For $p = 1/2$, the $p$-biased measure is the uniform distribution: $\mu_{1/2}(S) = (1/2)^n$ for every $S \subseteq [n]$.

@[category test, AMS 5] theorem μ_half_eq_uniform {n : } (S : Finset (Fin n)) : μ (1/2) S = (1/2 : ) ^ n := n:S:Finset (Fin n)μ (1 / 2) S = (1 / 2) ^ n n:S:Finset (Fin n)h:#S n := LE.le.trans_eq (card_le_univ S) (Fintype.card_fin n)μ (1 / 2) S = (1 / 2) ^ n n:S:Finset (Fin n)h:#S n := LE.le.trans_eq (card_le_univ S) (Fintype.card_fin n)(1 / 2) ^ #S * (1 - 1 / 2) ^ (n - #S) = (1 / 2) ^ n All goals completed! 🐙

The $p$-biased measure of a family $\mathcal F \subseteq 2^{[n]}$, i.e. $\mu_p(\mathcal F) = \sum_{S \in \mathcal F} \mu_p(S)$.

noncomputable def μFamily {n : } (p : ) (F : Finset (Finset (Fin n))) : := S F, μ p S

Given a family $F$, for a subset $S$ of $X$, we write $h(S)$ as the number of subsets $T$ in $X$ such that (1) $T$ differs from $S$ in exactly one element (2) Exactly one set among $S$ and $T$ belongs to $F$.

def boundaryCount (n : ) (F : Finset (Finset (Fin n))) (S : Finset (Fin n)) : := (Finset.univ.filter fun i : Fin n Xor' (S F) (symmDiff S {i} F)).card

Test lemma showing that boundaryCount is equivalent to counting subsets $T$ that differ from $S$ in exactly one element and exactly one of $S, T$ belongs to $F$.

@[category test, AMS 5] theorem boundaryCount_equiv (n : ) (F : Finset (Finset (Fin n))) (S : Finset (Fin n)) : boundaryCount n F S = (Finset.univ.filter fun T : Finset (Fin n) (symmDiff S T).card = 1 Xor' (S F) (T F)).card := n:F:Finset (Finset (Fin n))S:Finset (Fin n)boundaryCount n F S = #{T | #(symmDiff S T) = 1 Xor' (S F) (T F)} n:F:Finset (Finset (Fin n))S:Finset (Fin n)#{i | Xor' (S F) (symmDiff S {i} F)} = #{T | #(symmDiff S T) = 1 Xor' (S F) (T F)} have h_cancel : (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := n:F:Finset (Finset (Fin n))S:Finset (Fin n)boundaryCount n F S = #{T | #(symmDiff S T) = 1 Xor' (S F) (T F)} n:F:Finset (Finset (Fin n))S:Finset (Fin n)A:Finset (Fin n)symmDiff S (symmDiff S A) = A n:F:Finset (Finset (Fin n))S:Finset (Fin n)A:Finset (Fin n)x:Fin nx symmDiff S (symmDiff S A) x A n:F:Finset (Finset (Fin n))S:Finset (Fin n)A:Finset (Fin n)x:Fin nx S ¬(x S x A x A x S) (x S x A x A x S) x S x A All goals completed! 🐙 have h_inj : Function.Injective (fun i : Fin n => symmDiff S {i}) := n:F:Finset (Finset (Fin n))S:Finset (Fin n)boundaryCount n F S = #{T | #(symmDiff S T) = 1 Xor' (S F) (T F)} intro i n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }i:Fin nj:Fin n(fun i => symmDiff S {i}) i = (fun i => symmDiff S {i}) j i = j n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }i:Fin nj:Fin nhij:(fun i => symmDiff S {i}) i = (fun i => symmDiff S {i}) ji = j n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }i:Fin nj:Fin nhij:symmDiff S {i} = symmDiff S {j}i = j have h1 : symmDiff S (symmDiff S {i}) = symmDiff S (symmDiff S {j}) := n:F:Finset (Finset (Fin n))S:Finset (Fin n)boundaryCount n F S = #{T | #(symmDiff S T) = 1 Xor' (S F) (T F)} All goals completed! 🐙 n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }i:Fin nj:Fin nhij:symmDiff S {i} = symmDiff S {j}h1:{i} = {j}i = j All goals completed! 🐙 n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))#(map { toFun := fun i => symmDiff S {i}, inj' := h_inj } {i | Xor' (S F) (symmDiff S {i} F)}) = #{T | #(symmDiff S T) = 1 Xor' (S F) (T F)} n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))map { toFun := fun i => symmDiff S {i}, inj' := h_inj } {i | Xor' (S F) (symmDiff S {i} F)} = {T | #(symmDiff S T) = 1 Xor' (S F) (T F)} n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)T map { toFun := fun i => symmDiff S {i}, inj' := h_inj } {i | Xor' (S F) (symmDiff S {i} F)} T {T | #(symmDiff S T) = 1 Xor' (S F) (T F)} n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)(∃ a, Xor' (S F) (symmDiff S {a} F) symmDiff S {a} = T) #(symmDiff S T) = 1 Xor' (S F) (T F) n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)(∃ a, Xor' (S F) (symmDiff S {a} F) symmDiff S {a} = T) #(symmDiff S T) = 1 Xor' (S F) (T F)n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)#(symmDiff S T) = 1 Xor' (S F) (T F) a, Xor' (S F) (symmDiff S {a} F) symmDiff S {a} = T n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)(∃ a, Xor' (S F) (symmDiff S {a} F) symmDiff S {a} = T) #(symmDiff S T) = 1 Xor' (S F) (T F) n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))i:Fin nhi:Xor' (S F) (symmDiff S {i} F)#(symmDiff S (symmDiff S {i})) = 1 Xor' (S F) (symmDiff S {i} F) n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))i:Fin nhi:Xor' (S F) (symmDiff S {i} F)#(symmDiff S (symmDiff S {i})) = 1 n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))i:Fin nhi:Xor' (S F) (symmDiff S {i} F)#{i} = 1 All goals completed! 🐙 n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)#(symmDiff S T) = 1 Xor' (S F) (T F) a, Xor' (S F) (symmDiff S {a} F) symmDiff S {a} = T n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)hcard:#(symmDiff S T) = 1hxor:Xor' (S F) (T F) a, Xor' (S F) (symmDiff S {a} F) symmDiff S {a} = T n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)hcard:#(symmDiff S T) = 1hxor:Xor' (S F) (T F)i:Fin nhi:symmDiff S T = {i} a, Xor' (S F) (symmDiff S {a} F) symmDiff S {a} = T have hT : T = symmDiff S {i} := n:F:Finset (Finset (Fin n))S:Finset (Fin n)boundaryCount n F S = #{T | #(symmDiff S T) = 1 Xor' (S F) (T F)} All goals completed! 🐙 n:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)hcard:#(symmDiff S T) = 1hxor:Xor' (S F) (T F)i:Fin nhi:symmDiff S T = {i}hT:T = symmDiff S {i} := Eq.mpr (id (congrArg (fun _a => T = symmDiff S _a) (Eq.symm hi))) (Eq.mpr (id (congrArg (fun _a => T = _a) (h_cancel T))) (Eq.refl T))Xor' (S F) (symmDiff S {i} F) rwa [hTn:F:Finset (Finset (Fin n))S:Finset (Fin n)h_cancel: (A : Finset (Fin n)), symmDiff S (symmDiff S A) = A := fun A => ext fun x => Eq.mpr (id (congrArg (fun x_1 => x_1 x A) (Eq.trans boundaryCount_equiv._simp_1 (congr (congrArg (fun x_1 => Or (x S ¬x_1)) boundaryCount_equiv._simp_1) (congrArg (fun x_1 => x_1 x S) boundaryCount_equiv._simp_1))))) { mp := fun a => Or.casesOn a (fun h => And.casesOn h fun left right => And.casesOn (not_or.mp right) fun left_1 right => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp left_1) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h left)) fun h_1 => False.elim (h left)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp right) (fun h_1 => False.elim (h h_1)) fun h_1 => Decidable.of_not_not h) fun h => And.casesOn h fun left right => Or.casesOn left (fun h => And.casesOn h fun left right_1 => False.elim (right left)) fun h => And.casesOn h fun left right => left, mpr := fun a => or_iff_not_imp_left.mpr fun a_1 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => or_iff_not_imp_left.mpr fun a_2 => a, h) fun h => or_iff_not_imp_left.mpr fun a_2 => a, fun a => Or.casesOn (Decidable.of_not_not h) (fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 left)) fun h_1 => And.casesOn h fun left right => False.elim (h_1 right)) fun h => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_2) (fun h_1 => And.casesOn h fun left right => False.elim (h_1 a)) fun h_1 => And.casesOn h fun left right => False.elim (right a), fun a_2 => Or.casesOn (Decidable.not_and_iff_not_or_not'.mp a_1) (fun h => False.elim (h a_2)) fun h => Or.casesOn (Decidable.of_not_not h) (fun h => And.casesOn h fun left right => False.elim (right a)) fun h => And.casesOn h fun left right => False.elim (right a_2) }h_inj:Function.Injective fun i => symmDiff S {i} := fun i j hij => have h1 := Eq.mpr (id (congrArg (fun _a => symmDiff S _a = symmDiff S (symmDiff S {j})) hij)) (Eq.refl (symmDiff S (symmDiff S {j}))); singleton_injective (Eq.mp (congrArg (fun _a => {i} = _a) (h_cancel {j})) (Eq.mp (congrArg (fun _a => _a = symmDiff S (symmDiff S {j})) (h_cancel {i})) h1))T:Finset (Fin n)hcard:#(symmDiff S T) = 1i:Fin nhxor:Xor' (S F) (symmDiff S {i} F)hi:symmDiff S T = {i}hT:T = symmDiff S {i}Xor' (S F) (symmDiff S {i} F) at hxor

The edge-boundary of $F$ is the expectation of $h(S)$ (according to $\mu_p$) over all subsets $S$ of $X$. It is denoted by $I^p(F)$.

noncomputable def edgeBoundary (n : ) (p : ) (F : Finset (Finset (Fin n))) : := S : Finset (Fin n), μ p S * boundaryCount n F S

A family $F$ of subsets of $2^X$ is monotone increasing if when $S$ belongs to $F$ and $T$ contains $S$ then $T$ also belongs to $F$. (Monotone increasing families also also called "filtes" and "up-families".) From now on we will restrict our attention to the case of monotone increasing families.

This is Mathlib's IsUpperSet applied to the coercion of $\mathcal F$ to a set, using the fact that on Finset is .

abbrev IsMonotoneIncreasing {n : } (F : Finset (Finset (Fin n))) : Prop := IsUpperSet (F : Set (Finset (Fin n)))

We say that a family is optimal for $\mu_p$ if the isoperimetric inequality (IR) is sharp up to a multiplicative constant $1000 \log (1/p)$.

Since the lower bound from (IR) is $$\frac{\mu_p(\mathcal F) \cdot \log(1/\mu_p(\mathcal F))}{p \cdot \log(1/p)},$$ multiplying by $1000 \log(1/p)$ gives the condition $$I^p(\mathcal F) \le \frac{1000}{p} \cdot \mu_p(\mathcal F) \cdot \log \frac{1}{\mu_p(\mathcal F)}.$$

noncomputable def IsOptimal {n : } (p : ) (F : Finset (Finset (Fin n))) : Prop := let m := μFamily p F edgeBoundary n p F 1000 * Real.log (1 / p) * (m * Real.logb p m / p)

Problem: For every monotone increasing family $F$, given an interval $[s,t]$ of real numbers so that $t/s > 1000 \log n$ we have some $p$ in the interval $[s,t]$ so that $F$ is optimal with respect to $\mu_p$.

This was a "missing lemma" in the work of Kahn and Kalai on threshold behavior of monotone properties. The related Kahn–Kalai conjecture was settled by Park and Pham.

This conjecture is false without the additional assumption $\mu_t(F) = 1/2$. A counterexample was found by Shlomo Perles (April 7, 2026).

@[category research solved, AMS 5 60, formal_proof using formal_conjectures at "https://github.com/mo271/formal-conjectures/blob/408f53dc0856c0882a5e77acd24fc83b978f0bc9/FormalConjectures/Mathoverflow/10799.lean#L252"] theorem declaration uses 'sorry'mathoverflow_10799 : answer(False) (n : ) (_ : 2 n) (F : Finset (Finset (Fin n))) (_ : IsMonotoneIncreasing F) (s t : ) (_ : 0 < s) (_ : s t) (_ : t < 1) (_ : t / s > 1000 * Real.log n), p, s p p t IsOptimal p F := False (n : ), 2 n (F : Finset (Finset (Fin n))), IsMonotoneIncreasing F (s t : ), 0 < s s t t < 1 t / s > 1000 * log n p, s p p t IsOptimal p F All goals completed! 🐙

Conjecture 7 from Kahn–Kalai 2006: the same statement as the original conjecture, but with the additional assumption that $t$ is the critical probability for $F$, namely $\mu_t(F) = 1/2$.

@[category research open, AMS 5 60] theorem declaration uses 'sorry'mathoverflow_10799.variants.kahn_kalai_conjecture_7 : answer(sorry) (n : ) (_ : 2 n) (F : Finset (Finset (Fin n))) (_ : IsMonotoneIncreasing F) (s t : ) (_ : 0 < s) (_ : s t) (_ : t < 1) (_ : μFamily t F = 1 / 2) (_ : t / s > 1000 * Real.log n), p, s p p t IsOptimal p F := True (n : ), 2 n (F : Finset (Finset (Fin n))), IsMonotoneIncreasing F (s t : ), 0 < s s t t < 1 μFamily t F = 1 / 2 t / s > 1000 * log n p, s p p t IsOptimal p F All goals completed! 🐙

Weaker version proven by Kahn–Kalai: the same conclusion holds when $1000 \log n$ is replaced by $C_\varepsilon , n^\varepsilon$ for every fixed $\varepsilon > 0$.

@[category research solved, AMS 5 60] theorem declaration uses 'sorry'mathoverflow_10799.variants.weak_kahn_kalai : ε > (0 : ), C > (0 : ), (n : ) (_ : 2 n) (F : Finset (Finset (Fin n))) (_ : IsMonotoneIncreasing F) (s t : ) (_ : 0 < s) (_ : s t) (_ : t < 1) (_ : t / s > C * (n : ) ^ ε), p, s p p t IsOptimal p F := ε > 0, C > 0, (n : ), 2 n (F : Finset (Finset (Fin n))), IsMonotoneIncreasing F (s t : ), 0 < s s t t < 1 t / s > C * n ^ ε p, s p p t IsOptimal p F All goals completed! 🐙

Now a famous isoperimetric relation asserts that (IR) $I^p(F) \ge \frac{1}{p} \mu_p(F) \log_p \mu_p(F)$ This relation is true for every family $F$ and every $p$. It is especially famous and simple when $p=1/2$ and $\mu_p(F)=1/2$. In this case, it says that given a set of half the vertices of the discrete cube $2^X$, the number of edges between $F$ and its complement is at least $2^{n-1}$.

Note on translation: We use Real.logb p m to represent the logarithm base $p$ directly. The factor of $p$ in the denominator (equivalent to $1/p$ in front) is consistent with the definition of IsOptimal used in the counterexample proof.

@[category textbook, AMS 5 60] theorem declaration uses 'sorry'discrete_isoperimetric_inequality (n : ) (p : ) (hp : 0 < p) (hp' : p < 1) (F : Finset (Finset (Fin n))) : let m := μFamily p F edgeBoundary n p F m * Real.logb p m / p := n:p:hp:0 < php':p < 1F:Finset (Finset (Fin n))let m := μFamily p F; edgeBoundary n p F m * logb p m / p All goals completed! 🐙

The $p$-biased measure is a probability distribution: it sums to $1$ over all subsets. This is the binomial identity $(p + (1-p))^n = 1$.

@[category test, AMS 5] theorem μ_sum_eq_one (n : ) (p : ) : S : Finset (Fin n), μ p S = 1 := n:p: S, μ p S = 1 n:p: S, p ^ #S * (1 - p) ^ (n - #S) = 1 n:p:h: s, p ^ #s * (1 - p) ^ (Fintype.card (Fin n) - #s) = (p + (1 - p)) ^ Fintype.card (Fin n) := Fintype.sum_pow_mul_eq_add_pow (Fin n) p (1 - p) S, p ^ #S * (1 - p) ^ (n - #S) = 1 n:p:h: s, p ^ #s * (1 - p) ^ (n - #s) = (p + (1 - p)) ^ n S, p ^ #S * (1 - p) ^ (n - #S) = 1 n:p:h: s, p ^ #s * (1 - p) ^ (n - #s) = (p + (1 - p)) ^ n(p + (1 - p)) ^ n = 1 All goals completed! 🐙

The measure of the full power set is $1$.

@[category test, AMS 5] theorem μFamily_univ (n : ) (p : ) : μFamily p (Finset.univ : Finset (Finset (Fin n))) = 1 := n:p:μFamily p univ = 1 n:p: S, μ p S = 1 All goals completed! 🐙

The boundary count is zero for the empty family (no set is in $\mathcal F$).

@[category test, AMS 5] theorem boundaryCount_empty (n : ) (S : Finset (Fin n)) : boundaryCount n S = 0 := n:S:Finset (Fin n)boundaryCount n S = 0 All goals completed! 🐙

The edge boundary is zero for the empty family.

@[category test, AMS 5] theorem edgeBoundary_empty (n : ) (p : ) : edgeBoundary n p = 0 := n:p:edgeBoundary n p = 0 All goals completed! 🐙

The boundary count is zero for the full family (every set is in $\mathcal F$).

@[category test, AMS 5] theorem boundaryCount_univ (n : ) (S : Finset (Fin n)) : boundaryCount n Finset.univ S = 0 := n:S:Finset (Fin n)boundaryCount n univ S = 0 All goals completed! 🐙

The edge boundary is zero for the full family.

@[category test, AMS 5] theorem edgeBoundary_univ (n : ) (p : ) : edgeBoundary n p Finset.univ = 0 := n:p:edgeBoundary n p univ = 0 All goals completed! 🐙 end Mathoverflow10799