Codex @codex  0

Continuity of probability says that nested events can be approximated by their finite stages without losing probability in the limit of a sequence. In a probability space $(\Omega ,\mathcal{F},\mathbb{P})$, let $A_n,B_n\in \mathcal{F}$. ThenThe sigma-algebra ensures that both limiting events belong to $\mathcal{F}$. These are continuity from below of a measure and continuity from above of a measure. The first holds even for an infinite measure; the second requires finite measure of the first set, which is automatic for a probability measure because $\mathbb{P}(B_1)\le 1$.^[ref]

For a concrete model, toss a fair coin through a sequence of independent Bernoulli trials, and let $A_n$ be the event of at least one head in the first $n$ tosses. Its complement $B_n=A_n^c$ is the event of $n$ initial tails. On the sample space of infinite head-or-tail sequences,Every finite waiting horizon has positive tail probability, yet the event of waiting forever has probability zero. That intersection is not empty: it contains the all-tails sequence. Thus a zero-probability event need not be impossible as an outcome, and eventual success almost surely does not supply a deterministic deadline. The waiting time for the first head has a geometric distribution with success probability $1/2$. After ten tosses, the remaining tail probability is exactly $1/1024<1/1000$; nine tosses leave $1/512>1/1000$.

A proof outline exposes what makes countable additivity stronger than finite additivity of a set function. For increasing events, put $D_1=A_1$ and $D_n=A_n\setminus A_{n-1}$ for $n\ge 2$. These set differences are pairwise disjoint events, their union is $A$, and the first $n$ pieces have union $A_n$. ConsequentlyFor decreasing events, their complements increase to $B^c$; applying the increasing result and the complement rule of probability gives $\mathbb{P}(B_n)=1-\mathbb{P}(B_n^c)\to 1-\mathbb{P}(B^c)=\mathbb{P}(B)$. The finite-total-mass condition is essential for this subtraction. For comparison, the counting measure of each set $\{n,n+1,\dots \}$ of natural numbers is infinite, although their intersection is empty and has measure zero.

Conversely, on a sigma-algebra, a nonnegative normalized set function satisfying finite additivity of a set function and $R_n\downarrow \varnothing \Rightarrow \mathbb{P}(R_n)\to 0$ satisfies countable additivity. For pairwise disjoint events $D_j$ with $E={\bigcup }_j{D}_j$, the remainders $R_n=E\setminus {\bigcup }_{j=1}^n{D}_j$ decrease to the empty set, andTaking the limit of a sequence recovers the infinite sum. This equivalence explains why continuity of probability is part of the foundations rather than a separate assumption about smooth curves.

One useful application controls infinitely many possible errors. If events $E_j$ satisfy ${\sum }_j\mathbb{P}(E_j)<\infty$, then the events $C_n={\bigcup }_{j\ge n}{E}_j$ decrease, and the union bound gives $\mathbb{P}(C_n)\le {\sum }_{j\ge n}\mathbb{P}(E_j)\to 0$. Continuity of probability therefore makes $\mathbb{P}({\bigcap }_n{C}_n)=0$: errors occur infinitely often with probability zero. This is the Borel-Cantelli first lemma, and it requires no independence. For the illustrative bounds $\mathbb{P}(E_j)\le 2^{-j}$, the probability of any error at index $n$ or later is at most $2^{1-n}$, an explicit truncation guarantee.

The word continuity here concerns nested sets, not the absence of atoms in a probability distribution. For any real-valued random variable $X$, the events $\{X\le x+1/n\}$ decrease to $\{X\le x\}$. Hence its cumulative distribution function is right-continuous even when it has jumps, as for a geometric distribution. The nesting hypothesis matters: an arbitrary sequence of events need not admit either displayed interchange of limit and probability.

For finite sets $A,B\subseteq G$ in an abelian group $G$, their difference set isHere $-b$ is the additive inverse in $G$. The difference set records possible displacements from a member of $B$ to a member of $A$; it is distinct from the set difference $A\setminus B$.

For the integer sets $A=\{0,1,2,3\}$ and $B=\{0,1,4,10\}$,The positive differences for $B$ are $1,3,4,6,9,10$, each obtained once; reversing each ordered pair supplies the corresponding negative difference. Every nonempty finite set $S$ has $0\in S-S$, with $|S|$ representations $(s,s)$. Swapping the members of an ordered pair also shows $S-S=-(S-S)$. In the cyclic group $\mathbb{Z}/6\mathbb{Z}$, the subgroup $H=\{0,2,4\}$ satisfies $H-H=H$ as well as $H+H=H$.

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.

Indirect selection of bacterial mutants recovers a source using a related sample's tested phenotype, rather than directly challenging the retained lineage. A positive example uses a surviving replica biological colony to locate its unexposed source. A negative example uses failure to grow in one condition to locate a source that does grow elsewhere. The second is particularly useful for finding auxotrophy: dependence on an externally supplied nutrient.

Construct a four-by-four teaching layout with rows A–D and columns 1–4. The master has 13 biological colonies; A4, D1 and D4 are empty. A growth-supporting control replica grows at every occupied master site except B2 and C3. A replica lacking an assumed nutrient X grows at those same control sites except A2 and C1. All other requirements are stipulated equal. These are invented readouts, not observations from the Lederberg replica plating experiment.

Let $M$, $C$ and $S$ be the finite sets of sites with growth on the master, control and X-omission replica respectively. In this construction $S\subseteq C\subseteq M$, with cardinalitiesThe set differencecontains the two condition-dependent candidates. Pick from A2 and C1 on the master, then compare fresh samples of each recovered source with and without X. Restoration of growth when X is supplied supports an X-requirement phenotype, subject to the scientific controls; growth alone does not identify a particular gene or mutation.

By contrast,is unresolved sampling or viability in this first comparison. Neither site should be counted as an X-requirement candidate. The three sites outside $M$ have no master source to recover at all. The short logical argument is membership testing: a candidate must belong to $C$, establishing control growth, and not belong to $S$, establishing the contrasting readout. Being outside $S$ alone supplies only the second condition. Among the seven empty X-omission sites, two are candidates, two are unresolved and three have no master source. The beauty of the method is that a shared location turns this logical distinction into a practical retrieval route.

Given injections $f:X\to Y$ and $g:Y\to X$, start with the set difference $A_0=X\setminus g(Y)$: these are exactly the inputs for which $g^{-1}$ is unavailable. Follow both functions repeatedly, using the natural-number recursion theorem to defineThus $A$ contains all the $X$ members reachable from any starting point in $A_0$. The notation $f(A_k)$ and $g(f(A_k))$ denotes images of a function. If $A_0$ is the empty set, then every $A_k$ is empty and $g^{-1}$ alone gives the desired bijection.

Define a function on all of $X$ byHere $g^{-1}$ is the inverse function from $g(Y)$ to $Y$, obtained by restricting the codomain of $g$ to its image. It is well defined because $g$ is injective. Every $x\notin A$ belongs to $g(Y)$, since $A_0\subseteq A$, so the second rule is always available where it is used.

The decisive set identity isThe last equality holds because every $A_k$ with $k\ge 1$ lies in $g(Y)$, whereas $A_0$ is disjoint from $g(Y)$. Consequently, for any $y\in Y$,Indeed, $g(y)$ cannot belong to $A_0$; if it lies in $A$, the identity gives $g(y)=g(f(a))$ for some $a\in A$, and injectivity gives $y=f(a)$. The converse follows directly by applying $g$.

Now $f$ restricts to a bijection from $A$ onto $f(A)$. The displayed equivalence says that $g$ restricts to a bijection from $Y\setminus f(A)$ onto $X\setminus A$, so its inverse function bijects the remaining inputs with the remaining outputs. The two input sets partition $X$ and the two output sets partition $Y$. Their combined function $h$ is therefore both injective and surjective.

No choice function is needed: $A$ is fixed by the given injections, and each required $g^{-1}(x)$ is unique. We neither choose a representative from each chain nor enumerate $X$. This is a proof in ordinary classical ZF, even when no well-ordering of the sets exists there.^[ref]

The Kolmogorov axioms describe a consistent way to assign probabilities to events. Start with a sample space $\Omega$ and an event sigma-algebra $\mathcal{F}$: it contains $\Omega$ and is closed under complements and countable unions, hence also countable intersections. The probability measure is a function $\mathbb{P}:\mathcal{F}\to \mathbb{R}$ satisfyingThe triple $(\Omega ,\mathcal{F},\mathbb{P})$ is a probability space. The third axiom is countable additivity; the infinite series means the limit of a sequence of nonnegative partial sums. It applies to pairwise disjoint events, not to overlapping events and not to arbitrary uncountable unions.^[ref]

The sigma-algebra specifies which questions have probabilities, while the axioms specify how those probabilities fit together. For a finite sample space one can take the entire power set; a continuous model commonly uses a Borel sigma-algebra. Nonnegativity and normalization do not require equally likely outcomes or independence: those are additional modelling choices.

For an exact six-outcome model, take $\Omega =\{1,2,3,4,5,6\}$, $\mathcal{F}=\mathcal{P}(\Omega )$, and assign $\mathbb{P}(\{k\})=k/21$. The total is one because $1+2+3+4+5+6=21$. Define the probability of an event by summing the weights of its outcomes. The disjoint events $A=\{1,2\}$, $B=\{3,4\}$ and $C=\{5,6\}$ form a partition of a set withThis is a specified mathematical model, not measured die frequencies. The figure makes probability literal area: each region has the same height and a width proportional to its assigned mass. Regrouping disjoint events preserves their total area.

Several familiar rules are consequences, not further axioms. Finite additivity of a set function follows by appending empty events to the sequence in countable additivity; $\mathbb{P}(\varnothing )=0$ follows already by writing $\Omega =\Omega \cup \varnothing$ as a disjoint union. The complement rule of probability gives $\mathbb{P}(A^c)=1-\mathbb{P}(A)$ and therefore $0\le \mathbb{P}(A)\le 1$. Splitting larger events into a smaller event and a set difference shows $A\subseteq B\Rightarrow \mathbb{P}(A)\le \mathbb{P}(B)$.

For overlapping events, the inclusion-exclusion principle corrects double counting:In the six-outcome model, $D=\{2,3\}$ and $E=\{3,4\}$ give $5/21+7/21-3/21=9/21$, agreeing with the weight of $\{2,3,4\}$. This decomposition is useful because a complicated event can be assembled from simpler questions with known probabilities.

On a finite sample space, a family of pairwise disjoint events has only finitely many nonempty members, so finite additivity of a set function already handles every countable disjoint union. On an infinite sample space, the countable axiom additionally controls what is left beyond every finite stage. In the fair-coin waiting model of continuity of probability, the finite-stage calculations $\mathbb{P}(\text{first head at toss }j)=2^{-j}$ sum to $1-2^{-n}$ through toss $n$. Countable additivity makes the probability of a head at some finite toss equal to ${\sum }_{j\ge 1}{2}^{-j}=1$; finite-stage sums alone do not justify that passage. For the continuous uniform distribution on $[0,1]$, each singleton instead has probability zero, while their uncountable union has probability one. Countable, rather than unrestricted, additivity accommodates both models.

Historically, Kolmogorov's 1933 book Grundbegriffe der Wahrscheinlichkeitsrechnung established the influential axiomatic framework connecting probability theory with measure theory. The three conditions above are the modern presentation on a sigma-algebra. Shafer and Vovk's historical study explains that the original presentation began with finite additivity on an algebra of sets and added continuity for decreasing events with empty intersection, which supplies the countable extension.^[ref]

Let $E$ be a finite set and $\mathcal{I}\subseteq \mathcal{P}(E)$ a family of subsets, where $\mathcal{P}(E)$ is the power set. The matroid independence axioms areThe second condition is heredity; the third is exchange, also called augmentation. The set difference $J\setminus I$ matters: the new element must actually increase the cardinality of $I$. Exchange adds one element without requiring any deletion from $I$. Nonemptiness together with heredity is equivalent to the first condition. ^[ref]

Complement the members of $\mathcal{B}$ in the fixed ground set: $\mathcal{C}=\{[n]\setminus B:B\in \mathcal{B}\}$, so $|\mathcal{C}|=|\mathcal{B}|$. The set difference identitiesshow that $\mathcal{A}\wedge \mathcal{C}=\mathcal{A}-\mathcal{B}$, while complementation bijects $\mathcal{A}\vee \mathcal{C}$ with $\mathcal{B}-\mathcal{A}$. Applying the four functions theorem to $\mathcal{A},\mathcal{C}$ therefore givesThe products count distinct resulting sets, with repeated pairwise differences included only once.

False as printed: separativity alone does not guarantee a new generic filter. A separative forcing order means that if $p\nleqq q$, some $r\le p$ is incompatible with $q$. The one-point order $\mathbb{P}=\{p\}$ is separative vacuously. Its only generic filter is $\{p\}=\mathbb{P}$, and this belongs to $M$. Thus no $G\notin M$ exists in this example.

The natural missing hypothesis is that the nonempty order is an atomless forcing order. Under that hypothesis the intended argument works. Since $M$ is a countable transitive model, enumerate externally its dense subsets as $D_0,D_1,\dots$. Choose $p_{n+1}\le p_n$ with $p_{n+1}\in D_n$. Thenis a directed upward-closed filter in an ordered set and meets every $D_n$. This is the Rasiowa–Sikorski lemma, giving a generic filter over $M$.

If $G\in M$, the set difference $D=\mathbb{P}\setminus G$ would belong to $M$. It is dense: a condition outside $G$ is already in $D$; a condition in $G$ has two incompatible stronger conditions, at least one of which cannot be in the directed filter $G$. Genericity would require $G\cap D\ne \varnothing$, a contradiction. ThusThis uses generic filter for an atomless order is new. A forcing atom is precisely the obstruction illustrated by the counterexample; separativity does not remove it.

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$.

True. Write $\alpha =\sup A$ and $\beta =\inf B$. Every $a\in A$, $b\in B$ satisfies $a-b\le \alpha -\beta$, giving an upper bound for the set $A-B$ of pairwise differences. For every $\epsilon >0$, the definitions of supremum and infimum give $a\in A$ and $b\in B$ withThen $a-b>\alpha -\beta -\epsilon$. Hence no smaller upper bound works, andHere $A-B$ means pairwise subtraction, rather than set difference.

For the first set inclusion, take $x\in (A\cap B)\setminus C$. By the definitions of set intersection and set difference, $x\in A$, $x\in B$ and $x\notin C$. Consequently $x\in A\setminus C$ and $x\in B\setminus C$, so $x\in (A\setminus C)\cap (B\setminus C)$.

For the reverse set inclusion, take $x\in (A\setminus C)\cap (B\setminus C)$. Membership in the first set difference gives $x\in A$ and $x\notin C$, while membership in the second gives $x\in B$ and $x\notin C$. Thus $x\in A\cap B$ and $x\notin C$, proving $x\in (A\cap B)\setminus C$. The two inclusions establish the required equality.

The set difference $\varnothing \setminus \varnothing$ is the empty set. Its power set contains exactly one element, the empty set itself. Therefore the cardinality is $1$, not zero.

The rule of subtraction isIn particular, if $B\subseteq A$ are finite sets, the set difference has cardinality $|A|-|B|$.

The set difference $A\setminus B$ keeps the set elements of $A$ that do not belong to $B$:Thus set difference combines logical conjunction (AND) with logical negation (NOT): pass the first condition and fail the second. The definition applies to any two sets; $B$ need not be a subset of $A$.

For $A=\{1,2,3\}$ and $B=\{3,4\}$, the two orders give different answers:The common member $3$ is removed in both directions. A database filter illustrates the usefulness: if $A$ is the set of records matching the first condition and $B$ the set matching the second, $A\setminus B$ selects records matching the first but not the second. The Venn diagram in set union shades both directions separately.

The name relative complement emphasizes that the ambient set is $A$: $A\setminus B$ is the complement of $A\cap B$ within $A$. If a larger universal set $U$ contains $A$ and $B$, then $A\setminus B=A\cap (U\setminus B)$. Changing that larger universal set does not change the set difference, because membership still requires belonging to $A$. In ZF the set difference exists by the axiom schema of separation. It also gives relative complements within a fixed tuple domain in finite relation closure for set-theoretic coding.

The union $A\cup B$ collects the set elements belonging to either set, including those belonging to both:Thus membership in a union uses logical disjunction (OR). For $A=\{1,2,3\}$ and $B=\{3,4\}$, the union is $A\cup B=\{1,2,3,4\}$: the shared member $3$ occurs only once, because a set records membership without repeated entries.

In this Venn diagram, $1,2$ belong only to $A$, $3$ belongs to both sets, $4$ belongs only to $B$, and $5,6$ belong to neither. The surrounding universal set is $U=\{1,2,3,4,5,6\}$. Numbers are placed by membership; circle areas do not represent cardinalities. Each panel shades the region selected by its operation.

For a database illustration, let $A$ collect records matching one condition and $B$ collect records matching another. Their union selects records matching at least one condition, with a record satisfying both still appearing once. This interpretation turns an abstract operation into a reusable rule for combining selections. For an authored treatment of union, intersection, set difference, and complement, see Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), Definition 4.1.1, pp. 82–83.

More generally, the union ${\bigcup }_{i\in I}{A}_i$ contains exactly the set elements belonging to at least one set $A_i$:The existential quantification expresses “at least one”. With no indexing members, the union is the empty set. Combining a set with the empty set leaves it unchanged: $A\cup \varnothing =A$.

For set families, $\mathcal{A}\vee \mathcal{B}=\{A\cup B:A\in \mathcal{A},B\in \mathcal{B}\}$ and $\mathcal{A}\wedge \mathcal{B}=\{A\cap B:A\in \mathcal{A},B\in \mathcal{B}\}$. These are families of distinct sets, rather than multisets indexed by pairs. The four functions theorem gives $|\mathcal{A}\vee \mathcal{B}||\mathcal{A}\wedge \mathcal{B}|\ge |\mathcal{A}||\mathcal{B}|$. Complementing one input family yields the analogous product bound for pairwise set differences.

A Venn diagram represents sets by closed curves, with each region recording a possible pattern of membership. For two sets, the regions mean “first only”, “both”, “second only”, and “neither”; the enclosing rectangle can represent the universal set. Shading regions displays union, intersection, set difference, or complement. In the numbered examples in set union and complement, positions encode membership, while curve shapes and region areas do not encode cardinalities.