False statementConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 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: every effective encoding is prefix-free

Statement

False claim: every effective binary encoding is prefix-free.

Facts & Assumptions

Given: The encoding $e : {0, 1}^{*} \to {0, 1}^{*}$ defined by $e (w) = 1 w$ .

[A1]

The false claim: every effective binary encoding is prefix-free.

[L1]

An effective binary encoding is an injective map into ${0, 1}^{*}$ with a total decoder and a fixed malformed-code output, and prefix-free means that no codeword is a proper prefix of another, by Effective binary encodings and total decoders.

Refutation

technique · direct

1.1

The map $e (w) = 1 w$ is injective: if $1 u = 1 v$ , deleting the common first bit gives $u = v$ .

givenalgebra

1.2

Define a total decoder $d : {0, 1}^{*} \to {0, 1}^{*} \cup {m a l}$ by setting $d (1 w) = w$ for every binary word $w$ and $d (x) = m a l$ for every binary word $x$ not beginning with $1$ (including the empty word). Then $d (e (w)) = d (1 w) = w$ for every $w$ , so $e$ is effective by [L1].

L1construct

1.3

The codeword $e (ε) = 1$ is a proper prefix of $e (0) = 10$ . So $e$ is not prefix-free.

givenL1

2.1

Step 1.2 shows that $e$ is an effective encoding, while step 1.3 shows that it is not prefix-free. Therefore [A1] is false.

A1step 1.2step 1.3∎

Depends on

Effective binary encodings and total decoders

Used by

The encoding w↦ 1w is effective but not prefix-free Counterexample

Dependency tree · two levels

4 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 E. Savage, Models of Computation: Exploring the Power of Computing (standard reference, not scraped)
Michael Sipser, MIT 18.404J Theory of Computation, Lecture 7 (standard reference, not scraped)