CorollaryStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passverified 2026-08-06 (claude-opus-5)

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.

For $f : A \to B$ : $S \subseteq f^{-1}[f[S]]$ for every $S \subseteq A$ , with equality for every such $S$ if and only if $f$ is injective; and $f[f^{-1}[T]] = T \cap f[A]$ for every $T \subseteq B$ , so equality with $T$ holds for every such $T$ if and only if $f$ is surjective

Statement

Let $f : A \to B$ . Then

(i) $S \subseteq f^{-1}[f[S]]$ for every $S \subseteq A$ ;
(ii) equality holds in (i) for every $S \subseteq A$ if and only if $f$ is injective;
(iii) $f[f^{-1}[T]] = T \cap f[A]$ for every $T \subseteq B$ ;
(iv) $f[f^{-1}[T]] = T$ for every $T \subseteq B$ if and only if $f$ is surjective.

Facts & Assumptions

Given: a function $f : A \to B$ .

[L1]

$b \in R[A]$ holds if and only if $(a,b) \in R$ for some $a \in A$ (The image $R[A]$ and the preimage $R^{-1}[B]$ of a set under a relation).

[L2]

We write $f : A \to B$ , and say $f$ is a function from $A$ to $B$ , when $f$ is a function with $\operatorname{dom} f = A$ and $\operatorname{ran} f \subseteq B$ (A function is a relation $f$ with $(a,b) \in f$ and $(a,c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f(a)$ , domain and codomain).

[L3]

$f$ is injective (one-to-one) if $f(x) = f(y)$ implies $x = y$ , for all $x, y \in A$ (Injection, surjection, bijection).

[L4]

$f$ is surjective (onto) if for every $b \in B$ there is some $x \in A$ with $f(x) = b$ ; equivalently, the image $f[A] := \{ f(x) : x \in A \}$ equals $B$ (Injection, surjection, bijection).

[L5]

$z \in a \cap b$ holds if and only if $z \in a$ and $z \in b$ ( $\bigcup \varnothing = \varnothing$ , $\bigcup \{a\} = a$ , $\bigcup \{a,b\} = a \cup b$ , $\bigcap \{a\} = a$ , and $\bigcap \{a,b\} = a \cap b$ ).

[L6]

$x \subseteq y$ means that every element of $x$ is an element of $y$ (Subset $x \subseteq y$ , proper subset $x \subsetneq y$ , and the separation notation $\{\, z \in x : \varphi(z) \,\}$ ).

[L7]

If every $z$ satisfies $z \in x$ if and only if $z \in y$ , then $x = y$ (The Axiom of Extensionality: $\forall x\,\forall y\,(\forall z\,(z \in x \leftrightarrow z \in y) \to x = y)$ ).

[L8]

$\{x\} := \{x,x\}$ , the singleton of $x$ , is the set whose only element is $x$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L9]

$\operatorname{ran} R := \{\, b : \exists a\ (a,b) \in R \,\}$ (Relation, $\operatorname{dom} R$ , $\operatorname{ran} R$ , $\operatorname{fld} R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

Proof

technique · direct

1.1

Membership criteria used throughout: for $S \subseteq A$ , $y \in f[S]$ exactly when $y = f(s)$ for some $s \in S$ ; and for $T \subseteq B$ , $a \in f^{-1}[T]$ exactly when $a \in A$ and $f(a) \in T$ .

L1L2L6L9

2.1

Claim (i): if $s \in S$ then $f(s) \in f[S]$ , so $s \in f^{-1}[f[S]]$ .

step 1.1

2.2

Claim (iii): if $y \in f[f^{-1}[T]]$ then $y = f(a)$ with $a \in A$ and $f(a) \in T$ , so $y \in T$ and $y \in f[A]$ ; conversely if $y \in T$ and $y = f(a)$ with $a \in A$ , then $f(a) \in T$ puts $a$ in $f^{-1}[T]$ and $y$ in $f[f^{-1}[T]]$ .

L5L7step 1.1

3.1

Claim (ii): suppose $f$ is injective and $a \in f^{-1}[f[S]]$ for some $S \subseteq A$ . Then $f(a) \in f[S]$ , so $f(a) = f(s)$ for some $s \in S$ , and injectivity gives $a = s \in S$ ; with step 2.1 this is equality. Conversely, if $f$ is not injective, take $a \neq a'$ in $A$ with $f(a) = f(a')$ and put $S := \{a\}$ ; then $a' \in f^{-1}[f[S]]$ while $a' \notin S$ , so equality fails for that $S$ .

L3L8step 1.1step 2.1

3.2

Claim (iv): if $f$ is surjective then $f[A] = B$ , so for $T \subseteq B$ claim (iii) gives $f[f^{-1}[T]] = T \cap B = T$ . Conversely, if the equality holds for every $T \subseteq B$ , take $T := B$ ; claim (iii) gives $B = B \cap f[A] = f[A]$ , which is surjectivity.

L4L5L6L7step 2.2

4.1

Claims (i) to (iv) are established, which is the statement.

step 2.1step 2.2step 3.1step 3.2∎

Remarks

Only one of the two criteria needs the injectivity lemma. Claim (ii) is the round-trip form of the equality criterion in For $f : A \to B$ and $S, T \subseteq A$ : $f[S \cup T] = f[S] \cup f[T]$ , $f[S \cap T] \subseteq f[S] \cap f[T]$ and $f[S] \setminus f[T] \subseteq f[S \setminus T]$ ; both inclusions are equalities for all $S$ and $T$ if and only if $f$ is injective; the argument is repeated here because the witness used to break equality is a singleton rather than a pair of sets.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 25 results over 13 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Image (mathematics) (Wikipedia) (standard reference, not scraped)
Bijection, injection and surjection (Wikipedia) (standard reference, not scraped)
B. Kaya, MATH 320 Set Theory (METU), §2.2 (standard reference, not scraped)