AFTD Auto-Formalizing Theoretical Domains

op_1370_singleton_element_family_bound

theoremverifiedoriginal

For at least three nonempty mutually strongly incomparable families of subsets of an n-element set, if one family consists of the single set {x} for some element x, their total size is at most 2^(n-1)-1. No uncomplementedness assumption is needed.

Statement

theorem op_1370_singleton_element_family_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hi : 𝒜 i = {{x}}) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1
Related work
arXiv:2611.12199, Conjecture 4.3, for a family consisting of a singleton set; the uncomplementedness assumption can be omitted in this case.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • strongly_incomparableAn indexed family of finset families 𝒜 : ι → Finset (Finset α) is strongly incomparable if for all i j : ι with i ≠ j, for all…

Read back from the Lean

For all natural numbers $n$ and $t$, assuming $3 \le t$, let $\mathcal{A}$ be a family of $t$ collections of subsets of $\mathrm{Fin}(n)$ (that is, $\mathcal{A} : \mathrm{Fin}(t) \to \mathrm{Finset}(\mathrm{Finset}(\mathrm{Fin}(n)))$) such that: 1. Every collection $\mathcal{A}(i)$ is nonempty; 2. $\mathcal{A}$ is strongly incomparable: for all $i, j \in \mathrm{Fin}(t)$ with $i \ne j$, no set $A \in \mathcal{A}(i)$ is a subset of any set $B \in \mathcal{A}(j)$; 3. For a given index $i \in \mathrm{Fin}(t)$ and element $x \in \mathrm{Fin}(n)$, $\mathcal{A}(i)$ is the singleton collection containing only the singleton set $\{x\}$ (i.e., $\mathcal{A}(i) = \{\{x\}\}$). Then the total number of sets across all collections $\sum_{j \in \mathrm{Fin}(t)} |\mathcal{A}(j)|$ is at most $2^{n - 1} - 1$.

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

Because the families are strongly incomparable, they are pairwise disjoint, reducing the sum of their sizes to the cardinality of their union. For the singleton family 𝒜ᵢ = {{x}}, every set S in any other family 𝒜ⱼ cannot contain x (lest {x} ⊆ S), cannot be empty (lest ∅ ⊆ {x}), and cannot equal the complement U = [n] \ {x} (because a third family 𝒜ₖ would provide a set D ⊆ U = S, violating incomparability). Therefore, every set in the union other than {x} is a proper, nonempty subset of U. Since |U| = n - 1, there are at most 2^(n-1) - 2 such subsets, and adding {x} gives the upper bound 2^(n-1) - 1.

  1. The families 𝒜ⱼ are pairwise disjoint, so the sum ∑ⱼ |𝒜ⱼ| equals the cardinality of their union |⋃ⱼ 𝒜ⱼ|.

    If two distinct families 𝒜ⱼ₁ and 𝒜ⱼ₂ shared an element A, then A ⊆ A would violate strong incomparability between them. Because the families are pairwise disjoint, the sum of their cardinalities equals the cardinality of their union.

    lines 2–13

    uses disjoint_iff_ne, subset_rfl, Finset.card_biUnion

      open Finset in
      have hdisj : ∀ (j1 j2 : Fin t), j1 ≠ j2 → Disjoint (𝒜 j1) (𝒜 j2) := by
        intro j1 j2 hj
        rw [disjoint_iff_ne]
        intro A hA B hB heq
        subst heq
        exact hinc j1 j2 hj A hA A hB subset_rfl
      have hp : (↑(Finset.univ : Finset (Fin t)) : Set (Fin t)).PairwiseDisjoint 𝒜 :=
        fun j1 _ j2 _ hj => hdisj j1 j2 hj
      have hsum : ∑ j, (𝒜 j).card = (Finset.univ.biUnion 𝒜).card := by
        rw [Finset.card_biUnion hp]
      rw [hsum]
  2. The complement U = [n] \ {x} is nonempty.

    Suppose for contradiction that U is empty, so that the underlying universe consists solely of {x}. Since t ≥ 3, there is an index j ≠ i. Any set B in the nonempty family 𝒜ⱼ cannot contain x (otherwise {x} ⊆ B, contradicting incomparability with 𝒜ᵢ = {{x}}), which forces B ⊆ U = ∅. But then B = ∅ ⊆ {x}, again contradicting incomparability with 𝒜ᵢ. Hence U must be nonempty.

    lines 14–45

    uses Finset.nonempty_iff_ne_empty, not_not, Finset.sdiff_eq_empty_iff_subset, Finset.card_le_card, Finset.card_fin, Finset.card_singleton, Finset.mem_sdiff, Finset.mem_singleton, Finset.singleton_subset_iff.mpr, Finset.mem_singleton_self, Ne.symm, Finset.mem_erase, Finset.mem_univ, Finset.subset_empty, Finset.empty_subset

      set U : Finset (Fin n) := Finset.univ.erase x
      have hU : U.Nonempty := by
        by_contra hU'
        rw [Finset.nonempty_iff_ne_empty, not_not] at hU'
        have hex : ∃ j : Fin t, j ≠ i := by
          have hne' : (Finset.univ \ ({i} : Finset (Fin t))).Nonempty := by
            rw [Finset.nonempty_iff_ne_empty]
            intro h
            have hsub : Finset.univ ⊆ ({i} : Finset (Fin t)) := by
              rw [Finset.sdiff_eq_empty_iff_subset] at h
              exact h
            have hle := Finset.card_le_card hsub
            rw [Finset.card_fin, Finset.card_singleton] at hle
            omega
          rcases hne' with ⟨j, hj⟩
          rw [Finset.mem_sdiff, Finset.mem_singleton] at hj
          exact ⟨j, hj.2⟩
        rcases hex with ⟨j, hij⟩
        rcases hne j with ⟨B, hB⟩
        have hx : x ∉ B := by
          intro hxB
          have hsub : ({x} : Finset (Fin n)) ⊆ B := Finset.singleton_subset_iff.mpr hxB
          have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _
          exact hinc i j (Ne.symm hij) {x} hxmem B hB hsub
        have hBU : B ⊆ U := by
          intro y hy
          rw [Finset.mem_erase]
          exact ⟨fun hyx => hx (hyx ▸ hy), Finset.mem_univ y⟩
        rw [hU', Finset.subset_empty] at hBU
        have hBempty : B ⊆ ({x} : Finset (Fin n)) := by rw [hBU]; exact Finset.empty_subset _
        have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _
        exact hinc j i hij B hB {x} hxmem hBempty
  3. Every set in the union ⋃ⱼ 𝒜ⱼ is either {x} or a proper, nonempty subset of U.

    Let S belong to some family 𝒜ⱼ. If j = i, then S = {x}. If j ≠ i, then x ∉ S (lest {x} ⊆ S violate incomparability with 𝒜ᵢ), so S ⊆ U. Moreover, S ≠ ∅ (lest ∅ ⊆ {x} violate incomparability with 𝒜ᵢ). Finally, S ≠ U: if S = U, then because t ≥ 3 there is a third family 𝒜ₖ with k distinct from both i and j; any set D ∈ 𝒜ₖ satisfies x ∉ D, giving D ⊆ U = S, which violates incomparability between 𝒜ₖ and 𝒜ⱼ. Thus S ∈ 𝒫(U) \ {∅, U}.

    lines 46–97

    uses Finset.mem_biUnion, Finset.mem_singleton, Finset.mem_insert_self, Finset.mem_insert_of_mem, Finset.mem_sdiff, Finset.mem_powerset, Finset.mem_insert, not_or, Finset.singleton_subset_iff.mpr, Finset.mem_singleton_self, Ne.symm, Finset.mem_erase, Finset.mem_univ, Finset.empty_subset, Finset.nonempty_iff_ne_empty, Finset.sdiff_eq_empty_iff_subset, Finset.card_le_card, Finset.card_fin, Finset.card_le_two, singleton_subset_iff.mpr

      have hsub : Finset.univ.biUnion 𝒜 ⊆ insert {x} (Finset.powerset U \ {∅, U}) := by
        intro S hS
        rw [Finset.mem_biUnion] at hS
        rcases hS with ⟨j, -, hjS⟩
        by_cases hij : j = i
        · subst hij
          rw [hi, Finset.mem_singleton] at hjS
          subst hjS
          exact Finset.mem_insert_self _ _
        · apply Finset.mem_insert_of_mem
          rw [Finset.mem_sdiff, Finset.mem_powerset, Finset.mem_insert, Finset.mem_singleton, not_or]
          have hx : x ∉ S := by
            intro hxS
            have hsub : ({x} : Finset (Fin n)) ⊆ S := Finset.singleton_subset_iff.mpr hxS
            have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _
            exact hinc i j (Ne.symm hij) {x} hxmem S hjS hsub
          refine ⟨?_, ?_, ?_⟩
          · intro y hy
            rw [Finset.mem_erase]
            exact ⟨fun hyx => hx (hyx ▸ hy), Finset.mem_univ y⟩
          · intro hSempty
            have hsub : S ⊆ ({x} : Finset (Fin n)) := by rw [hSempty]; exact Finset.empty_subset _
            have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _
            exact hinc j i hij S hjS {x} hxmem hsub
          · intro hSU
            have hex : ∃ k : Fin t, k ≠ i ∧ k ≠ j := by
              have hne' : (Finset.univ \ ({i, j} : Finset (Fin t))).Nonempty := by
                rw [Finset.nonempty_iff_ne_empty]
                intro h
                have hsub : Finset.univ ⊆ ({i, j} : Finset (Fin t)) := by
                  rw [Finset.sdiff_eq_empty_iff_subset] at h
                  exact h
                have hle := Finset.card_le_card hsub
                rw [Finset.card_fin] at hle
                have h2 : ({i, j} : Finset (Fin t)).card ≤ 2 := Finset.card_le_two
                omega
              rcases hne' with ⟨k, hk⟩
              rw [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton, not_or] at hk
              exact ⟨k, hk.2.1, hk.2.2⟩
            rcases hex with ⟨k, hki, hkj⟩
            rcases hne k with ⟨D, hD⟩
            have hxD : x ∉ D := by
              intro hxD
              have hsub : ({x} : Finset (Fin n)) ⊆ D := singleton_subset_iff.mpr hxD
              have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _
              exact hinc i k (Ne.symm hki) {x} hxmem D hD hsub
            have hDU : D ⊆ U := by
              intro y hy
              rw [Finset.mem_erase]
              exact ⟨fun hyx => hxD (hyx ▸ hy), Finset.mem_univ y⟩
            have hDS : D ⊆ S := by rw [hSU]; exact hDU
            exact hinc k j hkj D hD S hjS hDS
  4. The bounding set {{x}} ∪ (𝒫(U) \ {∅, U}) has cardinality 2^(n-1)-1, bounding the total family size.

    The set U has cardinality n - 1, so |𝒫(U)| = 2^(n-1). Since U is nonempty, ∅ ≠ U, so removing {∅, U} removes exactly 2 elements. The singleton {x} is not in 𝒫(U) because x ∉ U, so adjoining {x} adds 1, yielding a total cardinality of (2^(n-1) - 2) + 1 = 2^(n-1) - 1. Because the union ⋃ⱼ 𝒜ⱼ embeds into this bounding set, its cardinality—and therefore the sum ∑ⱼ |𝒜ⱼ|—is at most 2^(n-1) - 1.

    lines 98–133

    uses Finset.card_le_card, Finset.mem_sdiff, Finset.mem_powerset, Finset.mem_singleton_self, Finset.mem_erase, Finset.insert_subset_iff, Finset.singleton_subset_iff, Finset.mem_powerset.mpr, Finset.empty_subset, subset_rfl, Finset.card_insert_of_notMem, Finset.card_singleton, Finset.mem_singleton, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_fin, Finset.card_sdiff_of_subset, Finset.card_powerset, Finset.card_pos.mpr, Nat.pow_le_pow_right

      have hcard_le : (Finset.univ.biUnion 𝒜).card ≤ (insert {x} (Finset.powerset U \ {∅, U})).card :=
        Finset.card_le_card hsub
      have hnotmem : ({x} : Finset (Fin n)) ∉ Finset.powerset U \ {∅, U} := by
        intro h
        rw [Finset.mem_sdiff, Finset.mem_powerset] at h
        have : x ∈ ({x} : Finset (Fin n)) := Finset.mem_singleton_self x
        have hxU := h.1 this
        rw [Finset.mem_erase] at hxU
        exact hxU.1 rfl
      have hne : (∅ : Finset (Fin n)) ≠ U := by
        intro h
        have := hU.ne_empty
        exact this h.symm
      have hsub_pow : ({∅, U} : Finset (Finset (Fin n))) ⊆ Finset.powerset U := by
        rw [Finset.insert_subset_iff, Finset.singleton_subset_iff]
        exact ⟨Finset.mem_powerset.mpr (Finset.empty_subset U), Finset.mem_powerset.mpr subset_rfl⟩
      have h2 : ({∅, U} : Finset (Finset (Fin n))).card = 2 := by
        rw [Finset.card_insert_of_notMem, Finset.card_singleton]
        rw [Finset.mem_singleton]
        exact hne
      have hUcard : U.card = n - 1 := by
        dsimp [U]
        rw [Finset.card_erase_of_mem (Finset.mem_univ x), Finset.card_fin]
      have htarget : (insert {x} (Finset.powerset U \ {∅, U})).card = 2 ^ (n - 1) - 1 := by
        rw [Finset.card_insert_of_notMem hnotmem]
        rw [Finset.card_sdiff_of_subset hsub_pow]
        rw [h2]
        rw [Finset.card_powerset, hUcard]
        have hUpos : 1 ≤ U.card := Finset.card_pos.mpr hU
        rw [hUcard] at hUpos
        have : 2 ≤ 2 ^ (n - 1) := by
          calc 2 = 2 ^ 1 := by norm_num
          _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by norm_num) hUpos
        omega
      rw [htarget] at hcard_le
      exact hcard_le
disjoint_iff_ne
Two finite sets are disjoint if and only if no element of the first equals any element of the second.
subset_rfl
The subset relation is reflexive: every set is a subset of itself.
Finset.card_biUnion
The cardinality of a pairwise disjoint union of finite sets is the sum of their individual cardinalities.
Finset.nonempty_iff_ne_empty
A finite set is nonempty if and only if it is not equal to the empty set.
not_not
A proposition is equivalent to its double negation.
Finset.sdiff_eq_empty_iff_subset
The difference of two finite sets s \ t is empty if and only if s is a subset of t.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.card_fin
The cardinality of the standard finite type Fin(n) is n.
Finset.card_singleton
The cardinality of a singleton set {a} is 1.
Finset.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_singleton
An element b belongs to {a} if and only if b = a.
Finset.singleton_subset_iff.mpr
If an element a belongs to s, then the singleton {a} is a subset of s.
Finset.mem_singleton_self
An element belongs to its own singleton set, a ∈ {a}.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_erase
An element belongs to s.erase b if and only if it is distinct from b and belongs to s.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
Finset.subset_empty
A finite set is a subset of the empty set if and only if it is empty.
Finset.empty_subset
The empty set is a subset of every set.
Finset.mem_biUnion
An element belongs to a indexed union if and only if it belongs to some member of the union.
Finset.mem_insert_self
An element a belongs to insert a s.
Finset.mem_insert_of_mem
If an element belongs to s, it belongs to insert b s.
Finset.mem_powerset
A set s belongs to the power set of t if and only if s ⊆ t.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
not_or
A disjunction is false if and only if both disjuncts are false.
Finset.card_le_two
The cardinality of a pair {a, b} is at most 2.
singleton_subset_iff.mpr
If an element a belongs to s, then the singleton {a} is a subset of s.
Finset.insert_subset_iff
The set insert a s is a subset of t if and only if a ∈ t and s ⊆ t.
Finset.singleton_subset_iff
A singleton set {a} is a subset of s if and only if a ∈ s.
Finset.mem_powerset.mpr
If s ⊆ t, then s belongs to the power set of t.
Finset.card_insert_of_notMem
If a ∉ s, then the cardinality of insert a s is |s| + 1.
Finset.card_erase_of_mem
If a ∈ s, then the cardinality of s.erase a is |s| - 1.
Finset.card_sdiff_of_subset
If s ⊆ t, then |t \ s| = |t| - |s|.
Finset.card_powerset
The power set of a finite set s has cardinality 2^|s|.
Finset.card_pos.mpr
A finite set is nonempty if and only if its cardinality is positive.
Nat.pow_le_pow_right
For a positive base, exponentiation preserves non-strict order: if i ≤ j, then n^i ≤ n^j.

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

theorem op_1370_singleton_element_family_bound (n t : ℕ) (ht : 3 ≤ t) (𝒜 : Fin t → Finset (Finset (Fin n))) (hne : ∀ i, (𝒜 i).Nonempty) (hinc : strongly_incomparable 𝒜) (i : Fin t) (x : Fin n) (hi : 𝒜 i = {{x}}) : ∑ j, (𝒜 j).card ≤ 2 ^ (n - 1) - 1 := by  open Finset in  have hdisj : ∀ (j1 j2 : Fin t), j1 ≠ j2 → Disjoint (𝒜 j1) (𝒜 j2) := by    intro j1 j2 hj    rw [disjoint_iff_ne]    intro A hA B hB heq    subst heq    exact hinc j1 j2 hj A hA A hB subset_rfl  have hp : (↑(Finset.univ : Finset (Fin t)) : Set (Fin t)).PairwiseDisjoint 𝒜 :=    fun j1 _ j2 _ hj => hdisj j1 j2 hj  have hsum : ∑ j, (𝒜 j).card = (Finset.univ.biUnion 𝒜).card := by    rw [Finset.card_biUnion hp]  rw [hsum]  set U : Finset (Fin n) := Finset.univ.erase x  have hU : U.Nonempty := by    by_contra hU'    rw [Finset.nonempty_iff_ne_empty, not_not] at hU'    have hex : ∃ j : Fin t, j ≠ i := by      have hne' : (Finset.univ \ ({i} : Finset (Fin t))).Nonempty := by        rw [Finset.nonempty_iff_ne_empty]        intro h        have hsub : Finset.univ ⊆ ({i} : Finset (Fin t)) := by          rw [Finset.sdiff_eq_empty_iff_subset] at h          exact h        have hle := Finset.card_le_card hsub        rw [Finset.card_fin, Finset.card_singleton] at hle        omega      rcases hne' with ⟨j, hj⟩      rw [Finset.mem_sdiff, Finset.mem_singleton] at hj      exact ⟨j, hj.2⟩    rcases hex with ⟨j, hij⟩    rcases hne j with ⟨B, hB⟩    have hx : x ∉ B := by      intro hxB      have hsub : ({x} : Finset (Fin n)) ⊆ B := Finset.singleton_subset_iff.mpr hxB      have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _      exact hinc i j (Ne.symm hij) {x} hxmem B hB hsub    have hBU : B ⊆ U := by      intro y hy      rw [Finset.mem_erase]      exact ⟨fun hyx => hx (hyx ▸ hy), Finset.mem_univ y⟩    rw [hU', Finset.subset_empty] at hBU    have hBempty : B ⊆ ({x} : Finset (Fin n)) := by rw [hBU]; exact Finset.empty_subset _    have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _    exact hinc j i hij B hB {x} hxmem hBempty  have hsub : Finset.univ.biUnion 𝒜 ⊆ insert {x} (Finset.powerset U \ {∅, U}) := by    intro S hS    rw [Finset.mem_biUnion] at hS    rcases hS with ⟨j, -, hjS⟩    by_cases hij : j = i    · subst hij      rw [hi, Finset.mem_singleton] at hjS      subst hjS      exact Finset.mem_insert_self _ _    · apply Finset.mem_insert_of_mem      rw [Finset.mem_sdiff, Finset.mem_powerset, Finset.mem_insert, Finset.mem_singleton, not_or]      have hx : x ∉ S := by        intro hxS        have hsub : ({x} : Finset (Fin n)) ⊆ S := Finset.singleton_subset_iff.mpr hxS        have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _        exact hinc i j (Ne.symm hij) {x} hxmem S hjS hsub      refine ⟨?_, ?_, ?_⟩      · intro y hy        rw [Finset.mem_erase]        exact ⟨fun hyx => hx (hyx ▸ hy), Finset.mem_univ y⟩      · intro hSempty        have hsub : S ⊆ ({x} : Finset (Fin n)) := by rw [hSempty]; exact Finset.empty_subset _        have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _        exact hinc j i hij S hjS {x} hxmem hsub      · intro hSU        have hex : ∃ k : Fin t, k ≠ i ∧ k ≠ j := by          have hne' : (Finset.univ \ ({i, j} : Finset (Fin t))).Nonempty := by            rw [Finset.nonempty_iff_ne_empty]            intro h            have hsub : Finset.univ ⊆ ({i, j} : Finset (Fin t)) := by              rw [Finset.sdiff_eq_empty_iff_subset] at h              exact h            have hle := Finset.card_le_card hsub            rw [Finset.card_fin] at hle            have h2 : ({i, j} : Finset (Fin t)).card ≤ 2 := Finset.card_le_two            omega          rcases hne' with ⟨k, hk⟩          rw [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton, not_or] at hk          exact ⟨k, hk.2.1, hk.2.2⟩        rcases hex with ⟨k, hki, hkj⟩        rcases hne k with ⟨D, hD⟩        have hxD : x ∉ D := by          intro hxD          have hsub : ({x} : Finset (Fin n)) ⊆ D := singleton_subset_iff.mpr hxD          have hxmem : ({x} : Finset (Fin n)) ∈ 𝒜 i := by rw [hi]; exact Finset.mem_singleton_self _          exact hinc i k (Ne.symm hki) {x} hxmem D hD hsub        have hDU : D ⊆ U := by          intro y hy          rw [Finset.mem_erase]          exact ⟨fun hyx => hxD (hyx ▸ hy), Finset.mem_univ y⟩        have hDS : D ⊆ S := by rw [hSU]; exact hDU        exact hinc k j hkj D hD S hjS hDS  have hcard_le : (Finset.univ.biUnion 𝒜).card ≤ (insert {x} (Finset.powerset U \ {∅, U})).card :=    Finset.card_le_card hsub  have hnotmem : ({x} : Finset (Fin n)) ∉ Finset.powerset U \ {∅, U} := by    intro h    rw [Finset.mem_sdiff, Finset.mem_powerset] at h    have : x ∈ ({x} : Finset (Fin n)) := Finset.mem_singleton_self x    have hxU := h.1 this    rw [Finset.mem_erase] at hxU    exact hxU.1 rfl  have hne : (∅ : Finset (Fin n)) ≠ U := by    intro h    have := hU.ne_empty    exact this h.symm  have hsub_pow : ({∅, U} : Finset (Finset (Fin n))) ⊆ Finset.powerset U := by    rw [Finset.insert_subset_iff, Finset.singleton_subset_iff]    exact ⟨Finset.mem_powerset.mpr (Finset.empty_subset U), Finset.mem_powerset.mpr subset_rfl⟩  have h2 : ({∅, U} : Finset (Finset (Fin n))).card = 2 := by    rw [Finset.card_insert_of_notMem, Finset.card_singleton]    rw [Finset.mem_singleton]    exact hne  have hUcard : U.card = n - 1 := by    dsimp [U]    rw [Finset.card_erase_of_mem (Finset.mem_univ x), Finset.card_fin]  have htarget : (insert {x} (Finset.powerset U \ {∅, U})).card = 2 ^ (n - 1) - 1 := by    rw [Finset.card_insert_of_notMem hnotmem]    rw [Finset.card_sdiff_of_subset hsub_pow]    rw [h2]    rw [Finset.card_powerset, hUcard]    have hUpos : 1 ≤ U.card := Finset.card_pos.mpr hU    rw [hUcard] at hUpos    have : 2 ≤ 2 ^ (n - 1) := by      calc 2 = 2 ^ 1 := by norm_num      _ ≤ 2 ^ (n - 1) := Nat.pow_le_pow_right (by norm_num) hUpos    omega  rw [htarget] at hcard_le  exact hcard_le
See it in the graphDiscuss this resultChallenge it