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.
Ceilings give the least positive integer meeting a real threshold
Statement
Identify integers and naturals with their canonical copies in the reals. For every real , put , using Integer part: for every real there is exactly one integer with . Then is an integer, , and For , the least positive integer with is . In particular , and for every integer .
Facts & Assumptions
Given: Real , integer , and, for the positive-size claim, real .
Every real has a unique integer with , denoted . Integer part: for every real there is exactly one integer with
Integers form an ordered ring. Every nonnegative integer is the image of a unique natural, and this embedding preserves order, addition, zero and one. The integers form a totally ordered ring, The naturals embed in the integers
For naturals , exactly when ; in particular a positive natural is at least one. Discreteness: is the immediate successor
Real order is total and transitive, and addition preserves strict order; adjoining the equality case gives the nonstrict version. Ordered field, Order is preserved by adding a constant and by adding inequalities
Proof
Apply [F1] to and write , . By [F2], is an integer. Negating using [F4] gives .
For an integer , [F1] applied to gives , so . This includes .
Every positive integer is at least one: by [F2] it is the image of a natural, which is nonzero because the embedding is injective and preserves zero, and [F3] gives the conclusion. If an integer satisfies but , then the positive integer is at least one. Thus by step 1.1, a contradiction. Therefore implies ; conversely implies because . This proves the equivalence with .
For , step 1.1 gives . Thus is an integer at least one, hence a positive natural under [F2], and . If a positive integer satisfies , step 2.1 gives and step 2.1's discreteness argument gives . Hence , proving leastness.
Depends on
Used by
- BBHT search when the marked count is unknown Algorithm
- Known-count Grover search by exact integer maximization Algorithm
- Known-count search by randomized Grover iteration Algorithm
- An exact one-sided normal sample size and its effect-variance sensitivity Example
- Average Grover success for a uniform integer iteration count Lemma
- Bit cost of exact known-count iteration selection Proposition
- Classical bit cost of randomized known-count search Proposition
- Gate and reflection accounting for randomized known-count search Proposition
- Exact power and least sample size for a known-variance normal z-test Theorem
- Expected bit-query cost of unknown-count BBHT search Theorem
- Integer rounding gives a high-success Grover iterate Theorem
- Known-count Grover search uses O of the square root of N over t bit queries Theorem
- Query cost of randomized known-count Grover search Theorem
- Shannon bounds for finite binary codes Theorem
- The rational finite-register arithmetic code is prefix-free and lossless Theorem
- Unconditional convergence and existence for the periodic diagonal-diffusion HJB scheme Theorem
Dependency tree · two levels
36 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
- Emily Riehl, Category Theory in Context, Example 4.1.7, printed p. 134 (standard reference, not scraped)