2

Godels incompleteness theorem, which really should be called the undecidability theorem given that the paper of Godels which this theorem is taken from is named 'On formally undecidable propositions of the Principia Mathematica', essentially shows that there are statements in the formal language which cannot be shown to have a proof or a disproof.

Another way to say this is that its truth value cannot be established by the usual means. Are there 'unusual' means for giving it a truth-value, say by expanding the notion of turth from the simple binary of true/false to a multiply valued truth?

For example, in model-theoretic terms, a statement that is undecideable is one that is true in some models and not true in others. Suppose that there is some natural probability measure that we can put on the set of models, then can't we have a probable notion of truth?

5
  • Completeness and decidability should not be confused. I'm not sure about your assertion: "in model-theoretic terms, a statement that is undecideable is one that is true in some models and not true in others". But if that is the case then a conditional notion of truth would be better suited than a probabilistic notion of truth IMHO. Think of it as simplifiying an equation. Basically those statements are not true, false or probably any of them, but depend on others to be true or false. They are dependent, like dependent variables.
    – Trylks
    Aug 24, 2013 at 1:05
  • are you talking about decidability as in computation? Aug 24, 2013 at 9:53
  • is there other decidability?
    – Trylks
    Aug 24, 2013 at 17:57
  • 1
    yes, look here. Aug 24, 2013 at 18:14
  • Great, very interesting. Now I realize maybe dependent is not the best term, but I still see the system more similar to an equation or a set of constraints (dependencies) on some values. There variables will be dependent or independent based on whether there is some connection among them in the graph of dependencies.
    – Trylks
    Aug 24, 2013 at 19:26

2 Answers 2

3

I think you are conflating two different uses of the word "true".

First, in any formal system there can be sentences that are true in some models and not in others. It simply makes no sense to ask whether those sentences are true in some purely abstract sense. By analogy, the statement "The house is painted green" is true of some houses and not true of others. There's no reason to think we should be able to assign a single truth value to such a statement, and no reason to want to.

Second, it is sometimes (but not always) the case that we have a particular model in mind from the outset. So if we've all agreed in advance that the house we're talking about is the one located at 1600 Pennsylvania Avenue in Washington, DC, then it does make sense to ask about the truth value of a sentence like "The house is painted green", and there is no ambiguity about whether that sentence is true or false.

In particular, when we about arithmetic, we usually (but not always) have one particular model in mind, namely the standard model of the natural numbers (i.e. the counting numbers that you learned about in kindergarten). Therefore, statements in, say, Peano arithmetic, are unambiguously true or false (as long as we all realize that we're focused on that one model). That notion of truth coincides with Tarski's more formal definition. We determine whether such statements are true or not by studying the natural numbers. There is no single "usual" formal system in play here, so I don't know what you mean by the "usual means" for discovering which sentences are true. Sometimes we use Peano arithmetic. Sometimes we use induction up to epsilon-nought. Sometimes we use Grothendieck universes.

Therefore, in response to your questions: When we talk about arithmetic, there is no "usual means" for determining what's true and therefore no need to develop "unusual means". Moreover, it would certainly be way counterproductive to adopt as system of multiple truth values when every sentence we can state is already either unambiguously true or unambiguously false.

1

According to this answer by Michael Hardy on Math.SE, we have

Here's one small result I heard asserted once: Let's say you have a first-order language with finitely many relation symbols. If one regards all isomorphism classes of models of finite size n as equally probable, then each statement in this language has some probability of being true in models of size n. And then for each statement one can take a limit as n→∞. A mathematician I spoke to claimed to have published this result: in every instance the limit is either 0 or 1. I don't remember his name.

That is, in some sense, undecideable statements are probably true or false.

However, and more along the lines of what I was thinking of, in this paper by Christiano et al, they explicitly assign a natural probability measure over models as a replacement for the notion of truth, explicitly:

The language has a natural probability Prob, iff it has a measure Msr over all models M of the language such that for a sentence x, we have Prob(x)=Msr(all M: M|=x)

It has an axiomatic presentation as:

i. For any sentences x & y, we have: Prob(x)=P(x /\ y)+P(x /\ ~y)

ii. For a tautology x: Prob(x)=1

iii. For a contradiction x: Prob(x)=0

They end their paper by remarking:

However, our work shows that the obstructions presented by the liar's paradox can be overcome by tolerating an infinitesimal error, and that Tarski's result on the undefinability of truth is in some sense an artifact of the infinite precision demanded by reasoning about complete certainty.

1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .