coprime_divisor_progression_graph_decidable_adj
instanceoriginal
Adjacency in the coprime divisor progression graph coprime_divisor_progression_graph n a b is decidable via Classical.decRel.
Statement
noncomputable instance coprime_divisor_progression_graph_decidable_adj (n : ℕ) (a b : ℤ) : DecidableRel (coprime_divisor_progression_graph n a b).Adj
- Related work
- folklore
- Verified
- 29 Oct 2026
- Axioms
- none listed
- Built on 1
- coprime_divisor_progression_graphFor a natural number n and integers a and b, the coprime divisor progression graph is the bipartite simple graph on the disjoint union of…
- Used by 3
- op_657_half_degree_packing_of_min_degree_le_twoFor every squarefree natural number n with at least two distinct prime factors and any positive coprime integers a and b, if the coprime…
- op_652_half_degree_packing_of_min_degree_le_twoFor any natural number n ≥ 2 and integers a, b with b > 0, if the coprime divisor progression graph B has minimum degree at most 2 and…
- op_652_half_degree_packing_of_primeFor any prime p and integers a, b with b > 0, if the coprime divisor progression graph B has a perfect matching, then B contains at least…
Read back from the Lean
For any natural number $n$ and integers $a$ and $b$, the adjacency relation of the bipartite graph coprime_divisor_progression_graph n a b is decidable (registered as a noncomputable instance via classical logic).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Classical decidability instance for adjacency in the coprime divisor progression graph. -/ noncomputable instance coprime_divisor_progression_graph_decidable_adj (n : ℕ) (a b : ℤ) : DecidableRel (coprime_divisor_progression_graph n a b).Adj := Classical.decRel _