LemmaStatement: AI-generatedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Intersecting finitely many high-probability events

Statement

Let $S$ be an unbounded subset of the natural numbers and $k$ a fixed positive integer. For each $n \in S$ , let $(Ω_{n}, w_{n})$ be a finite probability space with event probability $P_{n}$ , and let $E_{1, n}, \dots, E_{k, n} \subseteq Ω_{n}$ be events in that space. Then $P_{n} (⋂_{j = 1}^{k} E_{j, n}) \geq 1 - \sum_{j = 1}^{k} P_{n} (E_{j, n}^{c})$ , where complements are relative to $Ω_{n}$ . If every $E_{j, n}$ has probability tending to one through $S$ , their intersection does too and is nonempty for every sufficiently large $n \in S$ . No independence is assumed.

Facts & Assumptions

[F1]

Asymptotic quantifiers and uniform parameter ranges defines high probability, eventual assertions and limits through an unbounded subset of the natural numbers.

[F2]

Finite probability spaces, outcome weights, events, and event probabilities defines a finite probability space $(Ω_{n}, w_{n})$ by nonnegative outcome weights whose sum is one; every subset is an event, with probability equal to the sum of its outcome weights.

Proof

Given: The objects and hypotheses in the Statement.

Goal: Establish every assertion of the Statement.

1.1F2algebra

For an event $A \subseteq Ω_{n}$ , define $1_{A} (ω) = 1$ when $ω \in A$ and $0$ otherwise. At each outcome, $1_{⋃_{j = 1}^{k} E_{j, n}^{c}} (ω) \leq \sum_{j = 1}^{k} 1_{E_{j, n}^{c}} (ω)$ , since membership in the union means membership in at least one constituent event. Multiplying by the nonnegative weight $w_{n} (ω)$ and summing over $Ω_{n}$ gives $P_{n} (⋃_{j = 1}^{k} E_{j, n}^{c}) \leq \sum_{j = 1}^{k} P_{n} (E_{j, n}^{c})$ . The weights sum to one, so the probability of a complement is one minus the event probability. The complement of this union is $⋂_{j = 1}^{k} E_{j, n}$ , giving the asserted inequality.

2.1F1F2step 1.1algebra∎

Suppose each $P_{n} (E_{j, n}) \to 1$ through $S$ . Given $ε > 0$ , for each $j$ take a cutoff $N_{j}$ such that $P_{n} (E_{j, n}^{c}) = 1 - P_{n} (E_{j, n}) < ε / k$ whenever $n \in S$ and $n \geq N_{j}$ . Since $k$ is fixed and finite, $N = \max_{1 \leq j \leq k} N_{j}$ is a common cutoff. Step 1.1 gives intersection probability greater than $1 - ε$ for $n \in S$ with $n \geq N$ ; its probability is at most one by F2, proving convergence to one in the sense of F1. Taking $ε = 1 / 2$ gives positive probability eventually. An empty event has weight sum zero, so the intersection is nonempty for every sufficiently large $n \in S$ .

Depends on

Used by · 2

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.