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
    There exists a nonstandard model M in which all polynomia... — Carmelics
    Statements
    321,452
    Perspectives
    108,905
    Topics
    42
    Home/Modality & Possibility
    HistoryEditSee Inverse

    There exists a nonstandard model M in which all polynomial-time computable functions are total but the exponential function is not total.

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

    Reasons For

    1 perspective
    Reason for
    ?
    • 1.The theory S^1_2 + ∃y¬∃z ε(2,y,z) is proof-theoretically consistent.
      ?

      Think about whether this reason is strong or weak

    • 2.By the completeness theorem for first-order logic, every consistent theory has a model.
      ?

      Think about whether this reason is strong or weak

    • 3.In such a model M, there exists an element a satisfying ¬∃z ε(2,a,z), meaning 2^a does not exist in M.
      ?

      Think about whether this reason is strong or weak

    Reasons Against

    2 perspectives
    Reason against 1 of 2
    ?
    • 1.The completeness theorem guarantees a model exists but not that it is ω-consistent; nonstandard models may satisfy sentences false in the standard interpretation.
      ?

      Think about whether this reason is strong or weak

    • 2.Kreisel's squeezing argument shows that provability in formal systems and truth in intended models can come apart, so model existence from consistency does not vindicate the claim about actual computational totality.
      ?

      Think about whether this reason is strong or weak

    • 3.The polynomial-time functions being 'total' in M means only that M satisfies their defining axioms, not that they are total over the genuine natural numbers, making the claim modal-epistemically ambiguous.
      ?

      Think about whether this reason is strong or weak

    Reason against 2 of 2
    ?
    • 1.Putnam's model-theoretic argument establishes that formal consistency alone cannot fix intended reference, so 'polynomial-time computable' in M may not refer to the same class as in the standard model.
      ?

      Think about whether this reason is strong or weak

    • 2.If the exponential function fails to be total in M, then M's arithmetic is too weak to interpret standard complexity-theoretic distinctions, undermining the claim that M's polynomial-time class is the complexity-theoretically relevant one.
      ?

      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

    Modality & PossibilityTruth & Knowledge

    Related

    All polynomial-time computable functions are defined for all inputs in M, so M s...By the completeness theorem for first-order logic, every consistent theory has a...If the exponential function fails to be total in M, then M's arithmetic is too w...In such a model M, there exists an element a satisfying ¬∃z ε(2,a,z), meaning 2^...
    +5 moreShow less
    Kreisel's squeezing argument shows that provability in formal systems and truth ...Putnam's model-theoretic argument establishes that formal consistency alone cann...The completeness theorem guarantees a model exists but not that it is ω-consiste...The polynomial-time functions being 'total' in M means only that M satisfies the...The theory S^1_2 + ∃y¬∃z ε(2,y,z) is proof-theoretically consistent.

    Similar

    There exists a consistent first-order model in which the exponential f...80%The universal partial computable function υ(i,x) is not total (i.e., n...77%The provably total functions of S¹₂ correspond to the polynomial-time ...76%A function f(x) is computable in polynomial time if and only if f(x) i...76%

    Source

    AI-extracted1/3 agreementValid
    SEP: computational-complexity
    View source passageHide passage
    Nonetheless, Parikh showed that for appropriate choices of \(\tau\), any proof of a contradiction in \(\mathsf{PA}^F\) must itself be very long. For instance, if we consider the super-exponential function \(2 \Uparrow 0 = 1\) and \(2 \Uparrow (x+1) = 2^{2 \Uparrow x}\) and let \(\tau\) be the primitive recursive term \(2 \Uparrow 2^k\), it is a consequence of Parikh’s result that any proof of a contradiction in \(\mathsf{PA}^F\) must be on the order of \(2^k\) steps long. e. non-vague) property
    Extraction notes

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

    Details

    Type
    claim
    Perspectives
    3 (1 for, 2 against)
    Edits
    1 edit