4

I am reading the book "Introduction to Metamathematics" by Kleene. I am now in Chapter 8 which is about "Systems of objects". I must warn you that this chapter is meant to be an introduction and, therefore, it is written in an intuitive language. Still, I would like to understand the details.

There, he defines:

  1. By a system of objects, we mean a set or class or domain $D$ of objects among which are established certain relationships. For example, the natural number sequence (given in his previous chapters by something very similar to Peano axioms) constitutes a system of the type $(D,0,')$, where $D$ is a set, $0$ is the member of the set, and $'$ is a unary operation.

  2. Any specification of what the objects are gives a model of the system, i.e. a system of objects which satisfy the relationships and have some further status as well.

  3. Two models of the same abstract system are isomorphic, i.e. can be put into 1-1 correspondence preserving the relationships.

Then, he gives an example of a model for the abstract system $(D, 0, ')$ to be the one with two distinct objects $0$ and $1$, where $0' = 1$ and $1' = 0$, and calls it residues modulo 2.

I do not see how this fits with the definitions.

I guess that usual natural numbers, i.e. sequence $0, 1, 2, ...$ is a model for the natural numbers.

Question 1: Are natural numbers a model for natural numbers $(D, 0, ')$ ? Intuitively, I feel that they are, because I give some information about the objects of the system, in a sense that I give names for each of the objects.

From definition 3, two models of the same abstract system can be put into 1-1 correspondence. Now, if residues modulo 2 have only two objects then I do not see how that could be given a 1-1 correspondence to a sequence $0, 1, 2, ... $, which I assume is a model for the abstract system of natural numbers.

What intuitively I would think could solve the problem is, that, for example, we have ordered pairs $(0, 0), (1, 0), (0, 1), ...$, where the first coordinate would be the way we wanted it to be, but the second coordinate shows which time $0$ or $1$ is produced.

Question 2: How can the model of residues modulo 2 be given a 1-1 correspondence with other models, such as natural number sequence?

I would appreciate your help and any comments.

Daniels Krimans
  • 1,473
  • 3
    $D={0,1}$ is a set. $D$ has an element labelled $0$. ${}'$ defined by $0'=1$ and $1'=0$ is a function $D\to D$. Does Kleene mean anything more than that? – Angina Seng Jul 19 '18 at 09:18
  • 1
    It looks confusing to me. Apparently by a "system" Kleene means what a modern introductory text would call an "interpretation" or "structure" over a particular logical language, and then, if the quote/paraphrase is correct, he spends effort on defining "model" to mean exactly the same thing once over again. – hmakholm left over Monica Jul 19 '18 at 11:30
  • 1
    Certainly the example of integers modulo 2 doesn't appear to show any more than that they are a structure over the language ${0,{}'}$. That he includes a $D$ symbol in the triple $(D,0,{}')$ may indicate that he's aiming for many-sorted logic, but it's hard to tell here. – hmakholm left over Monica Jul 19 '18 at 11:33
  • @LordSharktheUnknown, thanks for your comments! I am not sure, but as I understand, as he states that for every abstract system (say, $(D, 0, ')$), every two models can be put into 1-1 correspondence. I don't see how finite set ${0,1}$ can be put in this correspondence with the set of natural numbers, which is also a model of this system. – Daniels Krimans Jul 19 '18 at 14:24
  • @HenningMakholm thanks for your comments! Is it true that system $(D, 0, ')$ must necessarily have Peano axioms? Are axioms built in within a certain system of symbols? I think this is one of the main confusions for me because from Peano $1'=0$ is not allowed, and I don't see how that is a model of it. – Daniels Krimans Jul 19 '18 at 14:24
  • Maybe in his book he meant that "two models are isomorphic iff (not i.e.) they can be put in 1-1 correspondence"? – Daniels Krimans Jul 19 '18 at 14:49
  • 1
    @DanielsKrimans: What you quote here doesn't look like he's expecting it to satisfy particular axioms. However it is true that the usual meaning of "model" is a interpretation/structure that does satisfy the axioms of whichever theory you're considering. If you're paraphrasing rather than quoting it may be you have missed a statement to that effect. – hmakholm left over Monica Jul 19 '18 at 15:00
  • 1
    It makes it a bit difficult to answer the question that what you seem to be describing is a rather non-standard usage of the words, and it is not clear without having to book whether it is Kleene who uses the words in a (these days) non-standard way or you who misunderstand what he's saying -- and in the first case whether to answer with an explanation of the standard usage or by trying to divine a consistent meaning of what Kleene is saying. – hmakholm left over Monica Jul 19 '18 at 15:02
  • 1
    The best strategy may be to shrug and proceed to the (hopefully) more formal rest of the book, and then afterwards return and see if the passage makes more sense in light of his actual formalism. – hmakholm left over Monica Jul 19 '18 at 15:03
  • @HenningMakholm I will do it as you suggest, thanks! – Daniels Krimans Jul 19 '18 at 20:27
  • 1
    Are you sure you have quoted definition 3 correctly? (I'd expect it to say something like "two models are isomorphic if they can be put into 1-1 correspondence preserving all the relationships".) – Rob Arthan Jul 19 '18 at 20:47
  • @RobArthan Yes, this is the exact quote from the book. – Daniels Krimans Jul 19 '18 at 21:42

1 Answers1

3

I've had a look at this now and agree that Kleene's terminology is a little confusing. (Aside: your reference isn't quite right: it's section 8 and is in chapter II.)

Kleene goes on to say that "two different systems $(D_1, 0_1, '_1)$ and $(D_2, 0_1, '_2)$ of type $(D, 0, ')$ are (simply) isomorphic if there exists a $1$-$1$ correspondence between $D_1$ and $D_2$ that [preserves all the structure]".

What Kleene is calling an "abstract system" is an isomorphism class of models in more modern terminology. When he says "model of the abstract system" he means "representative of the isomorphism class". His notation is a bit confusing: when he says "of type $(D, 0, ')$", he just means what we would nowadays call (a model) with signature $(0, ')$. In modern terminology, explicit representations of the natural numbers and of the residues modulo 2 give two different models for the signature $(0, ')$. In Kleene's terminology the two representations belong to two distinct abstract systems of the same type.

Rob Arthan
  • 48,577