The set expressed by a wff is recursively enumerable iff the set
expressed is the set represented.
1. Is the above assertion true or false of Peano Arithmetic?
2. What simpler conditions (especially frequently used properties of
axiomatic systems e.g. sound, consistent) are necessary or sufficient?
3. Who has discussed or proven it?
Please & Thank You.
C-B
(A wff expresses (represents) the set of numbers that when substituted
for its free variables forms a true (provable) sentence.)
Charlie-Boo wrote:
> The set expressed by a wff is recursively enumerable iff the set
> expressed is the set represented.
> 1. Is the above assertion true or false of Peano Arithmetic?
It’s false. Let G be the Goedel sentence for Peano Arithmetic. Consider
the well-formed formula "G & x=x". The set expressed by this formula is
N, which is recursively enumerable. The set represented is the empty
set.
- Hide quoted text — Show quoted text -
> 2. What simpler conditions (especially frequently used properties of
> axiomatic systems e.g. sound, consistent) are necessary or sufficient?
> 3. Who has discussed or proven it?
> Please & Thank You.
> C-B
> (A wff expresses (represents) the set of numbers that when substituted
> for its free variables forms a true (provable) sentence.)
Rupert wrote:
> Charlie-Boo wrote:
> > The set expressed by a wff is recursively enumerable iff the set
> > expressed is the set represented.
> > 1. Is the above assertion true or false of Peano Arithmetic?
> It’s false. Let G be the Goedel sentence for Peano Arithmetic. Consider
> the well-formed formula "G & x=x". The set expressed by this formula is
> N, which is recursively enumerable. The set represented is the empty
> set.
Thanks much. The wffs I had in mind aren’t so weird as your clever
G&x=x. I wonder if there is an additional simple condition on the wff
that ensures the above i.e. "If a wff passes such-and-such a
condition, then the set expressed is r.e. iff the set expressed is the
set represented."? (Maybe I need to look at a few of each kind –
those that work and those that don’t.) Or just, "When do the
expressed and represented sets coincide??" Yeah, that would do it.
Bell the cat!
C-B
- Hide quoted text — Show quoted text -
> > 2. What simpler conditions (especially frequently used properties of
> > axiomatic systems e.g. sound, consistent) are necessary or sufficient?
> > 3. Who has discussed or proven it?
> > Please & Thank You.
> > C-B
> > (A wff expresses (represents) the set of numbers that when substituted
> > for its free variables forms a true (provable) sentence.)
"Charlie-Boo" <ch…@aol.com> writes:
> I wonder if there is an additional simple condition on the wff
> that ensures the above i.e. "If a wff passes such-and-such a
> condition, then the set expressed is r.e. iff the set expressed is the
> set represented."?
Sure, Sigma_1-formulas, assuming T to be Sigma-sound (1-consistent).
Again I recommend Smullyan’s book.
On 30 Dec 2005 08:45:45 +0100, Torkel Franzen <tor…@sm.luth.se>
wrote:
>"Charlie-Boo" <ch…@aol.com> writes:
>> I wonder if there is an additional simple condition on the wff
>> that ensures the above i.e. "If a wff passes such-and-such a
>> condition, then the set expressed is r.e. iff the set expressed is the
>> set represented."?
> Sure, Sigma_1-formulas, assuming T to be Sigma-sound (1-consistent).
??? Since you answer the question it seems you must have
figured out what it means. Given a wff, what are the sets
"expressed by" and "represented by" the wff, and in particular
how do they differ (how do the definitions differ)?
I can guess at reasonable definitions for either phrase but
I can’t guess at reasonable definitions that come out different…
>Again I recommend Smullyan’s book.
************************
David C. Ullrich
David C. Ullrich <ullr…@math.okstate.edu> writes:
> ??? Since you answer the question it seems you must have
> figured out what it means. Given a wff, what are the sets
> "expressed by" and "represented by" the wff, and in particular
> how do they differ (how do the definitions differ)?
Charlie-Boo actually explained these terms:
(A wff expresses (represents) the set of numbers that when substituted
for its free variables forms a true (provable) sentence.)
There are various uses and definitions of "representable",
"definable", "expressible" in the literature. The above agrees with
the terminology used in Smullyan’s "Gödel’s incompleteness theorems".
- Hide quoted text — Show quoted text -
David C. Ullrich wrote:
> On 30 Dec 2005 08:45:45 +0100, Torkel Franzen wrote:
> >"Charlie-Boo" writes:
> >> I wonder if there is an additional simple condition on the wff
> >> that ensures the above i.e. "If a wff passes such-and-such a
> >> condition, then the set expressed is r.e. iff the set expressed is the
> >> set represented."?
> > Sure, Sigma_1-formulas, assuming T to be Sigma-sound (1-consistent).
> ??? Since you answer the question it seems you must have
> figured out what it means. Given a wff, what are the sets
> "expressed by" and "represented by" the wff, and in particular
> how do they differ (how do the definitions differ)?
> I can guess at reasonable definitions for either phrase but
> I can’t guess at reasonable definitions that come out different…
OMG You don’t know what it means to express or represent a relation?
That is at the core of Logic and Incompleteness. People use those
terms all the time. (I hesitated to include the definition for fear of
ridicule.) The simplest Godel Incompleteness Theorem – the 1st. and
based on Soundness, is simply the fact that the set of (Godel numbers
of) the unprovable sentences is expressible [because Logic has the
means to state "x is not provable"] but not representable [due to
diagonalization] so truth does not equal provability. (Seen at a
different angle, the provable sentences form an r.e. set and the true
sentences do not.)
And I explained the definitions right there. You need some new
glasses!
- Hide quoted text — Show quoted text -
> ************************
> David C. Ullrich
"Charlie-Boo" <ch…@aol.com> writes:
> People use those terms all the time.
There are many terms that are used all the time in different senses.
> The simplest Godel Incompleteness Theorem – the 1st. and
> based on Soundness, is simply the fact that the set of (Godel numbers
> of) the unprovable sentences is expressible [because Logic has the
> means to state "x is not provable"] but not representable [due to
> diagonalization] so truth does not equal provability.
I recommend Smullyan’s book for an explanation of these matters, and
as an antidote to a preoccupation with the unnecessarily strong
and highly impenetrable condition of omega-consistency.
David C. Ullrich wrote:
> ??? Since you answer the question it seems you must have
> figured out what it means. Given a wff, what are the sets
> "expressed by" and "represented by" the wff, and in particular
> how do they differ (how do the definitions differ)?
> I can guess at reasonable definitions for either phrase but
> I can’t guess at reasonable definitions that come out different…
Look at this. I ask this nice question and Rupert says, "No, not
true." I thank him and ask him when it is true. Then Torkel
volunteers a precise answer to that. We’re having this nice
conversation and you walk up like a 4-year-old tugging on his
father’s shirttails – "Daddy, what do those words mean?"
But that’s ok! We should all feel free to ask questions without fear
of embarrassment. (Anything less is wrong.) But you harp about people
not knowing the right terminology when you yourself have a problem with
determining the right terms. "express" and "represent" are
standard.
"He who lives by the sword dies by the sword."
- Hide quoted text — Show quoted text -
> ************************
> David C. Ullrich
"Charlie-Boo" <ch…@aol.com> writes:
> "express" and "represent" are standard.
Sure, but their definition is not. Have you looked at what
"representable" means in various standard texts? For example, Herb
Enderton remarks, in his commentary on "A mathematical introduction
to logic":
One consequence of the work here is the fact (page 232) that any
recursive relation (i.e., a relation representable in some consistent
finitely axiomatizable theory) is actually representable in Cn
A_E. (Of course, the axioms of A_E were selected to make this happen.)
This is tied to the fact that the theory given by A_E is strong enough
to represent computability concepts. Section 3.6 will pursue this
point.
Torkel Franzen wrote:
> "Charlie-Boo" writes:
> > I wonder if there is an additional simple condition on the wff
> > that ensures the above i.e. "If a wff passes such-and-such a
> > condition, then the set expressed is r.e. iff the set expressed is the
> > set represented."?
> Sure, Sigma_1-formulas, assuming T to be Sigma-sound (1-consistent).
> Again I recommend Smullyan’s book.
Thanks, Torkel. I’m seeing light at the end of the tunnel, but
you’re getting into an area that you likely know a lot more about
that I do. That’s Sigma-1 as in (eA)P(A,x) where P is recursive
which (the set expressed) is therefore r.e? As in Kleene’s
Arithmetic Hierarchy? And let me guess: Sigma-sound means these wffs
are sound (given a value for x)? But there’s no reference to 1. And
1-consistent is a synonym or different but provably equivalent? And
are we back to Smullyan’s GIT again – which page?
Are you talking about some cases where we know truth = provability for
a wff, or a characterization of all such wffs?
Thanks again,
C-B
(I do need to get deeper into KAH. It seems to be the closest thing in
the literature to my axiomatizations of programming and computability.
I also see where they have a kludge: (eA)P(A)^LT(A,x) is recursive if P
is but they use the syntax (eA<x)P(A) and have a kludge rule for it.
In my formalization, you show that (eA)P(A)^LT(A,x) is recursive using
simple general rules that are potentially more general – i.e. reveal
recursivity more often, as I describe in my ARXIV post. The axiom is
LT(x,I)* which says that we can list the numbers less than a given
number and halt. It’s one of 4 characterizations of sets that I
use.)
"Charlie-Boo" <ch…@aol.com> writes:
> That’s Sigma-1 as in (eA)P(A,x) where P is recursive
> which (the set expressed) is therefore r.e?
We need to specify the syntactic form of the formula P(A,x). If by
"P is recursive" you just mean that P(A,x) expresses a recursive
relation, that’s not sufficient.
If you have Smullyan’s book at hand, I suggest that you just
work through it. Much more rewarding than usenet polemics.
Torkel Franzen wrote:
> I recommend Smullyan’s book for an explanation of these matters, and
> as an antidote to a preoccupation with the unnecessarily strong
> and highly impenetrable condition of omega-consistency.
Oh, c’mon. I’m all for re-focus and weaker conditions but
omega-consistency IS NOT "highly" impenetrable.
"george" <gree…@cs.unc.edu> writes:
> Oh, c’mon. I’m all for re-focus and weaker conditions but
> omega-consistency IS NOT "highly" impenetrable.
What theorems of an omega-consistent extension of PA are true?
Torkel Franzen wrote:
> "Charlie-Boo" <ch…@aol.com> writes:
> > I wonder if there is an additional simple condition on the wff
> > that ensures the above i.e. "If a wff passes such-and-such a
> > condition, then the set expressed is r.e. iff the set expressed is the
> > set represented."?
> Sure, Sigma_1-formulas, assuming T to be Sigma-sound (1-consistent).
> Again I recommend Smullyan’s book.
Isn’t the set expressed by a Sigma-1 formula always r.e.? Whereas it
would be the case that the set expressed by a Sigma-1 formula is always
the set represented only if T were Sigma-1-complete.
"Rupert" <rupertmccal…@yahoo.com> writes:
> Isn’t the set expressed by a Sigma-1 formula always r.e.?
Yes.
> Whereas it
> would be the case that the set expressed by a Sigma-1 formula is always
> the set represented only if T were Sigma-1-complete.
Yes, I was assuming only extensions of Q to be at issue.
On 30 Dec 2005 07:34:12 -0800, "Charlie-Boo" <ch…@aol.com> wrote:
- Hide quoted text — Show quoted text -
>David C. Ullrich wrote:
>> ??? Since you answer the question it seems you must have
>> figured out what it means. Given a wff, what are the sets
>> "expressed by" and "represented by" the wff, and in particular
>> how do they differ (how do the definitions differ)?
>> I can guess at reasonable definitions for either phrase but
>> I can’t guess at reasonable definitions that come out different…
>Look at this. I ask this nice question and Rupert says, "No, not
>true." I thank him and ask him when it is true. Then Torkel
>volunteers a precise answer to that. We’re having this nice
>conversation and you walk up like a 4-year-old tugging on his
>father’s shirttails – "Daddy, what do those words mean?"
>But that’s ok! We should all feel free to ask questions without fear
>of embarrassment. (Anything less is wrong.) But you harp about people
>not knowing the right terminology
No, I don’t harp on that. I may harp on people _using_ standard
terms _incorrectly_. There’s a big difference.
And I may hard on people stating profound facts that are _obviously_
false. Especially when someone announces a simple yet profound
theorem that’s supposed to give an awesomely simple proof of
Godel’s theorem, when it’s _obvious_ that the simple yet
profound theorem directly _contradicts_ Godel.
Or I may harp on people making absurd claims about the
_non-existence_ of a definition of a term like "wff".
Or bizarre claims about something which obviously is
a wff not being one.
>when you yourself have a problem with
>determining the right terms.
Nonsense. Cite a place where I had trouble finding the right
terms to _express_ what I wanted to say. If I wanted to
talk about the set of n such that Phi(n) was provable versus
the set of n such that Phi(n) is true I’d simply say something
about "the set of n such that Phi(n) is provable" and
"the set of n such that Phi(n) is true". No problem finding
the right terms at all there.
You seem to have big problems with form versus content.
_I_ have for example never said that truth and provability
are the same thing, while you _have_.
>"express" and "represent" are
>standard.
Yes. And they mean many different things in various contexts.
You’re (guffaw) the expert. Is this distinction between "express"
and "represent" actually used by a large number of people, or
is it just Smullyan’s terminology? If the first please provide
references.
>"He who lives by the sword dies by the sword."
Giggle.
That would be a little more apt if you’d found me insisting
on the truth of some assertion that was in fact clearly
false. Or if you’d caught me _using_ a term that I didn’t
know the definition of…
************************
David C. Ullrich
> "george" <gree…@cs.unc.edu> writes:
> > Oh, c’mon. I’m all for re-focus and weaker conditions but
> > omega-consistency IS NOT "highly" impenetrable.
Torkel Franzen wrote:
> What theorems of an omega-consistent extension of PA are true?
There are a great many different omega-consistent extensions of PA,
and since the standard model itself is one of them, I fail to see how
this question is relevant to the "impenetrability" of
omega-consistency.
Perspective on this question is going to again highlight our long-
running personal feud about the definition of "theory".
In a formal theory with a recursive axiom-set, under the usual notion
of first-order consequence, it doesn’t make any sense to ask
which "theorems" are "true". By the completeness theorem,
all theorems are true by definition (because in order to BE theorems,
they have to have PROOFS; that is what "to be a theorem" MEANS;
and by the completeness theorem, EVERYthing that is provable is true
under ALL interpretations, of the axioms from which it was proved).
As for "extensions of PA", I would think it would make far more
sense to locate the "impenetrability" in PA, not in omega-
consistency.
Rupert wrote:
> Isn’t the set expressed by a Sigma-1 formula always r.e.? Whereas it
> would be the case that the set expressed by a Sigma-1 formula is always
> the set represented only if T were Sigma-1-complete.
How in the heck is T going to manage NOT to be be Sigma-1
complete?! There IS a completeness THEOREM!
Standard/Classical FOL AS A WHOLE *is* complete in a
RELEVANT sense here!
george wrote:
> Rupert wrote:
> > Isn’t the set expressed by a Sigma-1 formula always r.e.? Whereas it
> > would be the case that the set expressed by a Sigma-1 formula is always
> > the set represented only if T were Sigma-1-complete.
> How in the heck is T going to manage NOT to be be Sigma-1
> complete?! There IS a completeness THEOREM!
> Standard/Classical FOL AS A WHOLE *is* complete in a
> RELEVANT sense here!
It’s easy for a theory in the first-order language of arithmetic not to
be Sigma-1 complete. The completeness theorem has nothing to do with it.
"george" <gree…@cs.unc.edu> writes:
> There are a great many different omega-consistent extensions of PA,
> and since the standard model itself is one of them, I fail to see how
> this question is relevant to the "impenetrability" of
> omega-consistency.
An extension T of PA is consistent if and only if every Pi-1-theorem
of T is true. Omega-consistency is also a partial soundness condition,
but just how strong is it, in relation to Sigma-n-soundness?
(Smorynski has the answer.)
george wrote:
> How in the heck is T going to manage NOT to be be Sigma-1
> complete?! There IS a completeness THEOREM!
> Standard/Classical FOL AS A WHOLE *is* complete in a
> RELEVANT sense here!
First order logic is complete in an entirely irrelevant sense here. A
theory T is Sigma_1 complete just in case every true Sigma_1 sentence is
provable in T. First order logic is not complete in this sense, and
neither is, for example, the theory with 0=0 as its only axiom.
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Aatu Koskensilta wrote:
> First order logic is complete in an entirely irrelevant sense here.
Wrong.
> A theory T is Sigma_1 complete just in case
You better KNOW this definition, kid.
> every true Sigma_1 sentence
What UTTER bullshit.
Unless the theory is arithmetic or something that is KNOWN
to have ONE standard model, the whole question of whether any
sentence in it CAN be TRUE is UTTERLY precluded, which is why,
I repeat, your lame attempt at a definition here, is, UTTER BULLSHIT.
We are talking about first-order theories here.
If they have recursive axiom-sets then they are chock-full of
sentences that are TRUE IN SOME MODELS AND FALSE IN OTHERS.
Alleging that ANY setnence in this framework is "true" (or false
either)
unless it is a theorem (or the negation of one) is, I repeat, UTTER
BULLSHIT.
Rupert wrote:
> It’s easy for a theory in the first-order language of arithmetic not to
> be Sigma-1 complete.
Sure,
if you concede the existence of a first-order language of
arithmetic.
Standard parlance in that arena is unreasonable.
If you define a theory (as is standardly and wrongly done)
as just any old consequence-closed class of sentences, then,
yes, you can get a whole lot of basically worthless junk.
Those definitions of those
classes are problematic for the simple reason that it is
too hard to say that you ever know what class you are talking
about; you don’t know which sentences are in the class and which
are not.
Standard parlance usually uses "formal theory" to mean
what "theory" ought to mean, but even that is not sufficient.
Theories deserve to be called that BECAUSE they contain
THEOREMS, NOT merely sentences.
Theorems deserve to be called that because they are PROVABLE,
NOT "true".
> The completeness theorem has nothing to do with it.
It would be more accurate to say that "truth" has nothing to do with
it,
although the separate/AK front of the battle.
george wrote:
> Aatu Koskensilta wrote:
>>First order logic is complete in an entirely irrelevant sense here.
> Wrong.
Well, what is the relevance of the completeness theorem for first order
logic here?
>>A theory T is Sigma_1 complete just in case
>>every true Sigma_1 sentence is provable in T.
> What UTTER bullshit.
It’s a perfectly standard and straightforward definition.
> Alleging that ANY setnence in this framework is "true" (or false
> either) unless it is a theorem (or the negation of one) is, I repeat, UTTER
> BULLSHIT.
We’re talking about Sigma_1 sentences, which are sentences in the
language of arithmetic. It makes perfect sense to speak of sentences in
the language of arithmetic, such as Sigma_1 sentences, being true (or
false).
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, darüber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus