0
$\begingroup$

Axioms:

  • Peano Axioms (defines natural number, introducing 0 and ')
  • For each predicate φ, there exist exactly one set X, s.t. forall x, φ(x) <=> x∈X.

So, it's possible to define less-than in First-order logic as:

$$ x < y : (x \neq y) ∧ [\forall X, (x\in X)∧(∀t∈X, t'∈X)\rightarrow y∈X]$$

Questions:

  • Can this model define addition? (Note that sets of sets are not supported)
  • Can this model define multiplication?
  • Can this model construct uncomputable questions?
$\endgroup$
3
  • $\begingroup$ The Peano axioms define addition and multiplication. Once you have addition you can define less than as $x \lt y \iff \exists b (x+b=y)$ $\endgroup$
    – Ross Millikan
    Commented Jun 18 at 3:08
  • $\begingroup$ @RossMillikan That part isn't introduced into this model $\endgroup$
    – l4m2
    Commented Jun 18 at 3:12
  • $\begingroup$ According to Wikipedia what I was thinking of as Peano axioms are correctly called Peano arithmetic. Sorry for the confusion $\endgroup$
    – Ross Millikan
    Commented Jun 18 at 3:19

1 Answer 1

Reset to default
2
$\begingroup$

In more standard terminology, you're asking about the monadic second-order theory of the natural numbers with sucessor ("monadic second-order" means that you can quantify over sets, but not relations of arity $>1$). This - and indeed much more - is decidable, so the answer to all three of your questions is negative. See wiki, or Rabin's famous paper on the monadic second-order theory of the binary tree.

(And if you want a glimpse at how messy things can get with more complicated orderings, look at Shelah's The monadic theory of order.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .