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.
Finite power-oracle queries cannot universally certify no feasible sample size
Statement refuted
The claim is that there is a deterministic procedure which, for every exact Boolean feasibility oracle on all positive integers, accesses that oracle only through queries of individual sizes, terminates after finitely many queries, and returns the least feasible positive size or if there is none. The claim remains false even when the oracle is promised to be nondecreasing. This is a finite-query black-box statement; it does not exclude analytic solutions or additional global certificates for specified model families.
Facts & Assumptions
Given: A purported deterministic, universally terminating procedure of this type. Each oracle query has an exact terminating answer. The procedure has no additional information distinguishing the oracles below.
A planning specification allows a model at each size and defines power as the rejection probability at the target parameter; its empty feasible set has extensional answer none. Power and sample-size planning specifications, Test size and power
A statistical experiment is a family of probability laws on a data measurable space, a measurable rejection function defines a randomized test, and the Dirac set function is a probability law concentrated at . Statistical experiments, Randomized tests, Every measurable rejection function defines a randomized test, The Dirac set function at a point, A Dirac set function is a probability measure
Counterexample
Give the procedure the constant-false oracle . Correctness forces the output none, and universal termination makes its queried set finite. Put , which is a positive integer greater than every queried positive size, including when is empty, and define . Both oracles are nondecreasing and answer false at every query in the completed transcript.
Run the same deterministic procedure with . Its initial internal state is the same, and whenever a query is reached along the original transcript, its answer is the same false value. Induction through the finite transcript therefore gives identical internal states, queries and terminal output. It returns none on , although is the least feasible size. This contradicts the claimed correctness.
These oracles are realizable as exact power-feasibility inputs: use candidate plans with one allocation count equal to , for every positive integer ; at that size take the measurable space with its full power set, parameters , null law , target law , and test . The full power set makes measurable, and the proved point-mass and measurable-rejection-function suppliers in [F2] make this an experiment and randomized test. Its null size is zero and target power is , so a size bound zero and target power in [F1] make feasibility equivalent to . Use either or ; hence the distinction is compatible with explicit statistical laws, not a numerical approximation error.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
32 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.