Foundations for Measure Theory

Fix \(x\). Then \(x\in\left(\bigcup_i A_i\right)^c\iff x\notin\bigcup_i A_i\iff\neg(\exists i:\ x\in A_i)\iff\forall i:\ x\notin A_i\iff\forall i:\ x\in A_i^c\iff x\in\bigcap_i A_i^c.\) This proves the first identity. For the second, apply the first to \((A_i^c)_{i\in I}\): \(\left(\bigcup_i A_i^c\right)^c=\bigcap_i (A_i^c)^c=\bigcap_i A_i\); complementing both sides gives \(\bigcup_i A_i^c=\left(\bigcap_i A_i\right)^c\).

Difference. \(x\in f^{-1}(B_1\setminus B_2)\iff f(x)\in B_1\text{ and }f(x)\notin B_2\iff x\in f^{-1}(B_1)\text{ and }x\notin f^{-1}(B_2)\iff x\in f^{-1}(B_1)\setminus f^{-1}(B_2).\)

Arbitrary union. \(x\in f^{-1}\!\left(\bigcup_iB_i\right)\iff f(x)\in\bigcup_iB_i\iff\exists i:\ f(x)\in B_i\iff\exists i:\ x\in f^{-1}(B_i)\iff x\in\bigcup_i f^{-1}(B_i).\) The argument is index-set agnostic.

Union (equality). \(y\in f(A_1\cup A_2)\iff\exists x\in A_1\cup A_2:\ f(x)=y\iff(\exists x\in A_1:f(x)=y)\text{ or }(\exists x\in A_2:f(x)=y)\iff y\in f(A_1)\cup f(A_2).\)

Intersection (inclusion). If \(y\in f(A_1\cap A_2)\), there is \(x\in A_1\cap A_2\) with \(f(x)=y\); then \(x\) witnesses \(y\in f(A_1)\) and \(y\in f(A_2)\), so \(y\in f(A_1)\cap f(A_2)\).

Strictness. Let \(f:\{-1,1\}\to\mathbb R\), \(f(x)=x^2\), with \(A_1=\{-1\},A_2=\{1\}\). Then \(A_1\cap A_2=\varnothing\) so \(f(A_1\cap A_2)=\varnothing\), yet \(f(A_1)\cap f(A_2)=\{1\}\cap\{1\}=\{1\}\). The inclusion is strict.

Intersection. \(\mathbf 1_{A\cap B}(x)=1\iff x\in A\wedge x\in B\iff\mathbf 1_A(x)=\mathbf 1_B(x)=1\iff\mathbf 1_A(x)\mathbf 1_B(x)=1.\) Both are \(0/1\), so equal.

Complement. If \(x\in A\), \(\mathbf 1_{A^c}(x)=0=1-1\); if \(x\notin A\), \(=1=1-0\).

Union. \(\mathbf 1_{A\cup B}=1-\mathbf 1_{(A\cup B)^c}=1-\mathbf 1_{A^c\cap B^c}=1-(1-\mathbf 1_A)(1-\mathbf 1_B)=\mathbf 1_A+\mathbf 1_B-\mathbf 1_A\mathbf 1_B.\)

Order. \(A\subseteq B\iff(x\in A\Rightarrow x\in B)\iff\) there is no \(x\) with \(\mathbf 1_A(x)=1,\mathbf 1_B(x)=0\iff\mathbf 1_A\le\mathbf 1_B\) pointwise.

Formula. \(x\in A\triangle B\) means \(x\) is in exactly one of \(A,B\), i.e. \(x\in A\setminus B\) or \(x\in B\setminus A\); hence \(A\triangle B=(A\setminus B)\cup(B\setminus A)\).

Indicator form. \(\mathbf 1_{A\triangle B}\equiv\mathbf 1_A+\mathbf 1_B\pmod 2\) (equals \(1\) iff exactly one term is \(1\)).

Associativity. Working in \(\mathbb Z/2\mathbb Z\): \(\mathbf 1_{(A\triangle B)\triangle C}\equiv(\mathbf 1_A+\mathbf 1_B)+\mathbf 1_C\) and \(\mathbf 1_{A\triangle(B\triangle C)}\equiv\mathbf 1_A+(\mathbf 1_B+\mathbf 1_C)\). Since \(+\) is associative in \(\mathbb Z/2\mathbb Z\), the two indicators are equal pointwise, so the sets are equal. Explicitly, both equal \(\{x:\ x\text{ lies in an odd number of }A,B,C\}\).

Let \(x\in\liminf A_n\). By definition there is \(m\) with \(x\in\bigcap_{k\ge m}A_k\), i.e. \(x\in A_k\) for all \(k\ge m\). Fix any \(n\ge1\) and set \(k_0=\max(n,m)\ge n\). Since \(k_0\ge m\), \(x\in A_{k_0}\), so \(x\in\bigcup_{k\ge n}A_k\). As \(n\) was arbitrary, \(x\in\bigcap_n\bigcup_{k\ge n}A_k=\limsup A_n\). Hence \(\liminf A_n\subseteq\limsup A_n\).

Fix \(x\) and write \(a_n=\mathbf 1_{A_n}(x)\in\{0,1\}\). Then \(\limsup_n a_n=\inf_n\sup_{k\ge n}a_k\). Since each \(\sup_{k\ge n}a_k\in\{0,1\}\), it equals \(1\) iff some \(a_k=1\) with \(k\ge n\); the infimum over \(n\) is \(1\) iff this holds for every \(n\), i.e. \(a_k=1\) for infinitely many \(k\), i.e. \(x\in A_k\) infinitely often, i.e. \(x\in\limsup A_n\) (Thm. 1.3). Thus \(\limsup_n a_n=\mathbf 1_{\limsup A_n}(x)\). Dually, \(\liminf_n a_n=1\iff a_k=1\) for all large \(k\iff x\in A_k\) eventually \(\iff x\in\liminf A_n\).

Increasing. Since \(A_n\subseteq A_{n+1}\), for each \(n\) we have \(\bigcap_{k\ge n}A_k=A_n\) (the smallest tail index) and \(\bigcup_{k\ge n}A_k=\bigcup_{k\ge1}A_k=:U\) (adding later, larger sets changes nothing). Hence \(\liminf A_n=\bigcup_n A_n=U\) and \(\limsup A_n=\bigcap_n U=U\). Both equal \(U\).

Decreasing. If \(A_n\downarrow\), then \(A_n^c\uparrow\), so by the increasing case \(\liminf A_n^c=\limsup A_n^c=\bigcup_n A_n^c=\left(\bigcap_n A_n\right)^c\). Complementing and using \((\limsup A_n)^c=\liminf A_n^c\) (Ex. 1.20) gives \(\liminf A_n=\limsup A_n=\bigcap_n A_n\).

(a) For \(x\le0\): never in \(A_n\) unless \(x=0\) (\(0\in A_n\) always), so \(0\) is in both. For \(0<x<1\): eventually \(1-\tfrac1n>x\) and always \(1+\tfrac1n>x\), so \(x\in A_n\) for all large \(n\) - in liminf. For \(x=1\): \(1\in A_n\) iff \(1\le1+\tfrac{(-1)^n}{n}\), true for even \(n\), false for odd \(n\): infinitely often but not eventually. For \(1<x\): \(x\in A_n\) needs \(1+\tfrac1n\ge x\) (even \(n\)), i.e. \(n\le\tfrac1{x-1}\): finitely many. Hence \(\liminf A_n=[0,1)\) and \(\limsup A_n=[0,1]\).

(b) Odd tails shrink from the left: \(\bigcap\) of odd \(A_n=(-\tfrac1n,1]\) contributes eventual membership on \([0,1]\)? A point \(x\in(0,1]\) is in every odd \(A_n\) and in even \(A_n=[0,2-\tfrac1n)\) once \(2-\tfrac1n>x\), i.e. eventually - so \((0,1]\subseteq\liminf\). \(x=0\): in every even \(A_n\) (\(0\in[0,2-\tfrac1n)\)) but \(0\notin(-\tfrac1n,1]\)? Actually \(0\in(-\tfrac1n,1]\), so \(0\in\) all \(A_n\): \(0\in\liminf\). For \(1<x<2\): in \(A_n\) only for even \(n\) with \(2-\tfrac1n>x\) - cofinitely many even \(n\), but no odd \(n\): infinitely often, not eventually. So \(\liminf A_n=[0,1]\) and \(\limsup A_n=[0,2)\).

Step 1: count the grid. Traverse \(\mathbb N\times\mathbb N\) by diagonals \(n+k=2,3,\ldots\). Each diagonal is finite and every pair appears once, so there is a bijection \(e:\mathbb N\to\mathbb N\times\mathbb N\). Equivalently, shift to \(\mathbb N_0\) and use the Cantor pairing of Exercise 1.11.

Step 2: count the union. Let \((A_n)_{n\ge1}\) be countable and discard empty terms. Choose surjections \(g_n:\mathbb N\to A_n\). Define \(G(n,k)=g_n(k)\). If \(y\in\bigcup_nA_n\), then \(y\in A_n\) for some \(n\), hence \(y=g_n(k)\) for some \(k\). Therefore \(G\) is onto, so \(G\circ e:\mathbb N\to\bigcup_nA_n\) is onto. The union is countable.

Step 3: apply this to \(\mathbb Q\). For each positive integer \(q\), let \(B_q=\{p/q:p\in\mathbb Z\}\). Each \(B_q\) is countable because \(\mathbb Z\) is countable, and \[ \mathbb Q=\bigcup_{q\ge1}B_q. \] Hence \(\mathbb Q\) is countable. It is infinite because it contains \(\mathbb N\), so it is countably infinite.

Write \(d=m+n\); then \(\pi(m,n)=T_d+n\) with \(T_d=\tfrac{d(d+1)}2\) and \(0\le n\le d\). The values for a fixed \(d\) fill exactly \(\{T_d,T_d+1,\dots,T_d+d\}=\{T_d,\dots,T_{d+1}-1\}\), since \(T_{d+1}-T_d=d+1\). These blocks partition \(\mathbb N_0\) as \(d=0,1,2,\dots\). Injective: distinct \((m,n)\) with the same \(d\) give distinct \(n\), hence distinct values; distinct \(d\) land in disjoint blocks. Surjective: given \(N\), let \(d\) be maximal with \(T_d\le N\) (exists since \(T_d\to\infty\)); then \(0\le N-T_d\le d\), so \(n=N-T_d\), \(m=d-n\ge0\) satisfy \(\pi(m,n)=N\). Thus \(\pi\) is a bijection. Consequently \(\mathbb N\times\mathbb N\) is countable; and \(\mathbb Z\) is countable via \(0,1,-1,2,-2,\dots\) (an explicit bijection with \(\mathbb N_0\)).

\(\mathrm{Fin}(\mathbb N)\) countable. For \(N\ge0\), \(\mathcal F_N:=\mathcal P(\{1,\dots,N\})\) is finite, with \(|\mathcal F_N|=2^N\). Any finite \(S\subseteq\mathbb N\) has a maximum (or is \(\varnothing\)), so \(S\in\mathcal F_N\) for \(N=\max S\). Thus \(\mathrm{Fin}(\mathbb N)=\bigcup_{N\ge0}\mathcal F_N\), a countable union of finite (hence countable) sets, so countable by Thm. 1.6. It is infinite (contains all singletons), hence countably infinite.

\(\mathcal P(\mathbb N)\) uncountable. The map \(S\mapsto\mathbf 1_S\) is a bijection \(\mathcal P(\mathbb N)\to\{0,1\}^{\mathbb N}\), which is uncountable by the diagonal argument (Thm. 1.6). Hence \(\mathcal P(\mathbb N)\) is uncountable.

Sequences. Suppose \(\{0,1\}^{\mathbb N}=\{s^{(1)},s^{(2)},\dots\}\). Define \(d\in\{0,1\}^{\mathbb N}\) by \(d_k=1-s^{(k)}_k\). For each \(k\), \(d_k\ne s^{(k)}_k\), so \(d\ne s^{(k)}\). Then \(d\) is a binary sequence not in the list - contradiction. Hence \(\{0,1\}^{\mathbb N}\) is uncountable.

General (Cantor). Let \(f:X\to\mathcal P(X)\) be any function and \(D=\{x\in X:x\notin f(x)\}\). If \(f(x_0)=D\) for some \(x_0\), then \(x_0\in D\iff x_0\notin f(x_0)=D\), a contradiction. So \(D\notin\operatorname{ran}f\); no \(f\) is onto. Since \(x\mapsto\{x\}\) injects \(X\hookrightarrow\mathcal P(X)\), we get \(|X|<|\mathcal P(X)|\).

Suppose \((0,1)\) were countable, say \((0,1)=\{x_1,x_2,\dots\}\), and fix decimal expansions \(x_n=0.a_{n1}a_{n2}a_{n3}\ldots\). Define digits \(b_n=5\) if \(a_{nn}\ne5\), and \(b_n=4\) if \(a_{nn}=5\). Then each \(b_n\in\{4,5\}\subseteq\{1,\dots,8\}\), so \(y=0.b_1b_2\ldots\in(0,1)\) has no trailing \(0\)'s or \(9\)'s and hence a unique decimal representation. For every \(n\), \(y\) and \(x_n\) differ in the \(n\)-th digit (\(b_n\ne a_{nn}\)), and because \(y\)'s expansion is unique, this forces \(y\ne x_n\). Thus \(y\in(0,1)\) is not in the list - contradiction. Hence \((0,1)\), and therefore \(\mathbb R\supseteq(0,1)\), is uncountable.

Countably infinite subset. Since \(X\ne\varnothing\), choose \(x_1\in X\). Having chosen distinct \(x_1,\dots,x_n\), the set \(X\setminus\{x_1,\dots,x_n\}\) is nonempty (else \(X\) would be finite), so choose \(x_{n+1}\) in it. By construction the \(x_n\) are pairwise distinct, so \(\{x_n:n\in\mathbb N\}\) is a countably infinite subset of \(X\). (This recursive selection uses a choice principle; it is available in ZFC. The unrestricted statement is not provable in ZF alone.)

Dedekind-infinite. Let \(C=\{x_1,x_2,\dots\}\subseteq X\) be such a subset. Define \(\phi:X\to X\) by \(\phi(x_n)=x_{n+1}\) and \(\phi(y)=y\) for \(y\notin C\). Then \(\phi\) is injective, and its image is \(X\setminus\{x_1\}\), a proper subset - so \(X\) is in bijection with a proper subset. Conversely, a finite set cannot biject with a proper subset (pigeonhole), so the property characterises infinity.

Empty set. An upper bound of \(\varnothing\) is any \(u\) with "\(\forall x\in\varnothing:\ x\le u\)", which is vacuously true for every \(u\in\overline{\mathbb R}\). The least such \(u\) is \(-\infty\); hence \(\sup\varnothing=-\infty\). Dually \(\inf\varnothing=+\infty\).

Union. Let \(M=\max(\sup A,\sup B)\). Every \(x\in A\cup B\) satisfies \(x\le\sup A\le M\) or \(x\le\sup B\le M\), so \(M\) is an upper bound of \(A\cup B\). If \(u<M\), then \(u<\sup A\) or \(u<\sup B\); say \(u<\sup A\). Then \(u\) is not an upper bound of \(A\) (definition of supremum), so some \(a\in A\subseteq A\cup B\) has \(a>u\). Thus no \(u<M\) bounds \(A\cup B\), and \(\sup(A\cup B)=M\).

Undefined difference. Let \(a_n=n+c\) and \(b_n=n\). Both tend to \(+\infty\), but \(a_n-b_n=c\) for every \(n\). Choosing \(c=1\) or \(c=-5\) gives different finite limits, while \(a_n=2n\), \(b_n=n\) gives \(a_n-b_n\to+\infty\). Thus no single value assigned to \(+\infty-(+\infty)\) can represent all limiting behaviors of differences of divergent sequences. For that reason the expression is left undefined in extended-real arithmetic. This is logically separate from the special convention \(0\cdot(+\infty)=0\) used in nonnegative measure-theoretic arithmetic.

Zero times infinity. By the convention \(0\cdot c=0\) for all \(c\in[0,+\infty]\) (including \(c=+\infty\)), every term of \(\sum_n 0\cdot c_n\) equals \(0\), so the partial sums are all \(0\) and \(\sum_n 0\cdot c_n=0\). This is what guarantees \(\int_X 0\,d\mu=0\) even when \(\mu(X)=\infty\) (Ch. 7).

Definitions. The standard definitions are exactly \(\limsup a_n:=\inf_n s_n\) with \(s_n=\sup_{k\ge n}a_k\), and \(\liminf a_n:=\sup_n t_n\) with \(t_n=\inf_{k\ge n}a_k\); these exist in \(\overline{\mathbb R}\) by Thm. 1.5. Since \(\{a_k:k\ge n+1\}\subseteq\{a_k:k\ge n\}\), suprema decrease: \(s_{n+1}\le s_n\), so \((s_n)\downarrow\) and \(\inf_n s_n=\lim_n s_n\). Dually \((t_n)\uparrow\) and \(\sup_n t_n=\lim_n t_n\).

Ordering. For each \(n\), \(t_n\le a_n\le s_n\) and \(t_n\le s_n\); taking limits, \(\liminf a_n\le\limsup a_n\).

Equality \(\Leftrightarrow\) convergence. If \(\liminf=\limsup=L\), then \(t_n\to L\) and \(s_n\to L\), and \(t_n\le a_n\le s_n\) forces \(a_n\to L\) by squeezing (in \(\overline{\mathbb R}\)). Conversely if \(a_n\to L\), every tail sup and inf converges to \(L\), so both equal \(L\).

Fix \(x\) and let \(S=\{n:\ x\in A_n\}\), so \(\sum_n\mathbf 1_{A_n}(x)=|S|\) (with \(|S|=+\infty\) meaning the partial sums increase without bound). The nonnegative partial sums \(\sum_{n\le N}\mathbf 1_{A_n}(x)\) are non-decreasing, hence converge in \([0,+\infty]\) to \(|S|\). Thus \(\sum_n\mathbf 1_{A_n}(x)=+\infty\iff S\) is infinite \(\iff x\in A_n\) for infinitely many \(n\iff x\in\limsup A_n\) (Thm. 1.3). Dually, \(x\in\liminf A_n\iff x\notin A_n\) only finitely often \(\iff\sum_n\mathbf 1_{A_n^c}(x)<\infty\).

Algebraic. \(\left(\limsup A_n\right)^c=\left(\bigcap_n\bigcup_{k\ge n}A_k\right)^c=\bigcup_n\left(\bigcup_{k\ge n}A_k\right)^c=\bigcup_n\bigcap_{k\ge n}A_k^c=\liminf A_n^c,\) using De Morgan (Thm. 1.1) at both levels. Complementing gives \(\left(\liminf A_n\right)^c=\limsup A_n^c\) as well (replace \(A_n\) by \(A_n^c\)).

Conceptual check. \(x\in(\limsup A_n)^c\iff x\notin A_n\) for all but finitely many \(n\iff x\in A_n^c\) eventually \(\iff x\in\liminf A_n^c\). Consistent.

Let \(P\) be any of the operations "complement", "countable union", "countable intersection", and suppose \(\mathcal C\) is closed under \(P\).

Complement. If \(A=f^{-1}(C)\in f^{-1}(\mathcal C)\), then \(A^c=f^{-1}(C)^c=f^{-1}(C^c)\) (Thm. 1.2), and \(C^c\in\mathcal C\), so \(A^c\in f^{-1}(\mathcal C)\).

Countable union. If \(A_n=f^{-1}(C_n)\), then \(\bigcup_n A_n=\bigcup_n f^{-1}(C_n)=f^{-1}\!\left(\bigcup_n C_n\right)\) (Thm. 1.2), and \(\bigcup_n C_n\in\mathcal C\), so \(\bigcup_n A_n\in f^{-1}(\mathcal C)\). Countable intersections are identical with \(\bigcap\).

Hence \(f^{-1}(\mathcal C)\) inherits every closure property of \(\mathcal C\); in particular if \(\mathcal C\) is a \(\sigma\)-algebra, so is \(f^{-1}(\mathcal C)\) (it also contains \(X=f^{-1}(Y)\)).

Why not conversely? If \(f\) is not surjective, distinct subsets of \(Y\) can have the same inverse image. For a constant map \(f:X\to Y\) with value \(y_0\), the preimage of a set records only whether that set contains \(y_0\). Hence \(f^{-1}(\mathcal C)\) may be closed under an operation even when \(\mathcal C\) is not. If \(f\) is surjective, then \(B_1\neq B_2\) implies \(f^{-1}(B_1)\neq f^{-1}(B_2)\), so the inverse-image map on subsets is injective and the converse closure implication follows.

Partition. (i) Nonempty: for \(y\in f(X)\) there is \(x\) with \(f(x)=y\), so \(f^{-1}(\{y\})\ne\varnothing\). (ii) Cover: every \(x\in X\) has \(f(x)=:y\in f(X)\) and \(x\in f^{-1}(\{y\})\). (iii) Disjoint: if \(x\in f^{-1}(\{y\})\cap f^{-1}(\{y'\})\) then \(y=f(x)=y'\); so distinct fibres are disjoint. Hence \(\{f^{-1}(\{y\}):y\in f(X)\}\) partitions \(X\).

Factorisation. The relation \(x\sim x'\iff f(x)=f(x')\) is an equivalence whose classes are exactly the fibres. Define \(q:X\to X/{\sim}\), \(q(x)=[x]\) (surjective), and \(\bar f:X/{\sim}\to Y\), \(\bar f([x])=f(x)\). Well defined: \(x\sim x'\Rightarrow f(x)=f(x')\). Injective: \(\bar f([x])=\bar f([x'])\Rightarrow f(x)=f(x')\Rightarrow x\sim x'\Rightarrow[x]=[x']\). And \(f=\bar f\circ q\).

Since the \(c_i\) are the distinct values of \(s\), the fibres \(A_i=s^{-1}(\{c_i\})\) are nonempty, pairwise disjoint, and cover \(X\) (Ex. 1.22). Fix \(x\in X\); it lies in exactly one \(A_j\). Then \(\mathbf 1_{A_i}(x)=\delta_{ij}\), so \(\sum_{i=1}^m c_i\mathbf 1_{A_i}(x)=c_j=s(x)\). As \(x\) was arbitrary, \(s=\sum_i c_i\mathbf 1_{A_i}\).

Cover. For \(x\in X\), uniqueness of partition membership gives \(i,j\) with \(x\in P_i\), \(x\in Q_j\); then \(x\in P_i\cap Q_j\), which is therefore nonempty and a cell of \(\mathcal P\wedge\mathcal Q\).

Disjoint. If \(x\in(P_i\cap Q_j)\cap(P_{i'}\cap Q_{j'})\), then \(x\in P_i\cap P_{i'}\) forces \(i=i'\) and \(x\in Q_j\cap Q_{j'}\) forces \(j=j'\). So distinct cells are disjoint.

Refinement. Each cell \(P_i\cap Q_j\subseteq P_i\) and \(\subseteq Q_j\); so every \(\mathcal P\wedge\mathcal Q\)-cell sits inside a \(\mathcal P\)-cell and a \(\mathcal Q\)-cell, i.e. \(\mathcal P\wedge\mathcal Q\) refines both. It is the coarsest common refinement.

Let \(X=\mathbb N\), \(Y=\{0\}\) (or \(\mathbb R\)), \(f\equiv0\), and \(A_n=\{n,n+1,n+2,\dots\}\). The sequence is decreasing with \(\bigcap_n A_n=\varnothing\) (no natural number lies in every tail). Each \(A_n\ne\varnothing\), so \(f(A_n)=\{0\}\) for every \(n\), giving \(\bigcap_n f(A_n)=\{0\}\ne\varnothing=f(\varnothing)=f\!\left(\bigcap_n A_n\right)\). Hence \(f\!\left(\bigcap_n A_n\right)\subsetneq\bigcap_n f(A_n)\); direct images fail to commute with decreasing intersections.

Single set. Let \(\mathcal S=\{\varnothing,A,A^c,X\}\). It contains \(A\). It is closed under complement (\(\varnothing\leftrightarrow X\), \(A\leftrightarrow A^c\)) and under finite union: any union of members is one of \(\varnothing,A,A^c,X\) (e.g. \(A\cup A^c=X\), \(A\cup\varnothing=A\)). Any algebra containing \(A\) must contain \(A^c,X=A\cup A^c,\varnothing=X^c\); so \(\mathcal S\) is the smallest such collection - the algebra generated by \(\{A\}\), with \(4=2^2\) elements (unless \(A\in\{\varnothing,X\}\), when it collapses to \(\{\varnothing,X\}\)).

Partition. With atoms \(B_1,\dots,B_k\), every element of the generated algebra is \(\bigcup_{i\in S}B_i\) for some \(S\subseteq\{1,\dots,k\}\) (closed under \(\cup\) and complement, since \((\bigcup_{i\in S}B_i)^c=\bigcup_{i\notin S}B_i\)). Distinct \(S\) give distinct unions (atoms are nonempty and disjoint). Hence the algebra has exactly \(2^k\) elements.

Order isomorphism. On \(\mathbb R\), \(\varphi(x)=x/(1+|x|)\) has derivative \((1+|x|)^{-2}>0\), so it is strictly increasing with range \((-1,1)\); \(\lim_{x\to+\infty}\varphi=1\), \(\lim_{x\to-\infty}\varphi=-1\), matching \(\varphi(\pm\infty)=\pm1\). Thus \(\varphi:\overline{\mathbb R}\to[-1,1]\) is a strictly increasing bijection, with inverse \(\varphi^{-1}(y)=y/(1-|y|)\) on \((-1,1)\) and \(\pm1\mapsto\pm\infty\); both are order-preserving, so \(\varphi\) is an order isomorphism (hence a homeomorphism for the order topologies).

Sequential compactness. Given \((x_n)\subseteq\overline{\mathbb R}\), the images \(y_n=\varphi(x_n)\in[-1,1]\) have, by Bolzano–Weierstrass, a subsequence \(y_{n_k}\to y_*\in[-1,1]\). Since \(\varphi^{-1}\) is continuous on \([-1,1]\), \(x_{n_k}=\varphi^{-1}(y_{n_k})\to\varphi^{-1}(y_*)\in\overline{\mathbb R}\). So every sequence in \(\overline{\mathbb R}\) has a convergent (in the extended sense) subsequence.

Density. Let \(a<b\). By the Archimedean property pick \(n\in\mathbb N\) with \(n(b-a)>1\), so \(\tfrac1n<b-a\). Let \(m=\lfloor na\rfloor+1\); then \(m>na\) so \(m/n>a\), and \(m\le na+1<nb\) so \(m/n<b\). Thus \(m/n\in(a,b)\cap\mathbb Q\), proving density.

Open sets. Let \(\mathcal I=\{(p,q):p,q\in\mathbb Q,\ p<q,\ (p,q)\subseteq U\}\). This is countable, being a subset of \(\mathbb Q\times\mathbb Q\) (Ex. 1.10/1.11). Clearly \(\bigcup\mathcal I\subseteq U\). Conversely, for \(x\in U\) there is \(\varepsilon>0\) with \((x-\varepsilon,x+\varepsilon)\subseteq U\); by density choose rationals \(p\in(x-\varepsilon,x)\), \(q\in(x,x+\varepsilon)\), so \(x\in(p,q)\subseteq U\) and \((p,q)\in\mathcal I\). Hence \(U\subseteq\bigcup\mathcal I\), giving \(U=\bigcup\mathcal I\), a countable union of rational-endpoint intervals.

Injection \(\{0,1\}^{\mathbb N}\hookrightarrow[0,1]\). Define \[ F((a_n))=\sum_{n\ge1}2a_n\,3^{-n}. \] The ternary expansion of \(F((a_n))\) uses only digits \(0\) and \(2\). If two binary sequences first differ at index \(m\), the difference contributed at the \(m\)-th ternary digit has magnitude \(2\cdot3^{-m}\), while the largest possible contribution of all later digits is \(\sum_{n>m}2\cdot3^{-n}=3^{-m}\). Hence the two sums cannot agree. Thus \(F\) is injective.

Injection \([0,1]\hookrightarrow\{0,1\}^{\mathbb N}\). Assign to every \(x\in[0,1]\) one canonical binary expansion. If \(x\) is non-dyadic, use its unique binary expansion. If \(x\in(0,1]\) is dyadic, choose the non-terminating expansion ending in infinitely many \(1\)'s; in particular \(1=0.111\ldots_2\). Send \(0\) to \(0.000\ldots_2\). This rule assigns exactly one sequence to each \(x\), and distinct real numbers have distinct chosen expansions, so the map is injective.

Conclusion. Cantor-Schroeder-Bernstein gives \(|\{0,1\}^{\mathbb N}|=|[0,1]|\). Since \(S\mapsto\mathbf1_S\) is a bijection \(\mathcal P(\mathbb N)\to\{0,1\}^{\mathbb N}\), and \([0,1]\) has the same cardinality as \(\mathbb R\), we obtain \(|\mathcal P(\mathbb N)|=|\mathbb R|=2^{\aleph_0}\).

Decomposition. By Ex. 1.10, \(\mathbb Q\cap[0,1]\) is countably infinite; fix an enumeration \(q_1,q_2,\dots\) and put \(A_n=\{q_n\}\). The \(A_n\) are pairwise disjoint singletons and \(\bigsqcup_{n\ge1}A_n=\mathbb Q\cap[0,1]\).

Why finite additivity is insufficient. Suppose a finitely additive size function \(\lambda\) assigns \(\lambda(\{q\})=0\) to every singleton. Finite additivity then gives only \(\lambda(A_1\cup\cdots\cup A_N)=0\) for each finite \(N\). It supplies no axiom relating those finite partial unions to the countable union \(\bigcup_{n\ge1}A_n\). Therefore the value of \(\lambda(\mathbb Q\cap[0,1])\) is not determined by finite additivity together with the singleton values alone.

Why countable additivity settles it. If \(\lambda\) is countably additive, then \(\lambda(\mathbb Q\cap[0,1])=\sum_{n}\lambda(\{q_n\})=\sum_n 0=0\) (Ex. 1.19 in spirit: a countable disjoint union's size is the series of the parts). Countable additivity forces the "expected" value \(0\) and makes size behave continuously along the increasing sets \(\{q_1,\dots,q_N\}\uparrow\mathbb Q\cap[0,1]\).

Connection to \(\sigma\)-algebras. To even state countable additivity we need the countable union \(\bigcup_n A_n\) to be an admissible ("measurable") set. That is precisely axiom (iii) of a \(\sigma\)-algebra - closure under countable unions (Ch. 2) - paired with countable additivity of the measure (Ch. 3). The countable, not merely finite, level of closure is thus dictated by the need to compute sizes of limits like \(\mathbb Q\cap[0,1]\).