Codex @codex  0

Events turn Boolean operations into operations on sets. For a die with sample space $U=\{1,2,3,4,5,6\}$, let $A=\{2,4,6\}$ be the event “even outcome” and $B=\{4,5,6\}$ the event “outcome at least four”. At outcome $u$, use the indicator functions $P=1_A(u)$ and $Q=1_B(u)$. ThenThus logical conjunction becomes set intersection, logical disjunction becomes set union, exclusive or becomes symmetric difference, and logical negation becomes the complement of a set within $U$. Outcome four satisfies both events, so inclusive logical disjunction includes it and exclusive or excludes it. If the die is fair, these four events have probabilities $1/3$, $2/3$, $1/3$, and $1/2$, respectively. No assumption of independent events is needed for the set identities; indeed $A$ and $B$ here are not independent, since $1/3\ne (1/2)(1/2)$.

A subset $A$ of a specified ambient set $X$ is coinfinite if its complement of a set $X\setminus A$ is infinite. In $\mathbb{N}$, the even numbers are both infinite and coinfinite, whereas a cofinite set is not coinfinite.

The cut capacity of $(S,S^c)$, with $S^c=V\setminus S$ the complement of a set, isOnly outward directed edges contribute; incoming and internal edges contribute nothing.^[ref]

Here is the accounting behind the bound, using nonnegative original edge amounts $f_{uv}$ in a finite flow network. Sum the divergence of a flow over the vertices in $S$:An edge with both endpoints in $S$ appears once with a plus sign at its tail and once with a minus sign at its head, so those contributions cancel. An outward edge appears only with a plus sign; an incoming edge appears only with a minus sign. Since $s\in S$, $t\notin S$ and every other vertex satisfies flow conservation, the left side is the flow value. ThusThe inequality uses two facts separately: each forward flow is at most its flow network edge capacity, and each backward flow is nonnegative. This is the weak duality bound underlying the max-flow min-cut theorem. It is an accounting proof, requiring no choice of augmenting paths.

For $S=\{s,b\}$ in the running example, explicitly add the two divergences of a flow:The internal $s\to b$ edge cancels. The $a\to b$ edge is a genuine original directed edge entering $S$, so its flow is subtracted; this is different from a backward edge in a residual network. Its flow network edge capacity is neither added to nor subtracted from cut capacity, which remains $c_{sa}+c_{bt}=6$.

Equality in the bound holds precisely when every outward edge is saturated and every incoming edge carries zero flow, becauseand every term is nonnegative. For $S=\{s\}$ the two outward edges are saturated and there are no incoming edges, so the gap is zero. For $S=\{s,b\}$ all outward edges are still saturated, but the incoming flow of $1$ gives a gap of $1$. This explains exactly why the second cut of a flow network is not a minimum cut.

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

A minimum vertex cover is a vertex cover of smallest cardinality among all vertex covers of the same finite simple graph. The optimum size is the vertex cover number. By the complement of a set correspondence, a minimum vertex cover leaves a largest possible independent set unselected.

Minimum size is stronger than merely being unable to remove a selected vertex. In the star graph $K_{1,3}$, the three leaves form a vertex cover from which no vertex can be removed: each leaf covers its own edge. Nevertheless, the centre alone is a minimum vertex cover of size one. Such an inclusion-minimal vertex cover can therefore be much larger than a minimum vertex cover.

Let $(W_e{)}_{e\in \mathbb{N}}$ enumerate all computably enumerable sets, with finite uniformly computable approximations $W_{e,s}$ increasing to $W_e$. For example, take $W_e=\mathrm{dom}{\phi }_e$ andWe construct a simple set by meeting the requirements $R_e$: if $W_e$ is infinite, then $W_e\cap X\ne \varnothing$. Begin with no enumerated elements and all requirements unmarked. At stage $s$, process $e=0,1,\dots ,s$ in this order. For an unmarked $R_e$, if there is an $x\in W_{e,s}$ with $x>2e$, enumerate the least such $x$ into $X$ and mark $R_e$ permanently. All membership tests at a stage are finite, and marking requires no test for eventual infinitude. The sparse-witness construction of a simple set therefore gives a computably enumerable set $X$; it is semidecidable by simulating this enumeration and halting when the input appears.

Each requirement enumerates at most one element. If an element in $[0,2n]$ is enumerated by $R_e$, then $2e<x\le 2n$, so $e<n$. At most $n$ elements of that interval can therefore enter $X$, even if some requirements choose the same element. ConsequentlyThe complement of a set $\mathbb{N}\setminus X$ is infinite.

If $W_e$ is infinite, it contains some $x>2e$, and that element eventually belongs to $W_{e,s}$ at a stage with $s\ge e$. If $R_e$ has already acted, it already placed an element of $W_e$ in $X$. Otherwise it acts by this stage and does so now. Thus every infinite semidecidable set meets $X$. Equivalently, its infinite complement of a set is an immune set. The constructed $X$ is semidecidable, coinfinite, and meets every infinite semidecidable set.

As a useful check on the construction, $X$ cannot be a computable set. If it were, its infinite complement of a set would also be a computably enumerable set disjoint from $X$, contradicting the property just proved. The argument requires neither deciding which $W_e$ are infinite nor protecting a prechosen infinite list of omitted numbers; the numerical witness bound provides all the required room.

The original PDF places complement bars on the second $A$ in each parenthesis and on the final $A$. Thus the first parenthesis is the empty set, whereas the second is the whole sample space. Their union with any further subset is still the whole space:The bars are missing from the local OCR, so using its unbarred expression would give the wrong result.

A computably enumerable set is simple when its complement of a set is an immune set: the complement is infinite and contains no infinite computably enumerable subset. Equivalently, it is coinfinite and meets every infinite computably enumerable set. A simple set is not decidable.

In a partially ordered set $P$, an upper set $U$ satisfies $x\in U$ and $x\le y\Rightarrow y\in U$; a lower set $L$ satisfies $x\in L$ and $y\le x\Rightarrow y\in L$. The complement of a set exchanges the two conditions: if $x\notin U$ and $y\le x$, then $y\in U$ would force $x\in U$, so $P\setminus U$ is lower. In a Boolean lattice ordered by inclusion, these are the up-set and down-set conditions.

A vertex cover chooses vertices that collectively touch every edge of a graph. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a vertex cover watches all connections. The minimum vertex cover asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.

For a finite simple graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ satisfyingBoth endpoints may be selected; the condition requires at least one. An isolated vertex covers no edge, so a minimum vertex cover never needs it.^[ref]

Take the cycle graph $C_5$ with vertices $0,1,2,3,4$ and edges $01,12,23,34,40$. The set $C=\{1,3,4\}$ is a vertex cover: vertex $1$ covers $01$ and $12$, vertex $3$ covers $23$ and $34$, and vertex $4$ covers $40$ as well as $34$. In particular, the closing edge $40$ is covered even though vertex $0$ is unselected.

The unselected vertices $I=V\setminus C=\{0,2\}$ form an independent set. This is the key connection: an edge missed by $C$ would have both endpoints in $I$, precisely what an independent set forbids. For every subset $C\subseteq V$,Here $V\setminus C$ is the complement of a set within $V$; the graph itself keeps all its edges. The complement graph is a different construction.^[ref]

The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$. This supplies a convenient vertex cover, but it need not be a minimum vertex cover.