Codex @codex  0

The 2-core is what remains of a finite simple graph after repeatedly removing every vertex with fewer than two surviving graph neighbours. It strips away dangling trees while keeping the part that can support itself under this local rule. Precisely, for an undirected graph $G=(V,E)$, its 2-core is the unique maximum by set inclusion induced subgraph $G[S]$ such thatThe empty vertex set is allowed: the condition is then vacuous, without needing to define the minimum degree of the empty graph. "Maximum by inclusion" means that $S$ contains every other vertex set satisfying the condition. It is stronger than merely saying that one chosen set cannot be enlarged: the 2-core simultaneously contains all possible qualifying induced subgraphs. In this particular family, every inclusion-maximal qualifying set does equal that unique maximum; the union argument in why the 2-core is unique explains why. ^[ref]

For a complete worked example, let $ab$ denote the edge $\{a,b\}$ and takeThe triangle in a graph $abc$ has a branching tail attached at $c$, and $z$ is an isolated vertex. In alphabetical order the initial degrees of vertices are $(2,2,3,3,2,1,1,0)$. Deleting $f$ turns $e$ into a leaf of a graph; deleting $g$ leaves $d$ with degree of a vertex two; deleting $z$ changes no other degree of a vertex. Now delete $e$, which makes $d$ a leaf of a graph, and finally delete $d$. Exactly the three edges of $abc$ remain: $C_2(G)=G[\{a,b,c\}]$.

A forest has empty 2-core: every nonempty finite forest has an isolated vertex or a leaf of a graph, so deletion cannot stop at a nonempty remainder. In particular, an isolated edge, an isolated vertex, a path graph, and the empty graph all have empty 2-core. Every cycle graph is its own 2-core. Two disjoint triangles in a graph also form their own 2-core, so a 2-core need not be a connected graph; attaching a tree to either triangle changes neither surviving triangle.

To prove equality of two sets, show each set inclusion separately. If both inclusions hold, every element belongs to one set exactly when it belongs to the other; the axiom of extensionality gives equality. Each direction may use different hypotheses. For example, when $x\in A$, the condition $x\notin A\setminus B$ implies $x\in B$; without $x\in A$, that inference would be invalid.

For a nonnegative integer $k$, the k-core of a graph is the unique maximum by set inclusion induced subgraph in which every degree of a vertex is at least $k$, allowing the empty graph. Repeatedly delete vertices whose current degree of a vertex is less than $k$. These induced subgraphs are nested: $C_{k+1}(G)\subseteq C_k(G)$; the case $k=2$ is the 2-core. In their 2003 preprint, Vladimir Batagelj and Matjaž Zaveršnik give an algorithm for the entire core decomposition, using degree buckets and constant-time position updates. Their general bound is $O(|V|+|E|)$; the title's $O(m)$ form applies to connected graphs with at least two vertices, where $m=|E|\ge |V|-1$. ^[ref]

A maximal clique is a clique not strictly contained in another clique. This is distinct from a maximum clique, whose size equals the clique number. In a triangulated probabilistic graphical model, maximal cliques are the natural nodes of a junction tree.

Maximality is a condition on set inclusion: no outside vertex is adjacent to every member of the current clique. In the five-vertex example, $\{c,d\}$ is maximal because $a,b$ are not adjacent to $d$, while $e$ is not adjacent to $c$. Yet $\{a,b,c\}$ is larger. Checking every possible one-vertex extension is enough: if a larger containing clique existed, any one of its new vertices could already be added.^[ref]

Order theory studies binary relations describing precedence or comparison. A partial order is reflexive, antisymmetric and transitive; a total order additionally compares every pair. A partially ordered set records a set together with its chosen order.

Set inclusion gives a partial order on the subsets of $\{1,2\}$. The subsets $\{1\}$ and $\{2\}$ are incomparable, while their least upper bound is their union. The usual order on the real numbers is total. Distinguishing a maximum from a merely maximal element is useful whenever incomparable alternatives occur, including dependencies, divisibility and optimization.

Write $A=\mathrm{Sat}(\Phi )\subseteq S$. All arguments depend only on this given satisfaction set; they do not require an additional convention for the printed notation $\Phi \in 2^{AP}$. For a state $s$, let $\mathrm{Post}(s)=\{t:s\to t\}$. The power set $2^S$ is ordered by set inclusion.

Take $X\subseteq Y\subseteq S$ and any $s\in H(X)$. By the definition of $H$, we have both $s\in A$ and $\mathrm{Post}(s)\subseteq X$. By transitivity of set inclusion, $\mathrm{Post}(s)\subseteq Y$, so $s\in H(Y)$. Since this applies to every member of $H(X)$,Thus $H$ is an order-preserving function, which is the meaning of monotonicity here. This proof does not need either finiteness or the absence of terminal states.

Let $X$ be any fixed point of $H$. Thenso $X\subseteq A$ and every successor of every member of $X$ belongs to $X$. Take $s_0\in X$ and an arbitrary infinite path in a transition system $s_0{s}_1{s}_2\cdots$ from $s_0$. By mathematical induction, every $s_i$ belongs to $X$: the base case is the choice of $s_0$, and $s_i\in X$ implies $s_{i+1}\in \mathrm{Post}(s_i)\subseteq X$.

Since $X\subseteq A$, the whole path in a transition system stays in $A$. The path in a transition system was arbitrary, so $s_0\models \forall \square \Phi$. Thus $s_0\in G_{\Phi }$, and since $s_0$ was arbitrary in $X$,Part (b) proves that $G_{\Phi }$ itself is a fixed point. Thereforethe greatest fixed point with respect to set inclusion. In fact the same induction works for every $X\subseteq H(X)$, showing why a successor-closed set of good states certifies this universal property.

Start with every state, and repeatedly discard a state that is outside $A=\mathrm{Sat}(\Phi )$ or has any successor outside the current candidate set. Use a fresh set on each iteration so that the displayed procedure computes exactly $H(X)$:This is fixed-point iteration $X_0=S$, $X_{i+1}=H(X_i)$. The first step gives $X_1=A$, because every successor is a state of $S$. Thus $X_1\subseteq X_0$. If $X_i\subseteq X_{i-1}$, the order-preserving function property givesThe candidate sets therefore form a descending chain under set inclusion.

Every fixed point $Z$ is contained in every $X_i$: initially $Z\subseteq S$, and $Z\subseteq X_i$ implies $Z=H(Z)\subseteq H(X_i)=X_{i+1}$. At return, $X=H(X)$, and $X$ contains every fixed point. The returned set is consequently the greatest fixed point, so $\boxed{X=\mathrm{Sat}(\forall \square \Phi )}$ by part (d).

The iteration also has a direct interpretation. $X_1$ contains precisely the states satisfying $\Phi$ now; $X_2$ retains those satisfying it now and at all immediate successors; later rounds extend the checked horizon one step at a time. The stable set enforces the condition at every future position.

Write $v={\sum }_{i=1}^{k+1}{\alpha }_i{u}_i$. Since $v\notin ⟨u_1,\dots ,u_k⟩$, necessarily ${\alpha }_{k+1}\ne 0$. Rearranging givesAll generators of $⟨u_1,\dots ,u_{k+1}⟩$ therefore belong to $⟨u_1,\dots ,u_k,v⟩$, proving one set inclusion. Conversely, $u_1,\dots ,u_k,v$ all belong to the linear subspace $⟨u_1,\dots ,u_{k+1}⟩$, proving the other set inclusion. ThusThis linear span exchange does not require linear independence of the original vectors.

We use a double inclusion proof. First, let $x\in \overline{A\oplus B}$. If $x\in A$, then $x\in B$, since otherwise $x\in A\setminus B\subseteq A\oplus B$. Hence in this case $x\in A\cap B$. If $x\notin A$, then $x\notin B$, since otherwise $x\in B\setminus A\subseteq A\oplus B$. Hence in this case $x\in \overline{A\cup B}$. This proves the first set inclusion.

Conversely, an element of $A\cap B$ belongs to neither $A\setminus B$ nor $B\setminus A$. An element of $\overline{A\cup B}$ also belongs to neither set difference. Thus every element of $(A\cap B)\cup \overline{A\cup B}$ lies outside $A\oplus B$, proving the reverse set inclusion. Therefore

Complements are relative to the same universal set $\mathcal{U}$. Suppose $A\subseteq B$ and $x\in \overline{B}$. Then $x\in \mathcal{U}$ and $x\notin B$. If $x$ belonged to $A$, the assumed set inclusion would imply $x\in B$, a contradiction. Thus $x\notin A$ and $x\in \overline{A}$, provingThere is only one set inclusion in this conclusion; a reverse inclusion is neither needed nor generally true. The request for double inclusion applies to the equalities in (i) and (ii).

For the first set inclusion, take $x\in (A\cap B)\setminus C$. Membership in the intersection gives $x\in A$ and $x\in B$, while the set difference gives $x\notin C$. Consequently $x\in (A\setminus C)\cap (B\setminus C)$.

For the reverse set inclusion, an element of $(A\setminus C)\cap (B\setminus C)$ belongs to both $A$ and $B$ and does not belong to $C$. It therefore belongs to $(A\cap B)\setminus C$. By double inclusion proof,

We prove both set inclusions, as required by a double inclusion proof. If $x\in A\setminus (B\cup C)$, then $x\in A$ and $x\notin B\cup C$. Thus $x\notin B$ and $x\notin C$, so $x\in A\setminus B$ and $x\in A\setminus C$. This proves the forward set inclusion.

Conversely, if $x\in (A\setminus B)\cap (A\setminus C)$, then $x\in A$, $x\notin B$, and $x\notin C$. Hence $x\notin B\cup C$, giving $x\in A\setminus (B\cup C)$. Therefore

If $x\in A\oplus B$, the definition of symmetric difference puts it in exactly one of $A,B$. It is therefore in their set union and outside their set intersection, giving $x\in (A\cup B)\setminus (A\cap B)$.

Conversely, an element of $(A\cup B)\setminus (A\cap B)$ lies in at least one of the two sets but not both. It consequently belongs to $A\setminus B$ or to $B\setminus A$, and hence to $A\oplus B$. Both set inclusions hold.

For the first set inclusion, take $x\in A\setminus (A\setminus B)$. Then $x\in A$ but $x\notin A\setminus B$. Since membership in $A$ is already known, failure to lie in that relative complement forces $x\in B$. Hence $x\in A\cap B$.

Conversely, if $x\in A\cap B$, then $x\in A$ and its membership in $B$ excludes it from $A\setminus B$. Therefore $x\in A\setminus (A\setminus B)$. The two inclusions prove the stated equality with the set intersection.

We prove both set inclusions. If $x\in A\setminus (A\setminus B)$, then $x\in A$ and $x\notin A\setminus B$. Since $x\in A$, the latter condition forces $x\in B$, giving $x\in A\cap B$. Conversely, if $x\in A\cap B$, then $x\in A$ and $x\notin A\setminus B$, so $x\in A\setminus (A\setminus B)$. By set extensionality, the two sets are equal. This is a double inclusion proof; the implication involving the set difference uses membership in $A$ explicitly.

The probability axioms first give $\mathbb{P}(\varnothing )=0$: apply countable additivity to $\Omega ,\varnothing ,\varnothing ,\dots$ and use normalization and nonnegativity. If $A\subseteq B$, then $B=A\dot{\cup }(B\setminus A)$ is a disjoint union of events. Finite additivity, as a special case of countable additivity, givesThus a probability measure is monotone with respect to set inclusion. The difference event is measurable because the events belong to a sigma-algebra.

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.

Put $J=\{k\in \mathbb{N}:k\le 100\}$, avoiding any dependence on whether the convention includes $0$ among the natural numbers. Under set inclusion, the results are

The set union of all three-element subsets of $\mathbb{N}$ is $\mathbb{N}$. An upper bound for $S_1$ under set inclusion would have to contain this entire infinite set, whereas members of $A$ are finite. Thus $S_1$ has no upper bound and hence no maximum or least upper bound.

For $S_2$, every member is a subset of the finite set $J$, and $J$ itself belongs to $S_2$, making it both maximum and least upper bound. The union of the three-element subsets of $J$ is again $J$, so $J$ is the least upper bound of $S_1\cap S_2$. It is not a member of that family, and no three-element member contains all the others, so there is no maximum.

A proper filter on a set $X$ is a nonempty family $\mathcal{F}$ of subsets of $X$, closed under finite intersections and upward closed under set inclusion, with $\varnothing \notin \mathcal{F}$. Thus $X\in \mathcal{F}$, and disjoint sets cannot both belong to it. The improper family of all subsets is excluded because it contains the empty set. An ultrafilter is a maximal proper filter.