2

As far as I understand, we define truth in first order theories like predicate calculus or PA by working in some stronger first order theory like set theory. Is it true? Are there other attempts in defining truth in first order theories without considering stronger first order theories?

I would appreciate your help!

Daniels Krimans
  • 1,473
  • 4
    What does "truth in a theory" mean? Saying that a statement is true only makes sense with respect to a model. We can talk about provability with respect to a theory, but then there's no need for set theory at all - this is directly arithmetizable (per Godel). – Noah Schweber Dec 02 '18 at 20:56
  • @NoahSchweber That is a very good comment, thank you. I was not careful enough here. I think what I meant is that consider, for example, PA. Then as a model for its axioms we can use something from set theory and then define truth to be something that we can conclude about natural numbers from set theoretic axioms. Similarly for other first order theories we can take some model from set theory. I feel that truth then is basically relying on axioms of set theory. But what if I don't believe in them? Is there any way around this? I hope I made myself clearer, sorry. – Daniels Krimans Dec 02 '18 at 21:01
  • 1
    Broadly speaking, semantics is about interpreting formulas into mathematical objects. Traditionally, for (classical) FOL, those mathematical objects have been (sub)sets. This is not required. You can use any collection of mathematical objects that serves the need. This is the basis for, e.g., categorical semantics where we interpret logics in arbitrary categories supporting the necessary structure. $\mathbf{Set}$ is but one possible category one could use. You'll still need some meta-theory to be able to talk about these mathematical objects. It need not be set theory or a first-order theory. – Derek Elkins left SE Dec 02 '18 at 21:07
  • @DerekElkins Do you mean something like using Elementary Theory of the Category of Sets? – Daniels Krimans Dec 02 '18 at 21:12
  • 1
    @DanielsKrimans Not really, as that's just a different set theory that is also formulated as a first-order theory. For the categorical semantics, I mean you can interpret formulas into things like topological spaces or sheaves or generally any first-order hyperdoctrine. For the meta-theory, it's typically a set theory when talking about categorical semantics, but it could be a type theory instead, say. (Generally, not just for categorical semantics). It's still generally going to be "stronger" than the theory you're interpreting. – Derek Elkins left SE Dec 02 '18 at 21:45

2 Answers2

6

Let's stick to the concrete example of PA. Tarski's undefinability theorem shows that truth for sentences of PA cannot be defined in PA.

We can look at even simpler sentences, though. For example, if we just look at the truth of $\Sigma^0_1$ sentences, we are essentially asking about whether various Turing machines halt. By the unsolvability of the halting problem, this means that there will not be any computable way to determine which $\Sigma^0_1$ sentences of PA are true. (The overall Turing degree of the set of true sentences of PA is $0^\omega$, which is very far from being computable.)

So, in whatever semantics we want to use for PA, we will have to go beyond means definable in PA, and the resulting semantics will certainly not be computable. We do not need to use set theory - we could use second-order arithmetic, or another type theory, or topos theory, to define a semantics for PA. All of these will require something that goes beyond PA itself.

Carl Mummert
  • 81,604
  • Just to toe the line with Noah’s first comment under OP, by “PA” you mean the first order language of arithmetic. There are no axioms involved here. (I know you know this... more for the benefit of OP.) – spaceisdarkgreen Dec 03 '18 at 19:29
  • Great answer, thank you! – Daniels Krimans Dec 03 '18 at 20:56
  • @spaceisdarkgreen: for truth, exactly. But also Tarski's theorem shows that truth in that language is not definable even using the axioms of PA. – Carl Mummert Dec 04 '18 at 01:04
  • @Carl Yes I suppose I had “definable in arithmetic” in mind, which come to think of it has quite a few more “axioms involved” than PA. – spaceisdarkgreen Dec 04 '18 at 03:27
5

Conventionally, we interpret a first-order theory by assigning extensions (sets of objects) to its predicates, and fixing a domain (another set of objects) for its quantifiers to run over. And then we appeal to some modest set-theoretic ideas to do the metatheory for our first-order theories.

But it is a nice question whether we need to invoke sets here. We might wonder: why not directly assign a (monadic) predicate the objects, plural, which satisfy the predicate, rather than something over and above those objects, namely the set of them? Why not treat quantifiers as ranging over some objects, plural, rather than something over and above them, namely the set of them?

Well, to handle a metatheory which deals in objects, plural, we'll need a plural logic. See for example Plural Logic by Alex Oliver and Timothy Smiley: in Ch. 11 they give an account of the semantics of standard first-order logic using a plural metatheory with no commitment to sets. So this can be done.

It is, however, an interesting question what exactly is gained by the exercise. OK we'll avoid ontological commitment to sets. But we'll still find ourselves tangling with some strongly infinitary ideas. For Oliver and Smiley have to trade in arbitrary sets (whose membership we can't specify) for an unreduced notion of arbitrary properties and arbitrary functions (whose graphs we can't specify); and someone who is worried about the notion of an arbitrary infinite set will argue that we should be equally worried about these substitutes. But that's a debate for another day.

Peter Smith
  • 54,743