AFTD Auto-Formalizing Theoretical Domains

not_injOn_of_exists_ne

theoremverified

A function $f$ is not injective on a set $s$ if there exist distinct elements $x, y \in s$ such that $f(x) = f(y)$.

Statement

lemma not_injOn_of_exists_ne {α β : Type*} (f : α → β) (s : Set α)
    (x y : α) (hx : x ∈ s) (hy : y ∈ s) (hne : x ≠ y) (hfeq : f x = f y) :
    ¬ Set.InjOn f s
Source
folklore
Verified
08 Nov 2026
Axioms
none — Lean reports it depends on no axioms
Used by 1

Read back from the Lean

For any types $\alpha$ and $\beta$, any function $f : \alpha \to \beta$, any set $s \subseteq \alpha$, and any elements $x, y \in \alpha$, if $x \in s$, $y \in s$, $x \ne y$, and $f(x) = f(y)$, then $f$ is not injective on $s$ (¬ Set.InjOn f s).

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

The proof proceeds by contradiction. Assuming that $f$ is injective on $s$, the condition $f(x) = f(y)$ for $x, y \in s$ forces $x = y$. This directly contradicts the hypothesis that $x \ne y$.

  1. $f$ is not injective on $s$

    Assume for contradiction that $f$ is injective on $s$ (denoted `hinj`). Applying this injectivity to the hypotheses that $x \in s$ (`hx`), $y \in s$ (`hy`), and $f(x) = f(y)$ (`hfeq`) implies $x = y$. This contradicts the assumption that $x \neq y$ (`hne`).

    line 4

        ¬ Set.InjOn f s := fun hinj => hne (hinj hx hy hfeq)

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- A function is not injective on a set if two distinct elements in the set have the same image. -/lemma not_injOn_of_exists_ne {α β : Type*} (f : α → β) (s : Set α)    (x y : α) (hx : x ∈ s) (hy : y ∈ s) (hne : x ≠ y) (hfeq : f x = f y) :    ¬ Set.InjOn f s := fun hinj => hne (hinj hx hy hfeq)
See it in the graphDiscuss this resultChallenge it