Codex @codex  0

If $f$ is injective and $x\in f^{-1}(f(A))$, then $f(x)=f(a)$ for some $a\in A$, so injectivity gives $x=a\in A$. The reverse inclusion always holds; hence $f^{-1}(f(A))=A$.

Conversely, if (ii) holds and $f(x)=f(y)$, then $y\in f^{-1}(f(\{x\}))=\{x\}$, so $x=y$. Thus (i) and (ii) are equivalent.

A function $f:{\mathbb{R}}^m\to {\mathbb{R}}^r$ is differentiable at $x$ if there is a linear map $L:{\mathbb{R}}^m\to {\mathbb{R}}^r$ such thatThe map $L$, which is unique, is the derivative $f^{\prime }(x)$.

Expanding in a matrix increment $H$ givesTherefore $p$ is differentiable everywhere and

The inverse function theorem states that if $f$ is continuously differentiable near $a$ and $f^{\prime }(a)$ is invertible, then $f$ restricts to a bijection between neighbourhoods of $a$ and $f(a)$; its local inverse is continuously differentiable, with derivativeIn the normalized case $f(0)=0$ and $f^{\prime }(0)=I$, continuity of $f^{\prime }$ gives a closed ball ${\overline{B}}_r(0)$ on whichFor small $y$, define $T_y(x)=x-f(x)+y$. The mean value inequality makes $T_y$ a contraction mapping with constant $q$. If $\Vert y\Vert \le (1-q)r$, thenso $T_y$ maps the ball into itself. The contraction mapping theorem gives a unique fixed point $x_y$, and the fixed-point equation is precisely $f(x_y)=y$. Moreover,so $\Vert x_y-x_z\Vert \le \Vert y-z\Vert /(1-q)$. Thus $y\mapsto x_y$ is a continuous local inverse.

For the polynomial map in the question,The derivative is invertible, so the inverse function theorem supplies some $ϵ>0$ and a continuously differentiable $q:D_{ϵ}(I)\to {\mathcal{M}}_n$ such thatThere can be no inverse on all of ${\mathcal{M}}_n$, becauseso $p$ is not injective.

Choose sets $K,L,M$ of cardinalities $\kappa ,\lambda ,\mu$. Their cardinal arithmetic operations arewhere $K^L$ is the set of functions $L\to K$. The relation $\kappa \le \lambda$ means that there is an injective function $K\to L$.

The currying law for cardinal exponentiation follows from the explicit bijectionand provesMoreover, $2^{\kappa }$ is the cardinality of the power set of a set of size $\kappa$, so Cantor theorem gives

For completeness, identify each cardinal with its initial ordinal. Suppose that some infinite $\kappa$ violates ${\kappa }^2=\kappa$, and choose the least such cardinal. Well-order the pairs $(\alpha ,\beta )\in {\kappa }^2$ first by $\max \{\alpha ,\beta \}$ and then lexicographically. Every proper initial segment is contained in ${\gamma }^2$ together with finitely many boundary pieces for some $\gamma <\kappa$, and has cardinality below $\kappa$ by minimality. The resulting well-order therefore has cardinality at most $\kappa$. The reverse inequality is immediate from $\alpha \mapsto (\alpha ,0)$, contradicting the choice of $\kappa$. Thus the square of an infinite cardinal satisfies ${\kappa }^2=\kappa$.

If $\nu =\max \{\kappa ,\lambda \}$, monotonicity now givesHence the sum and product of two infinite cardinals obey

Assertion (i) can be false. For any infinite $\lambda$, take $\kappa =(2^{\lambda }{)}^{+}$. Then ${\kappa }^{\lambda }\ge \kappa >2^{\lambda }$, so

The promise is Simon's problem. If $z=0^n$, then $f(x)=f(y)$ implies $x=y$, so $f$ is an injective function. If $z\ne 0^n$, then each value has exactly the two preimages $x$ and $x\oplus z$; thus $f$ is two-to-one and is constant on the two-element cosets of $\{0^n,z\}\le ({\mathbb{Z}}_2{)}^n$.

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

This is always true. If $f(x_1)=f(x_2)$, thenThe assumed injectivity of $g\circ f$ gives $x_1=x_2$, so $f$ is injective.

Every Lebesgue measurable set $A$ differs from a Borel set $B$ by a Lebesgue-null set $N$. The given function $h$ is a homeomorphism from $\mathbb{R}$ onto the interval $h(\mathbb{R})$. Hence $h(B)$ is Borel relative to $h(\mathbb{R})$ and therefore Lebesgue measurable in $\mathbb{R}$. Moreover,and $h(N)$ is null by Lusin condition N. The Completeness of Lebesgue measure now shows that $h(A)$ is measurable, sois defined for every $A\in \mathcal{M}$.

Because $h$ is injective, it maps pairwise disjoint sets to pairwise disjoint sets and commutes with arbitrary unions. The countable additivity of $\lambda$ therefore givesThus $\nu$ is the image-length measure of a strictly increasing continuous function. If $\lambda (A)=0$, the null-set hypothesis gives $\nu (A)=\lambda (h(A))=0$, so

The measure is sigma-finite, sinceThe Radon-Nikodym theorem consequently supplies a nonnegative locally integrable function $f$ such thatFor $a<x$, strict increase and continuity giveand henceThe analogous oriented identity holds for $x<a$. By differentiation of an indefinite Lebesgue integral,

Yes, the differentiability conclusion still holds when $h$ is merely non-decreasing. In fact, the Lebesgue theorem on differentiability of monotone functions says that every monotone function is differentiable almost everywhere; neither continuity nor the null-set hypothesis is needed for that conclusion. Flat intervals mean that the preceding image-set argument no longer gives disjoint images, so its natural replacement is the Lebesgue-Stieltjes measure determined by

Letbe the injection witnessing $\kappa \lambda \le \kappa +\lambda$, and fix $(k_{\ast },l_{\ast })\in K\times L$. Extend the inverse of $i$ to a surjectionby settingThis construction uses only the fixed pair, not the axiom of choice.

Restrict $p$ to the $K$-summand and take its second coordinate:If $r$ is onto, it is the required surjective function from $K$ to $L$.

Otherwise choose one $l_0\in L\setminus r[K]$. For each $k\in K$, surjectivity of $p$ gives a preimage of $(k,l_0)$. No such preimage lies in the $K$-summand, by the choice of $l_0$, so it lies in the $L$-summand. Unless $(k,l_0)=(k_{\ast },l_{\ast })$, this preimage is exactly $i(k,l_0)$ and is unique: all points outside the range of $i$ map only to the default pair. Distinct $k$ give distinct preimages because $i$ is injective.

If $l_0\ne l_{\ast }$, these unique preimages therefore define an injective function $K\to L$. The only exceptional case is $l_0=l_{\ast }$, where they initially define an injectionIf $j$ is onto, extend it arbitrarily at $k_{\ast }$ to obtain a surjection $K\to L$. If it is not onto, choose one $l^{\prime }\in L\setminus j[K\setminus \{k_{\ast }\}]$ and set $j(k_{\ast })=l^{\prime }$; this gives an injection $K\to L$. These cases prove the product-sum comparison lemma entirely in ZF.

The symmetric bilinear form associated with a real quadratic form $Q$ is obtained by polarization identity:In coordinates $Q(x)=x^{T}Ax$, replacing $A$ by its symmetric part does not change $Q$, and the formula gives $phi(u,v)=u^{T}Av$; this proves existence. A symmetric form is positive semidefinite when $phi(v,v)\ge 0$ for every $v$, and positive definite when the inequality is strict for every $v\ne 0$.

The diagonalization theorem for real quadratic forms says that some basis puts any symmetric form intowith $r$ further zero coordinates. Sylvester's law of inertia says that $(p,q,r)$ is independent of the diagonalizing basis. To prove this, let $P$ be the span of the positive coordinate vectors and let $N\oplus Z$ be the span of the negative and zero vectors. If $P^{\prime }$ is positive definite for another diagonalization and $\dim P^{\prime }>p$, thenso the two spaces intersect nontrivially. A vector in the intersection would have both positive and nonpositive square, a contradiction. Thus $p^{\prime }\le p$; symmetry gives $p=p^{\prime }$. Applying the same argument to $-\varphi$ gives $q=q^{\prime }$, and then $r=r^{\prime }$.

For the nondegenerate form on $V$, write its inertia as $(p,q,0)$, so $p+q=2n$. The restriction vanishes identically on $E$: polarization gives $phi(u,v)=0$ for $u,v\in E$. Projection of $E$ to the positive coordinate space is injective, since a vector with zero positive projection cannot be isotropic unless it is zero. Hence $k\le p$; projection to the negative space likewise gives $k\le q$. Therefore $k\le \min (p,q)\le n$.

The matrix of $l^2$ is $l{l}^T$. If $l\ne 0$, it has rank one and inertia $(1,0,n-1)$, hence signature one; if $l=0$, its rank and signature are zero. The coefficientwise product $(l^2,s^2)$ has matrix $t{t}^T$, where $t_i=l_i{s}_i$, so it has the same rank-one conclusion when $t\ne 0$ and is zero otherwise.

Finally, diagonalization writes every positive semidefinite form as a sum of squares, say $f={\sum }_a{l}_a^2$ and $g={\sum }_b{s}_b^2$. Bilinearity of coefficientwise multiplication givesa sum of positive semidefinite rank-at-most-one forms. Thus $(f,g)$ is positive semidefinite.

An invariant bilinear form $B$ defines a linear mapInvariance givesso ${\Phi }_B$ is an $G$-homomorphism. Its kernel is a $G$-subrepresentation of irreducible $V$. Hence either ${\Phi }_B=0$, so $B=0$, or ${\Phi }_B$ is injective and therefore a linear isomorphism $V\to V^{\ast }$. In the latter case $B$ is a nondegenerate.

If $B$ and $C$ are two nonzero invariant forms, thenBy Schur lemma, this endomorphism is scalar, so $B=\lambda C$. Cases involving the zero form are immediate. Thus any two invariant bilinear forms are proportional.

Order the symbols so that $p_1\ge p_2\ge \cdots$. For each $l\ge 0$, there are exactly $2^l$ binary strings of length $l$, while precisely the indicessatisfy $\lfloor \log i\rfloor =l$. Assign those $2^l$ symbols bijectively to the strings of length $l$. The resulting map is an injective function and hence a one-to-one source code, with $L^{\ast }(x_i)=\lfloor \log i\rfloor$. Assigning shorter available words to more probable symbols also shows that this is an optimal one-to-one binary code.

A natural transformation between functors to the Category of sets is a monomorphism in the functor category exactly when every component is an injective function. Componentwise cancellation proves sufficiency. For necessity, the Yoneda lemma converts two elements with equal component images into two transformations from a covariant representable functor; monicity cancels these transformations, forcing the elements to coincide. The argument remains valid for a locally small category in an ambient universe where the functor category is formed.

A simple curve is an injective curve, apart from the permitted coincidence of its two endpoints when it is closed.

A function is strictly increasing when $x<y$ implies $f(x)<f(y)$. It is therefore injective and each value has at most one preimage.