op_1370_singleton_element_family_bound
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 alli j : ιwithi ≠ j, for all…
- strongly_incomparableAn indexed family of finset families
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.
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.
uses
disjoint_iff_ne,subset_rfl,Finset.card_biUnionopen 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]
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.
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_subsetset 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
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}.
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.mprhave 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
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.
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_righthave 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.
- Finite set difference and cardinality inequalities relying on t ≥ 3 are closed by `omega` (lines 27, 81, and 131).
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.
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