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.

A formal language whose complement of a set, relative to the set of all input words, is a recursively enumerable language. A recognizer for the complement detects every negative instance eventually and need not halt on positive instances. A formal language is a decidable language exactly when it and its complement are both recursively enumerable languages.

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.

In propositional logic with the usual two truth values, negating a proposition twice preserves its truth value. Thus the complement of a set taken twice, in one fixed universal set, is the original set.

In extremal set theory, a set family $\mathcal{F}\subseteq \mathcal{P}([n])$ is constrained by its intersections, inclusions or traces, and one asks for the largest possible cardinality of $\mathcal{F}$. The choice of constraint is essential: without one, the whole Boolean lattice gives $2^n$ members.

For example, let $n\ge 1$ and require an intersecting family. A set and its complement of a set cannot both belong, so pairing all subsets with their complements gives $|\mathcal{F}|\le 2^{n-1}$. All subsets containing a fixed point attain equality. Adding a uniform-size requirement leads to the Erdős-Ko-Rado theorem.

An antichain instead forbids containment between distinct members. Sperner's theorem gives the sharp central-binomial bound, attained by a full middle level. Coordinate shifts of a set family simplify extremizers while preserving size; the polynomial method in combinatorics turns other intersection restrictions into linear independence. These two methods explain why a problem about subsets can become either an order argument or a vector space dimension bound.

Foreground-background polarity specifies which of two image classes is treated as the selected structure and which as its background. It involves a numerical convention as well as the intended interpretation: high-valued pixels can represent foreground in one encoding, while a dark feature may require the opposite threshold direction. A binary image's appearance alone does not establish its polarity.

For a chosen intensity threshold $T$, define complementary normalized masksThe second is the complement of a set within the declared pixel grid. For the stipulated row $I=(20,80,120,200)$ and $T=120$, the two binary selection masks are $(0,0,0,1)$ and $(1,1,1,0)$. Equality belongs to the second selection. OpenCV's THRESH_BINARY and THRESH_BINARY_INV use these respective comparison directions, with the chosen output maximum replacing 1.^[ref]

An image lookup table is a separate mapping from stored values to displayed colors. ImageJ's Create Mask command writes 255 inside a selection and 0 outside, but its default inverting lookup table can display the selected 255-valued pixels as black.^[ref] Reversing that display mapping does not exchange the stored pixel values.

The distinction has a direct computational consequence. In its binary-image input, the documented Sholl analysis implementation treats zero intensities as background regardless of the lookup table or Black Background option.^[ref] A visually inverted display can therefore leave the selected numerical structure unchanged, whereas replacing an 8-bit mask $B$ by $255-B$ exchanges its zero and 255 classes.

A reproducible geometric measurement records the threshold comparison, the values assigned to selected and excluded pixels, and any display-only inversion. A region of interest can further restrict the grid over which a complement is intended; reversing a mask over the whole image is different from selecting its complement only inside that region.

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 $V$ be the decidable language of syntactically valid descriptions $\mathrm{enc}(M)\#\#w$. ThenHere the complement of a set on the left is taken in all words over an alphabet, while the non-halting problem only has valid machine-and-input descriptions as instances. Any malformed description belongs to $\overline{{\mathcal{L}}_{\mathrm{H}}}$ but not to ${\mathcal{L}}_{\mathrm{NH}}$. For example, the empty word has no separating ##, so cannot be a valid instance under the displayed encoding.

Fix valid descriptions $h$ and $\ell$ of, respectively, an immediately halting Turing machine on the empty word and a Turing machine looping forever on the empty word. ThenFor the first many-one reduction, use the total computable functionFor a valid input, nonmembership in ${\mathcal{L}}_{\mathrm{H}}$ is exactly membership in ${\mathcal{L}}_{\mathrm{NH}}$, so retaining it is correct. Every invalid input is a yes-instance of $\overline{{\mathcal{L}}_{\mathrm{H}}}$, and $f$ sends it to the fixed yes-instance $\ell$. Therefore $x\in \overline{{\mathcal{L}}_{\mathrm{H}}}$ if and only if $f(x)\in {\mathcal{L}}_{\mathrm{NH}}$.

For the reverse many-one reduction, useThe equivalence again holds on valid inputs. Invalid inputs are no-instances of ${\mathcal{L}}_{\mathrm{NH}}$, and $h$ is a no-instance of $\overline{{\mathcal{L}}_{\mathrm{H}}}$. Syntax checking terminates, so $g$ is also a total computable function. We have proved

Writing $\mathrm{PTime}$ as P and $\mathrm{co}\text{-}\mathrm{PTime}$ as co-P, the known relationships among the four complexity classes areThe equality supplies both inclusions between P and co-P, and it also gives co-P $\subseteq$ NP and co-P $\subseteq$ co-NP.

For the equality, a deterministic polynomial-time algorithm halts on every input; interchange its accepting and rejecting outcomes to decide the complement of a set in the same polynomial time. For P $\subseteq$ NP, a Nondeterministic Turing machine can simply make no choices and follow the deterministic computation. Finally, if $A\in \mathrm{P}$, then $\overline{A}\in \mathrm{P}\subseteq \mathrm{NP}$, whence $A\in \mathrm{co}\text{-}\mathrm{NP}$ by the definition of co-NP.

Neither NP $\subseteq$ co-NP nor co-NP $\subseteq$ NP is known; either would imply equality by taking complements. Nor is either inclusion of P into NP or co-NP known to be strict. These unresolved relationships must not be presented as strict separations.

$P$ is a co-recursively enumerable language, is not a recursively enumerable language, and is not a decidable language. The stipulated order on halting times includes $\infty \ge \infty$.

First, failure has a finite witness. For valid machine descriptions,Indeed, a strict inequality $t(N_1,x)<t(N_2,x)$ forces the first halting time to be finite. The second can be either a larger finite time or infinity. Whether the displayed condition holds for fixed $x,t$ is decidable by a finite simulation, including the initial configurations when $t=0$.

Enumerate all pairs $(x,t)$ and perform these finite tests by dovetailing, accepting the complement of a set of $P$ on finding a witness. Equivalently, at stage $s$, inspect all inputs of length at most $s$ through $s$ transitions. A genuine violation eventually appears; if there is no violation, the procedure never accepts. Malformed descriptions or differing input alphabets can be recognized and accepted as nonmembers immediately. Thus the complement is a recursively enumerable language, proving that $P$ is a co-recursively enumerable language.

For non-enumerability, use the standard result that the complement of a set of the halting problemis not a recursively enumerable language. Given $⟨M,w⟩$, effectively construct two Turing machines over the same fixed input alphabet. On every input $x$, let $N_1$ ignore $x$ and simulate $M$ on the fixed word $w$, halting precisely when that simulation halts. Let $N_2$ loop forever on every input.

If $M$ does not halt on $w$, both halting times are infinity for every $x$, so the pair belongs to $P$. If $M$ halts on $w$, the first halting time is finite while the second is infinity, so the pair does not belong to $P$. ThereforeThis is a many-one reduction from non-halting to the pointwise running-time domination problem. Were $P$ a recursively enumerable language, constructing the pair and running its recognizer would recognize non-halting, contradicting the stated result. Hence $P$ is not a recursively enumerable language. Since every decidable language is a recursively enumerable language, $P$ is also undecidable.

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.

Write each set difference as an intersection with a complement of a set. Applying De Morgan's laws and then the distributive property givesThe complements turn the inner union into an intersection and vice versa. Thus

Use De Morgan's laws to remove the complement of a set, then distribute the two unions:The first and last intersections in the middle line are the empty set. The remaining union is precisely the collection of elements belonging to exactly one of the original sets. Therefore both expressions define the same symmetric difference:

Write the set difference as an intersection and use the fact that taking the complement of a set twice returns that set. The commutativity of intersection gives the reversible calculation

An algebraic way to prove the set identity is to show that $D=\overline{A}\cup \overline{B}$ is a complement of a set for $A\cap B$. By the distributive property,andA complement of a set is unique: if $D,E$ both complement $S$, then $D=D\cap (S\cup E)=D\cap E$, and similarly $E=D\cap E$. Consequently

Every complement of a set is taken in the same universal set $\mathcal{U}$. Apply De Morgan's laws for propositional logic to the membership propositions. For every $x\in \mathcal{U}$,Equality of membership for every element proves the set identities

Using set difference as an intersection with a complement of a set, and using double negation, givesInterchanging the two sets simply interchanges the two terms of this union, whose commutativity gives