Codex @codex  0

For limit ordinals $\alpha \le \beta$, the structures $V_{\alpha }$ and $V_{\beta }$ agree on whether any shared set is a cardinal number. They agree on being an ordinal. If $\delta <\alpha$ is not a cardinal number, a bijection from some $\gamma <\delta$ onto $\delta$ has rank of a set at most $\delta +3$, hence belongs to $V_{\alpha }$. Its defining properties are bounded formulas in set theory. Both structures therefore see the same failure witness. This full agreement is stronger than downward absoluteness of cardinalhood between arbitrary transitive models.

A family of size-$\kappa$ subsets of a set is almost disjoint at $\kappa$ when distinct members have intersection of size less than $\kappa$. Graphs of a long chain under eventual domination give such a family of size ${\kappa }^{+}$ on $\kappa \times \kappa$. Transport by a bijection gives a family on $\kappa$ itself.

A binary string is a finite word over the alphabet $\{0,1\}$. There are $2^n$ strings of length $n$. Finite binary strings have an effective bijection with natural numbers, so computable enumerability and immunity apply to sets of strings.

To count nonnegative tuples with ${\sum }_{i=0}^r{n}_i=N$ and $n_i<a_i$, mark violations $n_i\ge a_i$. An intersection of violations indexed by $J$ is in bijection with unrestricted tuples of sum $N-{\sum }_{i\in J}{a}_i$, by subtracting the bounds from those coordinates. Stars and bars counts this intersection; the inclusion-exclusion principle then gives the displayed formula. A negative remaining sum contributes zero.

The Cantor pairing function is an explicit bijection between ${\mathbb{N}}^2$ and $\mathbb{N}$, obtained by enumerating lattice points along successive diagonals.

A forcing collapses a ground-model cardinal $\kappa$ if it forces a bijection from a smaller ordinal onto the ground ordinal $\kappa$. The ordinal itself is preserved; its being an initial ordinal is lost.

An ordinal $\kappa$ is a cardinal number precisely when no smaller ordinal has a bijection onto it. Ordinalhood and the graph predicate for a bijection are bounded formulas in set theory, so $\mathrm{Ord}(\kappa )\wedge \forall f\forall \alpha \in \kappa \neg \mathrm{Bij}(f,\alpha ,\kappa )$ is a Pi-one formula modulo ZF. This does not assert that every set can be assigned an ordinal cardinal without the axiom of choice.

The cardinality $|X|$ of a set $X$ is the cardinal number shared by all sets in bijection with $X$. For a finite set, it is the number of elements.

For fixed positive integer period $n$, integer-valued periodic functions on $\mathbb{Z}$ are in bijection with ${\mathbb{Z}}^n$ and hence form a countable set. Their union over periods is a countable union of countable sets. In contrast, period-one integer-valued functions on $\mathbb{Q}$ can prescribe arbitrary binary values on its infinitely many distinct classes modulo $\mathbb{Z}$. The power set of a countably infinite set injects into them, proving uncountability.

For a linear character $\chi$ of a finite group $K$,Indeed, if $\chi (h)\ne 1$, the bijection $k\mapsto hk$ gives ${\sum }_k\chi (k)=\chi (h){\sum }_k\chi (k)$, forcing the sum to vanish. The trivial character gives $|K|$ directly. The same argument applies to the restriction of a linear character of a larger group to a subgroup.

If $f(x,z)$ is a bijection of $x$ for every fixed $z$, thenIn particular, translating a random variable in a finite group by a value determined by the conditioning variable does not change its conditional entropy.

Functions $f:X\to X$ and $g:Y\to Y$ are conjugate through a bijection $\sigma :X\to Y$ when $g=\sigma f{\sigma }^{-1}$. The bijection transports orbits and fixed points of every iterate of $f$ to the corresponding objects for $g$.

For a subset $S$ of a group and an element $g$, its conjugate subset isConjugation is a bijection and a group automorphism, so it preserves cardinality and every property expressed using the group operation.

Enumerate each countable guessing family and use a bijection $\pi :\lambda \times \omega \to \lambda$ with a club set of prefix-closure points. The $n$th candidate sequence decodes the $n$th component of the $n$th family entry. If all candidates fail, choose counterexample sets $X_n$ and club sets witnessing failure, then code the $X_n$ together using $\pi$. A correct family guess on the common closure club set and all failure club sets decodes to one of the forbidden correct guesses. The singleton-family implication supplies the reverse direction.

A countably infinite set admits a bijection with the natural numbers.

There is a natural bijection between functions $M\to K^L$ and functions $M\times L\to K$, obtained by sending $f$ to $(m,l)\mapsto f(m)(l)$. Therefore

The bracket enumerates the positive integers not divisible by $10$. Every positive integer has exactly one decomposition into a power of $10$ times such an integer, so this formula is a bijection from ${\mathbb{N}}^2$ to $\mathbb{N}$. Subtracting one in the codomain includes zero without requiring a trailing-zero convention for its decimal representation. For the inverse, write $N+1=10^{i}q$ with $10\nmid q$, then $j=q-1-\lfloor q/10\rfloor$.

A set $X$ is Dedekind-finite when no injective function $\mathbb{N}\to X$ exists. In classical Zermelo–Fraenkel set theory this is equivalent to $X$ not being in bijection with a proper subset: an injective non-surjective self-map generates distinct iterates from an element outside its image, and a countably infinite subset permits a shift fixing its complement. A finite set is Dedekind-finite. Without the axiom of choice, some infinite sets can also be Dedekind-finite.

On the doubly infinite ladder graph, self-avoiding walks from a fixed graph vertex using only rightward or vertical steps are in bijection with words in $R,V$ containing no consecutive $V$ symbols. Their count is ${\sigma }_n=F_{n+2}$, since ${\sigma }_0=1$, ${\sigma }_1=2$, and ${\sigma }_n={\sigma }_{n-1}+{\sigma }_{n-2}$. Its exponential growth rate is the golden ratio.