0
$\begingroup$

In the question (Validity of predicate logic formulas) I see the following way of expressing:

"The predicate $P(x,y) \equiv \bigl[ y \cdot x = 1 \bigr]$, where the domain of discourse is $\mathbb{Q}$."

However, I am used to call this domain of discourse a first-order theory. For instance, I would have rewritten the above phrase as:

"The predicate $P(x,y) \equiv \bigl[ y \cdot x = 1 \bigr]$, where the first-order theory is $\mathcal{T}_{\mathbb{Q}}$.", where $\mathcal{T}_{\mathbb{Q}}$ denotes the theory of Linear Rational/Real Arithmetic (I call them like that, since, in the linear fragment, arithmetics for $\mathbb{Q}$ and $\mathbb{R}$ are equivalent).

Then, my question is: which is the difference between domain of discurse and first-order theory? Someone could say that if I am using a theory, then I am accepting all of its axioms, but the same happens with domain of discourse! That is, if I say the domain of discourse is $\mathbb{Q}$, then I am accepting all the axioms of the rationals, in the same way.

Does the difference come from the signature? Maybe the domain of discourse is not specifying whether the arithmetic is linear or no?

Improve this question
$\endgroup$
9
  • $\begingroup$ A first-order theory is a set of axioms, see Wikipedia. To understand where a formula belongs you don't need to specify a first-order theory. $\endgroup$
    – Yuval Filmus
    Nov 8, 2021 at 11:29
  • $\begingroup$ I suggest picking up a good textbook on first-order logic. It should contain all relevant definitions (except "domain of discourse", which I'm not sure is a standard formal notion in mathematical logic). $\endgroup$
    – Yuval Filmus
    Nov 8, 2021 at 11:30
  • $\begingroup$ I have the problem precisely with the notion of domain of discourse. $\endgroup$
    – Theo Deep
    Nov 8, 2021 at 15:54
  • $\begingroup$ Why after specifying a domain, you have to accept all of its axioms? Say if you specify your domain as $\mathbb{N}$, you don't need to accept all its usual axioms as in first order theory PA. You may only accept order relation (<) in your language and then still can prove it embeds into the $\mathbb{Q}$ line... $\endgroup$
    – Double Knot
    Nov 8, 2021 at 20:27
  • $\begingroup$ Hi, the answer below of @Pseudonym is not saying the contrary? I mean, that accepting naturals as discourse yields accepting all of its axioms. $\endgroup$
    – Theo Deep
    Nov 9, 2021 at 12:11

1 Answer 1

Reset to default
1
$\begingroup$

Unless I'm missing something, you're simply asking a different question than the previous questioner did.

The previous question is asking an abstract question about predicate logic, so all axioms are available. But the question could also have been expressed as a question about a specific theory, too. Asking "is $P$ a tautology where the domain of discourse is $\mathbb{N}$" is not the same question as "is $P$ a tautology in the theory of Peano arithmetic". In the former question, all axioms and theorems are available, and in the latter, you are restricting yourself to the first-order theory with addition and multiplication, plus induction.

The statement that $P\ne NP$ can be expressed as a formula in the domain of discourse $\mathbb{N}$, but not in any first-order theory.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think you understood my question, I am precisely wondering why asking "is 𝑃 a tautology where the domain of discourse is ℕ" is not the same question as "is 𝑃 a tautology in the theory of Peano arithmetic". You say that in the former question, all axioms and theorems are available. Which are 'all the axioms' of predicate logic? That is the point I am missing. $\endgroup$
    – Theo Deep
    Nov 8, 2021 at 15:42
  • 1
    $\begingroup$ You gave a good example when you noted that the linear fragment of $\mathbb{Q}$ is the same as the linear fragment of $\mathbb{R}$, but of course the first-order field theories are different; polynomials have more real solutions than rational ones. (In fact, the theory of first-order real closed fields is decidable, as shown by Tarski, but this is not true of the rationals.) $\endgroup$
    – Pseudonym ♦
    Nov 9, 2021 at 1:10
  • $\begingroup$ But if you're asking what there is to know about $\mathbb{N}$ apart from the Peano axioms, well, there's second-order induction as one example. See math.stackexchange.com/questions/2984410/… $\endgroup$
    – Pseudonym ♦
    Nov 9, 2021 at 2:23
  • $\begingroup$ When you say the first-order field theories are different, are you referring to the nonlinear fragment? As far as I know, the nonlinear fragment of rational arithmetic is undecidable, is not it? $\endgroup$
    – Theo Deep
    Nov 9, 2021 at 12:18
  • $\begingroup$ @TheoDeep That's correct. The first-order theory of rationals with the field operations (addition, subtraction, multiplication, division) is undecidable, but reals are decidable. See en.wikipedia.org/wiki/Real_closed_field $\endgroup$
    – Pseudonym ♦
    Nov 9, 2021 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.