Prev: 3SAT - CNF to CNF Conversion
Next: Program automatically Solves Sudoku
From: cplxphil on 4 Apr 2010 13:29
On Apr 4, 1:25 pm, cplxphil <cplxp...(a)gmail.com> wrote:
> On Apr 4, 8:31 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote:
>
>
>
>
>
> > cplxphil says...
>
> > >Consider the following sentence :
>
> > >S = "S cannot be proven true in PA, and the sentence '(The axioms of
> > >PA are consistent) --> S' cannot be proven true."
>
> > If Pr(A) means A is provable, and Con(PA) means PA is consistent,
> > and ~X means the negation of X, then you are saying that
>
> > S <-> ~Pr(S) & ~Pr(Con(PA) -> S)
>
> > >Assume that PA is consistent.  Then, is S true or false?  Assume, for
> > >the sake of contradiction, that it is false.  Then we have, "S can be
> > >proven true in PA, OR '(The axioms of PA are consistent) --> S can be
> > >proven true' can be proven true."
> > >The first part of the OR clause is false, because S cannot be
> > >proven true in PA if S is false and PA is consistent.
> > >The second part is also false, because if S were true,
> > >then by our assumption that PA is consistent, we would have that PA is
> > >consistent, and thus that S can be proven true.
>
> > Okay, we have:
>
> > ~S <-> Pr(S) or Pr(Con(PA) -> S)
>
> > So if S is false, we have:
>
> > Pr(S) or Pr(Con(PA) -> S)
>
> > Now, you say that if PA is consistent and S is false,
> > then it is not possible for S to be provable. But that doesn't
> > follow. A consistent theory can prove false statements.
>
> > You need something stronger than Con(PA) to be able
> > to conclude
>
> > ~S -> ~Pr(S)
>
> > You need soundness: PA is sound if it doesn't prove any false statements.
> > It follows from your argument that:
>
> > If PA is sound, then S is true.
>
> > But it doesn't follow that
>
> > If PA is consistent, then S is true.
>
> > You could try redoing your argument with soundness instead of consistency,
> > but unfortunately, there is no single statement in PA saying "PA is sound".
>
> > --
> > Daryl McCullough
> > Ithaca, NY
>
> Ah...OK, that makes sense.  Thanks to both of you (Tim Little and
> Daryl McCullough) for pointing this out.  I've been confused by this
> point before, I think; I've always (inaccurately) equated consistency
> with soundness.
>
> I was, actually, wondering why the universe didn't promptly end after
> I came up with my "proof" that the axioms of PA are inconsistent. :)
>
> Are there any axiom systems that are powerful enough to express the
> notion of their own soundness?  If so, would it not follow that all
> such axiom systems are inherently inconsistent?
>
> Thanks again.
>
> -Phil


One other thing though...what if I constructed a sentence like
this?...

S = "~Provable('S') and ~Provable('For all sentences T, (T<--
>Provable(T))-->S')"

Why doesn't that express soundness?

-Phil
From: glird on 4 Apr 2010 16:38
On Apr 3, 9:04 pm, cplxphil <cplxp...(a)gmail.com> wrote:
>
> As usual, I've probably made a mistake; but I don't know what it is.
> If someone could point it out that would be greatly appreciated.

The logic of present physics is based on two sentences:
1. If A is true, so is B.
2. B says "A is false".

regards
glird
From: tchow on 4 Apr 2010 17:27
In article <5b1b7a29-e4c9-43bb-aad5-17052104aacb(a)x3g2000yqd.googlegroups.com>,
cplxphil <cplxphil(a)gmail.com> wrote:
>Are there any axiom systems that are powerful enough to express the
>notion of their own soundness? If so, would it not follow that all
>such axiom systems are inherently inconsistent?

http://en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: tchow on 4 Apr 2010 17:30
In article <23946bf8-1be3-4aa1-9947-7e36b3cc9ddb(a)r27g2000yqn.googlegroups.com>,
cplxphil <cplxphil(a)gmail.com> wrote:
>S = "~Provable('S') and ~Provable('For all sentences T, (T<--
>>Provable(T))-->S')"
>
>Why doesn't that express soundness?

I'm not even sure what you're trying to do here. You can talk about
provability until you're blue in the face but it's not going to express
the concept of truth.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Nam Nguyen on 4 Apr 2010 17:51
tchow(a)lsa.umich.edu wrote:
> In article <23946bf8-1be3-4aa1-9947-7e36b3cc9ddb(a)r27g2000yqn.googlegroups.com>,
> cplxphil <cplxphil(a)gmail.com> wrote:
>> S = "~Provable('S') and ~Provable('For all sentences T, (T<--
>>> Provable(T))-->S')"
>> Why doesn't that express soundness?
>
> I'm not even sure what you're trying to do here. You can talk about
> provability until you're blue in the face but it's not going to express
> the concept of truth.

I think that's a bit too strong a sentiment. We certainly can define
a formula being true in a formal system if it's provable there and
the system is syntactically consistent. Whether or not we know
the system be syntactically consistent is a different matter, but
we can express the concept of truth using provability. Iow, FOL "truth"
is a dispensable concept.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: 3SAT - CNF to CNF Conversion
Next: Program automatically Solves Sudoku