LemmaStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-26

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Every set shattered by $S_{j} (F)$ is shattered by $F$

Statement

Let $F \subseteq P ([n])$ , let $j < n$ , and let $T \subseteq [n]$ . If $T$ is shattered by $S_{j} (F)$ , then $T$ is shattered by $F$ .

Facts & Assumptions

Given: a family $F \subseteq P ([n])$ , an index $j < n$ , and a set $T$ shattered by $S_{j} (F)$ .

[F1]

The down-shift is defined by the two cases in The down-shift $S_{j}$ of a set family at a point $j$ .

[F2]

A set is shattered when its trace is the whole power set (Shattering and the Vapnik–Chervonenkis dimension of a set family).

Proof

technique · direct

1.1

Suppose first that $j \notin T$ . Then every trace of $S_{j} (F)$ on $T$ is also a trace of $F$ on $T$ , because removing or keeping $j$ changes nothing on the set $T$ . Since $T$ is shattered by $S_{j} (F)$ , it is shattered by $F$ as well.

F1F2

1.2

Now suppose that $j \in T$ , and let $A \subseteq T$ be arbitrary. Since $T$ is shattered by $S_{j} (F)$ , both $A$ and $A \cup {j}$ occur as traces of shifted sets. The second clause of [F1] implies that whenever $A$ appears as a trace with $j$ removed, the original family already contains a set realising $A$ or a set realising $A \cup {j}$ ; applying this to the two traces $A$ and $A \cup {j}$ shows that $F$ realises both. Hence every subset of $T$ is a trace of $F$ , so $T$ is shattered by $F$ .

F1F2

2.1

The two cases cover all possibilities for $j$ , so no new shattered set is created by the down-shift.

step 1.1step 1.2∎

Remarks

The case $j \in T$ is where the clause "and $F ∖ {j} \notin F$ " does real work. Without it the conclusion would fail.

Depends on

Used by

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, §7.5 (standard reference, not scraped)

Every set shattered by Sj(F)Sj​(F) is shattered by FF