Homework #5
10.2
Exhibit non-isomorphic countable models of .
We demonstrate an injective mapping from subsets to countable models . Since , this exhibits distinct countable models for .
Take some . For let denote the prime number. Let be a new constant symbol in the language of , and consider the theory
asserting that is divisible exactly by those primes whose indices in are elements of .
This theory is satisfiable by compactness. Take some finite subet of the theory. We can characterize this subset as follows: consists of some subset of plus, for some sets , the requirement of existence of a which is divisible by primes in and not divisible by primes in . We can satisfy by extending with the assigment
By construction is divisible by all of . Additionally we need that it is divisible by none of ; this follows from the fact that we construct as a product of primes (and hence it takes on no extra prime factors).
Since each finite subset of the theory is satisfiable, then by compactness the theory as a whole is satisfiable. Note also that since we satisfy finite subtheories with countable models, then the big model produced by compactness is also countable (probably true).
Hence we have a mapping from subsets to countable models . What remains to be shown is that this mapping is injective. Take distinct, and let be their respectively-induced models. Since and are distinct, then one has at least one element that the other doesn’t; WLOG assume . Then we know that
by construction of . Hence and thus .
10.5
Say is a countable nonstandard model of PA. Define over as
and define over as
noting that this is well-defined and gives a linear ordering.
Our goal is to show that over is dense with a minimum element but no maximum.
Frankly I don’t see why it is dense, but (with a hint from Chase) I was able to show the other two:
No maximum — Since is nonstandard, it has at least on infinite element . Then I claim for any class that . Take an .
First note that because otherwise we’d have that they differ by some finite amount meaning that is in fact not infinite.
Now take some . Then we know either or for some finite . In the first case we have
and in the second case we have
Hence all elements of are lesser than , and so .
Density — seems untrue to me. Chase pointed out that we can think of nonstandard elements as polynomials over the chosen infinity . Then becomes equivalence classes of polynomials differing by only a finite amount. But such classes just aren’t dense, as e.g. and have nothing between them.
10.6
because it forms a discrete ordered semiring
because which is not true in ; as a counter-example we have .
11.13
(⇒)
Take representable. Note that the indicator function
is then representable in by
Thus is computable by thm 11.12, meaning that is.
(⇐)
Take computable. Then is computable and hence representable in by thm 11.12; calling its representation we get a representation for as:
13.4
-
14.4
(⇒)
Say is computable, and take some . Since is quantifier-free and is computable we can just, like, compute the truth value.
(⇐)
Say is computable. We aim to compute , meaning we need to compute:
We do so as follows.
Take a constant symbol. Since is computable then we can iterate over elements of . Do so until we find an element for which the -sentence
holds. Note that , meaning that testing its truth is indeed computable. Once such a is found, emit it as the result of the algorithm.
Since each constant symbol must have an interpretation, we know that this algorithm will always halt.
14.5
-