10.2Exhibit 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.5Say 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:
Minimum elt — note always and hence always.
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.
because it forms a discrete ordered semiring
because which is not true in ; as a counter-example we have .
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:
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.
Take . Test if the -sentence holds in .
Take . Iterate over values until one is found for which the -sentence holds in .