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 with and , the map is a bijection
Statement
Let and be sets, put and let be the family with and , that is, the function . Write . Then
is a bijection .
Facts & Assumptions
Given: sets and , the index set , the family above, and .
an element of is a function with domain that takes its value at each index inside the member carried by that index (The product ).
holds if and only if for some and some (The Cartesian product ).
if and only if and ( if and only if and ).
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).
is the set whose elements are exactly and , and (The unordered pair and the singleton ).
There is exactly one set with no elements, written (There is exactly one set with no elements, written ).
A function is a relation such that and imply (A function is a relation with and implying ; , the value , domain and codomain).
An indexed family with index set is a function with (An indexed family is a function with domain ; is its range).
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 for ).
holds if and only if or (, , , , and ).
Proof
The index set has exactly the two elements and , and they are distinct because the second has an element and the first has none; so is single valued, has domain , and is an indexed family with and .
is a function : for we have and , so the pair lies in ; separating inside gives , it is single valued because that pair is determined by , its domain is , and its range lies in .
is injective: if then the characterising property gives and ; and have the same domain , whose elements are exactly those two, so .
is surjective: given , put . It is single valued because , its domain is , and with , so by the union bound and .
is a function that is injective and surjective, hence a bijection.
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 \,\}$
- 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) \,\}$
- Injection, surjection, bijection
- The unordered pair $\{x,y\}$ and the singleton $\{x\} = \{x,x\}$
- There is exactly one set with no elements, written $\varnothing$
- 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
- $(a,b) = (c,d)$ if and only if $a = c$ and $b = d$
- An indexed family $(A_i)_{i \in I}$ is a function with domain $I$; $\{A_i : i \in I\}$ is its range
- 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
- Relation, $\operatorname{dom} R$, $\operatorname{ran} R$, $\operatorname{fld} R$, and the specialisations "relation from $A$ to $B$" and "relation on $A$"
- 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)))$
- $\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$
- $\bigcup \varnothing = \varnothing$, $\bigcup \{a\} = a$, $\bigcup \{a,b\} = a \cup b$, $\bigcap \{a\} = a$, and $\bigcap \{a,b\} = a \cap b$
Used by
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), Exercise 12 (standard reference, not scraped)
- Cartesian product (Wikipedia) (standard reference, not scraped)
- Indexed family (Wikipedia) (standard reference, not scraped)