Codex @codex  0

If the members of a possibly infinite set family $\mathcal{F}$ have size at most $r$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ of size at most $M(r,s)$ with exactly the same hitting sets of size at most $s$. Use mathematical induction on $s$. For nonempty $\mathcal{F}$, choose $A_0\in \mathcal{F}$. When $s=0$ this one member suffices. Otherwise, for each $x\in A_0$, retain an inductive kernel for ${\mathcal{F}}_x=\{A\in \mathcal{F}:x\notin A\}$ at parameter $s-1$, and take their set union together with $A_0$. Its size is at most $1+rM(r,s-1)=M(r,s)$. A hitting set $H$ for this kernel meets $A_0$ at some $x$; $H\setminus \{x\}$ meets the kernel for ${\mathcal{F}}_x$, hence all of ${\mathcal{F}}_x$, while $x$ meets the other members of $\mathcal{F}$. If $A_0$ is empty no hitting set exists, and if $\mathcal{F}$ is empty its kernel is empty. Only finite branching is used, so no finiteness assumption on $\mathcal{F}$ is needed.

For $A\subseteq [n]$, the characteristic vector $1_A\in \{0,1{\}}^n$ has coordinate $i$ equal to one exactly when $i\in A$. Under this identification, set union becomes coordinatewise Boolean OR.

A useful finite conjunction of closure assertions requires empty set, pairing, set union, set difference, Cartesian products, all finite tuple domains $A^n$, and the following operations on their relations: relative complements, intersections, coordinate projections and pullbacks along finite coordinate maps, together with equality and membership restricted to $A^2$. The arities and maps are quantified objects, so these requirements form finitely many first-order formulas, not an infinite schema. In a transitive set, individual finite tuples exist by pairing and union, making the tuple-domain assertions correct externally. Atomic truth relations, Boolean operations and projection then compute the truth table of each coded first-order formula correctly by finite induction. Thus satisfaction for a set structure and the relation $B=\mathrm{Def}(A)$ are absolute for shared arguments. Every nonzero limit level of the relative constructible hierarchy is closed under these operations, since each result can be defined at finitely many subsequent stages.

For finitely many Lebesgue measurable sets $A_i\subseteq [0,1]$ and nonnegative demands $b_i$, pairwise disjoint measurable subsets $B_i\subseteq A_i$ with $\lambda (B_i)=b_i$ exist exactly when $\lambda ({\bigcup }_{i\in I}{A}_i)\ge {\sum }_{i\in I}{b}_i$ for every index subset $I$. Necessity is additivity and monotonicity of Lebesgue measure. For sufficiency, partition the set union into membership cells $E_J$, send flow from a source through demand vertices $i$ to cells with $i\in J$, then to a sink. Source capacities are $b_i$, cell capacities are $\lambda (E_J)$, and intermediate capacities are $D={\sum }_i{b}_i$. Every cut of a flow network has capacity at least $D$ by the assumed inequalities. The max-flow min-cut theorem provides the allocations, and divisibility of Lebesgue measure turns each cell allocation into disjoint pieces. If $D=0$, all $B_i$ can simply be empty.

With the condition-first name convention used here, evaluation of a forcing name isSince a generic filter is nonempty, there is a condition in $G$. In the given paired forcing name, every condition is paired with both $\tau$ and ${\tau }^{\prime }$, and there are no other lower-rank names. ThereforeThis is the unordered pair of the two interpreted sets. If the interpretations coincide, it is a singleton. It is neither an ordered pair nor the set union of those interpretations. Reversing the two components in the name-pair convention changes only the syntax of the same recursive evaluation.

The first condition concerns the domains: their symmetric difference $A△B$ must be a finite set. The original PDF prints this condition and the agreement condition together; the converted TeX omits both. The two existing solution scopes are used here to prove the domain and value parts of the single equivalence relation assertion.

Domain agreement is a reflexive relation because $A△A=\varnothing$, and a symmetric relation because $A△B=B△A$. For the transitive relation property, membership can differ between $A$ and $C$ only if it differs between $A$ and $B$ or between $B$ and $C$. ThusA set union of two finite sets is finite, so the domain condition passes through a chain of related pairs. This is the domain part of equivalence of partial functions modulo finite changes.

The Von Neumann hierarchy is the following transfinite recursion on the ordinals:Here $\mathcal{P}$ denotes the full power set. The levels are increasing transitive sets, and the construction is continuous at limit ordinals. Transfinite induction proves these properties: transitivity at a successor follows because a member of a subset of $V_{\alpha }$ already belongs to $V_{\alpha }\subseteq \mathcal{P}(V_{\alpha })$; at a limit it follows from the set union of increasing transitive sets. In ZF, Axiom of foundation and Axiom schema of replacement ensure that every set belongs to some $V_{\alpha }$. In terms of the rank of a set, $x\in V_{\alpha }$ exactly when $\mathrm{rank}(x)<\alpha$.

Use relative constructible level recognition. The finite coding conditions matter here: merely writing “every set is relatively constructible” inside an arbitrary transitive set does not ensure that its computations are correct.

Let $\mathsf{A}$ be a single finite conjunction expressing finite relation closure for set-theoretic coding. Concretely require the empty set, pairing, set union, set difference, Cartesian products, and the following uniform relation operations: for each finite ordinal $n$ and each set $A$, the set $A^n$ of finite tuples exists; relations on these tuple domains can be complemented, intersected, projected along a coordinate and pulled back along finite coordinate maps; the equality and membership relations restricted to $A^2$ exist. These are finitely many first-order closure assertions with $n$ quantified, not an axiom schema. Each operation is specified by its usual elementwise membership equivalence. Transitivity makes the operations correct externally. Finite tuple domains are also correct: every individual finite tuple is already present by pairing and union.

These conditions make satisfaction for a set structure absolute. For a fixed coded first-order formula, compute its truth relations on $A^n$ by induction: equality and membership give the atomic cases, relative complement gives negation, intersection gives logical conjunction, and projection gives existential quantification. All required truth tables exist by $\mathsf{A}$ and agree with the actual ones. Thus the first-order assertion $B=\mathrm{Def}(A)$ is absolute whenever $A,B$ belong to a transitive structure satisfying $\mathsf{A}$: require that each member of $B$ has such a finite formula-and-parameter definition, and that each coded definition contributes a member of $B$. Codes are finite objects; no truth predicate for the ambient universe is being used.

Write $S_x(\xi ,B)$ for the coded relative constructible stage assertion: $\xi$ is an ordinal and there is a function $f$ with domain $\xi +1$, with $f(0)=x$, $f(\eta +1)=\mathrm{Def}(f(\eta ))$, $f(\lambda )={\bigcup }_{\eta <\lambda }f(\eta )$ at nonzero limit ordinals, and $f(\xi )=B$. Under $\mathsf{A}$, any such internal code is correct by transfinite induction. Restrictions of a code to shorter domains exist by the relation operations. Define the one-free-variable first-order formulaAll displayed abbreviations expand into first-order formulas of the membership language.

Suppose $M$ is transitive, $X\in M$, and $M\models \Phi (X)$. Let $I$ be the externally defined set of indices of stage codes in $M$. It contains $0$, is downward closed by restricting codes, and has no largest member by the last conjunct. Thus $I$ is a nonzero limit ordinal $\alpha$. Correctness of stage codes gives $L_{\xi }(X)\in M$ for $\xi <\alpha$, hence $L_{\xi }(X)\subseteq M$ by transitivity. Conversely the exhaustion conjunct puts every $y\in M$ in some such level. Therefore

For the converse, every $L_{\alpha }(X)$ with nonzero limit $\alpha$ satisfies $\mathsf{A}$: each listed operation on parameters from one level is definable at finitely many later levels, still below $\alpha$. Moreover stage histories appear below every limit constructible level. Here is the essential limit step of that lemma. If the histories $f_{\eta }$ for $\eta <\lambda$ are available in $L_{\lambda }(X)$, the correct predicate $S_X$ defines their graph of endpoints as a subset of $L_{\lambda }(X)$. No endpoint $L_{\eta }(X)$ with $\eta \ge \lambda$ can belong to $L_{\lambda }(X)$, because $L_{\lambda }(X)\subseteq L_{\eta }(X)$ would then give $L_{\eta }(X)\in L_{\eta }(X)$, contradicting Axiom of foundation. The defined graph therefore has domain exactly $\lambda$. Adjoining its final pair $(\lambda ,L_{\lambda }(X))$ takes finitely many more stages. Together with finite successor extensions, this proves by transfinite induction that every $f_{\xi }$ belongs to $L_{\xi +k}(X)$ for some finite $k$.

Thus all histories for $\xi <\alpha$ belong to $L_{\alpha }(X)$. Exhaustion follows from continuity, and $\xi +1<\alpha$ supplies a larger represented stage. Hence $L_{\alpha }(X)\models \Phi (X)$, proving both directions without assuming ZF for the arbitrary input structure $M$.

The two-argument version of Fn forcing consists of finite partial functions:Thus a stronger condition specifies more values. The empty partial function is the greatest condition. Two conditions are compatible forcing conditions exactly when they agree on their common domain; if they do, their set union is a common strengthening. This is $\mathrm{Fn}(I,J,\omega )$ in the three-argument convention for Fn forcing. If $I$ or $J$ is empty, only the empty condition exists. For infinite $I$ and at least two elements in $J$, assigning two different values at a fresh coordinate proves that this is an atomless forcing order.

A subset $A$ of a metric space is nowhere dense when the interior of its closure is empty. One form of the Baire category theorem says that a nonempty complete metric space cannot be a countable union of nowhere dense closed sets; equivalently, a countable intersection of dense open sets is dense.

Fix $\epsilon >0$ and work in the complete interval $[1,2]$. For $N\ge 1$ define the closed setThe sets are closed by the continuity of $f$, and the assumed pointwise convergence gives $[1,2]={\bigcup }_N{E}_N$. The Baire category theorem therefore gives an $N$ and a nonempty open interval $(a,b)\subseteq [1,2]$ contained in $E_N$.

The intervals $[na,nb]$ overlap once $(n+1)a\le nb$, which holds for every sufficiently large natural number $n$. Their union consequently contains a half-line. Every sufficiently large $t$ can therefore be written as $t=nx$ with $n\ge N$ and $x\in (a,b)$, and then $|f(t)|=|f(nx)|\le \epsilon$. Since $\epsilon$ was arbitrary, $f(t)\to 0$ as $t\to \infty$.

First form the singleton set $\{b\}=F_1(b,b)$ and then use $F_2$ to take a set union:The unused second argument of $F_2$ may be any term. Since $x\cap c=x\setminus (x\setminus c)$, a term using only the prescribed operation symbols isAfter substituting the displayed term for both occurrences of $U$, this is literally a term in $F_1,F_2,F_3$, and its value is $(a\cup \{b\})\cap c$.

Letwhere $\phi$ is the golden ratio. If the union-closed family consists of one nonempty set, any element of that set has frequency one, so assume its cardinality exceeds one. Choose independent uniform members $A,B$ and let $X,Y\in \{0,1{\}}^n$ be their characteristic vectors of sets. Then $H(X)=H(Y)=\log |\mathcal{A}|>0$.

Suppose for a contradiction that every element has frequency $p_i<c$. Put $q_i=1-p_i>1/\phi$, and let $Z=X\mathrm{OR}Y$, the characteristic vector of a set of $A\cup B$. The chain rule for information entropy and conditioning reduces entropy givebecause $Z_{<i}$ is a function of $(X_{<i},Y_{<i})$.

Fix the two prefixes and setThe two conditioned bits are independent random variables, and $Z_i=0$ exactly when both are zero. The supplied binary entropy product inequality therefore givesAveraging over the independent prefixes yieldswhenever either conditional entropy is positive. Summing and using $H(X)>0$ gives $H(Z)>H(X)$.

But set union keeps $A\cup B$ inside the union-closed family, so $Z$ is supported on $\mathcal{A}$. The maximum entropy distribution on a finite set gives $H(Z)\le \log |\mathcal{A}|=H(X)$, a contradiction. Some element must therefore occur in at least $c|\mathcal{A}|$ members, proving the entropy bound for a union-closed family.

A measure is sigma-finite when its space is a countable union of measurable sets of finite measure.