4
$\begingroup$

I have a question about compactness, non standard models of reals and illusory paradoxes.

Now, we know that because of the compactness theorem in FOL there are, for instance, non standard models of reals. In fact, if we call R the collection of all (and only) the true formulae in the standard model of real numbers, because of compactness there will be a model of R in which there are infinitely large numbers (ie. objects that do not respect the Archimedean property).

Proving that this holds true is extremely simple. Let us extend the signature of real numbers theory with a new constant, ∞. Let's create a new set of formulae and call it T, where T={n<∞|n∈N} and now consider the set of formulae R∪T. Every finite subset of R∪T has a model because the standard model obviously satisfies it (you just keep interpreting ∞ in a large enough real number to validate all the formulae in F). Hence, by the Compactness Theorem, R∪T has a model. This model will make true all the formulae in R, so it is a model of reals, but it is an alternative model of reals because it will make true all the formulae in T. So ∞ must be interpreted in an element of this new model which will be bigger (in the new, non standard, order relation) than any (non standard) natural number. ∞ will indeed be an infinite element that contradicts the Archimedean property for standard real numbers.

The problem is this. The "Archimedean property sentence", ie. the FOL formal sentence that in the standard model expresses the Archimedean property, being true in the standard model, is obviously one of the formulae in R, so it must also be true in the non-standard model.

There seems to be a contradiction between this sentence being true in the non-standard model, and the existence of a real number with the properties of ∞. I sort of understand that there really isn't a contradiction because, being a non standard model, there will be something in the interpretation of fundamental symbols that is different from the standard one in a way that dissolves the contradiction, but I am unable to point out exactly and with clarity why there isn't a contradiction. Can anyone help me? Thanks a lot.

New contributor
WaLuigi is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
3
  • $\begingroup$ I think the issue is that the "natural numbers" in your new model, which the first-order Archimedean property sentence is about, are different from the metatheoretic $\Bbb N$ you used to define $T$. $\endgroup$
    – Karl
    yesterday
  • 2
    $\begingroup$ Actually, what is the first-order sentence expressing the Archimedean property? How does it refer to natural numbers? $\endgroup$
    – Karl
    yesterday
  • $\begingroup$ Yes, there isn't one. $\endgroup$
    – WaLuigi
    yesterday

3 Answers 3

6
$\begingroup$

Not only that the Archimedean property is not a first-order property, if we add $\Bbb N$ as a predicate to the language, making it a first-order property (by saying $\forall x\exists n(x<n\land n\in\Bbb N)$, for example), then compactness will simply "extend" that predicate.

Compactness lets you create new models, or even extensions of your current model, but it brings in some wildness into the mix. In this case, $\Bbb N$ will be re-interpreted as a non-standard model of $\sf PA$. And indeed, in any non-Archimedean field we can consider such a copy of non-standard integers (note that if the language does not contain some additional predicates or function symbols, this copy might not be definable itself).

$\endgroup$
5
  • $\begingroup$ It's a predicate. It can be anything, as long as it satisfies whatever axioms you've put for it to satisfy. And if you require it to be unbounded, then the compactness theorem will also "increase" the content of that predicate. $\endgroup$
    – Asaf Karagila
    yesterday
  • $\begingroup$ I get it. I have to admit I am not at all used to non standard models, but your explanation is extremely good. Thank you. $\endgroup$
    – WaLuigi
    yesterday
  • 1
    $\begingroup$ In mathematics you don't understand things, you get used to them. As the von Neumann quote goes. $\endgroup$
    – Asaf Karagila
    yesterday
  • $\begingroup$ I was reasoning, and correct me if you think I'm wrong, that my compactness argument per se doesn't show that the property of being a natural number is not expressible in the basic signature of real numbers. I think at most it shows a disjunction: it shows that either it is not expressible on the basic signature, or that if it is then the predicate expressing the property of being a natural number has an extended interpretation in the non standard model (0,1,2 etc. will be in N but also something else). In order to show that it is not expressible I think you need something more. $\endgroup$
    – WaLuigi
    yesterday
  • $\begingroup$ The point is that I don't explicitly get a contradiction if I just suppose that the natural number property is definable in the basic signature. Because yes, if the property of being a natural number is definable in the signature (let's use N as a shorthand) then the formulae N(0), N(1), N(2) etc... will all be true in the non standard model. The formula ~∃x∀y(N(y)->y<x) will be true in the non standard model. And also the formulae 0<∞, 1<∞, 2<∞ etc... will also be true. But that is different than showing that ∃x∀y(N(y)->y<x) holds in the non standard model, so we didn't show a contradiction. $\endgroup$
    – WaLuigi
    yesterday
4
$\begingroup$

As your compacity argument shows, the property of being Archimedean is not expressible in first order in that language (and, hence, the set $\mathbb{N}$ of natural numbers is not a definable subset of $\mathbb{R}$).

$\endgroup$
2
  • $\begingroup$ Now I get it. You are right, the property of being Archimedean is not expressible in FOL. And yes, natural numbers are not a definable subset. $\endgroup$
    – WaLuigi
    yesterday
  • $\begingroup$ I was reasoning, and correct me if you think I'm wrong, that my compactness argument per se doesn't show that the property of being a natural number is not expressible in the basic signature of real numbers. I think at most it shows a disjunction: either it is not expressible on the basic signature, or if it is then the predicate expressing the property of being a natural number has an extended interpretation in the non standard model. In order to show that it is not expressible I think you need something more than just my argument. $\endgroup$
    – WaLuigi
    yesterday
2
$\begingroup$

The "true" Archimedean property cannot be expressed in first-order logic. This is because, in order for it to work, you need a sense for which "$n$ is a natural number" to hold. Yet there is no first-order way to define this predicate - this can be seen when you look at what Peano's axioms for the natural numbers look like, which contain the following statement:

Induction: Suppose $S$ is any set of natural numbers containing $0$ and which is closed under succession, i.e. if $n \in S$ then $n + 1 \in S$. Then every natural number is contained in $S$.

The problem here is in the "any set" part. First-order logic cannot deal with that. The same goes with first-order ZFC. It can't "really" quantify over sets, only internal objects we "think to be sets".

You can write this statement in second-order logic, and perhaps there are still other kinds of logics that might be able to make it. However, they come with a price: you lack an algorithmically decidable (and thus presumably, physically decidable as well) deduction system, i.e. there is no computer program (or perhaps, even physically realizable process) that, if you feed it a bit of reasoning in the logic, will reliably tell you if it's valid or contains a fallacy.

In first-order logic we must weaken "set" to "a predicate $\phi$ on the natural numbers", and adjoin one copy of the axiom for each such predicate - that is, a finite formula involving the variable $n$, arithmetic operators, and logical operators, e.g. $\phi(n) = (n \ge 50) \wedge (n \le 100)$ is the predicate defining the set of natural numbers from 50 to 100 inclusive. The trick is that there are only countably many such formulas, but there are uncountably many total possible subsets of any candidate for $\mathbb{N}$, and thus the induction postulate is unable to "audit" them all to make sure that they didn't miss some "weeds" in amongst the naturals - those "weeds", of course, being the non-standard numbers you talk about.

And when you use that $\mathbb{N}$ to interpret the Archimedean property, it is kind of like using a ruler with large inches. Yes, my house is 6 inches tall according to a certain ruler - the caveat is that the "inches" are actually 2 feet long.

$\endgroup$
8
  • $\begingroup$ To clarify, there are sound and decidable deductive systems for second order logic, right? Just none that are complete in the sense that they prove all statements that are true in every model. $\endgroup$
    – Karl
    yesterday
  • 1
    $\begingroup$ @Karl Yes, that's right, if you mean "semidecidable" instead of "decidable" (even first-order logic isn't decidable!). A silly example would be the trivial deduction relation that doesn't let you deduce anything (trivially sound and semidecidable!). If you want a non-silly example, look at proof systems for Henkin semantics. $\endgroup$ yesterday
  • $\begingroup$ @NoahSchweber Ah, thanks! I guess when talking about (semi)decidability of a "deductive system" we have to be careful about the distinction between the set of provable statements and the set of valid proofs, since (as I understand it) the former is semidecidable when the latter is decidable. I was thinking in terms of proof-checking since this post said "there is no computer program that, if you feed it a bit of reasoning in the logic, will reliably tell you if it's valid". $\endgroup$
    – Karl
    yesterday
  • $\begingroup$ The distinction between the two notions of completeness also seems to lead to confusion here when trying to explain what we lose when switching from FOL to SOL. Both systems are subject to Godel's incompleteness theorem, but FOL has another weaker completeness property that higher-order logics don't. I wonder whether this answer misconstrued this or if I'm just missing something. $\endgroup$
    – Karl
    yesterday
  • $\begingroup$ @Karl "when talking about (semi)decidability of a "deductive system" we have to be careful about the distinction between the set of provable statements and the set of valid proofs" Quite right - I was focusing on the former, since it has less "definitional baggage" (given an arbitrary logic $\mathcal{L}$ I don't have to do any more work to look at the complexity of its entailment relation, but I may have to work to get a notion of "proof-object"). Sorry! $\endgroup$ yesterday

Your Answer

WaLuigi is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.