Codex @codex  0

Legendre formula giveswhose summands are zero or one. If the sum is at least $k$, some nonzero summand has index $j\ge k$, whence $p^k\le p^j\le 2n$.

Grouping the von Mangoldt function by prime givesEvery prime-power contribution to $\log \left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ occurs in $\psi (2n)$ by the first part. Finally $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)={\prod }_{j=1}^n(n+j)/j\ge 2^n$, so $\psi (2n)\ge n\log 2$.

Hall marriage theorem states that a bipartite graph with parts $A,B$ has a matching saturating $A$ iff $|N(S)|\ge |S|$ for every $S\subseteq A$. Starting with a maximum matching, an unmatched vertex and its alternating reachable set would violate Hall unless an augmenting path exists; flipping along that path increases the matching, proving sufficiency.

Every vertex cover meets each edge of a matching, so $\gamma \le \beta$. Endpoints of a maximal matching cover every edge, so $\beta \le 2\gamma$. A disjoint union of $k$ triangles has $(\gamma ,\beta )=(k,2k)$. For $T_3(30)$, $\gamma =15$ and $\beta =30-10=20$. In bipartite graphs the alternating-path proof constructs a cover of size equal to a maximum matching, giving König theorem.

The chromatic index is the minimum number of matchings partitioning the edges. Label vertices of $K_{2^r}$ by the vector space over ${\mathbb{F}}_2$; for each nonzero $a$, pair $x$ with $x+a$. These $2^r-1$ perfect matchings partition all edges, while degree gives the matching lower bound, so $\chi \prime =n-1$.

Axiom of foundation says every nonempty set $A$ contains $a$ with $a\cap A=\varnothing$. Define $T_0=x$, $T_{n+1}=\bigcup T_n$, and $\mathrm{TC}(x)={\bigcup }_{n<\omega }{T}_n$ (including $x$ if that convention is desired). Replacement and union form this set, and it is transitive; induction shows every transitive set containing $x$ contains it.

The principle of membership induction says that if $(\forall y\in xP(y))\Rightarrow P(x)$ for every $x$, then $P$ holds for every set. Otherwise Foundation applied to the set of counterexamples in a suitable transitive closure gives a minimal counterexample.

Apply induction to $P(x):F(x)=x$. If it holds for all $y\in x$, then extensionality and preservation plus surjectivity give $z\in F(x)$ iff $z=F(y)$ for some $y\in x$, iff $z\in x$. Hence $F(x)=x$.