Proof of `Taking induced subgraphs and left lexicographic products` (2nd statement)

groundedproofs/Lax871432Proofs/Results.lean · lax-871432

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

prop:lexprodindsubprop:lexprod-indsub, (1) ⇒ (2). In the formula for hom(F,GH)hom(F, G ⋅ H) the factor depending on HH counts homomorphisms out of a disjoint union of subgraphs of FF induced by the classes of a partition. Each of those induced subgraphs lies in F\mathcal{F}, so none of them distinguishes HH from HH', and the counts agree summand by summand.