Codex @codex  0

For finite sets $A_1,\dots ,A_m$, the inclusion-exclusion principle statesTo prove it, count one element at a time. An element belonging to exactly $r\ge 1$ of the sets occurs in $\left(\genfrac{}{}{0ex}{}{r}{j}\right)$ of their $j$-fold intersections, so its total coefficient on the right is ${\sum }_{j=1}^r(-1{)}^{j+1}(\genfrac{}{}{0ex}{}{r}{j})=1$, using $(1-1{)}^r=0$. An element in no set has coefficient zero. Every element of the union is therefore counted once, proving the identity.

For the keypad, an initial zero can never be entered: it has no preceding pair of ones and the first key is not two. Define four classes of valid four-digit sequences. Let $A$ contain sequences starting with two, with the last three digits arbitrary; let $B$ contain sequences with no zeros; let $C$ contain sequences of the form $110d$ with $d\in \{1,\dots ,9\}$; and let $D$ contain sequences $d110$ with $d\in \{1,\dots ,9\}$.

These classes exhaust the valid codes. A sequence starting with two is unrestricted thereafter. Otherwise a zero cannot occur in position two, a zero in position three requires the first two digits to be ones, and a zero in position four requires digits two and three to be ones. Positions three and four cannot both be zero, since the last zero would then lack the required preceding pair. Thus a code outside $A$ either belongs to $B$ or has precisely one of the zero patterns covered by $C,D$.

Their sizes areThe only nonempty pairwise intersections are $A\cap B$, consisting of first digit two and three nonzero remaining digits, and $A\cap D$, containing the single code $2110$. Hence $|A\cap B|=9^3=729$ and $|A\cap D|=1$. All other pairwise intersections vanish, and therefore so do all intersections of three or four classes. Applying inclusion-exclusion givesThis counts sequences actually enterable under the history-dependent zero-key rule, rather than simply counting sequences which contain the substring $110$.

A real sequence $x_n$ converges to $l$ if, for every $\epsilon >0$, there is an integer $N$ such that $|x_n-l|<\epsilon$ for every $n\ge N$. A convergent series ${\sum }_{n=1}^{\infty }{x}_n$ is one whose partial sums $s_N={\sum }_{n=1}^N{x}_n$ converge to a finite real limit.

If $s_N\to s$, then $x_N=s_N-s_{N-1}\to s-s=0$. This necessary condition is the term test for divergence. Its converse fails: the harmonic series has terms $1/n\to 0$ but diverges. For a direct proof, each block from $n=2^{j-1}+1$ to $2^j$ contains $2^{j-1}$ terms each at least $2^{-j}$, so contributes at least $1/2$. Infinitely many such blocks make the partial sums unbounded.

For the positive sequences in the final request, the inequality makes $y_n$ decreasing and bounded below by zero. The bounded monotone sequence theorem gives $y_n\to l\ge 0$. Summing the decrements givesSuppose $l>0$. Since $y_n\ge l$, this impliesBut clipping preserves divergence of a positive series: if infinitely many $x_n\ge l$, the clipped series has infinitely many terms equal to $l$; otherwise its tail equals the divergent tail of $\sum x_n$. Either case contradicts the displayed bound. Hence the only possible limit isThis proves the minimum-decrement convergence criterion without assuming that the divergent positive sequence $x_n$ itself tends to zero.

We use these countability facts: the integers are countable; a finite Cartesian product of countable sets is countable; a countable union of countable sets is countable; and every subset of a countable set is countable. Finite products can be enumerated by listing index tuples in increasing maximum coordinate, and countable unions by diagonal enumeration of pairs of indices.

Fix $d\ge 1$. For each degree bound $D$, there are finitely many monomials $X_1^{{\alpha }_1}\cdots X_d^{{\alpha }_d}$ with ${\alpha }_1+\cdots +{\alpha }_d\le D$. An integer polynomial of total degree at most $D$ is specified by an integer coefficient for each of them, so these polynomials form a finite Cartesian product of copies of $\mathbb{Z}$ and are countable. Every polynomial has some finite degree bound. Taking the union over $D=0,1,2,\dots$ proves the countability of integer polynomial rings:It is infinite because it contains all integer constant polynomials.

For $d=1$, each nonzero polynomial has only finitely many real roots: repeated application of the factor theorem bounds their number by its degree. The real algebraic numbers are the union of these finite root sets over the countably many nonzero integer polynomials. Thus they are countable. If the real transcendental numbers were countable too, their union with the algebraic numbers would make $\mathbb{R}$ countable, contrary to the allowed uncountability assumption. Hence there are uncountably many real transcendental numbers.

To construct an algebraically independent real sequence, choose $x_1$ outside the algebraic numbers. Suppose $x_1,\dots ,x_d$ already satisfy the required nonvanishing condition. For each nonzero $P\in \mathbb{Z}[X_1,\dots ,X_d,T]$, writeAt least one coefficient polynomial $P_j$ is nonzero, and the inductive hypothesis makes its value at $(x_1,\dots ,x_d)$ nonzero. Consequently $P(x_1,\dots ,x_d,T)$ is a nonzero one-variable polynomial and has only finitely many real roots. There are countably many choices of $P$, so the union of all these forbidden roots is countable. Choose $x_{d+1}$ outside it, which is possible because $\mathbb{R}$ is uncountable. This extends the nonvanishing condition to $d+1$. Recursion therefore givesIn particular the chosen numbers are distinct, since a relation $X_i-X_j$ is forbidden. Clearing rational denominators shows that every finite initial segment consists of algebraically independent elements over $\mathbb{Q}$.

For finite sets $A_1,\dots ,A_s$, the inclusion-exclusion principle statesTo prove it, consider an element belonging to exactly $d$ of the sets. If $d=0$, it contributes zero to both sides. If $d>0$, its contribution on the right iswhich is its contribution to the union. Summing these contributions proves the formula.

For the keypad, a first digit zero cannot be entered. Define four families of valid codes: $A$ consists of all codes with no zero; $B$ consists of codes beginning with $2$; $C$ consists of $110b$ with $b\in \{1,\dots ,9\}$; and $D$ consists of $a110$ with $a\in \{1,\dots ,9\}$. They cover every valid code. Indeed, if the first digit is not $2$, a zero in the second position is impossible; a zero in the third requires the prefix $11$; a zero in the fourth requires the middle pair $11$. In the third-position case the last digit cannot also be zero. Hence the only remaining zero-containing possibilities are exactly $C$ and $D$.

Their cardinalities areThe only nonempty pairwise intersections are $A\cap B$, with $9^3=729$ codes, and $B\cap D=\{2110\}$, with one code. All triple and fourfold intersections are empty. Applying inclusion-exclusion therefore givesThe restriction concerns actual preceding keypresses. It cannot license two successive zeros unless the first-key condition is already satisfied.