A real-valued random variable is a map $X:\Omega \to \mathbb{R}$ measurable from $(\Omega ,\mathcal{F})$ to the Borel real line. Equivalently,Its values are finite real numbers here; extended-real-valued random variables require a correspondingly enlarged target.

For $x\in M$, let $k$ be the unique index such that $g(x)\in B_{n,k}$. Then $f(x)\in A_{n,k}$ and $h_n(f(x))=k{2}^{-n}$. The chosen interval is open on the left and closed on the right, soThis remains correct at dyadic endpoints; changing it to a floor approximation with a non-strict left endpoint would describe a different approximation.

By part (iii), define the finite limit $h(t)={\lim }_n{h}_n(t)$ for every $t\in \mathbb{R}$. Part (a) makes this limit Borel measurable. Letting $n\to \infty$ in the displayed error bound givesThis is the factorization conclusion of the Doob-Dynkin lemma under the specified Borel-image hypothesis.

The two child intervals partition their parent:Their preimages under $g$ satisfy the same identity. Since all $A$ sets lie inside $f(M)$ and $f$ is onto its image, equality of their preimages under $f$ impliesOn the first child, $h_{n+1}=2k{2}^{-n-1}=k{2}^{-n}=h_n$; on the second it is $h_n+2^{-n-1}$. Outside the image both functions are zero. ThusFor $m>n$, summing these bounds givesThis tends to zero uniformly in $m>n$, proving that each real sequence $h_n(t)$ is Cauchy and has a finite limit.

If $t\notin f(M)$, all indicator functions vanish and $h_n(t)=0$. If $t\in f(M)$, the partition in part (i) puts it in exactly one $A_{n,k}$, so exactly one term can be nonzero and the sum is a finite real number at that point. There is no ambiguous infinite sum of positive and negative terms.

For measurability, each symmetric partial sumis Borel measurable by closure under finite linear combinations. For each $t$, these partial sums eventually include its unique possible term and converge to $h_n(t)$. The measurable-limit result from part (a) therefore proves $h_n$ is Borel measurable.

measurability with respect to $\sigma (f)$ gives a Borel set $C_{n,k}$ with $g^{-1}(B_{n,k})=f^{-1}(C_{n,k})$. Restrict it to the actual image:This is Borel by the assumed Borel property of $f(M)$, and its preimage under $f$ is unchanged.

The intervals $B_{n,k}$ partition the real line, so their preimages under $g$ partition $M$. If two of the restricted sets overlapped, a point in their intersection would equal $f(x)$ for some $x$, making $g(x)$ lie in two disjoint intervals, a contradiction. Similarly any $t\in f(M)$ has a preimage $x$, whose real value $g(x)$ belongs to one of those intervals; that puts $t$ in the corresponding $A_{n,k}$. Thus the restricted sets are disjoint and their union is exactly $f(M)$. This restriction is what removes arbitrary overlaps of the initially chosen Borel sets outside the image.

Use the characterization of measurability by preimages of open half-lines, allowing intermediate extended-real-valued functions. Put $u_m={\inf }_{n\ge m}{f}_n$. For each real $a$,Thus every $u_m$ is measurable. Countable suprema are measurable too, since $\{{\sup }_m{u}_m>a\}={\bigcup }_m\{u_m>a\}$ and the upper half-lines also generate the Borel sigma-algebra. Thereforeis measurable. Its values are real by the stated hypothesis, so it is the required ordinary real-valued measurable function, rather than only an extended-real-valued one.

A map between the measurable spaces is measurable whenA real-valued function $f$ on $S$ is $\Sigma$-measurable when it is measurable from $(S,\Sigma )$ to $(\mathbb{R},\mathcal{B}(\mathbb{R}))$. Equivalently each set $\{f<a\}$ is in $\Sigma$, since open half-lines generate the Borel sigma-algebra.

A Borel measurable function on the real line is a function measurable with respect to the Borel sigma-algebra on both its domain and range. Continuity is sufficient for this property, but is not required.

Repeat the preceding construction starting at ${\alpha }_0=\gamma +1$, for any given ordinal $\gamma$. A stabilized value or the strictly increasing sequence's supremum is a fixed point at least $\gamma +1$. Thus fixed points occur above every ordinal.

If the fixed points formed a set $S$, their union would be an ordinal bounding them all. Applying the construction above that bound contradicts it. HenceThis is the unboundedness part of the fixed point of a normal ordinal function theorem.

By the natural-number recursion theorem, let ${\alpha }_0=0$ and ${\alpha }_{n+1}=F({\alpha }_n)$. These ordinals form a nondecreasing sequence by the preceding bound. If ${\alpha }_{n+1}={\alpha }_n$ for some $n$, it is already a fixed point.

Otherwise the sequence is strictly increasing. Its supremum $\lambda ={\bigcup }_{n<\omega }{\alpha }_n$ is a limit ordinal, and the sequence is cofinal in it. Continuity and monotonicity giveFor the middle equality, every $\beta <\lambda$ is below some ${\alpha }_n$, while every ${\alpha }_n<\lambda$. Therefore $F$ has a fixed point. The sequence is a set by Axiom schema of replacement, since $F$ is a definable set-theoretic class function.

Use transfinite induction. For any $\beta <\alpha$, the induction hypothesis and strict increase give $\beta \le F(\beta )<F(\alpha )$. Thus every $\beta <\alpha$ belongs to $F(\alpha )$, so $\alpha \subseteq F(\alpha )$, i.e.This includes $\alpha =0$ and does not yet use continuity of the normal function on an ordinal.

Put $\alpha =\bigcup X$. Every element of $\alpha$ belongs to some ordinal in $X$ and is itself an ordinal. If $u\in v\in \alpha$, choose $\beta \in X$ with $v\in \beta$; transitivity of $\beta$ gives $u\in \beta \subseteq \alpha$. Thus $\alpha$ is a transitive set of ordinals.

Any two ordinals are comparable by membership or equality, so membership strictly totally orders $\alpha$. Every nonempty subset $A\subseteq \alpha$ has an $\in$-minimal element by the Axiom of foundation, and totality makes it the least element. Hence $\bigcup X$ is an ordinal, including $\bigcup \varnothing =0$.

A well-order is a strict total order in which every nonempty subset has a least element. A Von Neumann ordinal is a transitive set well-ordered by membership. Thus its predecessors are precisely its members, and its ordering is the restriction of $\in$.

Let $a\in b\in \mathcal{P}(X)$. Since $b\subseteq X$, we have $a\in X$. Transitivity of $X$ gives $a\subseteq X$, so $a\in \mathcal{P}(X)$. This is exactly the membership criterion for a transitive set, proving the power set of a transitive set is transitive.

A transitive set $X$ is one for which every member is a subset: $\forall y\in X(y\subseteq X)$, equivalently $\bigcup X\subseteq X$. If $x\in y\in X$, the subset condition puts $x\in X$. Conversely, if this membership implication always holds, every element of each $y\in X$ belongs to $X$, so $y\subseteq X$. Thus

Suppose $h:\omega \hookrightarrow X$ is an injection. Shift its image by definingThe two pieces have disjoint images, so $g$ is injective, but $h(0)$ is omitted. Thus $g$ is not surjective.

Conversely, let $g:X\to X$ be an injection which omits some $a\in X$. The natural-number recursion theorem defines $h(0)=a$, $h(n+1)=g(h(n))$. If $h(m)=h(n)$ with $m<n$, repeated injectivity cancels $m$ iterations and gives $a=g^{n-m}(a)$, putting $a$ in the image of $g$, a contradiction. Hence $h$ is injective. ThereforeChoosing one witness $a$ from a single known nonempty set uses no axiom of choice. This is the Dedekind-infinite characterization.

An approximation is a function $s:n+1\to X$ with $s(0)=x_0$ and $s(k+1)=g(s(k))$ for $k<n$. By induction on $n$, there is such a function: start with $\{(0,x_0)\}$ and append the uniquely specified value $g(s(n))$.

Any two approximations agree on their common domain, by induction from their common initial value and the same transition function $g$. The collection $\mathcal{S}$ of all approximations is a set, being a definable subset of $\mathcal{P}(\omega \times X)$. Therefore $f=\bigcup \mathcal{S}$ is a function. Existence of approximations of every finite length gives $\mathrm{dom}(f)=\omega$. Each defining equation appears in a sufficiently long approximation, soThis proves the natural-number recursion theorem without the axiom of choice; no arbitrary sequence of choices was made.

No such first-order axiom collection can force actual identity when the displayed symbol is treated as an ordinary relation. The duplication obstruction to axiomatizing identity proves this even for an infinite collection of extra axioms.

Start with any nonempty first-order structure $\mathcal{A}$ in which the symbol is identity. Form $B=A\times \{0,1\}$ and the surjection $\pi :B\to A$. Interpret each relation by pulling it back along $\pi$; in particular,Interpret every function on first coordinates as in $\mathcal{A}$ and choose second coordinate zero; likewise lift constants with second coordinate zero. Induction on first-order terms gives $\pi (t^{\mathcal{B}}(v))=t^{\mathcal{A}}(\pi v)$. Induction on first-order formulas then givesThe quantifier steps use surjectivity of $\pi$, so every witness in $A$ lifts to $B$.

Every proposed axiom valid with actual equality is therefore true in $\mathcal{B}$ under every assignment, along with A1–A7. But $E^{\mathcal{B}}((a,0),(a,1))$ holds for two different domain elements. Thus those axioms cannot enforce identity. The usual interpretation of logical equality as identity is a semantic requirement.

Write $E(x,y)$ for the displayed equality predicate. A6 and A4 give $⊢E(x,x)$, establishing a reflexive relation.

An instance of A7, replacing just the first occurrence of $x$ in $E(x,x)$, isAssume $E(x,y)$, apply the modus ponens rule twice using reflexivity, and obtain $E(y,x)$. The deduction theorem for propositional logic discharges the assumption. This proves symmetry.

For transitivity, A7 suppliesby replacing $y$ in the atomic formula $E(x,y)$. From assumptions $E(x,y)$ and $E(y,z)$, two applications of the modus ponens rule give $E(x,z)$. Discharging assumptions and universally generalizing givesThus the predicate defines an equivalence relation within the calculus.

In a two-element first-order structure, $\varphi =\forall x_1(x_0=x_1)$ is false for every first-order variable assignment. Blind substitution of $x_1$ for $x_0$ yields $\forall x_1(x_1=x_1)$, which is true. This does not express the original property evaluated at the value of the inserted term: it has changed a free parameter into a bound variable.

For a direct failure of the substitution axiom, use $\theta (x_0)=\exists x_1(x_0\ne x_1)$. On a two-element domain, $\forall x_0\theta (x_0)$ is true, whereas the captured instance $\exists x_1(x_1\ne x_1)$ is false. Consequently an unrestricted A4 would prove a false implication. The free for substitution condition is necessary for soundness.

Take $\varphi =\forall x_1(x_0=x_1)$. The term $x_2$ is free for substitution for $x_0$: its variable is not bound by the enclosing quantifier. The term $x_1$ is not free for substitution for $x_0$, because insertion under $\forall x_1$ captures that occurrence.

Thus the first substitution gives $\forall x_1(x_2=x_1)$; the second, illegitimate substitution would give $\forall x_1(x_1=x_1)$.