Skip to content
Carmelics
TopicsThinkersChangesContributorsLoading account…

    Carmelics

    A reasoning platform. Break down any belief into clear reasons, explore both sides, and weigh the evidence honestly.

    Navigate

    • Topics
    • Search
    • Recent Changes
    • Contribute
    • How It Works
    • Glossary
    • Thinkers
    • Contributors
    • About
    • Statistics
    • Terms
    • Privacy

    Database

    Statements
    —
    Perspectives
    —
    Topics
    —

    Press ? for keyboard shortcuts

    LoyalLoyalJusticeJustice
    Made withinDC&Austin
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Exponentiation is not provably total in IΔ_0 — Carmelics
    Home/Skepticism
    HistoryEditSee Inverse

    Exponentiation is not provably total in IΔ_0

    SkepticismTruth & Knowledge
    ?Rate how convincing each reason is below to see the overall strength.
    2 reasons for
    2 reasons against

    Reasons For

    2 perspectives
    Reason for 1 of 2
    ?
    • 1.All provably total functions of IΔ_0 are of polynomial rate of growth
      ?

      Think about whether this reason is strong or weak

    • 2.The exponentiation function grows at super-polynomial (exponential) rate
      ?

      Think about whether this reason is strong or weak

    Reason for 2 of 2
    ?
    • 1.All provably total functions of IΔ_0 are of polynomial rate of growth
      ?

      Think about whether this reason is strong or weak

    • 2.Exponentiation grows faster than any polynomial
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.IΔ_0 with the axiom Ω_1 (asserting totality of exponentiation) is a consistent extension that many foundationalists accept as the correct base theory.
      ?

      Think about whether this reason is strong or weak

    • 2.The claim conflates provability within a specific weak system with a stronger metaphysical claim about the mathematical nature of exponentiation itself.
      ?

      Think about whether this reason is strong or weak

    • 3.Wilkie and Paris's 1987 result shows unprovability is relative to IΔ_0's restricted induction scheme, not an intrinsic feature of exponentiation's totality.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Edward Nelson's predicativist program in 'Predicative Arithmetic' (1986) disputes that exponential growth is well-defined at all, undermining the comparison premise rather than the conclusion.
      ?

      Think about whether this reason is strong or weak

    • 2.If one adopts Nelson's ultrafinitism, the supporting arguments' P2 begs the question by presupposing a completed infinite domain over which exponentiation's rate of growth is assessed.
      ?

      Think about whether this reason is strong or weak

    Sign in or register to share your perspective on this statement.

    Next step

    Based on where you are in your exploration

    Strongest counterpoint
    Explore the most compelling reason on the other side.

    Topics

    SkepticismTruth & Knowledge

    Connections

    2 topics

    Modality & Possibility2 linkedAll sources support it1 linked

    Related

    All provably total functions of IΔ_0 are of polynomial rate of growthEdward Nelson's predicativist program in 'Predicative Arithmetic' (1986) dispute...Exponentiation grows faster than any polynomialIf one adopts Nelson's ultrafinitism, the supporting arguments' P2 begs the ques...
    +4 moreShow less
    IΔ_0 with the axiom Ω_1 (asserting totality of exponentiation) is a consistent e...The claim conflates provability within a specific weak system with a stronger me...The exponentiation function grows at super-polynomial (exponential) rate

    Similar

    Exponentiation is not provably total in IΔ₀92%If P ⊊ NP, then NP-complete problems are not in P.76%IΔ_0 does not prove the totality of the exponential function.75%TQBF is PSPACE-complete.74%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    A first link between formal arithmetic and complexity was provided by Cobham’s (1965) original characterization of \(\textbf{FP}\) in terms of a functional algebra similar to that by which the primitive recursive functions are defined. 1 The function \(f(\vec{x},y)\) is said to be defined from \(g(\vec{x}), h_0(\vec{x},y,z), h_1(\vec{x},y,z)\) and \(k(\vec{x},y)\) by limited recursion on notation just in case \[ \begin{aligned} f(\vec{x},0) &= g(\vec{x})\\ f(\vec{x},s_0(y)) &= h_0(\v
    Extraction notes

    Validity: Extracted via Max plan + API grounding/validity checks

    Details

    Wilkie and Paris's 1987 result shows unprovability is relative to IΔ_0's restric...
    Type
    claim
    Perspectives
    4 (2 for, 2 against)
    Edits
    1 edit