AFTD Auto-Formalizing Theoretical Domains

is_matchable_one

theoremverified

The natural number 1 is matchable.

Statement

theorem is_matchable_one : is_matchable 1
Source
folklore
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_matchableA natural number n is matchable if there exists an equivalence e : Fin (Nat.divisors n).card ≃ Nat.divisors n such that (e i : ℕ) and (i :…

Read back from the Lean

The natural number 1 satisfies is_matchable, which means there exists a bijection (equivalence) between Fin (Nat.divisors 1).card and the set of divisors of 1 (Nat.divisors 1) such that each index i is paired with a divisor coprime to (i : ℕ) + 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

A positive integer n is matchable if there is a bijection between {0, ..., d(n) - 1} and its divisors pairing each index i with a divisor coprime to i + 1. For n = 1, the only divisor is 1, so both the index set and the divisor set are singletons. The unique bijection between them pairs index 0 with the divisor 1, which are coprime because gcd(1, 1) = 1.

  1. The problem reduces to finding a bijection from Fin 1 to {1} that satisfies the coprimality condition.

    By definition of `is_matchable`, we must find a bijection from `Fin (|divisors(1)|)` to `divisors(1)` pairing each index `i` with a divisor coprime to `i + 1`. Since the only positive divisor of 1 is 1 (`Nat.divisors_one`), the divisor set is the singleton `{1}`, which has cardinality 1 (`Finset.card_singleton`).

    lines 3–4

    uses Nat.divisors_one, Finset.card_singleton

      unfold is_matchable
      rw [Nat.divisors_one, Finset.card_singleton]
  2. The canonical bijection between the two singleton types is chosen as the witness.

    Both the domain `Fin 1` and the codomain `{1}` are singleton types. Applying `Equiv.ofUnique` constructs the unique bijection between them.

    line 5

    uses Equiv.ofUnique

      refine ⟨Equiv.ofUnique _ _, ?_⟩
  3. The coprimality condition holds for the unique index in Fin 1.

    Let `i : Fin 1`. The set `Fin 1` contains only the element 0, so `i + 1 = 1`. The bijection maps 0 to the single divisor 1. The condition therefore asks whether 1 and 1 are coprime, which `simp` resolves because gcd(1, 1) = 1.

    lines 6–7

      intro i
      simp
Nat.divisors_one
The set of divisors of 1 is the singleton set containing only 1.
Finset.card_singleton
The cardinality of a singleton finite set is 1.
Equiv.ofUnique
Any two types with unique elements are canonically in bijection.

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

/-- The natural number 1 is matchable. -/theorem is_matchable_one : is_matchable 1 := by  unfold is_matchable  rw [Nat.divisors_one, Finset.card_singleton]  refine ⟨Equiv.ofUnique _ _, ?_⟩  intro i  simp
See it in the graphDiscuss this resultChallenge it