Absence of a functional bound
Lax825442.DoesNotBound · concepts/Lax825442/DoesNotBound.lean · lax-825442
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
We write if no total computable nondecreasing function bounds in terms of on every finite simple graph. This relation is the negation of functional boundedness.
A family of graphs on which is uniformly bounded and is unbounded establishes this relation. Such a family is sufficient, but the absence of a computable bound does not imply the absence of every noncomputable bound.
Concept map
Lean source view on GitHub
| 1 | import Lax825442.Bounds |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Absence of a functional bound |
| 6 | type: definition |
| 7 | --- |
| 8 | We write if no total computable nondecreasing function bounds |
| 9 | in terms of on every finite simple graph. This relation is the |
| 10 | negation of functional boundedness. |
| 11 | |
| 12 | A family of graphs on which is uniformly bounded and is unbounded |
| 13 | establishes this relation. Such a family is sufficient, but the absence of a |
| 14 | computable bound does not imply the absence of every noncomputable bound. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax825442.DoesNotBound |
| 18 | |
| 19 | open Lax153141.GraphParameters |
| 20 | |
| 21 | /-- No computable nondecreasing functional bound from `p` to `q` exists. -/ |
| 22 | def DoesNotBound (p q : GraphParam) : Prop := |
| 23 | ¬ (Lax825442.Bounds.Bounds p q) |
| 24 | |
| 25 | end Lax825442.DoesNotBound |
| 26 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments