False statementConstruction: AI-adaptedVerification: 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.

FALSE: PCP permits reordering symbols inside a domino

Statement

In a PCP match, one may reorder the symbols inside a chosen domino before concatenating it.

Facts & Assumptions

Given: The one-domino PCP instance $(a b, b a) .$

[L1]

A PCP match must satisfy equality of the literal top and bottom concatenations of the chosen domino sequence, by The Post correspondence problem.

Refutation

technique · direct

1.1

If one were allowed to reorder symbols inside the domino, the unique tile could be changed from $(a b, b a)$ to $(a b, a b)$ by swapping the bottom symbols, and then a one-tile sequence would look like a match.

given

2.1

In actual PCP, [L1] forbids that operation. The only nonempty sequences use the same domino some number $k \geq 1$ of times, yielding top word $(a b)^{k}$ and bottom word $(b a)^{k}$ . Their first symbols are always different, so these words are never equal.

L1step 1.1

3.1

Therefore the claimed permission is false: PCP concatenates whole dominoes in the chosen order and does not allow symbol reordering within a tile.

step 2.1∎

Depends on

The Post correspondence problem

Used by

A domino family where matching fails unless one illegally permutes symbols inside a tile Counterexample

Dependency tree · one level

1 result within one dependency step 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 (standard reference, not scraped)