Exclusion Logic

Origin. Pietro Galliani, "Inclusion and exclusion dependencies in team semantics" (Annals of Pure and Applied Logic, 2012), which introduced the exclusion atom alongside the inclusion atom and settled its expressive power in the same paper.

Models. The dual constraint to inclusion: the values a team gives x̄ and the values it gives ȳ are disjoint. Like inclusion, it is a property of the team and not of any assignment in it. Unlike inclusion, it is downward closed — and that single property makes it expressively equivalent to dependence logic.

Formalism.

The exclusion atom: M, X ⊨ x̄ | ȳ iff ∀s, s′ ∈ X : s(x̄) ≠ s′(ȳ) No value of x̄ is a value of ȳ anywhere in the team.

Closure: Downward closed: X ⊨ φ and Y ⊆ X gives Y ⊨ φ. Same closure as dependence logic; opposite to inclusion logic.

Expressive power (Galliani 2012): Exclusion logic ≡ dependence logic, sentence for sentence. Both capture Σ¹₁, hence NP over finite structures. Each atom is definable from the other in the presence of first-order machinery.

Inclusion + exclusion: Together they give independence logic's strength. Inclusion–exclusion logic ≡ independence logic (Galliani 2012).

Contrast with inclusion: Two atoms, one paper, opposite closure properties, different logics. Downward closure tracks Σ¹₁; union closure tracks GFP⁺.

Symbols.

Symbol	Unicode	Name	Meaning
X	—	Team	Set of assignments
\|	—	Exclusion atom	x̄ \| ȳ: value sets disjoint
⊆	U+2286	Inclusion atom	The dual constraint
Σ¹₁	—	Sigma-1-1	Existential second-order; the captured class

Metatheory. The equivalence with dependence logic is the reason the atom matters: it shows that Σ¹₁ is reached by more than one route, and that the family's expressive landscape is organized by closure properties rather than by the intuitive content of the atoms. Combined with inclusion, it reaches independence logic — so two atoms with simple database readings suffice for the whole hierarchy.

Applies to. Database dependency theory (exclusion dependencies). Comparative expressive power in team semantics. Reductions among team-semantic logics.

Limitations. Less studied than inclusion, largely because it turned out to add nothing to dependence logic's strength — the negative result is what made it a footnote. No compositional contradictory negation. The disjointness reading is natural for databases and strained as an account of anything linguistic, which is where the dependence atom's motivation came from.