Re: Inside or Outside ?
- From: Nam Nguyen <namducnguyen@xxxxxxx>
- Date: Wed, 19 Jul 2006 02:26:48 GMT
bargiax wrote:
We talk about a theory for arithmetic S. Suppose that we are in the standard model, with the natural numbers (0 included) as semantic structure.
A numerical relation R(x_1,...,x_n) is said to be expressible in S iff there exists a wff A(x_1,...,x_n) of S with n free variables such that for every natural number k_1,...,k_n:
1) if R(k_1,...,k_n) holds, then |- A(#k_1,...,#k_n) in S;
2) if R(k_1,...,k_n) does not hold, then |- ~A(#k_1,...,#k_n) in S.
("#a" means the "numeral of a".)
I have noticed that, even tough the theorems should be in S, the proofs appearing on the right of the statements above depends a lot on the structure...
In a few words, I don't understand whether (for example) A(#k_1,...,#k_n) is really provable *inside* of S or it is provable in S due to some external conditions.
Example: Mendelson's book says that the equality relation is expressed by the formula x_1=x_2 in S. Indeed, if k_1=k_2 in N, then one can prove (in S) that #k_1=#k_2 (and that is the clause 1), it is ok for me).
But if k1<>k2 then the book says that there is a proof in S of #k1<>#k2. Do you believe it or not, but the statement that allows to affirm that uses concepts that are *outside* of S (namely, some inequalities in N).
So, the proofs of A (or ~A) are -technically- really in S?
Thank you
It's entirely a coincidence! But in pursuing a certain (possible)
resolution to GC (Goldbach Conjecture), I've tumbled into a similar
(if not essentially the same) situation. I once asked in this forum
how the proof of "2 is a prime" could be done. In other words, how
to prove P(SS0) in PA, where P(x) is simply "x is a prime". Similarly
to what you might have alluded to, I didn't see any "obvious"
provability path of P(SS0) (from the axioms), despite the fact that
we "know" it's a theorem.
The long and the short of it is that I think the "outside|external"
factor (you've alluded to above) for the proof of P(SS0) is one's
*knowledge* of what *a particular prime* is (e.g., 2 in this case).
In such a proof, the dependency on axioms (and rules of inference)
is still there, but the knowledge of *a particular constant* is now
also an important element of the proof: and this is something FOL
framework almost never mentions at length (to my knowledge anyway)!
Somewhere along the same breath of "investigation" into GC's possible
resolution, I'd like to say that's "impossible" to prove the
(un)decidability of GC in PA, because of some kind of GC's self-reference
in the meta level. Let me explain that self reference a little bit. If:
1) by 1-theorem we mean any axiom (of PA);
2) by 2-theorem we mean any theorem whose shortest proof
involves only axioms and whose proof length is 2 (i.e.
the proof of a 2-theorem t is from axiom(s) to t itself.
For instance let A be an axiom, and t = (A \/ ~A) then
t is a 2-theorem;
3.a) by "primeval"-theorem we mean any elementary formula of the
form P(c), where c is a constant, and P is a predicate (prime
predicate only?);
3.b) by a "prime" theorem, we mean a theorem that is a 2-theorem,
or a primeval-theorem. (A 2-theorem would also be called an
even-prime-theorem, while all other prime ones are "odd", to
resemble the arithmetic primes!);
4) given two theorems t1 and t2, we say t2 is "provable" by t1, if
t1 is one of t2's hypothesis.
Now then an even prime theorem is provable only by 1-formula(e) and
itself. I'd like to be able to similarly say that in general a
prime-theorem is provable only by 1-formula(e) and itself, but I
don't know for sure how the odd-prime theorems behave in this respect.
(Any help here is appreciated).
My ultimate motivation is to attempt to show that there is an 1-1
mapping, or an equivalence between 1-order formula GC and the
*infinite* composition of the prime-theorems, in the meta level.
Hence it's impossible to *know* the answer for GC's (un)decidability).
I know that's really nothing concrete or formal; it's just an intuition
I've had and you post seems to rekindle the thinking. Thanks in advance
for any constructive comments on this.
--
-----------------------------------------------------
What we call 'I' is just a swinging door which moves
when we inhale and exhale.
Shunryu Suzuki
----------------------------------------------------
.
- Follow-Ups:
- Re: Inside or Outside ?
- From: Rupert
- Re: Inside or Outside ?
- References:
- Inside or Outside ?
- From: bargiax
- Inside or Outside ?
- Prev by Date: Re: FOL & completeness
- Next by Date: Re: Inside or Outside ?
- Previous by thread: Re: Inside or Outside ?
- Next by thread: Re: Inside or Outside ?
- Index(es):
Relevant Pages
|
