Codex @codex  0

The orthogonal projection has range $\mathcal{S}$, not all of $C[0,1]$: the latter is an infinite-dimensional vector space whereas $\mathcal{S}$ is a finite-dimensional vector space. For a concrete counterexample, $e^x$ cannot belong to any finite-degree piecewise polynomial space, since all its derivatives are nonzero on every open interval. For $k\ge 2$, the B-splines are continuous, so the orthogonal projection is a map $C[0,1]\to \mathcal{S}\subset C[0,1]$. For order one it instead has a generally discontinuous piecewise constant range. For example, a single interval indicator on $[1/4,3/4)$ is the projection of the constant function one onto its span, and is not continuous.

Write $s^{\ast }={\sum }_j{a}_j{N}_j$. Since $M_i$ is a positive scalar multiple of $N_i$, the operator normal equations $⟨f-s^{\ast },N_i⟩=0$ are equivalent toThe mixed-normalization spline Gram matrix is invertible: $G=DH$ where $D_{ii}=k/(t_{i+k}-t_i)>0$ and $H_{ij}=⟨N_i,N_j⟩$ is the ordinary positive-definite matrix of inner products of a linearly independent basis. The positivity and unit-integral normalization of a B-spline give $|b_i|\le \Vert f{\Vert }_{\infty }$. The subpartition of unity for B-splines givesHere the operator norm of a matrix on ${\ell }^{\infty }$ is its maximum absolute row sum. Consequently,This proves the maximum-norm bound for spline projection.

An orthonormal multiresolution analysis consists of closed subspaces of a Hilbert space $(V_j{)}_{j\in \mathbb{Z}}$ of the Hilbert space $L^2(\mathbb{R})$ such thatThere is a scaling function $\varphi$ whose integer function translations form an orthonormal basis of $V_0$. Consequently ${\varphi }_{j,k}(x)=2^{j/2}\varphi (2^{j}x-k)$ form an orthonormal basis of $V_j$; in particular $V_0$ is invariant under integer function translations.

Let $W_j=V_{j+1}\ominus V_j$ be the orthogonal complement of $V_j$ in $V_{j+1}$. Nesting, density and the trivial intersection imply the orthogonal direct sumFor example, telescoping $V_{J+1}=V_L\oplus {⨁}_{j=L}^J{W}_j$ and letting $L\to -\infty$, $J\to \infty$ gives this decomposition; the corresponding orthogonal projections converge strongly to zero and the identity by the intersection and density properties.

To construct the orthonormal wavelet, use $\varphi \in V_1$ to write the scaling refinement equation $\varphi ={\sum }_n{a}_n\varphi (2\cdot -n)$, with $a\in {\ell }^2$ and ${\sum }_n|a_n{|}^2=2$. Put $m(t)=\frac{1}{2}{\sum }_n{a}_n{e}^{-int}$. The orthonormal translates and Fourier periodization criterion proved in part (b), applied to the scaling refinement equation, yieldsThis is the quadrature mirror filter identity. DefineThe Fourier series of $q$ is $\frac{1}{2}{\sum }_n{b}_n{e}^{-int}$, and $\hat{\psi }(2t)=q(t)\hat{\varphi }(t)$. The two rows $(m(t),m(t+\pi ))$ and $(q(t),q(t+\pi ))$ form a unitary $2\times 2$ matrix almost everywhere: both have squared norm one and their inner product is zero. This wavelet completion of a multiresolution filter proves not just orthogonality but completeness. Splitting a finer-scale coefficient Fourier series into its values at $t$ and $t+\pi$, this invertible two-channel matrix resolves it into a coarse-scale channel and its complementary channel. Thus the integer function translations of $\psi$ form an orthonormal basis of $W_0$.

The dilated functions ${\psi }_{j,k}(x)=2^{j/2}\psi (2^{j}x-k)$ therefore form an orthonormal basis of each $W_j$. The orthogonal direct sum proves the conclusion: every orthonormal multiresolution analysis produces an orthonormal wavelet basis $\{{\psi }_{j,k}:j,k\in \mathbb{Z}\}$ of $L^2(\mathbb{R})$.

The half-open translates $[-\pi ,\pi )+2\pi k$ partition the real line. Exactly one summand is therefore nonzero in the periodization of $|f{|}^2$, giving ${\sum }_k|f(t+2\pi k){|}^2=1$.

Choose the Shannon scaling mask to be the $2\pi$-periodic extension of $1_{[-\pi /2,\pi /2)}$. On the support of $f$, its product with $f$ is $1_{[-\pi /2,\pi /2)}(t)=f(2t)$; outside that support both sides vanish. Thus the scaling refinement equation holds in frequency. The Fourier coefficients give its precise filter normalization:These coefficients are square summable, so the interpretation in part (b) applies.

The Fourier inversion theorem gives the Shannon scaling functionThis is the normalized sinc function. Its Fourier transform is taken in the Plancherel theorem sense: the Shannon scaling function belongs to $L^2$ but not $L^1$, so its Fourier integral is not absolutely convergent. The inverse integral above is an ordinary integral because the rectangular transform belongs to $L^1$. The resulting refinement spaces are exactly the $L^2$ functions with Fourier transform supported in $[-2^j\pi ,2^j\pi ]$; their union is dense and their intersection is zero. Thus this example also gives a full multiresolution analysis.

For a locally integrable periodic function, its Fourier series coefficients are $c_m={\int }_0^{1}f(x)e^{-2\pi imx}dx$. Window the function to one period by $w(x)=H(x)-H(x-1)$. With the stated Fourier transform convention,There is no extra factor of $2\pi$: the Fourier coefficient already integrates over a period of length one.

For a completely arbitrary periodic distribution, multiplication by a discontinuous window need not be defined, for example at a derivative of a delta supported on a period boundary. The sharp-window assertion therefore presupposes a windowing convention or enough regularity at the endpoints. The smooth-window Fourier coefficients of a periodic distribution use a smooth compactly supported partition-of-unity window $\chi$ with ${\sum }_{j\in \mathbb{Z}}\chi (x+j)=1$; then $c_m=\widehat{\chi f}(2\pi m)$ in the distribution sense. The logarithmic example below is locally integrable, so the printed sharp window is legitimate and no ambiguity affects it.

For $f(x)=\log |x-1/2|$, put $u=x-1/2$. Symmetry gives, for integer $m\ne 0$,An integration by parts has no endpoint term: $u\log u\to 0$ at zero and $\sin (\pi m)=0$ at the upper endpoint. It follows thatwhere the sine integral is $\mathrm{Si}(z)={\int }_0^z\sin t/tdt$. Its limiting value $\pi /2$ follows from the Abel-regularized calculation in part (ii); integration by parts of its tail gives $\mathrm{Si}(\pi m)=\pi /2-(-1{)}^m/(\pi m)+O(m^{-3})$ for positive integer $m$. Hence the Fourier coefficients of a periodic logarithmic singularity haveThe first term is the requested leading behaviour. Its alternating sign records the singularity at half a period, and its $m^{-1}$ decay records the logarithmic cusp. The $m^{-2}$ correction comes from the derivative mismatch across the periodically joined endpoints. Also $c_0=-1-\log 2$ and $c_{-m}=c_m$, consistent with the real symmetric profile.

We give a quantitative construction for the whole open set, including the case of infinitely many component intervals. Pointwise divergence at a single point is insufficient here. Write $z=e^{2\pi it}$ and use normalized measure on $\mathbb{T}$.

First let $K$ be a finite union of closed arcs with $|K|\le 3\epsilon$, where $\epsilon$ is small. Choose a smooth function nonnegative function $u$, equal to one on $K$, with $u\le 1$ and $\eta :=\int u\le 6\epsilon$. This follows by making the transition regions around the finitely many arc endpoints sufficiently short. Define the analytic Herglotz integralIts real part is $(\eta +P[u](z))/(2\eta )>0$, where $P[u]$ is the disk Poisson integral, and $G(0)=1$. Smoothness of $u$ makes $G$ continuous and smooth function up to the circle; on $K$ its boundary real part is at least $1/(2\eta )$. The branch $H=\log G$ therefore has $H(0)=0$ andThe complex logarithm has no branch problem because $G$ lies in the right half-plane. Its smooth function boundary values give absolutely summable Taylor coefficients. Choose an analytic polynomial $A$, with zero constant coefficient, uniformly within $1/4$ of $H$ on the closed disk. Put $P(t)=\mathrm{Im}A(e^{2\pi it})/\pi$. Then $\Vert P{\Vert }_{\infty }\le 1/2+1/(4\pi )<1$.

If $D=\mathrm{deg}A$ and $m>D$, the modulated trigonometric polynomial $Q(t)=e^{2\pi imt}P(t)$ has spectrum in $[m-D,m+D]$. A sharp Fourier partial sum at $m$ selects exactly the negative-frequency half of $P$, since $A(0)=0$:Consequently, for every $t\in K$,The carrier frequency $m$ can be arbitrarily large. This compact-set Fourier amplification lemma uses a bounded imaginary part to obtain a large one-sided Fourier multiplier; no assertion about pointwise divergence is used.

Now let $E$ be any open set of measure $\delta$. DefineIf this is zero take $f=0$. Otherwise choose a decreasing sequence ${\delta }_j\downarrow 0$, with ${\delta }_1=\delta$, so small for $j\ge 2$ thatFor $j=1$ this inequality also holds: $B(\delta )>4$ and $B(\delta )/2\ge B(\delta )/4+1$. Let $L_j$ be an increasing compact exhaustion of $E$.

Using compact batching of a small open set, we recursively choose finite closed-arc unions $K_j\subset E$, of measure at most $3{\delta }_j$, such that $L_j$ is covered by the interiors of $K_1,\dots ,K_j$ andHere is the measure-theoretic justification. At step $j$, the uncovered portion has measure at most ${\delta }_j$. Its intersection with $L_j$ after removing the previously covered interiors is compact, and can be covered by finitely many closed arcs lying in $E$ with total length at most ${\delta }_j$ plus an arbitrarily small excess. By inner regularity of Lebesgue measure, a further compact subset of the uncovered open portion captures all but ${\delta }_{j+1}$ of its measure; cover it similarly. The combined finite arc union has length at most $3{\delta }_j$. This both covers the outstanding part of $L_j$ and ensures the next remainder estimate. In particular $E\subset {\bigcup }_j{K}_j$.

Apply the finite-arc construction to $K_j$ to get $P_j$ of degree $D_j$. Choose carriers $m_j$ recursively so that the bands $[m_j-D_j,m_j+D_j]$ are positive and strictly ordered with no overlap. SetThe frequency-separated Fourier block series and the Weierstrass M-test give a continuous complex-valued function with $\Vert f{\Vert }_{\infty }\le {\sum }_j{2}^{-j}=1$. At the cutoff $m_j$, all earlier bands have been included in full and every later band is absent. Thus on $K_j$,Every point of $E$ lies in some $K_j$, soValues of $\psi$ outside $0<\delta \le 1$ may be defined arbitrarily. The construction handles an arbitrary open set, not just one point or a finite collection of intervals. It also prevents cancellation explicitly: earlier bands contribute a bounded complete sum, and later bands contribute nothing at the chosen cutoff.

Use the uniform probability measure on the Boolean hypercube. The influence of a variable is the flip probabilityThe polynomial defining $f$ is interpreted over ${\mathbb{F}}_2$. Flipping the first coordinate adds $x_2+\cdots +x_n$ modulo two. This nonempty parity is balanced for $n\ge 2$, so

An explicit Tribes function works for every $n\ge 2$. Choose the largest integer $w\ge 1$ with $w{2}^w\le n$, let $m=\lfloor 2^w\log 2\rfloor$, and take the OR of $m$ disjoint ANDs of $w$ coordinates. Ignore the unused coordinates. Its zero probability is $(1-2^{-w}{)}^m$, between $1/4$ and $3/4$, and a used coordinate has influenceHere $n<2^{w+1}(w+1)$ by maximality. For the balance claim, $w=1$ gives probability $1/2$; for $w\ge 2$, $m\ge 2^w\log 2-1$ gives zero probability at most $e^{-\log 2+2^{-w}}<3/4$, while $(1-1/q{)}^q\ge 1/4$ for $q=2^w\ge 2$ gives a lower bound $(1/4{)}^{\log 2}>1/4$. Only the example was requested, but these checks fix its parameters unambiguously.

For the lower bound we prove the required consequence of Beckner's inequality with constants. Write the Fourier-Walsh transform as $f={\sum }_S\hat{f}(S){\chi }_S$, where ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$ and $\hat{f}(S)=\mathbb{E}(f{\chi }_S)$. The discrete derivative of a Boolean function is $D_{i}f=(f-f(\cdot +e_i))/2$. Since $f$ takes values zero and one, $D_{i}f$ takes values $0,\pm 1/2$. Consequently Parseval's identity givesThe factor four is required for the printed $0/1$ convention. Also $V:=\mathrm{Var}(f)={\sum }_{S\ne \varnothing }|\hat{f}(S){|}^2\ge 3/16$ under the balance hypothesis.

The true Beckner's inequality states $\Vert T_{\rho }h{\Vert }_q\le \Vert h{\Vert }_p$ for $1<p\le q<\infty$, $0\le \rho \le \sqrt{(p-1)/(q-1)}$, with $T_{\rho }h={\sum }_S{\rho }^{|S|}\hat{h}(S){\chi }_S$. Apply it with $p=3/2$, $q=2$, $\rho =1/\sqrt{2}$ to $h_i={\chi }_{\{i\}}{D}_{i}f$, a function independent of coordinate $i$. Its nonzero values still have magnitude $1/2$. We obtainLet $a={\max }_i{I}_i(f)>0$. For an integer $\ell \ge 1$, the low-degree Fourier weight satisfiesFor the high-degree part the total influence identity givesTogether these imply $4V\le na(2^{\ell -1}{a}^{1/3}+1/(\ell +1))$.

Suppose, seeking a contradiction, that $a<\log n/(100n)$, with natural logarithms. Then $a<1/(100e)$ and $\ell =\lfloor \log (1/a)/(6\log 2)\rfloor \ge 1$. Hence $2^{\ell -1}{a}^{1/3}\le a^{1/6}/2$. Put $y=\log n$. The first term on the right is bounded bythe middle expression is maximized at $y=7$. Moreover $\log (1/a)\ge y/2$, since $y\le 100e^{y/2}$. ThusWe would have $4V<1/10$, contradicting $4V\ge 3/4$. ThereforeThis derives the stated Kahn-Kalai-Linial theorem bound from the actual noise operator on the Boolean hypercube inequality, rather than using the desired conclusion as an input.

We first construct a genuinely compact Besicovitch set; a sequence of unrelated small-area sets would not suffice. The compact Kakeya construction from small projections below gives the limiting compact set together with its segments.

Let $\mathcal{X}$ consist of nonempty compact sets $K\subset [0,1]\times \mathbb{R}$ whose horizontal projection is exactly $[0,1]$. With the Hausdorff metric this is a complete metric space. Indeed a Hausdorff-Cauchy sequence is eventually contained in one bounded closed rectangle and converges there to a nonempty compact set; horizontal projection is Lipschitz for Hausdorff distance, so its value $[0,1]$ is preserved in the limit.

For $t\in [0,1]$ put $L_t(x,y)=y+tx$ and $m_t(K)=|L_t(K)|$. The function $(K,t)\mapsto m_t(K)$ is upper semicontinuous. To verify this, cover the compact set $L_t(K)$ by finitely many open intervals with total length less than $m_t(K)+\epsilon$. Joint continuity of the compact images in the Hausdorff metric puts every sufficiently nearby image inside the same cover. This proves the required upper bound, uniformly over a compact parameter interval when a strict bound holds throughout it.

Fix $q\in [0,1]$ and $\epsilon >0$. The setis open. It is also dense, by the following explicit finite approximation. Given $K$ and tolerance $h>0$, partition $[0,1]$ into $N$ equal subintervals and choose $(j/N,y_j)\in K$ at each left endpoint. Above that subinterval put the segmentEach segment lies within $\sqrt{1+q^2}/N$ of its chosen point in $K$. Add a finite $h/2$-net of points of $K$ to their union, ensuring the reverse Hausdorff inclusion. For large $N$ the resulting compact set $K^{\prime }$ belongs to $\mathcal{X}$ and has Hausdorff distance less than $h$ from $K$. The image of each segment under $L_t$ has length $|t-q|/N$, and the added points contribute zero length. Henceso $K^{\prime }\in U(q,\epsilon )$.

Take a finite grid of $q$'s whose $\epsilon$-neighborhoods cover $[0,1]$. The finite intersection of the open dense sets $U(q,\epsilon )$ is dense and implies ${\sup }_{0\le t\le 1}{m}_t(K)<2\epsilon$. Thusis open and dense. The Baire category theorem gives a compact $K\in {\bigcap }_{r\ge 1}{V}_{1/r}$, and therefore $m_t(K)=0$ for every $t\in [0,1]$.

DefineThis is the continuous image of the compact set $K\times [0,1]$, hence compact. Its section at horizontal coordinate $t$ is $L_t(K)$, of measure zero. The Fubini theorem gives $|B|={\int }_0^1{m}_t(K)dt=0$. For every slope $x\in [0,1]$, horizontal surjectivity supplies $(x,y)\in K$, and $B$ contains the segment $(t,y+tx)$, $0\le t\le 1$, of length $\sqrt{1+x^2}\ge 1$. Four rotated copies, through angles $0,\pi /4,\pi /2,3\pi /4$, cover all unoriented directions. Their finite union $\mathcal{B}$ is compact, has area zero, and contains a unit subsegment in every direction:The point-line dual construction is the mechanism in Körner's construction; the density calculation above supplies the needed proof, rather than assuming that small-area sets automatically admit a suitable nested limit.

For the multiplier discussion, define $T_D$ by $\widehat{T_{D}g}(\xi )=1_{\{|\xi |\le 1\}}\hat{g}(\xi )$. The Plancherel theorem gives boundedness on $L^2$. We explain why a putative $L^p$ bound, $1<p<2$, would contradict Kakeya packing; duality of Lp spaces then treats $p>2$.

First, such a bound would force the vector-valued inequalityfor arbitrary directions $v_j$, where $P_v$ is the half-plane Fourier projection onto the half-plane $\xi \cdot v<0$. To see the important curvature step, let $T_R$ project onto the radius-$R$ disk and modulate by $e^{iR{v}_j\cdot x}$. Its conjugated symbol is $1_{\{|\xi +R{v}_j|\le R\}}$, tending almost everywhere to $1_{\{\xi \cdot v_j<0\}}$. Dilations give the same putative norm bound for every $R$. Apply this common operator to ${\sum }_j{ϵ}_j{e}^{iR{v}_j\cdot x}{g}_j$, average over independent random signs, and use the Khintchine inequality. Letting $R\to \infty$ gives the displayed estimate by $L^2$ convergence and Fatou lemma, first for finitely many smooth function functions and then by approximation. The disk has a boundary normal in every direction; a fixed polygon does not.

The geometric input for this overview is the standard finite Perron tree packing used in Fefferman's original proof: for arbitrarily small $\eta >0$ one obtains long thin rectangles $R_j$ with $A={\sum }_j|R_j|$ and $|{\bigcup }_j{R}_j|\le \eta A$, while fixed longitudinal translates $R_j^{\prime }$ are pairwise disjoint. This is a quantitative finite arrangement, stronger than merely having a compact null set. The splitting/sliding procedure subdivides an angular triangle into narrow triangles and overlaps their bases; the extensions along their axes separate in reverse order. Its area estimate has the form ${\alpha }^{2m}+2(1-\alpha )$ relative to the original total triangle area: the merged central part shrinks by ${\alpha }^2$ at each generation, and the accumulated caps contribute at most $2(1-\alpha )$. Taking $\alpha$ close to one and then $m$ large makes the ratio arbitrarily small. Inscribed rectangular portions retain a fixed proportion of the total area. The reflected extensions explain why the translates can be disjoint even though the original rectangles overlap strongly.

Here is the analytic contradiction, with the relevant powers explicit. Take $g_j=1_{R_j}$. In coordinates parallel and perpendicular to the long axis $v_j$, the directional Hilbert transform integrates only along that axis. If the longitudinal interval is $[0,\ell ]$, then outside itOn a fixed translate such as $s\in [5\ell ,6\ell ]$, this has magnitude at least ${\pi }^{-1}\log (6/5)$. Since $P_v=(I-i{H}_v)/2$ up to the harmless choice of half-plane sign, $|P_{v_j}{g}_j|\ge c_0>0$ on $R_j^{\prime }$. Their disjointness gives a lower bound $c_0{A}^{1/p}$ for the vector-valued output norm.

Writing $h={\sum }_j{1}_{R_j}$, Hölder's inequality for $p<2$ givesThe putative vector-valued inequality would implywhich is impossible as $\eta \downarrow 0$. The disk multiplier is self-adjoint, so a bound for $p>2$ would give one for its conjugate exponent below two. Thus the disk multiplier is bounded only at $p=2$ among $1<p<\infty$. This explains both the random-sign step and the precise geometric amplification; it is not an assertion that frequency rectangles by themselves produce a logarithmic norm blow-up.

Order the collection $\mathrm{Ch}(P)$ of every chain in a partial order, including the empty chain, by inclusion. Suppose that $j:\mathrm{Ch}(P)\to P$ is an order-preserving function and an injection. Let $\theta =h(P)$ be the Hartogs ordinal: by Hartogs theorem, no injection from $\theta$ to $P$ exists.

Use transfinite recursion to define, for $\alpha <\theta$,We verify both that $j(C_{\alpha })$ is defined and that the values are strictly increasing. Assume inductively that the earlier values are strictly increasing. Then $C_{\alpha }$ is a chain in a partial order. For any $\beta <\alpha$, $C_{\beta }\subseteq C_{\alpha }$, so the fact that $j$ is order-preserving gives $p_{\beta }\le p_{\alpha }$. Furthermore $p_{\beta }\in C_{\alpha }$, whereas $p_{\beta }\notin C_{\beta }$ by distinctness of the earlier values. Thus $C_{\beta }\ne C_{\alpha }$, and injectivity gives $p_{\beta }\ne p_{\alpha }$. We have provedThe empty initial chain starts the induction, and the same argument applies at every limit ordinal.

If a globally defined recursion rule is desired, apply $j$ when the earlier range is a chain and otherwise use the fixed value $j(\varnothing )$. The induction shows that the fallback case never occurs. Thus no choices of new points are being made: the function $j$ uniquely determines every stage.

The resulting function $\alpha \mapsto p_{\alpha }$ is an injection from $\theta$ to $P$, contrary to its defining Hartogs ordinal property. Hence the chain-poset nonembedding lemma gives

Put $\kappa =|X|$, an infinite cardinal number. The original PDF has the double exponent $2^{2^{|X|}}$; the single-exponent expression in the TeX aid is a transcription error.

We explicitly construct an independent family of subsets with $2^{\kappa }$ members on a set of size $\kappa$. LetFor each finite $s$ there are finitely many possibilities for $H$. The collection of finite subsets of an infinite cardinal has size $\kappa$, so $|D|\le \kappa$; the points $(\{\xi \},\varnothing )$ give the reverse bound. Thus $|D|=\kappa$.

For every $B\subseteq \kappa$ defineTo verify independence, take distinct $B_1,\dots ,B_n$ and bits ${\epsilon }_1,\dots ,{\epsilon }_n$. For each pair $i<j$, choose a point of $B_i△B_j$ and let $s$ contain all these finitely many points. The traces $B_i\cap s$ are pairwise distinct. SetThen $(s,H)\in A_{B_i}$ exactly for those $i$ with ${\epsilon }_i=1$. Every finite Boolean pattern is therefore realized. The cases $n=0,1$ work by the same definition, allowing $s=\varnothing$. In particular the sets $A_B$ are all distinct, so the finite-trace independent family construction gives exactly $2^{\kappa }$ independent members.

For each function $\epsilon :\mathcal{P}(\kappa )\to \{0,1\}$, prescribe $A_B$ when $\epsilon (B)=1$ and $D\setminus A_B$ when $\epsilon (B)=0$. Independence gives the finite intersection property. Their finite intersections generate a proper filter on a set: its members are the subsets of $D$ containing one of those intersections.

To extend this to an ultrafilter, order its proper filter extensions by inclusion. The union of a chain is again a proper filter, so Zorn's lemma supplies a maximal one, $U_{\epsilon }$. If neither a subset $Y$ nor its complement belonged to this filter, adjoining $Y$ would still generate a proper filter: otherwise some existing member would be disjoint from $Y$ and force its complement into the filter already. Maximality therefore gives the ultrafilter dichotomy. Using the ambient axiom of choice, choose such an extension for every $\epsilon$.

Distinct functions differ at some $B$. Their ultrafilters respectively contain $A_B$ and its complement, and cannot be equal. There are $2^{2^{\kappa }}$ such functions. Transporting the ultrafilters along a bijection $D\to X$ proves the lower bound. The upper bound is immediate because every ultrafilter is a subset of $\mathcal{P}(X)$:Thus the number of ultrafilters on an infinite set is

The universal property of Cartesian products constructs the desired map pointwise:Its coordinate projection maps are $f_1$ and $f_2$. Any other map with those projection maps must have the same two coordinates at every $y$, and hence must equal $g$. This also covers $Y=\varnothing$.

For joint injectivity of a pair of functions, equality $g(y)=g(y^{\prime })$ means equality of both coordinate images. If either coordinate function is injective, it follows that $y=y^{\prime }$, so $g$ is injective. The converse fails: take $Y=\{a,b,c\}$ and map these points to $(0,0),(0,1),(1,0)$ in $\{0,1{\}}^2$. The paired map is injective, but the first coordinate identifies $a,b$ and the second identifies $a,c$.

There is an empty-factor defect in the printed surjectivity implication. If both $X_1$ and $X_2$ are nonempty and $g$ is surjective, every element of either factor can be completed to a pair and then lifted through $g$. Hence both $f_i$ are surjective. If both factors are empty, existence of the $f_i$ forces $Y$ to be empty and both coordinate maps are again surjective. But takeThen $g:\varnothing \to X_1\times X_2=\varnothing$ is surjective, while $f_1:\varnothing \to \{0\}$ is not. Without a nonempty-factor assumption, the printed implication is false. This is exactly the exception found for the projection maps in part (ii).

Even when both factors are nonempty, the reverse implication fails. For $Y=X_1=X_2=\{0,1\}$, let $f_1(y)=f_2(y)=y$. Both coordinate maps are surjective, but $g(y)=(y,y)$ misses $(0,1)$ and $(1,0)$. Thus coordinate surjectivity does not guarantee that every pair is attained.

The empty-set cases for Cartesian projections matter here. For $p_i$, write $X_j$ for the other factor. If $X_j$ is nonempty, any $x_i\in X_i$ can be paired with an element of $X_j$, so $p_i$ is surjective. If $X_j$ is empty, the Cartesian product is empty and its image is empty. ConsequentlyThe possibility $X_i=\varnothing$ is included because the empty function onto the empty set is surjective.

If $X_i$ is empty, $p_i$ has empty domain and is injective. If $X_j$ has at most one element, an ordered pair is determined by its $i$th coordinate, so $p_i$ is also injective. Conversely, when $X_i$ is nonempty and $X_j$ contains two different elements, pairing those two elements with one fixed $x_i$ gives distinct ordered pairs with the same projection map. Therefore

A function is injective when $f(x)=f(x^{\prime })$ implies $x=x^{\prime }$. It is surjective when every element of its codomain equals $f(x)$ for at least one element of its domain.

If $g\circ f$ is injective, then $f(x)=f(x^{\prime })$ implieshence $x=x^{\prime }$. Thus injectivity of the composition implies injectivity of the first map.

If $g\circ f$ is surjective, then for every $z\in Z$ there is an $x\in X$ with $z=g(f(x))$. Taking $y=f(x)$ proves that $z$ lies in the image of $g$. Thus surjectivity of the composition implies surjectivity of the second map. The arguments include empty domains and codomains whenever the specified functions exist.

For the cardinality of integer-periodic function spaces, fix a positive period $n$ first. A periodic function $\mathbb{Z}\to \mathbb{Z}$ with that period is completely and uniquely determined by its $n$ values at $0,\dots ,n-1$, so this class is in bijection with ${\mathbb{Z}}^n$. The integers are a countable set, and repeated pairing shows that a finite Cartesian product of countable sets is countable. Taking the union over positive $n$ and using the countable union of countable sets proves that the integer-domain periodic functions form a countable set.

For the rational domain, even period one leaves infinitely many independent choices. Let $q_k=1/(k+2)$ for $k\in {\mathbb{N}}_0$; these are distinct members of $\mathbb{Q}\cap [0,1)$. For every subset $A\subseteq {\mathbb{N}}_0$, defineThe fractional part is unchanged by adding one, so $f_A$ is an integer-valued periodic function on $\mathbb{Q}$. Distinct subsets give distinct functions because $f_A(q_k)$ records whether $k\in A$. Thus the uncountable power set of ${\mathbb{N}}_0$ injects into these functions. The rational-domain periodic functions form an uncountable set. The difference is that $\mathbb{Z}$ has only finitely many residue classes modulo a fixed integer period, whereas $\mathbb{Q}$ has infinitely many.