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.
; if for some then ; and for the evaluation is a bijection
Statement
Let be an indexed family. Then
- (i) if then ;
- (ii) if for some then ;
- (iii) if then the evaluation is a bijection .
Clauses (i) and (ii) pull in opposite directions and are the two cases most often mis-stated: an empty index set gives a product with one element, while a single empty member collapses the product entirely.
Facts & Assumptions
Given: an indexed family .
an element of is a function with domain that takes its value at each index inside the member carried by that index (The product ).
A function is a relation such that and imply (A function is a relation with and implying ; , the value , domain and codomain).
is injective (one-to-one) if implies , for all (Injection, surjection, bijection).
is surjective (onto) if for every there is some with (Injection, surjection, bijection).
if and only if and for every (Functions and are equal if and only if and for every in that common domain).
There is exactly one set with no elements, written (There is exactly one set with no elements, written ).
is the set whose elements are exactly and , and (The unordered pair and the singleton ).
For any parameters and any set , there is a set whose elements are exactly the elements of for which holds (The Axiom Schema of Separation: for each formula , ).
holds if and only if for some and some (The Cartesian product ).
holds if and only if for some (, and for ).
If every satisfies if and only if , then (The Axiom of Extensionality: ).
Proof
Claim (i): let . A function with domain has no elements, since each of its elements would be a pair whose first coordinate lies in its domain, so the only such function is ; and it satisfies the condition " for every " vacuously. Hence is the only element of the product, and the product is .
Claim (ii): let with . An element of the product would satisfy , and has no elements; so the product has no elements.
Claim (iii), the map: let and write . Each has , so as displayed is a set by separation inside , is single valued because is, has domain , and has range inside ; thus with .
Claim (iii), injectivity: if for , then and have the same domain and agree at , hence are equal.
Claim (iii), surjectivity: let and put . This is a function with domain and , and lies in , so and .
Claims (i), (ii) and (iii) are established, which is the statement.
Remarks
- Where the general question is settled, and where it is not. These three computations use no choice principle: in (i) and (ii) nothing is selected, and in (iii) the single value is determined. None of them is an instance of the general question, because each names its elements outright. Whether a product of nonempty members over an arbitrary index set is nonempty is that general question, and it is exactly the product formulation of the Axiom of Choice, stated earlier on this page at The Axiom of Choice; clause (ii) is the reason that formulation carries the hypothesis that every member is nonempty.
Depends on
- 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 \,\}$
- 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
- Injection, surjection, bijection
- There is exactly one set with no elements, written $\varnothing$
- Relation, $\operatorname{dom} R$, $\operatorname{ran} R$, $\operatorname{fld} R$, and the specialisations "relation from $A$ to $B$" and "relation on $A$"
- The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$
- 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)))$
- 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) \,\}$
- Functions $f$ and $g$ are equal if and only if $\operatorname{dom} f = \operatorname{dom} g$ and $f(x) = g(x)$ for every $x$ in that common domain
- $\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$
- The Axiom of Extensionality: $\forall x\,\forall y\,(\forall z\,(z \in x \leftrightarrow z \in y) \to x = y)$
Used by
- ∅ is a relation on every set, is the unique equivalence relation on ∅, is a function ∅ → B for every B, is a bijection ∅ → ∅, and is not a surjection ∅ → {∅} Example
- For any indexed family the product ∏_i ∈ I P(Xᵢ) contains the constant function with value ∅, and ∏_i ∈ I {i} has exactly one element Example
- FALSE: assuming ZF is consistent, ZF proves that every surjection f : A → B has a right inverse g : B → A with f ∘ g = Δ_B False statement
- The Axiom of Choice is stated on this page and assumed by no proof on it; the two statements that would need it are identified and left unsettled Remark
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 31 results over 14 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
- B. Kaya, MATH 320 Set Theory (METU), Def. 21 and Exercise 13 (standard reference, not scraped)
- Cartesian product (Wikipedia) (standard reference, not scraped)
- Empty product (Wikipedia) (standard reference, not scraped)