n-Consistency

[Zuhair]

This question might sound strange but I think it is a legitimate
question. Can the n-consistency of a theory T be proved in a theory
that is weaker than T.

Define: n-Con(T) <> For all m. T |-n m > ~ ( T |-n ~m )

where "|-n" refers to "proves in no more than n characters"

The idea is clear, n consistency doesn't entail consistency, however
if n is too large then it does tell us that T is non conceivably
inconsistent, and to me this is enough.

My simple view is: the harder you get to prove an inconsistency with a
theory the more is the chances that there is a strong fragment of it
that is consistent.

If we can prove for example that no inconsistency is prove-able in Z
in less than 10 ^ 10 ^ 100 characters, then this is for practical
purposes quite enough to accept this theory as a milieu to work
mathematics within it.

Zuhair

[Daryl McCullough]

On Sunday, May 20, 2012 4:31:32 AM UTC-4, Zuhair wrote:

> If we can prove for example that no inconsistency is prove-able in Z
> in less than 10 ^ 10 ^ 100 characters, then this is for practical
> purposes quite enough to accept this theory as a milieu to work
> mathematics within it.

Prove in what theory?

If it is true, then it is provable in PA, but the shortest proof
might require 10^10^100 steps. A shorter proof would be available
in some more powerful theory.

[Zuhair]

On May 20, 8:57 pm, Daryl McCullough <stevendaryl3...@yahoo.com>
wrote:

> On Sunday, May 20, 2012 4:31:32 AM UTC-4, Zuhair wrote:
> > If we can prove for example that no inconsistency is prove-able in Z
> > in less than 10 ^ 10 ^ 100 characters, then this is for practical
> > purposes quite enough to accept this theory as a milieu to work
> > mathematics within it.
>
> Prove in what theory?

Anyone that is weaker than Z.

[Daryl McCullough]

On Sunday, May 20, 2012 2:18:16 PM UTC-4, Zuhair wrote:
> On May 20, 8:57 pm, Daryl McCullough <stevendaryl3...@yahoo.com>
> wrote:
> > On Sunday, May 20, 2012 4:31:32 AM UTC-4, Zuhair wrote:
> > > If we can prove for example that no inconsistency is prove-able in Z
> > > in less than 10 ^ 10 ^ 100 characters, then this is for practical
> > > purposes quite enough to accept this theory as a milieu to work
> > > mathematics within it.
> >
> > Prove in what theory?
>
> Anyone that is weaker than Z.

As I said, if it is true, then it is provable in PA,
but the proof is VERY long.

[Zuhair]

On May 21, 12:04 am, Daryl McCullough <stevendaryl3...@yahoo.com>

wrote:
> On Sunday, May 20, 2012 2:18:16 PM UTC-4, Zuhair wrote:
> > On May 20, 8:57 pm, Daryl McCullough <stevendaryl3...@yahoo.com>
> > wrote:
> > > On Sunday, May 20, 2012 4:31:32 AM UTC-4, Zuhair wrote:
> > > > If we can prove for example that no inconsistency is prove-able in Z
> > > > in less than 10 ^ 10 ^ 100 characters, then this is for practical
> > > > purposes quite enough to accept this theory as a milieu to work
> > > > mathematics within it.
>
> > > Prove in what theory?
>
> > Anyone that is weaker than Z.
>
> As I said, if it is true, then it is provable in PA,
> but the proof is VERY long.

what make you think that PA can do that?

By Godel's second incompleteness theorem we know that PA cannot prove
n-consistency of Z for *every* n. There must be some n value above
which the n-consistency of Z cannot be proved in PA, how can we
determine that n value?

Zuhair

[Daryl McCullough]

On Sunday, May 20, 2012 5:37:14 PM UTC-4, Zuhair wrote:

> By Godel's second incompleteness theorem we know that PA cannot prove
> n-consistency of Z for *every* n.

Yes, it can. Maybe I'm misunderstanding what you mean by
n-consistency, but if it means "There is no proof of
a contradiction of length n or less" then every such
statement is provable in PA, or refutable in PA.
If Z is consistent, then for every n, PA can prove
that Z is n-consistent.

To prove that a theory is n-consistent, you just
have to enumerate all possible proofs of length n
or less, and check to see if any of them is a proof
of a contradiction.

--
Daryl McCullough
Ithaca, NY

[Zuhair]

On May 21, 3:17 am, Daryl McCullough <stevendaryl3...@yahoo.com>
wrote:

But wouldn't that contradict the second of Godel's incompleteness
theorems.

To say that a theory T is consistent (in the ordinary sense) is
equivalent to saying that T is n-consistent for *every* n. Now if PA
can prove that Z is n-consistent for *every* n, then PA is proving
that Z is consistent. But PA is known to be strictly weaker than Z,
and Z is a theory in which basic arithmetic can be formulated, so
according to Godel's Con(Z) must not proved by a proof that can be
formulated within a weaker theory. Am I missing something?

Zuhair

[Chris Menzel]

On Mon, 21 May 2012 05:23:55 -0700 (PDT), Zuhair <zalj...@gmail.com>
said:

You are getting the scope of the quantifier wrong. Daryl's claim is
that, for each n, PA can prove "Z is n-consistent". He is not claiming
that PA can prove "for every n, Z is n-consistent".

[Daryl McCullough]

Zuhair wrote:

> Daryl McCullough <stevendaryl3...@yahoo.com> wrote:

> > To prove that a theory is n-consistent, you just
> > have to enumerate all possible proofs of length n
> > or less, and check to see if any of them is a proof
> > of a contradiction.
>

> But wouldn't that contradict the second of Godel's incompleteness
> theorems.

No.

> To say that a theory T is consistent (in the ordinary sense) is
> equivalent to saying that T is n-consistent for *every* n.

Yes, but there is a difference between

(1) For every n, PA can prove that T is n-consistent, and
(2) PA can prove that for every n, T is n-consistent.

It's a lot harder to prove a universal statement than it
is to prove each instance.

If Phi(x) is some formula of arithmetic with one free
variable, it can be the case that

PA proves Phi(0)
PA proves Phi(1)
PA proves Phi(2)
...

In general, for each numeral n,
PA proves Phi(n)
but

PA does not prove forall x, Phi(x)

> Now if PA can prove that Z is n-consistent for *every* n,
> then PA is proving that Z is consistent.

No, it's not. It's the difference between
(1) for each n, PA proves "Z is n-consistent"
(2) PA proves "forall n, Z is n-consistent"

(1) does not imply (2)

[Zuhair]

On May 21, 8:07 pm, Daryl McCullough <stevendaryl3...@yahoo.com>
wrote:

In which theory (1) is proved?

Zuhair

[Zuhair]

I mean what would be the weakest theory that prove (1). It must be
stronger than Z, wouldn't it.

Zuhair

[Daryl McCullough]

I didn't say it was proved in any theory. I'm saying
that the two claims, (1) and (2) are not logically
equivalent. It is possible for (1) to be true while
(2) is false.

[Zuhair]

On May 22, 12:26 am, Daryl McCullough <stevendaryl3...@yahoo.com>
wrote:

Yes I know what you said and it is clear. I asked a simple question:
if Z was consistent then which is the weakest theory that can prove
(1), my guess is that any such theory cannot be weaker than Z
according to Godel's arguments, but it is interesting to know which
consistency strength this theory has, can it be a theory incomparable
with Z.

Zuhair

[Daryl McCullough]

The claim that "forall n, PA proves Z is n-consistent" is
exactly equivalent to "Z is consistent". If you can prove
one, you can prove the other.

[Zuhair]

On May 22, 1:52 pm, Daryl McCullough <stevendaryl3...@yahoo.com>

Ok so it must be proved in a system that is not weaker than Z. fine

Ok let's suppose that Z is inconsistent, and this inconsistency first
occur when n=m. Now should that be true can PA prove the following
statement:

PA proves ~Z is m-consistent.

Zuhair

[Daryl McCullough]

On Tuesday, May 22, 2012 7:44:52 AM UTC-4, Zuhair wrote:

> Ok let's suppose that Z is inconsistent, and this inconsistency first
> occur when n=m. Now should that be true can PA prove the following
> statement:
>
> PA proves ~Z is m-consistent.

Yes, the claim "T is n-consistent" is decidable---if it is true,
it's provable, and if it's false, it's disprovable.

[Zuhair]

On May 22, 3:04 pm, Daryl McCullough <stevendaryl3...@yahoo.com>
wrote:

Ok, Thanks for the clarification. But yet back to my original subject.
Suppose I proved using PA that Z is 10^10^10^10-Consistent. Now why
should I care anymore whether Z is consistent or not? To me it is more
than sufficient to prove that fragment of Z in order to formulate some
of math in it. Even if say Z turns to be inconsistent, what would be
the importance of such inconsistency, it is not practical. Practically
I will always be working within a theory with some proof length that
is much much much shorter than 10^10^10^10 character size. We can
simply work with Quasi-models (presumed models) and go on. Of course
this fragment of Z is stronger than PA, it can actually prove Con(PA).
Why we need to give epidemiological significance to the exclusion of
some remote inconsistency that is far beyond our practical arena of
working with theories. Aren't we being absolutist in seeking such
notions?

Zuhair

[abo]

The problem is you are talking of "proving" Z is n-consistent rather
than "n-proving." The arguments that Daryl are giving shows that it
is possible to prove that Z is n-consistent, but the proof will be in
more than n characters (in fact, much more, since the fall-back proof
is just the brute force technique of listing all possible n-proofs in
Z and checking none ends with a contradiction). What's the point of m-
proving Z is n-consistent if m is much much bigger than n, even if the
system you do it in is much weaker than Z? If you're worried about
the feasibility of n, then the m-proof is even less feasible.

[Zuhair]

Well I though that we can proof it in less than n-characters using
some abbreviations and some rules that can bypass a lot of steps.

Zuhair

[abo]

> Zuhair- Hide quoted text -
>
> - Show quoted text -

As long as you count the number of characters on both the left- and
right-hand sides in any abbreviation as part of the total number of
characters in the proof, I think that this is not possible - or at
least it will be very hard to show that it is possible. (If you don't
count them, then obviously you can write down the proof in 1 character
- simply abbreviate the entire proof with one character.)

But leave that objection aside. Without abbrevitions you have a proof
m characters long that there are no proofs in Z having n characters or
less of a contradiction. If you allow abbreviations and special rules
to get the m-proof to below n characters, then why aren't you doing
the same for a proof in Z that leads to a contradiction of m
characters long, so that it has less than n characters and becomes
feasible?

[Zuhair]

Well that's the trick. You are not allowed to use all kinds of
abbreviations with the original theory although you are allowed to use
them in the proof of it.

I was also thinking of ways to decrease proof sizes like for example Z
is n-consistent might be equivalent to saying that T is m-consistent
where T is some specific theory that is much stronger than Z and m is
much much smaller than n. In this way all what I need to do is to make
a proof in PA that T is m-Consistent and this would indirectly entail
that Z is n-consistent, so you see here the proof in PA of n-
consistency of Z might be much much shorter than m itself. However the
problem is that the proof of equivalence of n-consistency of Z with m-
consistency of T might be too long also. Anyhow. The idea is there
might be possible ways of proving these consistencies that are shorter
than what we think.

Zuhair

[abo]

On May 23, 8:05 pm, Zuhair <zaljo...@gmail.com> wrote:
> Well that's the trick. You are not allowed to use all kinds of
> abbreviations with the original theory although you are allowed to use
> them in the proof of it.

You may think of it as a trick, but IMHO it loses for you the
epistemological interest that you are claiming. What would be the
interest of a theory which, while having no unabbreviated proof of a
contradiction in less than n characters, has a proof, with
abbreviations, of a contradiction in much less than n characters?

>
> I was also thinking of ways to decrease proof sizes like for example Z
> is n-consistent might be equivalent to saying that T is m-consistent
> where T is some specific theory that is much stronger than Z and m is
> much much smaller than n. In this way all what I need to do is to make
> a proof in PA that T is m-Consistent and this would indirectly entail
> that Z is n-consistent, so you see here the proof in PA of n-
> consistency of Z might be much much shorter than m itself. However the
> problem is that the proof of equivalence of n-consistency of Z with m-
> consistency of T might be too long also. Anyhow. The idea is there
> might be possible ways of proving these consistencies that are shorter
> than what we think.

This kind of speculation strikes me as to be on the order of, "There
might be a way using abbreviations to figure out if a set of Boolean
formulas is satisfiable in polynomial time."

[Zuhair]

On May 26, 8:54 am, abo <dkfjd...@yahoo.com> wrote:
> On May 23, 8:05 pm, Zuhair <zaljo...@gmail.com> wrote:
>
> > Well that's the trick. You are not allowed to use all kinds of
> > abbreviations with the original theory although you are allowed to use
> > them in the proof of it.
>
> You may think of it as a trick, but IMHO it loses for you the
> epistemological interest that you are claiming.  What would be the
> interest of a theory which, while having no unabbreviated proof of a
> contradiction in less than n characters, has a proof, with
> abbreviations, of a contradiction in much less than n characters?
>
>

ah, you are right.

>
> > I was also thinking of ways to decrease proof sizes like for example Z
> > is n-consistent might be equivalent to saying that T is m-consistent
> > where T is some specific theory that is much stronger than Z and m is
> > much much smaller than n. In this way all what I need to do is to make
> > a proof in PA that T is m-Consistent and this would indirectly entail
> > that Z is n-consistent, so you see here the proof in PA of n-
> > consistency of Z might be much much shorter than m itself. However the
> > problem is that the proof of equivalence of n-consistency of Z with m-
> > consistency of T might be too long also. Anyhow. The idea is there
> > might be possible ways of proving these consistencies that are shorter
> > than what we think.
>
> This kind of speculation strikes me as to be on the order of, "There
> might be a way using abbreviations to figure out if a set of Boolean
> formulas is satisfiable in polynomial time."

hmmm..........

[Aatu Koskensilta]

Zuhair <zalj...@gmail.com> writes:

> Yes I know what you said and it is clear. I asked a simple question:
> if Z was consistent then which is the weakest theory that can prove
> (1), my guess is that any such theory cannot be weaker than Z
> according to Godel's arguments, but it is interesting to know which
> consistency strength this theory has, can it be a theory incomparable
> with Z.

Any theory that proves the consistency of Z is of greater consistency
strength than Z. That PA proves "Z is n-consistent" for every n is,
given the consistency of PA, equivalent to "Z is consistent".

--
Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

[Aatu Koskensilta]

Zuhair <zalj...@gmail.com> writes:

> Suppose I proved using PA that Z is 10^10^10^10-Consistent.

How? We know that PA proves the 10^10^10^10-consistency of Z. But this
is because we know that Z is consistent that PA proves all true
statements of the form "T is n-consistent", not because we have actually
produced a formal derivation in PA. If someone has doubts about the
consistency of Z, how do you propose to prove to them using PA that Z is
10^10^10^10-consistent. You can't in fact prove this using PA in any
practical sense, after all.

> We can simply work with Quasi-models (presumed models) and go on.

What are these Quasi-models and how does one work with them? The
problem with a merely n-consistent theory is that we have no reason to
suppose that what it proves e.g. about the naturals is true. So why
should we care about what's provable in the theory? If the suggestion is
that instead of naturals we should work with quasi-naturals, I'm afraid
this is completely unrealistic. Number theorists care about natural
numbers. They don't care about peculiar and technical concoctions
dreamed up by logicians and philosophers in their foundational
imaginings.

--
Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"

[Aatu Koskensilta]

Daryl McCullough <stevend...@yahoo.com> writes:

> If it is true, then it is provable in PA, but the shortest proof
> might require 10^10^100 steps. A shorter proof would be available
> in some more powerful theory.

I think Andrew already posted about this, but let's spell it
out. What's at issue is that n-consistency comes with n-Gödel.

Let's say that a proof is short if it has fewer than, say, n/100
characters. The n-Gödel sentence G for Z is:

This sentence has no short proof in Z.

Now, it's easy to see that G has no short proof in Z, provided Z is
n-consistent. For suppose there were. Then we could take a short proof
of G and turn it into a proof of "G has a short proof in Z". The proof
certainly would not require 100 times more characters than were used in
the short proof of G, so both G and not-G would be provable in Z with
fewer than n characters, i.e. Z would be n-inconsistent. This short
argument is of course formalizable in Z itself, so n-consistency of Z
can't be provable in Z by a short proof.

Suppose now PA proves the n-consistency of Z with a short
proof. Again, we can transform this proof into a proof in Z with fewer
than n characters of "PA proves the n-consistency of Z, and so, since PA
is sound, Z is n-consistent". But then Z is n-inconsistent, by our
previous observation. This also holds for extensions of PA by means of
abbreviations and other such devices for shortening proofs, as long as
their correctness can be proved in Z.

[Zuhair]

On May 29, 3:15 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> Zuhair <zaljo...@gmail.com> writes:
> > Suppose I proved using PA that Z is 10^10^10^10-Consistent.
>
>   How? We know that PA proves the 10^10^10^10-consistency of Z. But this
> is because we know that Z is consistent that PA proves all true
> statements of the form "T is n-consistent", not because we have actually
> produced a formal derivation in PA. If someone has doubts about the
> consistency of Z, how do you propose to prove to them using PA that Z is
> 10^10^10^10-consistent. You can't in fact prove this using PA in any
> practical sense, after all.
>

I think theoretically speaking if Z was 10^10^10^10-consistent then
there must be a proof of this in PA however the proof is too long and
this would be true whether Z is consistent (in the usual sense) or
not. But as you said because this proof is too long then practically
speaking it is not feasible so this is like saying it has no proof
practically.

[Zuhair]

On May 29, 3:15 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> The problem with a merely n-consistent theory is that we have no reason to
> suppose that what it proves e.g. about the naturals is true. So why
> should we care about what's provable in the theory? If the suggestion is
> that instead of naturals we should work with quasi-naturals, I'm afraid
> this is completely unrealistic. Number theorists care about natural
> numbers. They don't care about peculiar and technical concoctions
> dreamed up by logicians and philosophers in their foundational
> imaginings.
>
> --

> Aatu Koskensilta (aatu.koskensi...@uta.fi)
>

Do you think the "natural numbers" in the heads of number theorists is
in any practical sense something much "real" than the quasi-naturals?

Suppose that we had a kind of imaginary super-machine that can check
all proofs of length 10^10^10^10 in Z, and suppose that this check
revealed no contradiction in the set of all statements provable by up
to such length proofs in Z. and also suppose for the sake of argument
that this is the most that any super-machine can do, i.e. no super-
machine can check for example 10^10^10^10 +1-consistency of Z. So in
this imaginary world we have a limit on provability size in Z, and
that limit was 10^10^10^10. Now suppose all of that has been done and
it was verified that Z is 10^10^10^10 consistent. Now we have a
fragment of Z that we can simply define as all statements provable in
Z by no more than 10^10^10^10 characters length proofs, call this
fragment as 10^10^10^10-Z, now naturals are definable in this fragment
as finite Von Neumann ordinals for example, and this fragment do have
statements about those natural numbers. Call those naturals as you
said "quasi-naturals". Now we know that we don't have any
contradiction in statements about the quasi-naturals up to 10^10^10^10
length provability, so practically speaking this is much similar to
consistency (although theoretically not near it at all). Now why do
you think that "natural numbers" number theorists was constructing and
contemplating in their heads is in any practical sense something more
real than those "quasi-naturals". That was actually what I was asking
about in the head post.

Zuhair

[Aatu Koskensilta]

Zuhair <zalj...@gmail.com> writes:

> Do you think the "natural numbers" in the heads of number theorists is
> in any practical sense something much "real" than the quasi-naturals?

What's in people's heads is irrelevant. Say you're a number theorist
working on Goldbach's conjecture and one day learn that it is provable
in an n-consistent theory. Naturally you will ask what this tells us
about the problem whether all even naturals greater than two can be
expressed as the sum of two primes. And the answer is that it doesn't
really tell us much anything. That it follows that Goldbach's conjecture
is true of some quasi-naturals is of no apparent interest to a number
theorist, unless and until some mathematical connection is established
between naturals and quasi-naturals.

> Now why do you think that "natural numbers" number theorists was
> constructing and contemplating in their heads is in any practical
> sense something more real than those "quasi-naturals".

Reality is not at issue, and we can safely put people's heads and
contemplations aside. What we need is a clear explanation of how
n-consistency, quasi-models, and so on, relate to our actual
mathematical experience. We need in particular an elucidation or
definition of the concept of quasi-model.