TheoremStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

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.

Decidable languages are closed under the Boolean operations

Statement

If $L, K \subseteq Σ^{*}$ are decidable, then their complement, union, intersection, difference, and symmetric difference are decidable.

Facts & Assumptions

Given: Decidable languages $L, K \subseteq Σ^{*}$ .

[L1]

By Decidable and recognizable languages, a decider halts on every input with the correct membership answer.

[L2]

By Boolean operations on languages over a fixed alphabet, complements and differences are taken inside the fixed ambient $Σ^{*}$ .

[A1]

The set identities $L ∖ K = L \cap K^{c}, L △ K = (L ∖ K) \cup (K ∖ L)$ hold for all subsets of one set.

Proof

technique · direct

1.1L1L2given

If $M_{L}$ decides $L$ , then flipping its final yes-or-no answer gives a halting decider for $L^{c}$ . If $M_{L}$ and $M_{K}$ decide $L$ and $K$ , run both and combine their two halting answers by the ordinary Boolean truth tables to decide $L \cup K$ and $L \cap K$ .

2.1A1step 1.1

By [A1], the same deciders decide $L ∖ K$ as $L \cap K^{c}$ and decide $L △ K$ as $(L ∖ K) \cup (K ∖ L)$ . Because each constituent operation from step 1.1 preserves halting, these languages are decidable as well.

3.1step 1.1step 2.1∎

Therefore decidable languages are closed under all five stated Boolean operations.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

John Watrous, Introduction to the Theory of Computing, Lecture 18: Further discussion of computability (standard reference, not scraped)
Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)