Relations, Functions, and Quotients: Examples and Counterexamples

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

A four-pair relation on $\{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}$ with its domain, range, field, inverse, restriction, image and self-composite computed

Example

Write $u := \varnothing$ , $v := \{\varnothing\}$ and $w := \{\varnothing,\{\varnothing\}\}$ ; these are pairwise distinct, since $u$ has no element, $v$ has exactly the element $u$ , and $w$ has $v$ as an element while $v$ does not. Put $A := \{u,v\} \cup \{w\}$ and

$R := \{(u,v),(v,w)\} \cup \{(w,u),(u,u)\}.$

Then $R$ is a relation on $A$ with

$\operatorname{dom} R = \operatorname{ran} R = \operatorname{fld} R = A, \qquad R^{-1} = \{(v,u),(w,v)\} \cup \{(u,w),(u,u)\},$

$R \restriction \{u\} = \{(u,v),(u,u)\}, \qquad R[\{u\} \cup \{v\}] = A, \qquad R \circ R = \{(u,w),(u,v)\} \cup \{(u,u),(v,u)\} \cup \{(w,v),(w,u)\}.$

Facts & Assumptions

Given: $u := \varnothing$ , $v := \{\varnothing\}$ , $w := \{\varnothing,\{\varnothing\}\}$ , $A := \{u,v\} \cup \{w\}$ and $R$ as displayed.

[L1]

A relation is a set $R$ every element of which is an ordered pair (Relation, $\operatorname{dom} R$ , $\operatorname{ran} R$ , $\operatorname{fld} R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L2]

$\operatorname{dom} R := \{\, a : \exists b\ (a,b) \in R \,\}, \qquad \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$ ").

[L3]

$(b,a) \in R^{-1}$ holds if and only if $(a,b) \in R$ ; $(a,c) \in S \circ R$ holds if and only if $(a,b) \in R$ and $(b,c) \in S$ for some $b$ ; and $(a,b) \in R \restriction A$ holds if and only if $(a,b) \in R$ and $a \in A$ (The inverse relation $R^{-1}$ , the composite $S \circ R$ , and the restriction $R \restriction A$ ).

[L4]

$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).

[L5]

$(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ( $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ).

[L6]

$(a,b) := \{\{a\},\{a,b\}\}$ (The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$ ).

[L7]

$\{x,y\}$ is the set whose elements are exactly $x$ and $y$ , and $\{x\} := \{x,x\}$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L8]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[L9]

$z \in a \cup b$ holds if and only if $z \in a$ or $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$ ).

[L10]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

[L11]

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)$ ).

[L12]

$a \cup b := \bigcup\{a,b\}$ (The union $\bigcup x$ of a set, and the binary union $a \cup b := \bigcup \{a,b\}$ ).

Verification

technique · direct

1.1

$u$ , $v$ and $w$ are pairwise distinct and $A$ has exactly them as elements; every element of $R$ is an ordered pair with both coordinates in $A$ , so $R$ is a relation on $A$ , that is $R \subseteq A \times A$ .

L1L6L7L8L9L10L12

2.1

Reading off first coordinates gives $u$ , $v$ , $w$ , so $\operatorname{dom} R = A$ ; reading off second coordinates gives $v$ , $w$ , $u$ , so $\operatorname{ran} R = A$ ; and the field, being the union of the two, is $A$ as well.

L2L5L9L11step 1.1

2.2

Reversing each pair gives $R^{-1} = \{(v,u),(w,v)\} \cup \{(u,w),(u,u)\}$ ; keeping the pairs whose first coordinate is $u$ gives $R \restriction \{u\} = \{(u,v),(u,u)\}$ ; and the elements related to $u$ or to $v$ are $v$ , $u$ and $w$ , so $R[\{u\} \cup \{v\}] = A$ .

L3L4L5L7L9L11step 1.1

2.3

For the self-composite, each pair $(a,b)$ of $R$ is matched with every pair of $R$ whose first coordinate is $b$ : from $(u,v)$ and $(v,w)$ comes $(u,w)$ ; from $(u,u)$ and the two pairs starting at $u$ come $(u,v)$ and $(u,u)$ ; from $(v,w)$ and $(w,u)$ comes $(v,u)$ ; and from $(w,u)$ and the two pairs starting at $u$ come $(w,v)$ and $(w,u)$ . These six pairs are exactly the displayed $R \circ R$ .

L3L5L9L11step 1.1

3.1

The domain, range, field, inverse, restriction, image and self-composite are as displayed.

step 2.1step 2.2step 2.3∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

$\varnothing$ is a relation on every set, is the unique equivalence relation on $\varnothing$ , is a function $\varnothing \to B$ for every $B$ , is a bijection $\varnothing \to \varnothing$ , and is not a surjection $\varnothing \to \{\varnothing\}$

Example

The empty set does the work of five different objects at once.

$\varnothing$ is a relation, and a relation on $A$ for every set $A$ ; its domain, range and field are all $\varnothing$ .
$\varnothing$ is the only relation on $\varnothing$ , and it is an equivalence relation on $\varnothing$ ; so $\varnothing$ carries exactly one equivalence relation.
$\varnothing$ is a function $\varnothing \to B$ for every set $B$ , and it is the only one.
$\varnothing$ is a bijection $\varnothing \to \varnothing$ .
$\varnothing$ is not a surjection $\varnothing \to \{\varnothing\}$ , even though it is an injective function $\varnothing \to \{\varnothing\}$ .

The last two together are the reason a codomain belongs to the declaration $f : A \to B$ rather than to the set $f$ : one and the same set is a bijection under one declaration and a non-surjection under another. The empty function is also the unique element of the empty product.

Facts & Assumptions

Given: the set $\varnothing$ and arbitrary sets $A$ and $B$ .

[L1]

A relation is a set $R$ every element of which is an ordered pair (Relation, $\operatorname{dom} R$ , $\operatorname{ran} R$ , $\operatorname{fld} R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L2]

$\operatorname{dom} R := \{\, a : \exists b\ (a,b) \in R \,\}, \qquad \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$ ").

[L3]

A function is a relation $f$ such that $(a,b) \in f$ and $(a,c) \in f$ imply $b = c$ (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).

[L4]

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).

[L5]

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

[L6]

$f$ is surjective (onto) if for every $b \in B$ there is some $x \in A$ with $f(x) = b$ (Injection, surjection, bijection).

[L7]

A binary relation $\sim$ on $A$ is an equivalence relation when it is reflexive, symmetric and transitive (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L8]

$R$ is reflexive on $A$ when $(a,a) \in R$ for every $a \in A$ (Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set).

[L9]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[L10]

$\{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\}$ ).

[L11]

$A \times B = \varnothing$ if and only if $A = \varnothing$ or $B = \varnothing$ ( $A \times (B \cup C) = (A \times B) \cup (A \times C)$ , $A \times (B \cap C) = (A \times B) \cap (A \times C)$ , $A \times (B \setminus C) = (A \times B) \setminus (A \times C)$ , $(A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D)$ ; $A \times B = \varnothing$ if and only if $A = \varnothing$ or $B = \varnothing$ ; and for nonempty $A$ and $B$ , $A \times B \subseteq C \times D$ if and only if $A \subseteq C$ and $B \subseteq D$ ).

[L12]

$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) \,\}$ ).

[L13]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

[L14]

if $I = \varnothing$ then $\prod_{i \in I} A_i = \{\varnothing\}$ ( $\prod_{i \in \varnothing} A_i = \{\varnothing\}$ ; if $A_j = \varnothing$ for some $j \in I$ then $\prod_{i \in I} A_i = \varnothing$ ; and for $I = \{j\}$ the evaluation $f \mapsto f(j)$ is a bijection $\prod_{i \in I} A_i \to A_j$ ).

[L15]

an element of $\prod_{i \in I} A_i$ is a function with domain $I$ that takes its value at each index inside the member carried by that index (The product $\prod_{i \in I} A_i := \{\, f : I \to \bigcup_{i \in I} A_i \ \mid\ f(i) \in A_i \text{ for every } i \in I \,\}$ ).

Verification

technique · direct

1.1

$\varnothing$ has no elements, so "every element is an ordered pair" holds vacuously and $\varnothing$ is a relation; $\varnothing \subseteq A \times A$ for every $A$ , so it is a relation on every set; and no set satisfies the defining conditions for its domain or its range, so both are $\varnothing$ , hence so is its field.

L1L2L9L12

1.2

A relation on $\varnothing$ is a subset of $\varnothing \times \varnothing$ , which is $\varnothing$ , so $\varnothing$ is the only one. It is reflexive on $\varnothing$ , symmetric and transitive, since each condition quantifies over elements of $\varnothing$ ; hence it is the unique equivalence relation on $\varnothing$ .

L7L8L9L11L12L13

2.1

$\varnothing$ is single valued vacuously, has domain $\varnothing$ and range $\varnothing \subseteq B$ , so $\varnothing : \varnothing \to B$ for every $B$ ; and any function with domain $\varnothing$ has no elements, so it is $\varnothing$ .

L3L4L9L12step 1.1

3.1

As a function $\varnothing \to \varnothing$ it is injective, since the injectivity condition quantifies over elements of the domain, and surjective, since the surjectivity condition quantifies over elements of the codomain and $\varnothing$ has none; so it is a bijection.

L5L6L9step 2.1

3.2

As a function $\varnothing \to \{\varnothing\}$ it is still injective, for the same reason, but not surjective: $\varnothing$ is an element of $\{\varnothing\}$ and no element of the domain is sent to it.

L5L6L9L10step 2.1

3.3

The empty function is the unique element of the empty product: $\prod_{i \in \varnothing} A_i = \{\varnothing\}$ , and its one element is a function with domain $\varnothing$ .

L14L15step 2.1

4.1

All five descriptions hold of the single set $\varnothing$ , and the last two differ only in the declared codomain.

step 1.1step 1.2step 2.1step 3.1step 3.2step 3.3∎

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

Relations $R$ and $S$ on a two-element set with $S \circ R \neq R \circ S$

Statement refuted

Refuted claim: $S \circ R = R \circ S$ for all relations $R$ and $S$ . With $u := \varnothing$ , $v := \{\varnothing\}$ , $A := \{u,v\}$ and

$R := \{(u,v)\}, \qquad S := \{(v,u)\},$

the two composites are $S \circ R = \{(u,u)\}$ and $R \circ S = \{(v,v)\}$ , which are different. Composition of relations is associative ( $T \circ (S \circ R) = (T \circ S) \circ R$ , $(S \circ R)^{-1} = R^{-1} \circ S^{-1}$ , $(R^{-1})^{-1} = R$ , $\operatorname{dom}(R^{-1}) = \operatorname{ran} R$ , and $\Delta_B \circ R = R = R \circ \Delta_A$ for a relation $R$ from $A$ to $B$ ) but not commutative.

Facts & Assumptions

Given: $u := \varnothing$ , $v := \{\varnothing\}$ , $A := \{u,v\}$ , $R := \{(u,v)\}$ and $S := \{(v,u)\}$ .

[L1]

$(a,c) \in S \circ R$ holds if and only if $(a,b) \in R$ and $(b,c) \in S$ for some $b$ (The inverse relation $R^{-1}$ , the composite $S \circ R$ , and the restriction $R \restriction A$ ).

[L2]

A relation is a set $R$ every element of which is an ordered pair (Relation, $\operatorname{dom} R$ , $\operatorname{ran} R$ , $\operatorname{fld} R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L3]

$(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ( $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ).

[L4]

$(a,b) := \{\{a\},\{a,b\}\}$ (The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$ ).

[L5]

$\{x,y\}$ is the set whose elements are exactly $x$ and $y$ , and $\{x\} := \{x,x\}$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L6]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[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]

$T \circ (S \circ R) = (T \circ S) \circ R$ ( $T \circ (S \circ R) = (T \circ S) \circ R$ , $(S \circ R)^{-1} = R^{-1} \circ S^{-1}$ , $(R^{-1})^{-1} = R$ , $\operatorname{dom}(R^{-1}) = \operatorname{ran} R$ , and $\Delta_B \circ R = R = R \circ \Delta_A$ for a relation $R$ from $A$ to $B$ ).

[L9]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

Counterexample

technique · direct

1.1

$u \neq v$ , because $v$ has an element and $u$ has none; and $R$ and $S$ are relations on $A$ , each with one pair, both of whose coordinates lie in $A$ .

L2L5L6L9

2.1

$S \circ R$ : the only pair of $R$ is $(u,v)$ , and the only pair of $S$ whose first coordinate is $v$ is $(v,u)$ , so the only element of $S \circ R$ is $(u,u)$ .

L1L3L5L7step 1.1

2.2

$R \circ S$ : the only pair of $S$ is $(v,u)$ , and the only pair of $R$ whose first coordinate is $u$ is $(u,v)$ , so the only element of $R \circ S$ is $(v,v)$ .

L1L3L5L7step 1.1

3.1

$(u,u)$ and $(v,v)$ are different, since equality of ordered pairs would force $u = v$ ; so the two composites have different elements and $S \circ R \neq R \circ S$ , while the associativity of composition is unaffected.

L3L4L7L8step 1.1step 2.1step 2.2∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

A two-cell partition of a three-element set, the equivalence relation it induces listed pair by pair, and the quotient set recovered from it

Example

Write $u := \varnothing$ , $v := \{\varnothing\}$ and $w := \{\varnothing,\{\varnothing\}\}$ , which are pairwise distinct, and put $A := \{u,v\} \cup \{w\}$ . The collection $\{\{u,v\},\{w\}\}$ has nonempty cells, covers $A$ , and its two cells are disjoint. The equivalence relation it induces on $A$ , namely " $a$ and $b$ lie in the same cell", is

$\sim \;=\; \{(u,u),(u,v)\} \cup \{(v,u),(v,v)\} \cup \{(w,w)\},$

with classes $[u] = [v] = \{u,v\}$ and $[w] = \{w\}$ , so that $A/{\sim} = \{\{u,v\},\{w\}\}$ is the original collection again.

Facts & Assumptions

Given: $u := \varnothing$ , $v := \{\varnothing\}$ , $w := \{\varnothing,\{\varnothing\}\}$ , $A := \{u,v\} \cup \{w\}$ , and $\sim$ as displayed.

[L1]

reflexive: $a \sim a$ for every $a \in A$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L2]

symmetric: $a \sim b$ implies $b \sim a$ , for all $a, b \in A$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L3]

transitive: $a \sim b$ and $b \sim c$ imply $a \sim c$ , for all $a, b, c \in A$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L4]

$[a] \;:=\; \{\, b \in A \;:\; a \sim b \,\} \;\subseteq\; A$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L5]

$A/{\sim} \;:=\; \{\, [a] \;:\; a \in A \,\}$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L6]

The equivalence classes of an equivalence relation are nonempty, cover $A$ , and are pairwise equal or disjoint (The equivalence classes of an equivalence relation are nonempty, cover $A$ , and are pairwise equal or disjoint; conversely every such cover arises from exactly one equivalence relation).

[L7]

$\{x,y\}$ is the set whose elements are exactly $x$ and $y$ , and $\{x\} := \{x,x\}$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L8]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[L9]

$z \in a \cup b$ holds if and only if $z \in a$ or $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$ ).

[L10]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

[L11]

$(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ( $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ).

[L12]

$(a,b) := \{\{a\},\{a,b\}\}$ (The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$ ).

[L13]

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)$ ).

[L14]

A relation is a set $R$ every element of which is an ordered pair (Relation, $\operatorname{dom} R$ , $\operatorname{ran} R$ , $\operatorname{fld} R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L15]

$a \cup b := \bigcup\{a,b\}$ (The union $\bigcup x$ of a set, and the binary union $a \cup b := \bigcup \{a,b\}$ ).

Verification

technique · direct

1.1

$u$ , $v$ and $w$ are pairwise distinct: $u$ has no element, $v$ has exactly $u$ , and $w$ has $v$ as an element while $v$ does not. So $A$ has exactly those three elements, and $\sim$ is a relation on $A$ , each of its five listed pairs having both coordinates in $A$ .

L7L8L9L10L12L14L15

2.1

$\sim$ is an equivalence relation on $A$ : it contains $(u,u)$ , $(v,v)$ and $(w,w)$ , so it is reflexive on $A$ ; its pairs with distinct coordinates are $(u,v)$ and $(v,u)$ , and each of those has its reverse present, so it is symmetric; and every composable pair of its members has its composite present, since chains through $u$ and $v$ stay inside $\{u,v\}$ and $w$ relates only to itself.

L1L2L3L11L13step 1.1

3.1

The classes are as stated: $[u] = \{b \in A : u \sim b\} = \{u,v\}$ , $[v] = \{u,v\}$ by the pairs $(v,u)$ and $(v,v)$ , and $[w] = \{w\}$ . Hence $A/{\sim}$ has exactly the two elements $\{u,v\}$ and $\{w\}$ , which is the collection we started from.

L4L5L7L11L13step 1.1step 2.1

4.1

The collection is therefore a partition of $A$ in the sense of the classes being nonempty, covering $A$ and pairwise equal or disjoint, and it is recovered as the quotient set of the equivalence relation it induces.

L6step 2.1step 3.1∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

A two-to-one function on a four-element set, its kernel, the quotient, and the canonical factorisation computed explicitly

Example

Write $u := \varnothing$ , $v := \{\varnothing\}$ , $w := \{\varnothing,\{\varnothing\}\}$ and $x := \{\{\varnothing\}\}$ ; these four are pairwise distinct. Put $A := \{u,v\} \cup \{w,x\}$ and $B := \{u,v\}$ , and let

$f := \{(u,u),(v,u)\} \cup \{(w,v),(x,v)\},$

so $f : A \to B$ takes the value $u$ twice and the value $v$ twice. Then

$\ker f = \{(u,u),(u,v)\} \cup \{(v,u),(v,v)\} \cup \{(w,w),(w,x)\} \cup \{(x,w),(x,x)\},$

$A/{\ker f} = \{\{u,v\},\{w,x\}\}, \qquad f[A] = B,$

and the canonical factorisation $f = \iota \circ \bar f \circ \pi$ has $\pi(u) = \pi(v) = \{u,v\}$ , $\pi(w) = \pi(x) = \{w,x\}$ , $\bar f(\{u,v\}) = u$ , $\bar f(\{w,x\}) = v$ , and $\iota = \Delta_{B}$ .

Facts & Assumptions

Given: $u,v,w,x$ , $A$ , $B$ and $f$ as displayed.

[L1]

$\ker f$ is a set, is a relation on $A$ , and is an equivalence relation on $A$ (For a function $f : A \to B$ the relation $\ker f := \{\,(a,a') \in A \times A : f(a) = f(a')\,\}$ is an equivalence relation on $A$ ).

[L2]

there is a function $\bar f : A/{\sim} \to f[A]$ with $\bar f([a]) = f(a)$ for every $a \in A$ , and it is a bijection (Every function $f : A \to B$ factors as $f = \iota \circ \bar f \circ \pi$ with $\pi : A \to A/{\ker f}$ the surjective quotient map, $\bar f : A/{\ker f} \to f[A]$ the bijection $[a] \mapsto f(a)$ , and $\iota : f[A] \to B$ the inclusion injection; $\bar f$ is the only function making the factorisation hold).

[L3]

A function is a relation $f$ such that $(a,b) \in f$ and $(a,c) \in f$ imply $b = c$ (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).

[L4]

$[a] \;:=\; \{\, b \in A \;:\; a \sim b \,\} \;\subseteq\; A$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L5]

$A/{\sim} \;:=\; \{\, [a] \;:\; a \in A \,\}$ (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L6]

$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).

[L7]

$\{x,y\}$ is the set whose elements are exactly $x$ and $y$ , and $\{x\} := \{x,x\}$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L8]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[L9]

$f$ is surjective (onto) if for every $b \in B$ there is some $x \in A$ with $f(x) = b$ (Injection, surjection, bijection).

[L10]

$z \in a \cup b$ holds if and only if $z \in a$ or $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$ ).

[L11]

$a \cup b := \bigcup\{a,b\}$ (The union $\bigcup x$ of a set, and the binary union $a \cup b := \bigcup \{a,b\}$ ).

[L12]

$(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ( $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ).

[L13]

$\operatorname{dom} R := \{\, a : \exists b\ (a,b) \in R \,\}, \qquad \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$ ").

Verification

technique · direct

1.1

The four sets are pairwise distinct: $u$ has no element; $v$ and $x$ each have exactly one, namely $u$ and $v$ respectively, which differ; and $w$ has both $u$ and $v$ , so it differs from all three. Hence $A$ has exactly four elements and $B$ exactly two.

L7L8L10L11

2.1

$f$ is a function $A \to B$ : its four pairs have distinct first coordinates, so it is single valued; its domain is $A$ and its range is $B$ . It is surjective, since $u = f(u)$ and $v = f(w)$ , so $f[A] = B$ .

L3L6L9L12L13step 1.1

3.1

$\ker f$ is as displayed: a pair $(a,a')$ of elements of $A$ lies in it exactly when $f(a) = f(a')$ , and $f$ takes the value $u$ exactly at $u$ and $v$ , and the value $v$ exactly at $w$ and $x$ ; so the pairs are those with both coordinates in $\{u,v\}$ or both in $\{w,x\}$ . By the general lemma it is an equivalence relation on $A$ .

L1L12step 1.1step 2.1

4.1

The classes are $[u] = [v] = \{u,v\}$ and $[w] = [x] = \{w,x\}$ , so $A/{\ker f}$ has exactly the two elements $\{u,v\}$ and $\{w,x\}$ , and the quotient map sends $u$ and $v$ to the first and $w$ and $x$ to the second.

L4L5L7step 3.1

5.1

The canonical factorisation is as displayed: $\bar f$ sends $\{u,v\} = [u]$ to $f(u) = u$ and $\{w,x\} = [w]$ to $f(w) = v$ , and it is a bijection onto $f[A] = B$ ; the inclusion $\iota$ is the identity on $B$ because $f[A] = B$ ; and composing gives back $f$ .

L2L6step 2.1step 3.1step 4.1∎

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

A symmetric and transitive relation on a two-element set that is not reflexive on it

Statement refuted

Refuted claim: a symmetric and transitive relation on a set $A$ is reflexive on $A$ . Write $u := \varnothing$ and $v := \{\varnothing\}$ , put $A := \{u,v\}$ and

$R := \{(u,u)\}.$

$R$ is a relation on $A$ that is symmetric and transitive, and it is not reflexive on $A$ , because $(v,v) \notin R$ .

The failure is located exactly at the point of $A$ that $R$ does not touch: $R$ is reflexive on its own field $\{u\}$ , and symmetry and transitivity constrain $R$ only there.

Facts & Assumptions

Given: $u := \varnothing$ , $v := \{\varnothing\}$ , $A := \{u,v\}$ and $R := \{(u,u)\}$ .

[L1]

$R$ is reflexive on $A$ when $(a,a) \in R$ for every $a \in A$ (Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set).

[L2]

$R$ is symmetric when $(a,b) \in R$ implies $(b,a) \in R$ , for all $a, b \in A$ (Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set).

[L3]

$R$ is transitive when $(a,b) \in R$ and $(b,c) \in R$ imply $(a,c) \in R$ , for all $a, b, c \in A$ (Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set).

[L4]

A relation is a set $R$ every element of which is an ordered pair (Relation, $\operatorname{dom} R$ , $\operatorname{ran} R$ , $\operatorname{fld} R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L5]

$\operatorname{dom} R := \{\, a : \exists b\ (a,b) \in R \,\}, \qquad \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$ ").

[L6]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[L7]

$\{x,y\}$ is the set whose elements are exactly $x$ and $y$ , and $\{x\} := \{x,x\}$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L8]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

[L9]

$(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ( $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ).

[L10]

$(a,b) := \{\{a\},\{a,b\}\}$ (The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$ ).

[L11]

$z \in a \cup b$ holds if and only if $z \in a$ or $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$ ).

[L12]

$a \cup b := \bigcup\{a,b\}$ (The union $\bigcup x$ of a set, and the binary union $a \cup b := \bigcup \{a,b\}$ ).

Counterexample

technique · direct

1.1

$u \neq v$ , because $v$ has the element $u$ and $u$ has none; so $A$ has exactly the two elements $u$ and $v$ .

L6L7

2.1

$R$ is a relation on $A$ : its only element is the ordered pair $(u,u)$ , and both coordinates lie in $A$ , so $R \subseteq A \times A$ .

L4L8L10step 1.1

3.1

The three characteristic sets of $R$ are $\operatorname{dom} R = \operatorname{ran} R = \operatorname{fld} R = \{u\}$ , since $(u,u)$ is its only pair.

L5L7L9L11L12step 2.1

3.2

$R$ is symmetric: the only pair in $R$ is $(u,u)$ , whose reversal is itself. It is transitive: the only composable pair of members is $(u,u)$ with $(u,u)$ , and the required conclusion $(u,u) \in R$ holds.

L2L3L9step 2.1

4.1

$R$ is reflexive on $\operatorname{fld} R$ : the only element of $\{u\}$ is $u$ , and $(u,u) \in R$ .

L1L7step 3.1

5.1

$R$ is not reflexive on $A$ : $v \in A$ , and $(v,v) \neq (u,u)$ because $v \neq u$ , so $(v,v) \notin R$ . The failure is therefore confined to the single element of $A$ lying outside $\operatorname{fld} R$ ; symmetry and transitivity say nothing about such a point, which is exactly why they do not imply reflexivity on $A$ .

L1L9step 1.1step 2.1step 3.1step 3.2step 4.1∎

False statementConstruction: Literature-sourcedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

FALSE: a symmetric and transitive relation on a set $A$ is reflexive on $A$ , so reflexivity is redundant in the definition of an equivalence relation

Statement

False statement. If a relation $R$ on a set $A$ is symmetric and transitive, then it is reflexive on $A$ ; consequently the reflexivity clause in the definition of an equivalence relation follows from the other two and could be dropped.

Facts & Assumptions

Given: the claim above.

[L1]

$R$ is reflexive on $A$ when $(a,a) \in R$ for every $a \in A$ (Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set).

[L2]

$R$ is symmetric when $(a,b) \in R$ implies $(b,a) \in R$ , for all $a, b \in A$ (Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set).

[L3]

$R$ is transitive when $(a,b) \in R$ and $(b,c) \in R$ imply $(a,c) \in R$ , for all $a, b, c \in A$ (Reflexive, irreflexive, symmetric, asymmetric, antisymmetric, transitive, and connex relations on a set).

[L4]

A binary relation $\sim$ on $A$ is an equivalence relation when it is reflexive, symmetric and transitive (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$ ).

[L5]

$R$ is a relation on $A$ when $R \subseteq A \times A$ (Relation, $\operatorname{dom} R$ , $\operatorname{ran} R$ , $\operatorname{fld} R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[L6]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

[L7]

$(a,b) := \{\{a\},\{a,b\}\}$ (The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$ ).

[L8]

$\{x,y\}$ is the set whose elements are exactly $x$ and $y$ , and $\{x\} := \{x,x\}$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L9]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

Refutation

technique · direct

1.1

The argument that makes the claim look right: given $a \in A$ , take any $b$ with $(a,b) \in R$ ; symmetry gives $(b,a) \in R$ , and transitivity applied to $(a,b)$ and $(b,a)$ gives $(a,a) \in R$ .

L1L2L3

1.2

The witness: put $u := \varnothing$ , $v := \{\varnothing\}$ , $A := \{u,v\}$ and $R := \{(u,u)\}$ . Here $u \neq v$ , because $v$ has an element and $u$ has none.

L8L9

2.1

The gap in step 1.1 is the phrase "take any $b$ with $(a,b) \in R$ ": no hypothesis supplies such a $b$ . Symmetry and transitivity are conditional on pairs that are already in $R$ , so they constrain $R$ only at points that $R$ relates to something, and say nothing whatever about a point of $A$ that $R$ leaves untouched.

L2L3step 1.1

2.2

$R$ is a relation on $A$ : its only element is the ordered pair $(u,u)$ , whose coordinates both lie in $A$ .

L5L6L7step 1.2

2.3

$R$ is symmetric, since its only pair is its own reversal, and transitive, since the only composable pair of its members is $(u,u)$ with $(u,u)$ , whose conclusion $(u,u) \in R$ holds.

L2L3step 1.2

3.1

$R$ is not reflexive on $A$ : $v$ is an element of $A$ and $(v,v) \notin R$ , since the only element of $R$ is $(u,u)$ and $v \neq u$ .

L1L7L8step 1.2step 2.2

4.1

The claim is therefore false, and with it the conclusion drawn from it: the reflexivity clause in the definition of an equivalence relation is not redundant, since $R$ satisfies the other two clauses on $A$ and is not an equivalence relation on $A$ .

L4step 2.1step 2.3step 3.1∎

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

A function $f$ and sets $S, T$ with $f[S \cap T] \subsetneq f[S] \cap f[T]$

Statement refuted

Refuted claim: $f[S \cap T] = f[S] \cap f[T]$ for every function $f : A \to B$ and all $S, T \subseteq A$ . Write $u := \varnothing$ and $v := \{\varnothing\}$ , and take

$A := \{u,v\}, \qquad B := \{u\}, \qquad f := \{(u,u),(v,u)\}, \qquad S := \{u\}, \qquad T := \{v\}.$

Then $S \cap T = \varnothing$ , so $f[S \cap T] = \varnothing$ , while $f[S] = f[T] = \{u\}$ and therefore $f[S] \cap f[T] = \{u\}$ . The inclusion $f[S \cap T] \subseteq f[S] \cap f[T]$ of 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 is proper here, and it is proper exactly because $f$ is not injective.

Facts & Assumptions

Given: $u := \varnothing$ , $v := \{\varnothing\}$ , $A := \{u,v\}$ , $B := \{u\}$ , $f := \{(u,u),(v,u)\}$ , $S := \{u\}$ and $T := \{v\}$ .

[L1]

$f[S \cap T] \subseteq f[S] \cap f[T]$ (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).

[L2]

$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).

[L3]

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).

[L4]

$f$ is injective (one-to-one) if $f(x) = f(y)$ implies $x = y$ , for all $x, y \in A$ (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,y\}$ is the set whose elements are exactly $x$ and $y$ , and $\{x\} := \{x,x\}$ (The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$ ).

[L7]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[L8]

$(a,b) := \{\{a\},\{a,b\}\}$ (The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$ ).

[L9]

$\operatorname{dom} R := \{\, a : \exists b\ (a,b) \in R \,\}, \qquad \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$ ").

[L10]

$z \in a \cup b$ holds if and only if $z \in a$ or $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$ ).

[L11]

$a \cup b := \bigcup\{a,b\}$ (The union $\bigcup x$ of a set, and the binary union $a \cup b := \bigcup \{a,b\}$ ).

Counterexample

technique · direct

1.1

$u \neq v$ , since $v$ has an element and $u$ has none; so $A$ has exactly the two elements $u$ and $v$ , and $S$ and $T$ are the two singletons inside it.

L6L7

2.1

$f$ is a function $A \to B$ : its two pairs have distinct first coordinates, so it is single valued; its domain is $A$ and its range is $\{u\} = B$ . It is not injective, since $f(u) = u = f(v)$ while $u \neq v$ .

L3L4L8L9step 1.1

2.2

$S \cap T$ has no element, since an element would have to equal both $u$ and $v$ ; so $S \cap T = \varnothing$ and $f[S \cap T] = \varnothing$ , no element of $\varnothing$ being related to anything.

L2L5L6L7step 1.1

3.1

$f[S] = \{u\}$ and $f[T] = \{u\}$ , since $f(u) = u$ and $f(v) = u$ ; hence $f[S] \cap f[T] = \{u\}$ .

L2L5L6step 2.1

4.1

The general inclusion holds and is proper here: $u$ lies in $f[S] \cap f[T]$ and not in $f[S \cap T]$ , which has no element at all.

L1L7L10L11step 2.2step 3.1∎

ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)Open item page →

For any indexed family the product $\prod_{i \in I} \mathcal{P}(X_i)$ contains the constant function with value $\varnothing$ , and $\prod_{i \in I} \{i\}$ has exactly one element

Example

Two families whose products can be shown nonempty by writing an element down, with no choice principle involved.

Let $(X_i)_{i \in I}$ be any indexed family. Then $(\mathcal{P}(X_i))_{i \in I}$ is an indexed family, and the constant function $c := \{\,(i,\varnothing) : i \in I\,\}$ is an element of $\prod_{i \in I} \mathcal{P}(X_i)$ . So that product is nonempty for every $I$ and every family, even when some $X_i$ is empty.
Let $I$ be any set and let $(\{i\})_{i \in I}$ be the family carrying the singleton of the index at each index. Then $\prod_{i \in I} \{i\} = \{\Delta_I\}$ : its only element is the identity relation on $I$ .

Neither construction selects anything: in the first the value is the same set at every index, and in the second the value at $i$ is forced to be $i$ .

Facts & Assumptions

Given: an indexed family $(X_i)_{i \in I}$ and a set $I$ .

[L1]

an element of $\prod_{i \in I} A_i$ is a function with domain $I$ that takes its value at each index inside the member carried by that index (The product $\prod_{i \in I} A_i := \{\, f : I \to \bigcup_{i \in I} A_i \ \mid\ f(i) \in A_i \text{ for every } i \in I \,\}$ ).

[L2]

An indexed family with index set $I$ is a function $A$ with $\operatorname{dom} A = I$ (An indexed family $(A_i)_{i \in I}$ is a function with domain $I$ ; $\{A_i : i \in I\}$ is its range).

[L3]

$z \in \mathcal{P}(x)$ holds if and only if $z \subseteq x$ (The power set $\mathcal{P}(x) = \{\, z : z \subseteq x \,\}$ ).

[L4]

(i) $\varnothing \subseteq x$ ( $\varnothing \subseteq x$ , $x \subseteq x$ , inclusion is transitive, and $x = y$ if and only if $x \subseteq y$ and $y \subseteq x$ ).

[L5]

A function is a relation $f$ such that $(a,b) \in f$ and $(a,c) \in f$ imply $b = c$ (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).

[L6]

There is exactly one set with no elements, written $\varnothing$ (There is exactly one set with no elements, written $\varnothing$ ).

[L7]

$\Delta_A$ is a function with $\operatorname{dom} \Delta_A = A$ and $\Delta_A(a) = a$ for every $a \in A$ (If $f$ and $g$ are functions then $g \circ f$ is a function with domain $f^{-1}[\operatorname{dom} g]$ and $(g \circ f)(x) = g(f(x))$ there; $\Delta_A$ is a function with $\Delta_A(a) = a$ ; and $f \circ \Delta_A = f = \Delta_B \circ f$ for $f : A \to B$ ).

[L8]

$(a,b) \in \Delta_A$ holds if and only if $a = b$ and $a \in A$ (The identity relation $\Delta_A = \{\,(a,b) \in A \times A : a = b\,\}$ and the membership relation $\in_A\, = \{\,(a,b) \in A \times A : a \in b\,\}$ ).

[L9]

$\{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\}$ ).

[L10]

if $I = \varnothing$ then $\prod_{i \in I} A_i = \{\varnothing\}$ ( $\prod_{i \in \varnothing} A_i = \{\varnothing\}$ ; if $A_j = \varnothing$ for some $j \in I$ then $\prod_{i \in I} A_i = \varnothing$ ; and for $I = \{j\}$ the evaluation $f \mapsto f(j)$ is a bijection $\prod_{i \in I} A_i \to A_j$ ).

[L11]

For any parameters $\bar p$ and any set $x$ , there is a set $y$ whose elements are exactly the elements $z$ of $x$ for which $\varphi(z,\bar p)$ holds (The Axiom Schema of Separation: for each formula $\varphi$ , $\forall \bar p\,\forall x\,\exists y\,\forall z\,(z \in y \leftrightarrow (z \in x \wedge \varphi(z,\bar p)))$ ).

[L12]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

[L13]

$\operatorname{dom} R := \{\, a : \exists b\ (a,b) \in R \,\}, \qquad \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$ ").

[L14]

$z \in \bigcup_{i \in I} A_i$ holds if and only if $z \in A_i$ for some $i \in I$ ( $\bigcup_{i \in I} A_i := \bigcup \{A_i : i \in I\}$ , and $\bigcap_{i \in I} A_i := \bigcap \{A_i : i \in I\}$ for $I \neq \varnothing$ ).

Verification

technique · direct

1.1

$(\mathcal{P}(X_i))_{i \in I}$ is an indexed family: separating inside $I \times \mathcal{P}(\mathcal{P}(\bigcup_{i \in I} X_i))$ with the formula $\exists i\,\exists w\,(z = (i,w) \wedge i \in I \wedge w = \mathcal{P}(X_i))$ gives a set, which is single valued and has domain $I$ ; the ambient set contains each $\mathcal{P}(X_i)$ , since every subset of $X_i$ is a subset of $\bigcup_{i \in I} X_i$ .

L2L3L5L11L12L13L14

1.2

Similarly $(\{i\})_{i \in I}$ is an indexed family, obtained by separating inside $I \times \mathcal{P}(I)$ , since $\{i\} \subseteq I$ for $i \in I$ .

L2L3L5L9L11L12L13

2.1

The constant function $c := \{\,(i,\varnothing) : i \in I\,\}$ is a set, by separating inside $I \times \{\varnothing\}$ ; it is single valued, has domain $I$ , and $c(i) = \varnothing$ for every $i \in I$ . Since $\varnothing \subseteq X_i$ , we have $\varnothing \in \mathcal{P}(X_i)$ for every $i$ , so $c$ lies in $\prod_{i \in I} \mathcal{P}(X_i)$ and that product is nonempty.

L1L3L4L5L6L9L11L12L13step 1.1

2.2

$\Delta_I$ is a function with domain $I$ and $\Delta_I(i) = i$ , and $i$ is the only element of $\{i\}$ , so $\Delta_I \in \prod_{i \in I} \{i\}$ . Conversely any $f$ in that product has domain $I$ and $f(i) \in \{i\}$ , hence $f(i) = i$ for every $i \in I$ , so $f$ and $\Delta_I$ are functions with the same domain agreeing everywhere and are equal.

L1L5L7L8L9step 1.2

3.1

Both products are therefore nonempty, and the second has exactly one element; when $I = \varnothing$ both statements agree with the general computation of the empty product, whose single element is the empty function.

L10step 2.1step 2.2∎

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-06 (claude-opus-5)‡ rests on unproved materialOpen item page →

‡ Rests on 1 statement not proved in this library. Every dependency marked ‡ below is recorded with a citation but is not established here, because the track that would prove it has not yet been developed in this library. Everything else in this proof is proved here.

FALSE: assuming ZF is consistent, ZF proves that every surjection $f : A \to B$ has a right inverse $g : B \to A$ with $f \circ g = \Delta_B$

Statement

False statement. Assume ZF is consistent. Then ZF proves that every surjection $f : A \to B$ has a right inverse, that is, a function $g : B \to A$ with $f \circ g = \Delta_B$ .

The consistency assumption is not decoration: an inconsistent ZF proves everything, so without it the claim would be unrefutable.

Facts & Assumptions

Given: ZF is consistent, and the claim above.

‡ [A1]

If ZF is consistent, then ZF does not prove the Axiom of Choice (Cohen 1963, Cohen 1963: ZF does not prove the Axiom of Choice ‡). This is an external result, established by forcing and quoted rather than proved here.

[L1]

$f$ is surjective (onto) if for every $b \in B$ there is some $x \in A$ with $f(x) = b$ (Injection, surjection, bijection).

[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]

an element of $\prod_{i \in I} A_i$ is a function with domain $I$ that takes its value at each index inside the member carried by that index (The product $\prod_{i \in I} A_i := \{\, f : I \to \bigcup_{i \in I} A_i \ \mid\ f(i) \in A_i \text{ for every } i \in I \,\}$ ).

[L4]

if $A_j = \varnothing$ for some $j \in I$ then $\prod_{i \in I} A_i = \varnothing$ ( $\prod_{i \in \varnothing} A_i = \{\varnothing\}$ ; if $A_j = \varnothing$ for some $j \in I$ then $\prod_{i \in I} A_i = \varnothing$ ; and for $I = \{j\}$ the evaluation $f \mapsto f(j)$ is a bijection $\prod_{i \in I} A_i \to A_j$ ).

[L5]

$g \circ f$ is a function, $\operatorname{dom}(g \circ f) = f^{-1}[\operatorname{dom} g]$ , and $(g \circ f)(x) = g(f(x))$ for every $x$ in that domain (If $f$ and $g$ are functions then $g \circ f$ is a function with domain $f^{-1}[\operatorname{dom} g]$ and $(g \circ f)(x) = g(f(x))$ there; $\Delta_A$ is a function with $\Delta_A(a) = a$ ; and $f \circ \Delta_A = f = \Delta_B \circ f$ for $f : A \to B$ ).

[L6]

$\Delta_A$ is a function with $\operatorname{dom} \Delta_A = A$ and $\Delta_A(a) = a$ for every $a \in A$ (If $f$ and $g$ are functions then $g \circ f$ is a function with domain $f^{-1}[\operatorname{dom} g]$ and $(g \circ f)(x) = g(f(x))$ there; $\Delta_A$ is a function with $\Delta_A(a) = a$ ; and $f \circ \Delta_A = f = \Delta_B \circ f$ for $f : A \to B$ ).

[L7]

$(a,b) \in \Delta_A$ holds if and only if $a = b$ and $a \in A$ (The identity relation $\Delta_A = \{\,(a,b) \in A \times A : a = b\,\}$ and the membership relation $\in_A\, = \{\,(a,b) \in A \times A : a \in b\,\}$ ).

[L8]

$z \in A \times B$ holds if and only if $z = (a,b)$ for some $a \in A$ and some $b \in B$ (The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ ).

[L9]

An indexed family with index set $I$ is a function $A$ with $\operatorname{dom} A = I$ (An indexed family $(A_i)_{i \in I}$ is a function with domain $I$ ; $\{A_i : i \in I\}$ is its range).

[L10]

For any parameters $\bar p$ and any set $x$ , there is a set $y$ whose elements are exactly the elements $z$ of $x$ for which $\varphi(z,\bar p)$ holds (The Axiom Schema of Separation: for each formula $\varphi$ , $\forall \bar p\,\forall x\,\exists y\,\forall z\,(z \in y \leftrightarrow (z \in x \wedge \varphi(z,\bar p)))$ ).

[L11]

$\operatorname{dom} R := \{\, a : \exists b\ (a,b) \in R \,\}, \qquad \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$ ").

[L12]

$(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ( $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$ ).

[L13]

$z \in \bigcup_{i \in I} A_i$ holds if and only if $z \in A_i$ for some $i \in I$ ( $\bigcup_{i \in I} A_i := \bigcup \{A_i : i \in I\}$ , and $\bigcap_{i \in I} A_i := \bigcap \{A_i : i \in I\}$ for $I \neq \varnothing$ ).

[L14]

An equivalent formulation of the Axiom of Choice is that a product of nonempty sets is nonempty: if $X_i \ne \varnothing$ for every $i \in I$ , then $\prod_{i \in I} X_i \ne \varnothing$ (The Axiom of Choice).

Refutation

technique · contradiction

1.1

Suppose ZF proves that every surjection has a right inverse.

assume-contra

1.2

Let $(X_i)_{i \in I}$ be any indexed family with $X_i \neq \varnothing$ for every $i \in I$ . Separating inside $I \times \bigcup_{i \in I} X_i$ gives the set $E := \{\,(i,x) : i \in I \wedge x \in X_i\,\}$ , and separating inside $E \times I$ gives $f := \{\,(z,i) \in E \times I : \exists x\,(z = (i,x))\,\}$ , which is a function $E \to I$ sending $(i,x)$ to $i$ .

L2L8L9L10L11L12L13

2.1

$f$ is surjective: for $i \in I$ the set $X_i$ has an element $x$ , so $(i,x) \in E$ and $f((i,x)) = i$ .

L1step 1.2

3.1

By the supposition $f$ has a right inverse $g : I \to E$ with $f \circ g = \Delta_I$ . For $i \in I$ we get $f(g(i)) = i$ , so $g(i) = (i,x)$ for some $x \in X_i$ ; hence $\operatorname{ran} g$ is a set of pairs, one for each $i \in I$ , which is a function with domain $I$ whose value at $i$ lies in $X_i$ . That function is an element of $\prod_{i \in I} X_i$ , so that product is nonempty.

L3L5L6L7L11L12step 1.1step 1.2step 2.1

4.1

So ZF would prove that a product of nonempty sets is nonempty, over an arbitrary index set, which is the product formulation of the Axiom of Choice (The Axiom of Choice); note that the hypothesis $X_i \neq \varnothing$ is exactly what rules out the collapse of the product recorded in the cited computation of small products. Under the assumption that ZF is consistent, ZF does not prove the Axiom of Choice, so the supposition is untenable and the claim is false.

‡ A1L4L14step 3.1discharge-contradiction∎

Remarks

What is true, and where the line falls. A two-sided inverse is available without any choice principle, because it is determined rather than selected: that is $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = \Delta_A$ and $f \circ g = \Delta_B$ ; such a $g$ is unique, equals the inverse relation $f^{-1}$ , and is itself a bijection. So is a left inverse for an injection with nonempty domain, For $f : A \to B$ with $A \neq \varnothing$ : $f$ is injective if and only if there is $g : B \to A$ with $g \circ f = \Delta_A$ ; for $A = \varnothing$ the empty function is injective and has a left inverse if and only if $B = \varnothing$ . Only the right inverse of a surjection requires choosing one preimage at each point at once.
The external ingredient. The refutation quotes one result it does not prove, the unprovability of Choice in ZF, and everything else in it is proved on this page's own material.

Relations, Functions, and Quotients: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A four-pair relation on {∅,{∅},{∅,{∅}}}\{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}{∅,{∅},{∅,{∅}}} with its domain, range, field, inverse, restriction, image and self-composite computed

Example

Facts & Assumptions

Verification

Example

Facts & Assumptions

Verification

Relations RRR and SSS on a two-element set with S∘R≠R∘SS \circ R \neq R \circ SS∘R=R∘S

Statement refuted

Facts & Assumptions

Counterexample

A two-cell partition of a three-element set, the equivalence relation it induces listed pair by pair, and the quotient set recovered from it

Example

Facts & Assumptions

Verification

A two-to-one function on a four-element set, its kernel, the quotient, and the canonical factorisation computed explicitly

Example

Facts & Assumptions

Verification

A symmetric and transitive relation on a two-element set that is not reflexive on it

Statement refuted

Facts & Assumptions

Counterexample

FALSE: a symmetric and transitive relation on a set AAA is reflexive on AAA, so reflexivity is redundant in the definition of an equivalence relation

Statement

Facts & Assumptions

Refutation

A function fff and sets S,TS, TS,T with f[S∩T]⊊f[S]∩f[T]f[S \cap T] \subsetneq f[S] \cap f[T]f[S∩T]⊊f[S]∩f[T]

Statement refuted

Facts & Assumptions

Counterexample

For any indexed family the product ∏i∈IP(Xi)\prod_{i \in I} \mathcal{P}(X_i)∏i∈I​P(Xi​) contains the constant function with value ∅\varnothing∅, and ∏i∈I{i}\prod_{i \in I} \{i\}∏i∈I​{i} has exactly one element

Example

Facts & Assumptions

Verification

FALSE: assuming ZF is consistent, ZF proves that every surjection f:A→Bf : A \to Bf:A→B has a right inverse g:B→Ag : B \to Ag:B→A with f∘g=ΔBf \circ g = \Delta_Bf∘g=ΔB​

Statement

Facts & Assumptions

Refutation

Remarks

Sources

Standard references

A four-pair relation on $\{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}$ with its domain, range, field, inverse, restriction, image and self-composite computed

Relations $R$ and $S$ on a two-element set with $S \circ R \neq R \circ S$

FALSE: a symmetric and transitive relation on a set $A$ is reflexive on $A$ , so reflexivity is redundant in the definition of an equivalence relation

A function $f$ and sets $S, T$ with $f[S \cap T] \subsetneq f[S] \cap f[T]$

For any indexed family the product $\prod_{i \in I} \mathcal{P}(X_i)$ contains the constant function with value $\varnothing$ , and $\prod_{i \in I} \{i\}$ has exactly one element

FALSE: assuming ZF is consistent, ZF proves that every surjection $f : A \to B$ has a right inverse $g : B \to A$ with $f \circ g = \Delta_B$