3

So I am curious how to correctly reason about $Th(\mathbb{N})$. Is it a set of constants 0,1 and relations on them?

E.g can we say that $(1+1+1+1) * (1+1+1)$ is in $Th(\mathbb{N})$ because we take a constant $(1+1+1+1) \in \mathbb{N}$ and constant $(1+1+1) \in \mathbb{N}$ and apply relation $*$ on them that produces new number $n$ such that $n \in \mathbb{N}$?

Am I reasoning in a right way?

Can we say that relations $ +, -, *, /, \sqrt{} $ etc are all relations in $Th(\mathbb{N})$?

Eric Wofsey
  • 330,363
YanyongXu
  • 81
  • 3
    As your title asks, "What is $Th(\mathbb{N})$?", it is necessary to answer this part of the Question, defining $Th(\mathbb{N})$, before addressing the part about whether you "correctly reason" about it. You tagged this "elementary number theory", but it seems that your concerns are about the foundations of mathematics and logic. If you are interested in formal first-order theories of the natural numbers, you might learn something about that, e.g. Peano's axioms, to make your Question more specific and better grounded. – hardmath Sep 20 '15 at 18:24

2 Answers2

5

$Th(\mathbb{N})$ is the set of sentences in the first-order language of arithmetic (usually understood to be $\{+, \times, 0, 1\}$) which are true of the natural numbers.

So, for example:

  • "$\forall x(x=0)$" is not in $Th(\mathbb{N})$, because it is not true that every natural number is zero.

  • "$1+1=2$" is not in $Th(\mathbb{N})$, because there is no primitive symbol for "2".

  • "$1+1+1$" is not in $Th(\mathbb{N})$, because it is a term, not a sentence - what would it mean for "$1+1+1$" to be false?

  • "$\forall X\subseteq\mathbb{N}(0\in X\implies 0\not\in X)$" is not in $Th(\mathbb{N})$, since in first-order logic we can't quantify over sets.

  • But "$\forall x\forall y(x+y=y+x)$ is in $Th(\mathbb{N})$. It is a first-order sentence, using only (nonlogical) symbols from among $\{0, 1, +, \times\}$, which is true of $\mathbb{N}$.

EDIT: in first order logic, in addition to the nonlogical symbols provided by the specific context we're working in (in this case, $+, \times, 0, 1$), we always have: parentheses $(, )$, Boolean connectives $\wedge, \vee, \neg, \implies$, quantifiers $\forall,\exists$, variables $x_0, x_1, . . .$, and equality $=$.

Noah Schweber
  • 245,398
  • The 1st and 5th bullets should be problematic for the same reason as the 4th bullet, correct? That is, $x$ and $y$ are sets (all variables in set theory represent sets) and first-order logic doesn't have quantification. – EthanAlvaree Sep 20 '15 at 18:53
  • 3
    @EthanAlvaree No, that's not correct - first-order logic does have quantification. See https://en.wikipedia.org/wiki/First-order_logic. I think you are thinking of propositional logic, which indeed does not allow quantifiers (but also doesn't allow nonlogical symbols like "$+$" and "$\times$," etc.). – Noah Schweber Sep 20 '15 at 18:54
  • Sorry, you're right. I was mistakenly thinking of propositional logic. – EthanAlvaree Sep 20 '15 at 18:55
  • So x and y may be only 0 or 1? – YanyongXu Sep 20 '15 at 18:57
  • 1
    @YanyongXu No, the variables may refer to anything, but we only have specific names for 0 and 1. Think about it this way: suppose I only knew two people, named Sam and Alex. Then I might know "there are people other than Sam and Alex," but I wouldn't know any specific people other than Sam and Alex - I might not even know any names other than "Sam" and "Alex"! So I could still say things like, "Every person has a head," and this statement would be true even of people like Morgan (who I don't know), but I couldn't say "Morgan has a head" because I don't know the name "Morgan." – Noah Schweber Sep 20 '15 at 18:59
  • how do I know my $\Bbb N$ has the same theory as your $\Bbb N$ ? – mercio Sep 20 '15 at 19:01
  • Okay. But can I say that $(1+1+1) \times (1+1+1+1) \in Th(\mathbb N)$? – YanyongXu Sep 20 '15 at 19:02
  • 1
    @mercio For the moment I'm taking as granted that there is a "real" object $\mathbb{N}$ that we're talking about. If you want to get into philosophical issues around how we individually think about the natural numbers, there's lots of great stuff there, but I don't think this question is a good place to get into that. – Noah Schweber Sep 20 '15 at 19:02
  • 2
    @YanyongXu Well, you can't say that exact string in the language of arithmetic - what are "$\in$" and "$\mathbb{N}$"? However, in first-order logic we always assume that terms refer to things - that is, we don't allow undefined terms. So, since we can form the term $(1+1+1)\times (1+1+1+1)$, then yes, we can use this to refer directly to the number 12 even though we don't have a specific name "12" (similarly to how I can refer to "Sam's best friend" without knowing Sam's best friend's name - I've uniquely specified a person, and that's good enough). – Noah Schweber Sep 20 '15 at 19:04
  • @YanyongXu (cont'd) Now, $\mathbb{N}$ has a remarkable property - as long as I have symbols for $0, 1,$ and $+$, I can refer uniquely to every natural number! That is, every natural number corresponds to a closed term ("closed" just means "no variables"). So in practice I don't have to pay attention to what names for numbers I use. But this is a special feature of $\mathbb{N}$ which is not true of all, or even most, natural mathematical structures. For instance, in the structure $(\mathbb{R}, +, \times, 0, 1)$, how would you name $\pi$? – Noah Schweber Sep 20 '15 at 19:07
  • 3
    @YanyongXu It looks like I misread your most recent comment. No, $(1+1+1)\times (1+1+1+1)$ is not in $Th(\mathbb{N})$ (I read ". . .$\in\mathbb{N}$" instead of ". . . $\in Th(\mathbb{N})$"), since - as I explain in my answer - $(1+1+1)\times (1+1+1+1)$ is not a statement. What would it mean for it to be "true" or "false"? – Noah Schweber Sep 20 '15 at 19:08
3

We have to start with a language $\mathcal L$, e.g the first-order language for arithmetic (or elemntary number theory) :

Constant symbols: $0$

One-place function symbols: $S$ (for successor)

Two-place function symbols: $+$ (for addition) and $\times$ (for multiplication).

Then we have to consider a structure $\mathcal N =(\mathbb N, 0, S, +, \times)$ for that language.

Finally, we define the theory of $\mathcal N$, written $\mathsf {Th} \mathcal N$, as the set of all sentences true in $\mathcal N$.

Examples : $0=0 \in \mathsf {Th} \mathcal N$; $\exists n (S(n) = 0) \notin \mathsf {Th} \mathcal N$ (recall that $\mathsf {Th} \mathcal N$ is a set of sentences).

The first sentence is clearly true, while the second one is false ($0$ is not a successor).

But we have to pay attention to the language : we can take into account the expessive capability of it.

We cannot say, e.g. : $\exists n (n= \sqrt 4)$ but we can say : $\exists n (n \times n = S(S(S(S(0)))))$.

We cannot say : $0 < 2$ but we have to say : $\exists n (0+n = S(S(0)))$.

In order to use the "usual" expressions, we have to "enlarge" the original language adding suitable definition for the new terms and relations.

Community
  • 1
Mauro ALLEGRANZA
  • 94,169
  • So $\mathsf {Th} \mathcal N$ has ONLY function symbols $+$ and $\times$ ? Can I say that $(1+1+1) \times (1+1+1+1) \in \mathbb N$ ? – YanyongXu Sep 20 '15 at 19:00
  • @YanyongXu - after we have expanded the language with the definition : $1=S(0)$, we can use it. In alternative, see answer above, we can put it into the language from the start. The language has symbols; $\mathsf {Th} \mathcal N$ has sentences, like (after the introduction of $1$) $1+1+1=S(S(S(0)))$. Your example is not a sentence. – Mauro ALLEGRANZA Sep 20 '15 at 19:10
  • 1
    @YanyongXu Note that the language Mauro uses is different from the one I use. Technically, writing "$Th(\mathbb{N})$" is ambiguous - you need to specify exactly what the language is. In practice, though, it rarely matters which of the many natural languages for arithmetic one uses. – Noah Schweber Sep 20 '15 at 20:04