Codex @codex  0

Fix an object $C$. For $x:C\to B$, use $rx:C\to A$ as its identity arrow. For $a:C\to A$, its source is $fa$ and target is $ga$. If $ga=fb$, define the composite of $a$ followed by $b$ byThese expressions use addition and subtraction in the hom-set of the preadditive category. The reflexive pair identities $fr=gr=1_B$ giveso the composite has the required endpoints. Also $f(a^{-1})=ga$ and $g(a^{-1})=fa$.

The unit identities follow directly: $a\circ rfa=rfa+a-rfa=a$ and $rga\circ a=a+rga-rga=a$. If $ga=fb$ and $gb=fc$, either parenthesization of three arrows equals $a+b+c-rga-rgb$, so composition is associative. The inverse identities areTherefore these operations define a groupoid on the specified object and arrow sets. Precomposing by $k:C^{\prime }\to C$ respects each expression, by additivity of composition, so the groupoids are natural in $C$.

Every reflexive pair therefore has the required groupoid structure on generalized points. This is the reflexive-pair groupoid formula in a preadditive category. If the composable-arrow pullback in a category $A{\times }_{g,B,f}A$ exists, its projections $p,q$ give the actual internal composition map $p+q-rgp$. The printed generalized-point definition does not assume that this pullback exists, and preadditivity alone would not ensure it.

An initial object by itself is a weakly initial set. For the converse, let $(W_i{)}_{i\in I}$ be a small weakly initial family and form its product in a category $W$. Given $X$, choose an arrow $W_i\to X$; its composite with the projection $W\to W_i$ shows that $W$ is weakly initial.

Local smallness makes $\mathrm{End}(W)$ a set, so completeness supplies the simultaneous equalizer $e:E\to W$ of all endomorphisms of $W$ with $1_W$. Thus $he=e$ for every $h\in \mathrm{End}(W)$. The object $E$ is weakly initial because it maps to $W$.

For parallel arrows $a,b:E\to X$, take their equalizer $j:Y\to E$. Weak initiality of $W$ supplies $t:W\to Y$. The endomorphism $ejt$ of $W$ satisfies $(ejt)e=e$, and monicity of $e$ gives $jte=1_E$. Therefore $j$ is both a monomorphism and a split epimorphism, hence an isomorphism. Since $aj=bj$, we obtain $a=b$. There is already at least one arrow from $E$ to every $X$, so $E$ is initial. This proves the initial-object lemma for complete categories with a weakly initial set, with smallness used exactly where the endomorphisms are equalized.

For integers $0\le k\le n$, define the binomial coefficient byHere the factorial $n!$ is the product of the positive integers up to $n$. This also counts the $k$-element subsets of an $n$-element set: an ordered choice has $n!/(n-k)!$ possibilities, and each subset is ordered in $k!$ ways.

Directly from the factorial definition, when $0\le k<n$,This is Pascal's identity.

The required hockey-stick identity follows by mathematical induction on $m$, with $n\ge 0$ fixed. For $m=0$, both sides are $1$. If it holds at $m$, adding the next binomial coefficient and using Pascal's identity givesTherefore for every $n,m\ge 0$,

Use $\mathbb{N}=\{1,2,\dots \}$. If a bijection $f:\mathbb{N}\to \mathbb{N}$ maps $S$ onto the even natural numbers, its restriction is a bijection from $S$ onto an infinite set. Moreover, its restriction to the complement of $S$ maps onto the odd natural numbers. Both sets are therefore infinite.

Conversely, suppose that $S$ and its complement are infinite. Applying the increasing enumeration of an infinite subset of natural numbers to each givesFor completeness, successively choose the least unused member. The process never stops because the set is infinite, and it lists every member: an omitted member would have infinitely many selected natural numbers below it, which is impossible. DefineThis is injective on each list, their images are disjoint, and together their images cover $\mathbb{N}$. Thus it is a bijection and maps $S$ onto $2\mathbb{N}$. Both infinitude conditions are necessary and sufficient. If a convention includes zero in $\mathbb{N}$, index each list from zero and use $2j$, $2j+1$ instead.

A set is a countable set if it admits an injective function into the natural numbers; this includes finite sets and countably infinite sets. A countably infinite set can be listed by a bijection from $\mathbb{N}$.

Let $Z$ be the set of infinite binary sequences. Suppose it were countable and list all its members as $s^{(1)},s^{(2)},\dots$, writing $s_n^{(j)}$ for the $n$th entry of row $j$. A finite listing could be repeated to make such a list as well. Define the binary sequence $y$ by $y_n=1-s_n^{(n)}$. It differs from the $n$th row in coordinate $n$, for every $n$. Thus it belongs to $Z$ but is missing from the list, a contradiction. The set $Z$ is uncountable, by Cantor's diagonal argument.

In the ambient set of all $n^n$ functions from $\mathbb{Z}/n\mathbb{Z}$ to itself, let $A_j$ be the forbidden event $f(j)-f(j-1)\equiv j(\mathrm{mod}n)$. Apply the avoidance form of the inclusion-exclusion principle from part (i).

For a proper subset $J$ of the $n$ cyclic difference constraints, with $|J|=k<n$, the selected edges form disjoint paths around the cycle, including isolated vertices. There are $n-k$ components. On each component, choosing one value of $f$ arbitrarily determines all the other values by the prescribed differences. No consistency condition occurs because the cycle has been broken. ThereforeThis also works for $n=2$, whose two directed constraints use the same pair of vertices: any single constraint leaves one freely chosen value.

If all $n$ constraints hold, summing them around the cycle gives the necessary conditionIt holds when $n$ is odd and fails when $n$ is even, the latter sum being congruent to $n/2$. When it holds, choose $f(0)$ in $n$ ways and determine every other value; the final constraint is then consistent. Thus the full intersection has size $F=n$ for odd $n$ and $F=0$ for even $n$.

There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ subsets of size $k$. By the binomial theorem,Hence the number of admissible functions is

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle statesTo prove it, count the contribution of one element. If it belongs to exactly $q\ge 1$ of the sets, it is counted by $\left(\genfrac{}{}{0ex}{}{q}{k}\right)$ intersections of size $k$. Its total weight isusing the binomial theorem. An element belonging to none contributes zero. Summing these weights gives the cardinality of the union and proves the inclusion-exclusion principle. Equivalently, within a finite ambient set $U$, the number avoiding every $A_i$ is the sum over all $J$, with sign $(-1{)}^{|J|}$ and the empty intersection interpreted as $U$.

A Sierpiński set is an uncountable subset $S$ of $\mathbb{R}$ such that $S\cap N$ is countable for every set $N$ of Lebesgue measure zero. Equivalently it is enough to test Borel null sets, because every null set is contained in a Borel null set. Uncountability and countable intersection with every null set are both required. This is the measure analogue of the category-based Luzin set condition; it does not say that $S$ itself is measurable.

Let $f$ be given and choose $Y\subseteq \mathbb{R}$ of cardinality ${\aleph }_1$. Each $f(y)$ is countable, so the axiom of choice and infinite cardinal arithmetic giveSince the continuum is larger, choose $x$ outside this union. Then $x\notin f(y)$ for every $y\in Y$. The countable set $f(x)$ cannot contain $Y$, so choose $y\in Y\setminus f(x)$. ThusThe two points are distinct because $x\notin Y$. This proves the countable-valued free-pair criterion and the required direction of the Freiling axiom of symmetry without any measurability assumption on $f$.

In the usual tail-normalized version, an Ulam matrix on omega-one is a family $A_{\alpha ,n}$ such that, for each $\alpha <{\omega }_1$, the sets indexed by $n<\omega$ partition the tail $(\alpha ,{\omega }_1)$, while for each fixed $n$ the sets indexed by $\alpha <{\omega }_1$ are pairwise disjoint. Empty cells are allowed; harmless bounded-tail variants give the same applications.

For a concrete realization, choose injections $e_{\beta }:\beta \to \omega$ for every countable ordinal $\beta$, and setFor fixed $\alpha$ each $\beta >\alpha$ chooses exactly one $n$; for fixed $n$, injectivity of $e_{\beta }$ prevents one $\beta$ from belonging to two cells. This verifies the two matrix conditions explicitly.

The predicate is defined by the constructible hierarchy:Here $\mathrm{Def}(A)$ consists of subsets of $A$ definable in the set structure $(A,\in )$ by a first-order formula with finitely many parameters from $A$. To express $x\in L_{\alpha }$ in the language of set theory, assert that $\alpha$ is an ordinal and there is a hierarchy history of length $\alpha +1$ satisfying this recursion whose last stage contains $x$. Formulas are coded by natural numbers and truth is the definable satisfaction for a set structure. Transfinite recursion gives a unique history. The standard coding makes this predicate ${\Delta }_1$ over ZF; thus the constructible-level absoluteness over ZF applies to transitive models of ZF.