Re: Goldbach Conjecture & the Foundation of First Order Logic.



Barb Knox wrote:

In article <t81Sg.40226$R63.29472@pd7urf1no>,
Nam Nguyen <namducnguyen@xxxxxxx> wrote:

However *counterintuitive* to our knowledge of FOL reasoning,
I think that:

1) If GC is *genuinely* true, it will be impossible to (informally and
arithmetically) know that. Equivalently, it will be impossible
to know a proof of GC in "PA".

Why do you think that? The converse of it is certainly true, but that doesn't help any.

I think you mean if GC is undecidable in PA then it's (arithmetically)
true, which is of course true. But that's not what I meant. (Note that
I have PA in quotes!). It'd take much longer than what I could
write at this moment, so I'd defer a lot of it in later post and
only give an overall sketch.

Basically, given that for any given L(N) we'd have *countably
infinite* isomorphic languages LL(N)'s. But since a truth is
nothing more than an interpretation - a mapping between formulae
to n-aries in a structure - a truth is a function of the language
chosen. Any known truth is known iff a specific language L(N) is
known (out of infinite numbers of them). Ditto for any theorem
of any arithmetic theory. But the problem in this case is that
for any given arithmetic model (of any domain) we could infer
the existence of *uncountably* other models (all are in the very same
domain). The imbalance between the "lesser" countable numbers
of languages and the "greater" uncountably numbers of models,
in the same domain, means that when we talk about a theorem of
"PA", we actually talk about infinite number of isomorphic
formulae, each of which is a theorem in the perspective isomorphic
theory. In other words, in this case a formula is actually a
*variable-formula* (called an "omega" formula) ranging over the entire
countably infinite collection of languages LL(N)'s. If an omega formula
becomes provable in each of the isomorphic theories, then it becomes
an omega theorem. On the other hand, if an (omega) formula is not
omega-provable, we might not know which specific isomorphic theory
the formula would be provable. I have strong reason to believe that
if ~GC is not omega provable, then GC is omega-unprovable: it's
impossible to know which isomorphic "PA" theory it would be provable.
My 1) above basically reflects these notions.

Again, I'll have more details in a later post.


2) If GC is *genuinely* false, it's still possible that it's impossible
to prove that in PA.

No. Iff it is false, there is at least one particular n such that ~GC for such n. Simple calculation (in PA) can verify it. The hard part of course is finding such an n.

I certainly didn't claim that there exists no proof for ~GC, in this
case. What I claim is it's still possible that it's impossible for
us - human beings - to know the spelling of such proof, symbol by
symbol. The "hard part ... is finding such an n" is the key: it's
a real possibility that the smallest counter example of ~GC is so
big that a trillion universes couldn't adequately store a trillionth
of its decimal expansion. And in such case, we couldn't prove it
(i.e. write down the proof), despite that there *exists* a proof.

And I'm not kidding. We know any n, different than 0 or 1, can be
decomposed into a product of primes, some of which might appear k times
where k > 1. So then k could be decomposed into a product of primes,
some of which... But this whole recursive process is finite, and so
for any original n, there correspond a finite number of primes related
to n's prime decomposition. Let mk(n) df= the maximal prime amongst
these primes of n. (Let's name mk(n) the "minimum-knowledge" function
of n). It's possible then mk(n), where n is the smallest counter example
of ~GC, is way too big as mentioned above.

It might sound like a philosophical argument I've put forward, but
from a technicality point I'm not. A proof is by definition a finite
sequence of finite formulae. And the sole reason why lengths of formulae
and proofs are not of infinite cardinality is because our ability
to know them - to spell them out - is of finite cardinalities. (In other
words, because a finite cardinality < an infinite one). But herein lies
a problem: the inequality also works amongst the finite cardinalities
too! I mean a FOL proof of a finite effective length could be greater
than out finite ability to spell out the formulae or the sequence of
formulae. (By "effective length" we mean the greater between the
number of formulae in the proof and the longest formula). Note that
if p is a prime, mk(p) = p, and that there are infinite number of
primes. In other works, the minimum knowledge required to know the
primes would be ever increasing. And this observation would lead
to the following principle (the Uncertainty Principle of FOL):

(1) In any system strong enough to express arithmetic, there will
be theorem we can not prove, in the sense we can't not exactly
spell out the proof symbol by symbol.

Again, I know that doesn't sound right. But it just doesn't _sound_
so.

--
-----------------------------------------------------

What we call 'I' is just a swinging door which moves
when we inhale and exhale.
Shunryu Suzuki
----------------------------------------------------

.

Relevant Pages
Loading