The Richness of Models of Peano Arithmetic
A look into the axioms and logical symbols of Peano Arithmetic, exploring its properties related to addition, multiplication, identity elements, and ordering. The axioms establish the foundational principles governing arithmetic operations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
The richness of models of Peano Arithmetic Erez Shochat St. Francis College
Axioms of Peano Arithmetic Logical symbols , , , , , , = ,
Axioms of Peano Arithmetic Logical symbols Language: logical symbols together with LPA = { +, x, <, 0, 1} , , , , , , = ,
Axioms of Peano Arithmetic Logical symbols Language: logical symbols together with LPA = { +, x, <, 0, 1} Axioms: 1. Addition and multiplication are commutative and associative and satisfy the Distributive law. , , , , , , = ,
Axioms of Peano Arithmetic Logical symbols Language: logical symbols together with LPA = { +, x, <, 0, 1} Axioms: 1. Addition and multiplication are commutative and associative and satisfy the Distributive law. 2. 0 is the additive identity and 1 is the multiplicative identity. , , , , , , = ,
Axioms of Peano Arithmetic Logical symbols Language: logical symbols together with LPA = { +, x, <, 0, 1} Axioms: 1. Addition and multiplication are commutative and associative and satisfy the Distributive law. 2. 0 is the additive identity and 1 is the multiplicative identity. 3. The ordering is a discrete linear order, with a first element and no last element , , , , , , = ,
Axioms of Peano Arithmetic Logical symbols Language: logical symbols together with LPA = { +, x, <, 0, 1} Axioms: 1. Addition and multiplication are commutative and associative and satisfy the Distributive law. 2. 0 is the additive identity and 1 is the multiplicative identity. 3. The ordering is a discrete linear order, with a first element and no last element 4. Addition and multiplication respect order. , , , , , , = ,
Axioms of Peano Arithmetic Logical symbols Language: logical symbols together with LPA = { +, x, <, 0, 1} Axioms: 1. Addition and multiplication are commutative and associative and satisfy the Distributive law. 2. 0 is the additive identity and 1 is the multiplicative identity. 3. The ordering is a discrete linear order, with a first element and no last element 4. Addition and multiplication respect order. 5. Induction for all first order formulas. , , , , , , = ,
Models of Peano Arithmetic Every mathematical structure that satisfies the axioms of PA is a model of PA.
Models of Peano Arithmetic Every mathematical structure that satisfies the axioms of PA is a model of PA. The set of natural numbers, N, is a model of PA. (In particular, Th(N) extends PA)
Models of Peano Arithmetic Every mathematical structure that satisfies the axioms of PA is a model of PA. The set of natural numbers, N, is a model of PA. (In particular, Th(N) extends PA) Are there other structures (not isomorphic to N) which satisfy the axioms of PA?
Models of Peano Arithmetic Every mathematical structure that satisfies the axioms of PA is a model of PA. The set of natural numbers, N, is a model of PA. (In particular, Th(N) extends PA) Are there other structures (not isomorphic to N) which satisfy the axioms of PA? Answer: Yes. Infinitely many!
Compactness Theorem A very famous theorem in the field of model theory is the compactness theorem which says: If a theory is finitely realizable, then it is realizable, that is, it has a model.
Non-Standard Models of Arithmetic Consider the following theory: PA U {c > n: n is a natural number}
Non-Standard Models of Arithmetic Consider the following theory: PA U {c > n: n is a natural number} This theory is finitely realizable by N.
Non-Standard Models of Arithmetic Consider the following theory: PA U {c > n: n is a natural number} This theory is finitely realizable by N. Therefore, by the compactness theorem, it is realizable.
Non-Standard Models of Arithmetic Consider the following theory: PA U {c > n: n is a natural number} This theory is finitely realizable by N. Therefore, by the compactness theorem, it is realizable. But every structure realizing it, must be a model of PA.
Non-Standard Models of Arithmetic Consider the following theory: PA U {c > n: n is a natural number} This theory is finitely realizable by N. Therefore, by the compactness theorem, it is realizable. But every structure realizing it, must be a model of PA. On the other hand, any structure which realizes this, must have a number, c, which is greater than any natural number, hence this structure must have non-standard numbers.
Non-Standard Models of Arithmetic Consider the following theory: PA U {c > n: n is a natural number} This theory is finitely realizable by N. Therefore, by the compactness theorem, it is realizable. But every structure realizing it, must be a model of PA. On the other hand, any structure which realizes this, must have a number, c, which is greater than any natural number, hence this structure must have non-standard numbers. This shows that any theory extending PA has non-standard models, in particular, Th(N) (True Arithmetic).
Gdel Incompleteness Theorem The G del Incompleteness Theorem shows that any recursive theory in a finite language extending PA, has true sentences (statements) which cannot be proven in PA.
Gdel Incompleteness Theorem The G del Incompleteness Theorem shows that any recursive theory in a finite language extending PA, has true sentences (statements) which cannot be proven in PA. A famous result called the completeness theorem (also by G del) implies that if a theory is consistent (no contradictions), it has a model.
Gdel Incompleteness Theorem The G del Incompleteness Theorem shows that any recursive theory in a finite language extending PA, has true sentences (statements) which cannot be proven in PA. A famous result called the completeness theorem (also by G del) implies that if a theory is consistent (no contradictions), it has a model. But if we take a statement p which cannot be proven in PA, we get two consistent theories: PA U {p}, and PA U {~p}, both extending PA and by the completeness theorem, each has a model. So we get two models of PA which are not isomorphic, since they satisfy different theories with different statements.
Continuum Many Countable Models We can now construct a binary tree of countable length of formulas which imply continuum (2^ 0) many consistent theories.
Continuum Many Countable Models We can now construct a binary tree of countable length of formulas which imply continuum (2^ 0) many consistent theories. Every such theory has a countable model (Downward Skolem- Lowenheim Theorem)
Continuum Many Countable Models We can now construct a binary tree of countable length of formulas which imply continuum (2^ 0) many consistent theories. Every such theory has a countable model (Downward Skolem- Lowenheim Theorem) Therefore, each of the uncountably many theories then, has a countable non-standard model.
Continuum Many Countable Models We can now construct a binary tree of countable length of formulas which imply continuum (2^ 0) many consistent theories. Every such theory has a countable model (Downward Skolem- Lowenheim Theorem) Therefore, each of the uncountably many theories then, has a countable non-standard model. Two models which satisfy different theories, cannot be isomorphic.
Continuum many non-isomorphic models for each theory extending PA.
Continuum many non-isomorphic models for each theory extending PA. Let T be one of the continuum many theories extending PA.
Continuum many non-isomorphic models for each theory extending PA. Let T be one of the continuum many theories extending PA. For each subset S of N, Consider the following theory (with a constant c added to the language): T U {pn|c : n is in S} U {pn|c : n is not in S}
Continuum many non-isomorphic models for each theory extending PA. Let T be one of the continuum many theories extending PA. For each subset S of N, Consider the following theory (with a constant c added to the language): T U {pn|c : n is in S} U {pn|c : n is not in S} This theory is finitely realizable so by the compactness theorem it is realizable in some (countable) model of T.
Continuum many non-isomorphic models for each theory extending PA. Let T be one of the continuum many theories extending PA. For each subset S of N, Consider the following theory (with a constant c added to the language): T U {pn|c : n is in S} U {pn|c : n is not in S} This theory is finitely realizable so by the compactness theorem it is realizable in some (countable) model of T. Therefore every subset of N is coded in some model of T.
Continuum many non-isomorphic models for each theory extending PA. Let T be one of the continuum many theories extending PA. For each subset S of N, Consider the following theory (with a constant c added to the language): T U {pn|c : n is in S} U {pn|c : n is not in S} This theory is finitely realizable so by the compactness theorem it is realizable in some (countable) model of T. Therefore every subset of N is coded in some model of T. But any such countable model has only countably many elements so it can code on countably many subsets.
Continuum many non-isomorphic models for each theory extending PA. Let T be one of the continuum many theories extending PA. For each subset S of N, Consider the following theory (with a constant c added to the language): T U {pn|c : n is in S} U {pn|c : n is not in S} This theory is finitely realizable so by the compactness theorem it is realizable in some (countable) model of T. Therefore every subset of N is coded in some model of T. But any such countable model has only countably many elements so it can code on countably many subsets. Since every subset is coded in some model, there must be continuum many models.
Order type of countable models of PA Even though there are so many non-isomorphic countable models of PA, it turns out that all non standard countable models have the same order type, that it, if we only look at the one relation <, all these models are isomorphic to N+QZ (in some books N+ZQ).
Recursive Saturation Definition: A model is recursively saturated if it realizes every finitely realizable recursive type with a finite number of parameters.
Recursive Saturation Definition: A model is recursively saturated if it realizes every finitely realizable recursive type with a finite number of parameters. Theorem (Barwise and Schlipf (1976) and Ressayer (1977)): Every consistent theory in a finite language has a countable recursively saturated model.
Recursive Saturation Definition: A model is recursively saturated if it realizes every finitely realizable recursive type with a finite number of parameters. Theorem (Barwise and Schlipf (1976) and Ressayer (1977)): Every consistent theory in a finite language has a countable recursively saturated model. Theorem: Two countable recursively saturated models, M and N are isomorphic iff Th(M)=Th(N), SSy(M)=SSy(N).
