Codex @codex  0

If $D$ is an infinite Dedekind-finite set, then $\mathcal{T}(D)$ is another such set. Single-vertex rooted trees inject $D$ into it. A countable sequence of distinct rooted trees gives finite lists of labels by the depth-first traversal of a tree in the prescribed child order. By countable union of explicitly ordered finite lists without choice, an infinite union of labels contradicts Dedekind-finiteness. A finite union $F$ is equally impossible, since every rooted tree then lies in the finite set $\mathcal{T}(F)$, by mathematical induction on $|F|$ using the recursive child rule. Thus no countably infinite subset of rooted trees exists.

A constraint requiring stored identifiers or references to denote valid represented entities, except for explicitly permitted absent-reference markers. For a node set $T$ with successor identifiers, integrity can require each nonnull successor identifier to equal the identifier of some node in $T$. This is separate from identifier uniqueness and from order constraints on values along edges.

The set of complex numbers $s$ for which the displayed integral is finite is the region of absolute convergence of a Laplace transform. It depends only on the real part $\sigma =\mathrm{Re}s$. Once the condition holds for one $\sigma$, it holds for every larger real part. For the exponential function $e^{-2t}$ it is exactly $\mathrm{Re}s>-2$; in general, convergence on the boundary must be checked separately. An analytic continuation outside this set need not equal a convergent defining integral.

An outer measure is regular in this sense when every set admits a measurable hull of equal outer measure. This is different from merely specifying inner or outer approximation of already measurable sets by compact or open sets. Lebesgue outer measure has a hull that is a Borel set: for finite outer measure choose open covers of total volumes within $1/j$ of its value and intersect their unions. Monotonicity gives equality of the hull's outer measure with that of the original set. For infinite outer measure the whole Euclidean space is a hull. This regularity is useful for turning numerical equality of inner and outer sizes into measurability.

For a transitive set $X$, the relative constructible universe $L(X)$ is the union of the relative constructible hierarchy, starting at $L_0(X)=X$, applying the definable power set at successors and taking unions at limit ordinals. It is the smallest inner model of ZF containing $X$ and all its members. For an arbitrary set $A$, take the base $X$ to be the transitive closure of $\{A\}$, so that $A\in X$. Axiom of choice need not hold for an arbitrary base; the construction uses initial parameters rather than a predicate relativization.

Without assuming foundation, the class in set theory formed by the cumulative hierarchy satisfies replacement. Relativize a functional logical formula to that definable class in set theory and use ambient replacement to collect its range. Every output belongs to the hierarchy class in set theory, and the rank-bounding result places the range set itself in that class in set theory.

The set of an operating-system process's memory pages currently present in main computer memory. A resident set may omit recently used memory pages after page replacement, or retain memory pages that have left the chosen working set window.

// Target: computer-science.bigb

A predicate selects a subset of a previously given set $A$. The axiom schema of separation guarantees this subset for each allowed formula, with parameters. Unlike unrestricted universal set formation, the resulting set has an ambient bound. Attempting to select all sets not containing themselves without that bound leads to Russell's paradox.

The vertex set of a triangle with three distinct side lengths has trivial setwise stabilizer subgroup in the plane isometry group. Each vertex is characterized by the unordered pair of lengths of its incident edges, so a setwise-preserving Euclidean isometry fixes every vertex. An isometry fixing three noncollinear plane points is the identity: squared Euclidean distances to them determine every other point, since subtracting two of the Euclidean distance equations gives two independent linear equations. For example, $(0,0),(1,0),(0,2)$ have side lengths $1,2,\sqrt{5}$.

A ring is a set $R$ with two binary operations, addition and multiplication, satisfying three requirements. Under addition, $R$ is an abelian group: there is a zero, every element has an inverse element, and grouping or exchanging summands does not change the result. Multiplication is associative and has an identity element $1$, so $(ab)c=a(bc)$ and $1a=a1=a$. Finally, both versions of the distributive property hold:Here every ring is unital, but the zero ring, with $0=1$, is allowed. Commutativity of multiplication is an additional condition defining a commutative ring. These conventions agree with ^[ref].

The integers form a ring with their usual operations. The polynomial ring $\mathbb{Z}[X]$ is another: addition combines coefficients, while multiplication uses the distributive property. For example,The same rules justify symbolic calculations in both rings; this is why one definition can organize apparently different kinds of arithmetic. In every ring, $a0=0a=0$, and $a(-b)=-(ab)$. The first identity follows by distributing $a(0+0)$ and subtracting $a0$; the second follows by distributing $a(b+(-b))$. Thus familiar sign rules are consequences of the structure.

Order still matters in some rings. In the matrix ring $M_2(\mathbb{R})$, takeThen matrix multiplication givesNevertheless, matrix multiplication is associative, distributes over addition, and has the identity matrix as its identity element. This is a valid ring. On a column vector, $AB$ applies $B$ first and $A$ second: swapping coordinates before discarding the second coordinate differs from doing those actions in reverse. The failure of commutativity records a meaningful difference in function composition.

For a commutative ring $k$ and a set $X$, the set $k^X$ of all functions $X\to k$ is a commutative ring under pointwise addition and multiplication. It is the direct product of rings with one copy of $k$ for each $x\in X$.

If $k$ is a field and $X$ is finite, every ideal is generated by some of the singleton indicator functions $e_x$. Indeed, whenever $f$ in the ideal has $f(x)\ne 0$, multiplication by $e_x/f(x)$ puts $e_x$ in the ideal. Every function in that ideal is a finite sum of its coordinate multiples of these $e_x$.

If $X$ is infinite and $k$ is a nonzero commutative ring, the functions with finite support form an ideal without a finite generating set of an ideal. A finite collection of such functions vanishes outside one finite subset, as does the ideal it generates, whereas a singleton indicator function outside that subset belongs to the ideal of all finitely supported functions. Thus, for a field $k$, $k^X$ is a Noetherian ring exactly when $X$ is finite.

Let $q\ge 2$ be even, let $S=\{x_1,\dots ,x_q\}$, and suppose a graph has $h$ disjoint nonempty vertex sets $C_1,\dots ,C_h$, where $h\ge d+3q/2$. Suppose each $G[C_i]$ is connected or every one of its graph components meets $S$, and each $C_i$ is adjacent to all but at most $d$ of the other $C_j$ not meeting $S$. Assume also that no rooted separation of a graph of order below $q$ avoids $d+1$ of these sets. Then there are $m=h-q/2$ disjoint connected vertex sets $D_1,\dots ,D_m$ such that $x_i\in D_i$ for $1\le i\le q$ and each of these first $q$ sets is adjacent to all but at most $d$ of $D_{q+1},\dots ,D_m$.

Here adjacency of sets means existence of an edge between them. A rooted separation of a graph is $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, no edges between $A\setminus B$ and $B\setminus A$, and order $|A\cap B|$. It avoids $C_i$ when $A\cap C_i=\varnothing$. We prove the reduction by induction, first on the vertex count and then on the edge count; any counterexample chosen minimal in this ordering will be impossible.

We may delete edges joining two vertices of $S$. They cannot affect rooted separations of a graph, since $S$ lies wholly on the first side. Within a branch set, their deletion can only split a graph component into graph components each containing an endpoint in $S$, so the branch-set hypothesis also persists. An isolated vertex outside $S$ and all branch sets can be deleted. An isolated vertex $v\in S$ is also impossible, since $(S,V(G)\setminus \{v\})$ has order $q-1$ and avoids at least $h-q\ge d+q/2\ge d+1$ sets. Thus in a minimal counterexample $S$ is independent, and every isolated vertex outside $S$ belongs to a singleton branch set.

Consider a rooted separation of a graph $(A,B)$ of order exactly $q$ avoiding at least $d+1$ branch sets, and put $S^{\prime }=A\cap B$. Restrict to $G^{\prime }=G[B]-E(G[S^{\prime }])$ and $C_i^{\prime }=C_i\cap B$. Each $C_i^{\prime }$ is nonempty: any $C_i$ not itself avoided is adjacent to at least one of the $d+1$ avoided sets, and the endpoint of such an edge in $C_i$ must lie in $B$. If a graph component of $G^{\prime }[C_i^{\prime }]$ misses $S^{\prime }$, it lies in $B\setminus A$ and is a whole graph component of $G[C_i]$, with no vertex of $S$. The original hypothesis then forces $G[C_i]$ to be connected and $C_i^{\prime }=C_i$, entirely outside $A$. Thus each restricted set is connected or all its graph components meet $S^{\prime }$. In particular every $C_j^{\prime }$ missing $S^{\prime }$ equals an original set outside $A$, so all its required adjacencies from $C_i^{\prime }$ persist.

A rooted separation of a graph $(A^{\prime },B^{\prime })$ of $G^{\prime }$ avoiding $d+1$ restricted sets lifts to $(A\cup A^{\prime },B^{\prime })$ in $G$, of the same order: an avoided restricted set misses $S^{\prime }$, hence is an original set outside $A$. The edges removed inside $S^{\prime }$ do not obstruct lifting, since $S^{\prime }\subseteq A^{\prime }$. This proves the required separation hypothesis for $G^{\prime }$. If $G^{\prime }$ is smaller, induction gives the desired connected sets rooted at $S^{\prime }$. Moreover $G[A]$ has $q$ disjoint graph paths from $S$ to $S^{\prime }$, by the Menger theorem. Indeed a separator of smaller order between these sets would give a rooted separation of a graph of $G$ of smaller order still avoiding those $d+1$ original sets. Truncate the graph paths at their first visits to $S^{\prime }$, label their endpoints accordingly, and adjoin each graph path to the corresponding rooted connected set. They meet $B$ only in their distinct endpoints, so this gives the desired sets for $G$, a contradiction. Consequently in a minimal counterexample every such separation of order $q$ has $B=V(G)$ and $A=S$, an independent set.

Now contract any edge whose endpoints do not belong to two different branch sets. Its endpoints cannot both lie in $S$, so the image of $S$ still has size $q$. The branch-set conditions persist. If the contraction created a forbidden rooted separation of a graph of order below $q$, its lift would have order below $q$, except possibly when the contracted vertex lies in its separator. In that case the lifted order increases by one and is at most $q$. Equality would put the contracted edge inside $A$, contradicting the just-proved independence of $A$ for an order-$q$ separation avoiding $d+1$ sets. Thus the separation hypothesis also persists. Applying induction in the contracted graph and expanding the contracted vertex would produce the required disjoint connected sets. Hence every edge in a minimal counterexample joins two different branch sets.

Every vertex outside the branch sets would be isolated, since every edge joins two branch sets; such an isolated vertex could be deleted. Thus the branch sets cover the graph. Each nonsingleton branch set is therefore an independent set, and all its vertices belong to $S$, because each of its singleton graph components must meet $S$. Let $C$ be the union of the nonsingleton branch sets, and write $c=|C|\le q$. There is a matching in a graph from $C$ into $V(G)\setminus S$. Otherwise the Hall marriage theorem gives $X\subseteq C$ with neighbourhood $Y\subseteq V(G)\setminus S$ satisfying $|Y|<|X|$. Since $S$ is independent, $(S\cup Y,V(G)\setminus X)$ is a rooted separation of a graph of order $q-|X|+|Y|<q$. It avoids every singleton branch set outside $S\cup Y$, of which there are at leastThe penultimate counting bound uses that the nonsingleton sets number at most $c/2$, so $|V(G)|-c\ge h-c/2$. This contradicts the separation hypothesis.

Use that matching in a graph to make a two-vertex connected set for each terminal in $C$; terminals outside $C$ remain singleton sets. There are at leastunused vertices, all singleton original branch sets. Choose $m-q$ of them for the remaining $D_i$. Every rooted $D_i$ contains a singleton original branch set: either its terminal, or its terminal's matched neighbour. That singleton misses at most $d$ of the selected nonterminal singleton sets. This constructs the desired family and completes the proof.

For a specified set $S$ of vertices, a rooted separation is a pair $(A,B)$ with $A\cup B=V(G)$, $S\subseteq A$, and no edges between $A\setminus B$ and $B\setminus A$. Its order is $|A\cap B|$. It avoids a branch set $C$ when $A\cap C=\varnothing$. A graph with vertex connectivity at least $|S|$ has no rooted separation of order below $|S|$ avoiding a nonempty branch set: both sides of such a separation would be nonempty after deleting its separator.

For disjoint sets numeralwise enumerated by $P,R$, finite-initial-segment and total-comparison axioms let $H$ separate the first set from the second in the theory. For a member of the first set use a positive $P$ stage and finitely many refutations of $R$. For a member of the second set use its positive $R$ stage: earlier proposed $P$ stages are all refuted by a finite bounded proof, while later stages lose to that known $R$ witness. This proves a separator without inferring arbitrary negative facts from the mere Sigma-1 form of the enumerators.

For finite sets, the number of ordered choices of one element from each is the product of the individual numbers of choices. More generally, if stage $j$ has exactly $n_j$ possible choices after every permitted history of earlier stages, the total number of full choice sequences is ${\prod }_j{n}_j$, by mathematical induction on the stages. This counts $b^a$ functions between sets of sizes $a,b$, and counts the injective functions by the falling factorial $b(b-1)\cdots (b-a+1)$ when $a\le b$.

With five people, choose a captain in five ways and a different deputy in four ways: $5\cdot 4=20$ ordered assignments. The second choice depends on the first because the captain is excluded, but its number of permitted options is always four. The rule of product therefore applies without any assumption about independent events. To count two-person teams instead, each subset has two possible role assignments, so division by $2!=2$ gives ten teams. This division works because every team was counted equally often.

Unrestricted formation of a set $R=\{x:x\notin x\}$ contradicts its own membership condition: substituting $R$ for $x$ gives the displayed equivalence. Thus a predicate cannot always define a set of all objects satisfying it. Restricted set comprehension forms a subset of a previously given set, avoiding this argument. The contradiction does not assert that a set whose elements happen not to contain themselves is impossible; it rules out the universal collection with exactly the specified membership condition.

The sample space is the set $\Omega$ of outcomes represented by a probability model. One elementary outcome $\omega \in \Omega$ specifies a complete result at the level of detail the model keeps. An event is a subset belonging to the model's sigma-algebra $\mathcal{F}$; it occurs when the actual outcome lies in that subset. Together with a probability measure $\mathbb{P}$, these form a probability space $(\Omega ,\mathcal{F},\mathbb{P})$, with $\mathbb{P}(\Omega )=1$.^[ref]

Choosing a sample space means deciding which distinctions matter. For two tosses, recording the ordered head-or-tail sequence distinguishes $HT$ from $TH$; recording only the number of heads merges them. Neither representation is automatically wrong, but the second cannot answer a question about which toss was heads. Keeping a detailed sample space and defining a random variable for the desired observation lets several questions share one model.

A sample space alone assigns no probabilities. Even writing $\Omega =\{H,T{\}}^2$ as a Cartesian product does not establish independence: that requires a condition on the probability measure. On a finite sample space with all subsets admitted as events,Only when all elementary probabilities are equal does this become $\mathbb{P}(A)=|A|/|\Omega |$, where the bars denote cardinality. This is the uniform distribution on a finite set, an additional modelling choice.

Sample spaces can also be infinite. For example, take $\Omega =[0,1]$, its Borel sigma-algebra, and the continuous uniform distribution. Then $\mathbb{P}([a,b])=b-a$ for $0\le a\le b\le 1$, so each singleton has probability zero while $\mathbb{P}(\Omega )=1$. Thus an elementary outcome need not carry positive probability, and a continuous model cannot be understood by counting equally likely points. The distinction is developed in zero-probability event and countable additivity.

Let the numerical support of a probability distribution be $x_1<\cdots <x_n$. Its cumulative distribution function counts how many values have been passed:It is zero below $x_1$, equals $j/n$ on $x_j\le t<x_{j+1}$ for $1\le j<n$, and is one at and above $x_n$. Every jump is $1/n$, even when the horizontal gaps differ.

For inverse transform sampling, take an ideal continuous uniform distribution for $U$ on $[0,1)$. Partition that interval into $n$ intervals of width $1/n$ and outputEach interval has probability $1/n$, proving the desired discrete uniform distribution. Using the floor function, the index is $j=1+\lfloor nU\rfloor$; for consecutive integer values the output is $X=a+\lfloor nU\rfloor$. With the usual quantile function convention $Q(u)=\inf \{t:F_X(t)\ge u\}$, one instead writes $Q(u)=x_{\lceil nu\rceil }$ for $0<u\le 1$, using the ceiling function. The endpoint conventions differ only at a finite set of points with probability zero under the ideal continuous uniform distribution.

For $S=\{1,2,4,8\}$, the four intervals $[0,1/4)$, $[1/4,1/2)$, $[1/2,3/4)$, and $[3/4,1)$ select $1,2,4,8$, respectively. Thus $U=3/10$ selects $2$, while $U=9/10$ selects $8$. The upper half of the interval selects values at least four, recovering probability $1/2$. Equal widths refer to the sampling probability coordinate, not to distances between output values. This is an exact mathematical construction assuming an ideal continuous uniform distribution; a finite computer random-number source needs its own justification of equal output chances.

The satisfaction relation says that the finite code $e$ of a first-order formula is true in a set-sized first-order structure $A$ at assignment $\vec{a}$. It is defined uniformly in set theory by recursion on the finite syntax tree: evaluate atomic relations, Boolean operations and quantifiers over the given domain. A code includes only finitely many subformulas, and their truth relations are sets. This does not define a truth predicate for the ambient universe, whose domain is not a set. Finite relation closure for set-theoretic coding gives an explicit closure criterion ensuring that these truth relations are computed correctly in a transitive set.

For a state formula $\phi$ in a fixed labelled transition system, its satisfaction set is $\{s\in S:s\models \phi \}$. This is a set of states; it is distinct from the assertion that every initial state satisfies the formula.