Definable real numbers
tc...@lsa.umich.edu
a strongly inaccessible cardinal. In some models of ZFC the "powerset of
omega" is all of P, but in others it's not. Regardless, once I have a
model M of ZFC, I can talk about the subsets of omega in M that are
definable (by which I mean definable without parameters) in ZFC. Question:
is it true that as long as the "powerset of omega" in M is in fact all of P,
then I always get the *same* definable subsets of P? This seems like it
should be a trivial question but I'm getting confused about it.
This came up because a friend asked me what the definable real numbers are
and whether they form a field.
--
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
Mike Oliver
>
> Let P be the powerset of omega. Assume for simplicity that there exists
> a strongly inaccessible cardinal. In some models of ZFC the "powerset of
> omega" is all of P, but in others it's not. Regardless, once I have a
> model M of ZFC, I can talk about the subsets of omega in M that are
> definable (by which I mean definable without parameters) in ZFC.
You mean definable *in*M*, right? And hopefully we're considering
only transitive M? So I take it to mean that a subset A of the natural
numbers is definable in M just in case there's a first-order formula phi
in the language of set theory such that
M |= ( forall n)(n \in A <--> phi(n) )
By the way, it's more correct to say "definable in the language of
set theory" than "definable in ZFC"; ZFC doesn't have much to
do with it.
> Question:
> is it true that as long as the "powerset of omega" in M is in fact all of P,
> then I always get the *same* definable subsets of P?
No, at least not provably in ZFC. In fact you don't even necessarily get the same
definable subsets of omega, which I suspect is what you really meant to ask.
The problem is that the formula phi may quantify over things of much
higher rank than natural numbers or reals, and there's a great deal
of freedom to fiddle with these, say by forcing, in ways that affect
whether a set of naturals is definable. So for example you can force
over M to code an arbitrary real x up into the continuum function
of M[G], the forcing extension, in such a way that M[G] has the same
reals as M.
But off the top of my head I don't have a definitive answer to the
question you literally asked; because if M contains all the reals
then it's not a countable model so it's not clear that M[G] literally
exists.
tc...@lsa.umich.edu
Mike Oliver <oli...@math.ucla.edu> wrote:
>You mean definable *in*M*, right? And hopefully we're considering
>only transitive M? So I take it to mean that a subset A of the natural
>numbers is definable in M just in case there's a first-order formula phi
>in the language of set theory such that
>
> M |= ( forall n)(n \in A <--> phi(n) )
>
>By the way, it's more correct to say "definable in the language of
>set theory" than "definable in ZFC"; ZFC doesn't have much to
>do with it.
We can restrict to transitive M, that's fine; I don't want to worry about
"is a subset of" not being absolute or anything like that. And maybe
this is another thing I'm confused about, but when I said "definable
in ZFC" what I meant was that there is a first-order formula phi with
exactly one free variable such that ZFC proves
"There exists a unique subset x of the natural numbers such that phi(x)."
Is something wrong with that?
>> Question:
>> is it true that as long as the "powerset of omega" in M is in fact all of P,
>> then I always get the *same* definable subsets of P?
>
>No, at least not provably in ZFC. In fact you don't even necessarily
>get the same
>definable subsets of omega, which I suspect is what you really meant to ask.
You're right...I meant definable subsets of omega.
>The problem is that the formula phi may quantify over things of much
>higher rank than natural numbers or reals, and there's a great deal
>of freedom to fiddle with these, say by forcing, in ways that affect
>whether a set of naturals is definable. So for example you can force
>over M to code an arbitrary real x up into the continuum function
>of M[G], the forcing extension, in such a way that M[G] has the same
>reals as M.
Thanks...I'll have to think about that.
Mike Oliver
> And maybe
> this is another thing I'm confused about, but when I said "definable
> in ZFC" what I meant was that there is a first-order formula phi with
> exactly one free variable such that ZFC proves
>
> "There exists a unique subset x of the natural numbers such that phi(x)."
>
> Is something wrong with that?
Oh, I see. No, there's nothing wrong with that. It's just not quite
the setup I had in mind; I'm more used to talking about definable
sets of naturals in terms of formulas that say which naturals are in
the set, not formulas that define the set as a point.
It's not a big deal though. If tau(n) tells me which n are in
the set, then clearly we can turn it into a phi(x) which says
x is the unique set of naturals containing all and only those
n such that tau(n) holds; then clearly ZFC (but even much
less) proves that phi(x) is true of exactly one x.
Contrariwise, if phi is given satisfying your criterion,
then we can define
tau(n) iff (forall x)(phi(x) --> n \in x)
and tau will give the correct set of naturals in any model of ZFC
(and we seem to be considering only models of ZFC).
Herman Jurjus
"Mike Oliver" <oli...@math.ucla.edu> wrote in message
news:3DE3293F...@math.ucla.edu...
But does it contain the same elements, regardless of the model of ZFC?
What about
tau(n) := (n=0 and CH) or (n=1 and -CH) ?
Regards,
Herman Jurjus
Tim Mellor
> Let P be the powerset of omega. Assume for simplicity that there exists
> a strongly inaccessible cardinal. In some models of ZFC the "powerset of
> omega" is all of P, but in others it's not. Regardless, once I have a
> model M of ZFC, I can talk about the subsets of omega in M that are
> definable (by which I mean definable without parameters) in ZFC. Question:
> is it true that as long as the "powerset of omega" in M is in fact all of P,
> then I always get the *same* definable subsets of P? This seems like it
> should be a trivial question but I'm getting confused about it.
>
> This came up because a friend asked me what the definable real numbers are
> and whether they form a field.
The set of definable real numbers DR does form a field. Infact as a
structure in the language of rings I think its theory is the theory of
real closed fields regardless of the model of ZFC - i.e. ZFC tells us
enough about that part of the interpretable structure to determine its
theory even though ZFC is incomplete.
DR it is some (non trivial and probably depending on the model)
extension of the intersection of the algebraic numbers and the reals.
The field is not complete, but ofcourse every (uniformly) definable
cauchy sequence will converge.
I would be interested in any results people may know about this
phenomenon:
1. An incomplete theory T, such that for any model M of T, M^{eq}
contains some S (0-definable in L^eq, perhaps a sort) so that Th(S) in
the language of L_{eq} restricted to S is complete.
2. More particularly, can we for some T, classify the collection of
sorts which are T-fixes in this way? For the example of T=ZFC we have
Th(dN) (definable naturals) not T-fixed as it contains PA, asnd T is
recursively axiomatised but Th(dR) is T-fixed.
Mike Oliver
> "Mike Oliver" <oli...@math.ucla.edu> wrote in message
> news:3DE3293F...@math.ucla.edu...
>> the set, then clearly we can turn it into a phi(x) which says
>> x is the unique set of naturals containing all and only those
>> n such that tau(n) holds; then clearly ZFC (but even much
>> less) proves that phi(x) is true of exactly one x.
>> Contrariwise, if phi is given satisfying your criterion,
>> then we can define
>> tau(n) iff (forall x)(phi(x) --> n \in x)
>> and tau will give the correct set of naturals in any model of ZFC
>> (and we seem to be considering only models of ZFC).
>
> But does it contain the same elements, regardless of the model of ZFC?
No, certainly not, in general. My claim is only that, in any model
of ZFC, it defines natural-by-natural the same set that phi defines,
in that model, as a point.
tc...@lsa.umich.edu
Mike Oliver <oli...@math.ucla.edu> wrote:
>Oh, I see. No, there's nothing wrong with that. It's just not quite
>the setup I had in mind; I'm more used to talking about definable
>sets of naturals in terms of formulas that say which naturals are in
>the set, not formulas that define the set as a point.
So now let me ask another question, which is whether there's any way to
form the set of reals that are "really" definable, or "definable in V."
Methinks maybe not; if I try to let D be the family of all subsets of
omega of the form {n in omega | phi("n") is true} then I run into the
problem of having to define truth, which is impossible.
Mike Oliver
> So now let me ask another question, which is whether there's any way to
> form the set of reals that are "really" definable, or "definable in V."
> Methinks maybe not; if I try to let D be the family of all subsets of
> omega of the form {n in omega | phi("n") is true} then I run into the
> problem of having to define truth, which is impossible.
I'm not entirely certain what you mean by "forming" the set. It's
clear, informally, that the set exists; it's just a countable set
of reals. But the set is not definable over V, without parameters,
in the first-order language of set theory (I don't have a
proof of that off the top of my head, but I'm pretty confident).
George Greene
: By the way, it's more correct to say "definable in the language of
: set theory" than "definable in ZFC"; ZFC doesn't have much to
: do with it.
You're a damn liar. JEEzus.
The epsilon in what you call "the language of set theory"
just plain doesn't MEAN anything. It has MANY DIFFERENT
interpretations. They are NOT CONSTRAINTED UNTIL the predicate
APPEARS IN SOME AXIOMS. It very much *is* the language of ZFC
that is relevant. There is NO SUCH THING as "set theory"
OR ANY OTHER kind of theory until AFTER you have *some*
recursive axiom-set.
What you CALL "the language of set theory"
(with one binary predicate traditionally spelled
e) is EXACTLY ISOMORPHIC TO *ANY* other first-order
language with one binary predicate (including, say, =).
It IS NOT distinguishable AS "the language of set theory"
by any means other than the shape of the letter denoting
the predicate (which, mathematically speaking, DOES NOT
count) EXCEPT by occurrence IN AN AXIOM-SET.
Dumbass.
--
---
"It's difficult ... you need to be united to have any
strength, but internal issues have to be addressed."
--- E. Ray Lewis, on liberalism in America
tc...@lsa.umich.edu
George Greene <gre...@eagle.cs.unc.edu> wrote:
>What you CALL "the language of set theory"
>(with one binary predicate traditionally spelled
>e) is EXACTLY ISOMORPHIC TO *ANY* other first-order
>language with one binary predicate (including, say, =).
True. So what? Why should that stop anyone from calling it "the language
of set theory"? It's standard terminology. And it doesn't cause any
confusion---after all, even you knew exactly what he meant.
tc...@lsa.umich.edu
Mike Oliver <oli...@math.ucla.edu> wrote:
>tc...@lsa.umich.edu wrote:
>
>> So now let me ask another question, which is whether there's any way to
>> form the set of reals that are "really" definable, or "definable in V."
>
>clear, informally, that the set exists; it's just a countable set
>of reals. But the set is not definable over V, without parameters,
I guess what I'm asking is what assumptions I need to make in order to
prove that the set exists.
For example, let M be a transitive model of ZFC, and let D be the set of
reals in M that are definable in M. Then D isn't necessarily in M is it?
tc...@lsa.umich.edu
Tim Mellor <ti...@amsta.leeds.ac.uk> wrote:
>The set of definable real numbers DR does form a field. Infact as a
>structure in the language of rings I think its theory is the theory of
>real closed fields regardless of the model of ZFC - i.e. ZFC tells us
>enough about that part of the interpretable structure to determine its
>theory even though ZFC is incomplete.
Interesting...do you have a reference for this result?
Mike Oliver
> For example, let M be a transitive model of ZFC, and let D be the set of
> reals in M that are definable in M. Then D isn't necessarily in M is it?
I wouldn't think so, no. I'll give it some thought.
Daryl McCullough
>
>Mike Oliver <oli...@math.ucla.edu> writes:
> : By the way, it's more correct to say "definable in the language of
> : set theory" than "definable in ZFC"; ZFC doesn't have much to
> : do with it.
>
>You're a damn liar. JEEzus.
>The epsilon in what you call "the language of set theory"
>just plain doesn't MEAN anything. It has MANY DIFFERENT
>interpretations. They are NOT CONSTRAINTED UNTIL the predicate
>APPEARS IN SOME AXIOMS. It very much *is* the language of ZFC
>that is relevant. There is NO SUCH THING as "set theory"
>OR ANY OTHER kind of theory until AFTER you have *some*
>recursive axiom-set.
Mike wrote down explicitly what he means by "definable in the
language of set theory"
>...a subset A of the natural numbers is definable in M just
>in case there's a first-order formula phi
>in the language of set theory such that
>
> M |= ( forall n)(n \in A <--> phi(n) )
The relevant concepts are models and satisfaction, rather than
axioms and proof.
--
Daryl McCullough
Ithaca, NY
George Greene
: >The epsilon in what you call "the language of set theory"
: >just plain doesn't MEAN anything. It has MANY DIFFERENT
: >interpretations. They are NOT CONSTRAINTED UNTIL the predicate
: >APPEARS IN SOME AXIOMS. It very much *is* the language of ZFC
: >that is relevant. There is NO SUCH THING as "set theory"
: >OR ANY OTHER kind of theory until AFTER you have *some*
: >recursive axiom-set.
: Mike wrote down explicitly what he means by "definable in the
: language of set theory"
He might as well have tried to write down what he meant
by "definable in the language spoken on the third moon of
earth". THERE *IS*NO* such language, REGARDLESS of what he
meant. Even if he succeeded in identifying a particular language,
neither he NOR ANYBODY ELSE can defend CALLING it "the"
language of set theory.
: >...a subset A of the natural numbers is definable in M just
: >in case there's a first-order formula phi
: >in the language of set theory such that
: >
: > M |= ( forall n)(n \in A <--> phi(n) )
:
: The relevant concepts are models and satisfaction, rather than
: axioms and proof.
They are models AND THE LANGUAGES THAT PHI *can*be* in,
with all due respect. Calling the language in question
"the language of set theory" is idiotic. ALL FIRST-ORDER
LANGUAGES WITH ONE BINARY PREDICATE ARE CREATED EQUAL, at
least up to term-functor definitions. "The" language of
set theory has EXACTLY ONE of those: O. And even that one
does NOT designate the empty set (which is what it would TAKE
to make the phi in question "in the language of set theory")
until AFTER there is an AXIOM in which it occurs.
My point is simply that nobody has a clue what predicates
and functors to include in "the language of set theory" until
AFTER they see what predicates and functors occur IN SOME
AXIOMATIZATION of it. So ZFC *is*so*too* relevant.
tc...@lsa.umich.edu
Actually, maybe I've confused the issue by asking that question. Let's
stick to the previous formulation: Is "x is a definable subset of omega"
expressible in the first-order language of set theory? I think you said
the answer is no. Presumably it's easy to prove that "x is a definable
set" isn't expressible, but the tricky part is that there might be a way
of saying "x is a definable subset of omega" other than by saying "x is
definable and x is a subset of omega"?
Taneli Huuskonen
Hash: SHA1
In <xesd6oq...@eagle.cs.unc.edu> George Greene
<gre...@eagle.cs.unc.edu> writes:
[...]
>with all due respect. Calling the language in question
>"the language of set theory" is idiotic. ALL FIRST-ORDER
Yeah, definitely. It's almost as idiotic as using the word "teacup".
Heck, everyone except you and I is too stupid to realize that you can
perfectly well drink tea from a mug or a glass, or even straight from
the pot with a straw (better let it cool down a bit first, though).
You can also drink coffee, yoghurt, Perrier, or vodka from a so-called
"teacup". Indeed, everyone who uses the word "teacup" or the expression
"the language of set theory" should be publicly flogged and then jailed
until they learn not to use words or phrases that somehow refer to
common conventions.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPeeYB1+t0CYLfLaVEQJM1QCg5yAj9H2gVMCxYHMKqsuH1JzP02AAoMMX
MSjiKbON7tzhTFZ3K2xuEo//
=DWdH
-----END PGP SIGNATURE-----
--
I don't | All messages will be PGP signed, | The ultimate large
speak for | encrypted mail preferred. Keys: | cardinal: it's so large
the Uni. | http://www.helsinki.fi/~huuskone/ | it isn't true.
Bill Taylor
|> Yeah, definitely. It's almost as idiotic as using the word "teacup".
|> Heck, everyone except you and I is too stupid to realize that you can
|> perfectly well drink tea from a mug or a glass, or even straight from
|> the pot with a straw (better let it cool down a bit first, though).
|> You can also drink coffee, yoghurt, Perrier, or vodka from a so-called
|> "teacup". Indeed, everyone who uses the word "teacup" or the expression
|> "the language of set theory" should be publicly flogged and then jailed
|> until they learn not to use words or phrases that somehow refer to
|> common conventions.
_ _____ _ _
| | | _ | | | | |
_\|/_ | | | | | | | | |_| _\|/_
/|\ | |_ | |_| | | |_ _ /|\
|___| |_____| |___| |_|
So now we have the answer to one question at least:
Finns DO have a sense of humour!
===============================
No seriously Dan, forgive me for my teasing, but the above was very funny!
I really did laugh out loud here in my office.
But anyway it *is* good to see that Finns do have a sense of humour - that
almost completes my list. Now if I could just find out whether SWEDES do...
._,----._
Hammerfest ~-_
_/ >
__-- ___-~
/ _,-_ `---_,
_--\ / / `--\ /
/ * | ,'
/'\ \ TROMS0 ( (
Atlantic ocean /' \/ _/\___ / /
/'_,-Narvik___/ \_ `\/ |
/'/' _/ . / ~~\ \_
/`' / _/ | \
/ _/ \ |
_/ / ) (
_/ / \ |
/ / / |
_/ / \ \
/ | ,----+-. (
North Sea / / .' ) \_
_/ | | \ (
/ / | /~
_/ | > / FINLAND
__/ _) / /
___/ . /~~ SWEDEN / /
__/ Trondheim/ _/ /
,/ < / .'
/ | / |
| NORWAY | / | Vyborg
\____ | / | *
,----' . / ( | ___---
| Lillehammer \ \ __,--~~
|. \ \ _ ~-_ _*~Helsinki
Bergen Oslo / \ <_> ~---~~
| * | > ______
`\ | | | Stockholm*/ _-*~~~~
`. / \| /~ <><
Stavanger ,-' \ _/ __ <__>\ ESTONIA
`\___/ .Gothenburg / < / ~-,_______
===============================================================================
David Libert
I have some results relating to the recent articles of this thread,
so I am putting this as followup here, but it also relates to earlier
articles.
Paul Cohen's _Set Theory and the Continuum Hypothesis_ noted that
if ZF has well-founded models then there is a minimal well-founded
ZFC model, which futhermore has every element of the model definable
without parameters in the language of set theory.
In
[1] David Libert Mar 16, 2001 "Re: Compressed Transcendentals?"
http://mathforum.org/discuss/sci.math/m/329029/329037
I applied a similar argument, to only assume Con(ZF) (instead of ZF having
well-founded models), and constructing as a Skolem closure a ZFC model
with every element definable (ie without parameters: I will omit
mention below of "without parameters").
In fact the simplest version of this consturction gave V=L models.
So let M be a ZFC model with every element definable.
Then the set of all reals definable in M is the set of all reals in
M. This set is definable in M: ie "all reals". (Actually everything
was definable anyway.)
It is a ZFC model, so it is well-orderable, but in M everything is
definable, so the set of all reals definable in M even has a definable
in M well-ordering.
M thinks this set, being all reals, is uncountable.
We can get another example, changing that last though. Assume now
also M |= V=L, and M has every element definfinable, as above.
M is actually countable. So it has generic extensions.
Let M[G] be the generic extension of M collapsing M's continuum to
countable as usual.
M is the "L" of M[G], so M is a definable class in M[G]. So every
M element which was definable in M is still definable in M[G], ie M[G]
can repeat the old definition but with all quantifiers relativized to
M.
By homogeneity any real in M[G] which is definable in M[G] is
actually in M.
So the definable reals in M[G] is just the set of all reals from
M. But we made that countable by the forcing.
The M definable well-ordering as discussed above of that set is
still available in M[G] (relativize quantifiers to M), and M and M[G]
have the same ordinals and agree on what is well-founded.
So the definable reals in M[G] have a well-ordering definable in
M[G], namely into what M[G] thinks is some countable ordinal.
So M[G] is a ZFC model in which the set of all definable reals
exists, is definable, and has a definable well-ordering in order type
some countable ordinal.
Note that any ZFC model having its set of definable reals existing
as a member of the model and being definable can't have a definable
well-ordering of that set in order type omega. Otherwise, we could
use that to make a definition of a real diagonalizing out of the set,
refuting that it was the set of all definable reals.
So our M[G] model has a definable well-ordering of its definable
reals, but as some countable ordinal > omega. And this countable
ordinal has no definable bijection to omega, otherwise we could
diagonalize out of the definition as just noted.
Note that the M and M[G] examples above are available just assuming
Con(ZF). If we also assume ZF has well-founded models, then using
Cohen's claims, or applying [1] to those starting models, we can get M
and M[G] above well-founded.
That completes those first two examples. Next an example from the
flip side. Unfortunately I don't know how to do this style with
well-founded or even with omega models.
Assume Con(ZF). I am going to construct a ZFC model N so that there
is no element of N consisting exactly of those N reals which are
definable in N. Ie no set in N having as members the definable reals
of N.
N will be constructed syntactically, using the assumption Con(ZF).
Namely using Con(ZF) I will define a consistent Skolem theory. N will
be any Skolem term model of that theory.
The language of this theory will be the language of set theory,
augmented by Skolem function symbols, and an omega sequence
c_0, c_1, c_2, ... of individual constant symbols.
I am going to define the theory in an omega sequence of stages,
stage n+1 defining T_n+1 a consistent theory extending T_n. The
final theory will be the union of T_n for n in omega.
T_n will be in the sublanguage of the full language, namely having
all Skolem functions but only having constants c_0 , ... , c_n-1.
(T_0 will be in the sublanguage with no constant symbols.)
T_0 will be ZFC + Skolem axioms for all the Skolem function
symbols. Since Con(ZF), therefore Con(T_0).
I will define T_n+1 inductively. T_n+1 will be obtained from T_n
by adding new axioms about c_n. These axioms will be picked so
Con(T_n) -> Con(T_n+1), so this is how we inductively get all the
T_n 's consistent and hence the union of them consistent.
Toward this inductive definition, I first define an omega sequence
enumerating all the Skolem terms in the big final language (all omega
c_n 's included). First, enumerate all the Skolem terms of this
language. But now we use that preliminary listing to make a final
omega listing of these Skolem terms with the additional property that
the n'th listed term should be in the language of T-n, ie only use
constants from c_0, ... , c_n-1.
To define the 0th member of that list, note there are infintely many
Skolem terms that do not use any c_n 's. Find the first such term
listed in the preliminary list, mark that copy on that list as used,
and make it be the 0th member of the final list.
To define the 1st member of the final list, there are infinitely
many Skolem terms having either no constants, or else having c_0 but
no other constant. Find the first one of these in the preliminary
list, which has not been previously marked as used. Now mark that as
used, and make it be the 1st member.
For the second member, find the first term using at most c_0, c_1
and not previously used, mark that used and make it the second member,
can always find such as there are infinitely many.
And so on. n'th member of the final list is least preliminary
member not previously used and using constants at most
c_0, ... , c_n-1.
So our final list has each n'th member using only constants among
c_0, ... c_n-1. Also, every member of the preliminary list eventually
gets put into the final list, since by some finite stage the constants
it is using are allowed, so the only thing blocking it is earlier
members getting used first. But there are only finitely many of
these, so after finitely many stages those must have been used and the
member being considered moves to the htead of the line.
So we have an enumeration t_0, t_1, ... of all Skolem terms of the
big language, so that t_n is in the language of T_n, ie only
constants c_0, ... , c_n-1.
I earlier defined T_0. Now we define T_n+1, inductively on the
inductive assumption that T_n is defined and consistent.
T_n+1 is going to process Skolem term t_n, which is from the
language of T_n. Constant c_n was not in the language of T_n, it
is a new constant, so T_n+1 is going to add new axioms about c_n
which will make it impossible for t_n to be the set of all definable
reals (definable without parameters in the oure language of set
theory, not our extended language with Skolem functions and new
constants).
Toward this definition of T_n+1, consider all formulas phi(x) in
the pure language of set theory (only epsilon and =, no Skolem
function symbols or new constants).
For each such formula phi(x), let phi'(x) be the formula
[ ( [(exists real x) phi(x)] & phi(x) )
or
( ~[(exists real x) phi(x)] & x = real number 0 )
].
So for each formula phi(x), T_0 |- (exists real x) phi'(x).
We proceed to define T_n+1 from T_n by cases, according to the
properties of T_n. Recall from the final sequence, that t_n is a
Skolem term from T_n.
First case, suppose there exists some finite collection of formulas
phi_1(x), phi_2(x), ... , phi_m(x) (some finite m) each a formula
with only x free and each in the pure language of set theory, such
that
T_n |-
(exists real x1) (exists real x2) ... (exists real xm)
[ phi'(x1) & phi'(x2) & ... & phi'(xm)
&
(for all x) [ x member of t_n
->
[x = x1 or x = x2 or ... or x = xm]
]
]
So T_n would prove t_n has at most m members. So there is no way
t_n could be set of all definable reals in any model, since there are
more than m definable reals.
So in this case we don't need to do anthing, so T_n+1 will just be
the T_n axioms in the extended language, with extra constant c_n.
Next case, suppose there is no finite m and collection
phi1, ... , phi_m as above.
c_n does not appear in the language of T_n.
So T_n+1 in this case will be the T_n axioms together with the
infinitely many axioms
[(exists real x) phi(x)]
->
[(exists real x) [phi(x) & x ~= c_n] ]
for each formula phi with only x free and phi in the pure language
of set theory
and also the axiom: c_n member of t_n.
I claim that T_n+1 is consistent. Suppose not for contradiction.
Then by compactness, some finite subset of the new axioms are
inconsistent over T_n (since T_n is consistent: inductive hypothesis).
So suppose m is finite and the axioms above for
phi_1(x), ... , phi_m(x) are jointly inconsistent with
c_n member t_n and T_n.
But by the present case, T_n does not prove
(exists real x1) (exists real x2) ... (exists real xm)
[ phi'(x1) & phi'(x2) & ... & phi'(xm)
&
(for all x) [ x member of t_n
->
[x = x1 or x = x2 or ... or x = xm]
]
]
So find a model of T_n + the ~ of that last statment.
So in that model, there is an x member of t_n, this x ~= each of
x_1, ... , x_m these real and respectively with
phi'(x_1) , ... ,phi'(x_m).
Let c_n be a new constant denoting that x member, ie expand the T_n
model to have the extra constant, and denoting that x in that model.
So c_n member t_n, since x member t_n.
Consider the axiom
[(exists real x) phi_i(x)]
->
[(exists real x) [phi_i(x) & x ~= c_n] ]
for 1 <= i <= m.
If in this model ~(exists real x) phi_i(x), then the axiom is true
in the model by having a false antecedent.
If (exists real x) phi_i(x) in this model, then in the model
(for all x) phi_i(x) <-> phi_i'(x), from the way phi_i' was defined.
So we can take x_i from the model having phi_i'(x_i) and
x_i ~= c_n.
Since phi_i and phi_i' are equivalent in this case, this x_i
witnesses the (exists real x) consequent in the axiom, so again the
axiom is true.
We conclude we have constructed a model of T_n + c_n member T_n
+ the finitely many axioms.
This contradicting that this theory was supposed to be inconsistent.
So by this compactness argument in this case, we conclude the T_n+1
I have just defined is consistent.
So we have our sequence of theories ... T_n ... .
Let T be their union, consistent since union of consistent theories.
T is a Skolem theory, let N be any Skolem term model of T.
There is no Skolem term in T that could denote a set consisting
exactly of all the reals in N definable in pure language of set theory
in N. Namely, assume for contradiction there was such a Skolem term.
Then it would be enumerated as some t_n.
So consider T_n. If that was in the first case above, T_n would
prove that t_n has at most m members for some specific finite m.
T extending T_n would also prove this. N satisfying T would satisfy
this. So t-n couldn't be the set of all definable reals in N.
So suppose we are in the other case for T_n. Then T_n+1 put in
axioms, making c_n a t_n member.
If t_n were the set of all reals definable in N, then c_n being in
t_n would have to be definable, say by formula phi(x) in the pure
language of set thweory.
But in T_n+1 we added the axiom
[(exists real x) phi(x)]
->
[(exists real x) [phi(x) & x ~= c_n] ]
Since phi(x) is assumed to define a real in N, (ie by which I mean
unique existence of a real), the antecedent is true in N.
So the consequent is true in N.
But since phi is assumed to define a real in N, the uniqueness
clause is true in N.
From that uniqueness and from the consequence above we get
~phi(c_n).
This contradicting that phi defined c_n in N.
This contraction shows c_n was not definable, so in particular t_n
is not the set of all reals definable in N.
So we have shown no Skolem term t_n can be the set of reals
definable in N.
But N was a Skolem term model. So nothing in N could be that set.
Now restrict N back to the pure language of set theory, ie drop the
constants and the Skolem functions, to get a final ZFC model in which
the set of reals definable in that model does not exist in the model.
We used the compactness theorem to get this. So there is no reason
to expect this to be an omega model, let alone a well-founded model.
Note there is a bit for non-omega models to even say what the claim
is, the language saying the set of definable reals is not a member of
the model is sloppy. But the precise statement is there is no member
of N so that N's epsilon relation holds between that member and
exactly those members that are definable reals in N.
So we have seen the set of definable reals might exist and be
definable and be uncountable, or it might exist and be countable and
definable, in either of these cases it can even have a definable
well-ordering, or now in the 3rd example it might not even exist.
Those first two examples follow from just Con(ZF), you don't need to
assume well-founded models. If you do assume well-founded models, you
can make those 1st two well-founded.
For the 3rd, when the set of definable reals doesn't exist, I only
so far see it for general models. I don't know the status of this for
omega models or for well-founded models. The question quoted from the
start of this was for transitive models, so I don't know about that.
The other question, as came up earlier in this thread, is what about
a model in which the definable reals exists, but is undefinable.
That looks like the most reasonable case. I would conjecture that
ZF proves Con(ZF) -> there are ZFC models like this.
But the methods above don't settle that. And I don't know how to do
so.
In particular, if you assume there is an inaccessible cardinal, you
have the natural transitive ZFC model of that inaccessible rank. So
the set of reals definable in that model is itself a member of that
model, and is countable in that model, this similar to comments of
Mike's earlier in the thread.
But is that set definable in the model? A reasonable guess would be
no. But it is not so obvious how to prove that. In particular, there
is no fast simple argument to a quick contradiction from assuming it
is definable, since our previous example showed the set of definable
reals can exist, can be countable, can be definable, can even have a
definable well-ordering, and from all that there is no contradiction
for general ZFC models.
That model with all that was a very different model from an
inaccessible rank, and I would expect them to behave differently. But
any proof that they do must use extra properties of the inaccessible
rank to distinguish it from that case. I don't presently see what
those would be.
Also the other big question still remaining, is what about that last
example for well-founded models: ie there is no set in the model of
all the definable reals.
--
David Libert ah...@FreeNet.Carleton.CA
George Greene
: Yeah, definitely. It's almost as idiotic as using the word "teacup".
: Heck, everyone except you and I is too stupid to realize that you can
: perfectly well drink tea from a mug or a glass, or even straight from
: the pot with a straw (better let it cool down a bit first, though).
: You can also drink coffee, yoghurt, Perrier, or vodka from a so-called
: "teacup". Indeed, everyone who uses the word "teacup" or the expression
: "the language of set theory" should be publicly flogged and then jailed
: until they learn not to use words or phrases that somehow refer to
: common conventions.
There are many different set theories with many different axiomatizations
and it matters a WHOLE lot that WITHOUT any axiomatization there is NO
set theory PERIOD, let alone any language of set theory. The signs
in the language CAME FROM STATEMENTS OF THE AXIOMS. Whatever
connotations they may have that allow them to be used in the
language CAME FROM THE AXIOMS. Mugs and glasses have a lot
MORE IN COMMON with teacups THAN ANY 1st-order predicate-SYMBOL
has with ANY other. And you KNEW that: you were just being an asshole.
George Greene
: <gre...@eagle.cs.unc.edu> writes:
: [...]
: >with all due respect. Calling the language in question
: >"the language of set theory" is idiotic. ALL FIRST-ORDER
huus...@cc.helsinki.fi (Taneli Huuskonen) writes:
: Yeah, definitely. It's almost as idiotic as using the word "teacup".
: Heck, everyone except you and I is too stupid to realize that you can
: perfectly well drink tea from a mug or a glass, or even straight from
: the pot with a straw (better let it cool down a bit first, though).
: You can also drink coffee, yoghurt, Perrier, or vodka from a so-called
: "teacup". Indeed, everyone who uses the word "teacup" or the expression
: "the language of set theory" should be publicly flogged and then jailed
: until they learn not to use words or phrases that somehow refer to
: common conventions.
^^^^^^^^^^^^^^^^^^^^^
The NAME of the group is sci.LOGIC.
It is a *DEFINITIONAL* aspect of LOGIC that the
things whose definitions DON'T change, the things
that are defined BY CONVENTION, are the LOGICAL
symbols. THE OTHER symbols, MOST specifically
and importantly the symbols NAMING PREDICATES AND
FUNCTIONS, *DO* change in meaning from model to model,
from interpretation to interpretation, and from axiom-
set to axiom-set. But what *matters* for ALL these symbols
IS their meaning AND NOT their shape, AND NOT their
orthography.
THAT ITSELF is a common convention in LOGIC IN GENERAL.
The common convention of referring to things like
"the language of set theory" and "the language of
arithmetic" is at odds with it. If there is ANY
place where one OUGHT to be able to observe that truth
and NOT get laughed at, it OUGHT to be in sci.LOGIC.
David Libert
> In article <3DE51E7B...@math.ucla.edu>,
> Mike Oliver <oli...@math.ucla.edu> wrote:
> >tc...@lsa.umich.edu wrote:
> >
> >> For example, let M be a transitive model of ZFC, and let D be the set of
> >> reals in M that are definable in M. Then D isn't necessarily in M is it?
> >
> >I wouldn't think so, no. I'll give it some thought.
>
> Actually, maybe I've confused the issue by asking that question. Let's
> stick to the previous formulation: Is "x is a definable subset of omega"
> expressible in the first-order language of set theory? I think you said
> the answer is no. Presumably it's easy to prove that "x is a definable
> set" isn't expressible, but the tricky part is that there might be a way
> of saying "x is a definable subset of omega" other than by saying "x is
> definable and x is a subset of omega"?
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
"x is a definable subset of omega" is not expressible in the first
order language of set theory.
I will give a general discussion of this, from which that answer
above will follow.
This came up in another thread, titled almost the same as this one.
In that thread, Bill Taylor had proposed a version of math in which
every real was to be definable, and there was discussion of what this
meant:
[1] sci.math Aug 8 '02 David Libert "Re: Definable Reals"
http://mathforum.org/discuss/sci.math/a/m/423909/431062
From [1]:
> Even so, difficulties remain. What are we to make of the statement
> every real is definable? If that is an outright literal statement in
> the system, the system is talking about definability in its own language.
> The obvious way to define definability for a language is to use
> satisfaction for that language, which includes having a truth predicate.
>
> So to even formulate the statement as an internal one clashes with
> Tarski's theorem on the undefinability of truth.
>
> In fact a have a model theoretic formulation of what it would mean to
> define definability, and I can prove for theories having properties
> we would expect of a foundational system for a version of mathematics,
> such a definition is impossible.
[1] didn't write any more than the above about that formulation.
Since this has just come up again I will write about that now.
So we have a first order language L, and a first order theory T, in
the language L. We will be concerned about individuals being
definable, ie definable without parameters, "without parameters" being
understood and not repeated below.
Suggested by Tim asking this about the reals in ZFC, let R be a
formula with one free variable in the language L, so R defining a
subset of the universe. (Ie: R being the definition of the reals in
the language of ZFC in Tim's version above).
We want to formulate what it would mean to define definability of R
elements in T, and then to analyse how this notion works out for
various theories T.
As noted above, the most obvious first idea runs up against
Tarski's theorem, similar points to this also raised in this thread
recently by Tim.
So as noted above, we will make a model theoretic reformulation of
what it means to define definability.
Given any model M of T, we have a definite notion of what it means
for individuals in M to be definable in the language L: there is an L
formula with one free variable uniquely satisfied by the individual in
question.
So for any model M of T, we can form (in model theory outside the
model), the set of all R elements (ie R as interpreted in M) which are
L definable.
A T definition of definability in R would be a formula D in the
language L in one free variable so that for any model M of T the
individuals of x of M s.t. M |= D(x) are exactly those x
s.t. M |= R(x) and x is definable in M by an L formula without
parameters.
So definability is definable iff there exists a formula D with one
free variable in L satisfying the condition above.
Note that this formulation makes sense for any language L and theory
T, in particular (even though this point does not matter for Tim's
original ZFC case) even for L and T 's not able to arithmetize
syntax. We have quantified the definability notion out into the model
theory above the models.
So next is the question for which L,T,R is definabilty definable.
The first surprising realization is sometimes definability is
definable. In [1] I had some examples of this in mind.
Reading Tim's article and thinking about it again, I just realized
new examples where definability is definable. Namely suppose T is
inconsistent. The definition above of defining definability specifies
for all models M of T something happens. This becomes a vacuous
universal quantification if T is inconsistent, so inconsistent T have
definability definable. In fact, any formula D in one free variable
is a definition of definability.
(Hey: brainstorm! So to settle the question above all we need do is
prove ZFC inconsistent!!)
Ok, anyway, on to other examples. Consider L the language of =
only, and T the theory with only 1 non-logical axiom:
(exists x) (exists y) x ~= y. Ie: there are at least two
individuals in the universe. Let R be x=x: ie define the entire
universe.
Then nothing is definable. So I can define definability with the
following formula D : ~ x=x.
Or another example: L as above, and T with axiom
(all x) (all y) x=y : there is only one individual. R as before.
Then the unique individual is definable by the formula x=x. So all
individuals are definable, and definability is definable by x=x.
So I will proceed now to the general claim, which basically says
definability of R elements is definable iff there are only finitely
many definitions covering all R definitions.
I state this more precisely and then prove it. For phi a formula in
L with one free variable, I will use the meta-linguistic abbreviating
symbol Def(phi, x) to represent the L formula which is expressing
that phi defines individual x:
[ (all y) (all z) [ ( phi(y) & phi(z) ) -> y=z ]
&
phi(x) ]
where I write phi followed by a variable in parenthesis to denote a
permissible subsitution of phi's free variable by the displayed
variable.
The condition on L,T,R will be:
there exists finitely many L formula in one free variable
phi_1, phi_2, ... , phi_n
such that for all L formulas theta in one free variable
T |- ( all x s.t. R(x) )
[ Def(theta, x) ->
( Def(phi_1, x) or Def(phi_2, x) or ...
... or Def(phi_n, x) ) ]
Ie, this says any R element which is definable in any way is
definable by one of the phi_i 's. So finitely many definitions can
duplicate the work of all definitions.
In particular, if L,T,R has such a phi_1 ... phi_n, this says at
most n R elements can be definable in any T model.
Claim: definability for R elements is definable in T
<-> the condition above holds,
ie these exists such phi_1 ... phi_n .
Proof of <-
Suppose phi_1 ... phi_n is as claimed.
Let D be R(x) &
(Def(phi_1, x) or Def(phi_2, x) or ... or Def(phi_n, x))
Suppose M |= T and a is an individual in M.
Suppose M |= D(a). (ie substituting a for D's free variable x).
Then M |= R(a). Also, one of phi_1 ... phi_n defines a in M, by
the disjunction, so a is definable.
Conversely, suppose M |= R(a) and a is definable, say definable
by theta.
By the condition above, T |- that implication from Def(theta, x) to
the disjunction over Def(phi_i, x). Instantiate that to a, and we
get the required disjunction appearing as a conjunct in D.
QED <-
Proof of ->
I will prove the contrapositive.
Suppose we have L,T,R so the condition fails, ie there is no
phi_1 ... phi_n so all those statements are T provable.
I must show that definability of R elements is not definable. Ie, I
must show there is no formula D in one free variable defining
definability.
So let D be some formula in one free variable. I must show this D
does not define definability for R elements.
So suppose for contradiction D does define definability for R
elements.
Using that supposition, which gives me some information about D, I
am going to construct M a model of T such that D in M does not
coincide with the R elements that are definable in M, this
contradicting the supposition on D after all.
From this contradiction we will conclude D does not define
definabilty for R elements.
Specifically the construction of M will arrange there is an
individual c, such that M |= D(c) and yet c is not definable in
M.
To get started on constructing M, first note that since we are
presently assuming the condition fails (there is no phi_1 ... phi_n)
that T is consistent. Ie the condition on phi_1 ... phi_n was
that a bunch of formulas be T provable. If T were inconsistent,
everything would be T provable, so any choice of phi_i 's and n
would work to fulfill the condition.
So T is consistent. Add to L a new constant c, which will denote
the individual we seek in our constructed M.
Extend T in this expanded language, namely add axioms D(c) and
R(c) and for every formula phi in one free variable add the axiom
~Def(phi, c).
I claim this theory is consistent. Suppose not for contradiction.
Then by compactness, there would be an inconsistency from T, D(c),
R(c), and finitely many axioms ~Def(phi_1, c) , ... ,
~Def(phi_n, c) for some phi_1 ... phi_n formulas with one free
variable.
But the condition stated above is presently assumed to fail for
L,T,R. So these is some formula theta in one free variable
such that T does not prove
( all x s.t. R(x) )
[ Def(theta, x) ->
( Def(phi_1, x) or Def(phi_2, x) or ...
... or Def(phi_n, x) ) ]
Let N be a T model satisfying the negation of the last statement.
So there is some individual x in N, s.t. N |= R(x) and
Def(theta, x) yet ~Def(phi_i, x) all i: 1 <= i <= n.
We are presently assuming for contradiction that D defines
definability for R elements in T. N |= T, and in N x is defiable,
ie by theta, since N |= Def(theta, x).
So by the supposition that D defines definability, we get N |= D(x),
ie we had R(x) and theta defines x in N.
So we have in N that D(x) and R(x) and all the ~Def(phi_i, x).
Now expand N to the language with extra constant c, namely making c
denote that individual x.
Then in this expanded model, we have D(c), R(c), and
~Def(phi_i, c). And this is a T model of course.
So this is a model of the fragment above that was supposed to be
inconsistent from compactness. The existence of this model refutes
that inconsistency.
Hence by the compactness introducing that finite fragment, we refute
the assumed inconsistency of the entire theory: T + D(c) + R(c) +
all the ~Def(phi, c) all phi with one free variable.
So that theory is consistent.
Let M be a model of it. Or actually of the retriction of that
theory back to language L. Anyway, the denotation in M of constant
c is in D but is not definable, by all the ~Def(phi, c) axioms.
So we have shown that D doesn't define definability for R elements
after all.
To get that conclusion, we had to assume along the way D did define
definability, but at least we have gotten a contradiction from that
assumption, and discharing that assumption we get again the final
conclusion that D doesn't define definability for R elements.
D was picked as arbitrary formula in one free variable.
So we have shown under the assumption that the condition fails that
definability for R elements is not definable in T.
QED <-
For T = ZFC and R = the reals, since there are infinitely many
definable reals, the condition reducing all definitions to finitely
many fails.
So in ZFC, definability of reals is not definable.
--
David Libert ah...@FreeNet.Carleton.CA
tc...@lsa.umich.edu
David Libert <ah...@freenet.carleton.ca> wrote:
> "x is a definable subset of omega" is not expressible in the first
>order language of set theory.
>
> I will give a general discussion of this, from which that answer
>above will follow.
Wow! Very clear and thorough discussion (in this and in your other
article). That pretty much settles the questions I had.
Is all this in print somewhere or are your own Usenet articles the
only source you're aware of?
tc...@lsa.umich.edu
>Wow! Very clear and thorough discussion (in this and in your other
>article). That pretty much settles the questions I had.
Actually, I thought of two leftover questions.
1. Someone said that the theory of the definable reals is the theory of
real closed fields. I'm still looking for a proof/reference.
2. If "x is a definable subset of omega" is not expressible in the first-
order language of sets, is it expressible in some other "reasonable"
logic? The fact that there is no real problem with defining the truth
of a given finite set of formulas, and that trouble arises only with
trying to define the truth of all formulas simultaneously, has made me
wonder whether allowing infinite disjunctions would circumvent the
difficulty. But maybe the same liar-paradoxical argument used to
prove Tarski's theorem still goes through.
H. Enderton
>1. Someone said that the theory of the definable reals is the theory of
> real closed fields. I'm still looking for a proof/reference.
Tim, as I recall, the reals that are definable *in the real field*
(R; 0, 1, +, x) are exactly the real algebraic numbers, which
form the smallest elementary substructure of the real field.
Both are real-closed fields, and Tarski showed that the theory
of real-closed field is complete and (with <) admits elimination
of quantifiers.
Shoenfield's book covers this theorem.
I have always found it interesting that real-closed fields were
not invented by logicians. Algebraists studied them first.
--Herb Enderton
David Libert
> In article <m3ptsm1...@localhost.localdomain>,
> David Libert <ah...@freenet.carleton.ca> wrote:
> > "x is a definable subset of omega" is not expressible in the first
> >order language of set theory.
> >
> > I will give a general discussion of this, from which that answer
> >above will follow.
>
> Wow! Very clear and thorough discussion (in this and in your other
> article). That pretty much settles the questions I had.
Thanks.
> Is all this in print somewhere or are your own Usenet articles the
> only source you're aware of?
Off hand I don't recall related discussions to that outside of sci.math.
The earlier related discussions were various points about Bill's
proposal, as I mentioned last article.
Actually, I now recall the part about Bill's was the second round.
Before that was the Compressed transcendentals thread, when someone
asked about finite definitions of transcendentals like pi and e being
compressed compared to a listing of all digits, and could there only
be countably many such compressed transcendentals. So that led to the
discussion of every element definable in a ZFC model. That was picked
up again later is discussing Bill's proposal.
I recently referenced the Compressed transcendentals thread, in my
first recent article here, and last article refenced the Definable
real numbers thread, which was about Bill's idea.
There were other threads about Bill's proposal, as I recall that
actually started in Compressed transcendentals and moved to several
other threads.
One thing along those lines, Mike Oliver mentioned in one of those
discussions that any ZF model with every element definable actually
satisfies AC.
My last article in this current thread related the question of
defining definability of reals to the general claim about defining
definability.
There are other ways to see the that definability of reals is not
definable, more directly than the last article.
I had a followup to the article making the ZF model with everything
definable as cited recently, the followup:
[1] sci.math Mar 16 '02 David Libert
"Re: Compressed Transcendenals?"
http://mathforum.org/discuss/sci.math/m/329029/329038
That article was about models related to a ZFC model with every
element definable, namely elementary extensions with new undefinable
elements.
The simplest version was just by upward Lowenheim Skolem, adding a
new undefinable element to an infinite definable set from the base
model.
The second version of such an extension was if we take the base
model to be Skolemized, then we can add a single undefinable element
to a given infinite definable subset of the universe (ie or subclass
in set theory terms), and taking the rest of the extended model to be
generated by Skolem functions.
Anyway, that was phrased in [1] with the base model having
everything definable, but by the same argument, if we just assume the
base model is for any Skolemized theory, (not necessarily with
everything definable), then we can add a single undefinable element
to any definable infinite set, and in this version have the new model
the Skolem closure of the old base model (explicitly throw it in,
since we no longer assume everything is definable), and of the single
new undefinable element.
Ie: given base model, and given a definable part of that, you can
add one new undefinable element and Skolem operations on that and the
original base, having everything elementary extension of the base.
This is just a simple compactness argument.
So for a simpler proof that real definability is undefinable in ZFC,
suppose for contradiction D were a definition of real definability.
Assuming ZFC is consistent (else definability is definable as last
article) let M be a Skolemized ZFC model. Then D in M is infinite,
since infinitely many reals are definable.
So use that last result to make M(c), M adjoin c a new undefinable
element of D. This refutes D as a real definabilty definition.
The next 2 followup articles to [1] had discussion about examples of
models of other theories with everything definable, or whether some
theories had no such models, or had everything undefinable in every
model.
Getting off topic from the original question about ZFC, but just of
general interest for these properties about theories.
--
David Libert ah...@FreeNet.Carleton.CA
Taneli Huuskonen
Hash: SHA1
In <asdafk$8ge$1...@galois.mit.edu> tc...@lsa.umich.edu writes:
>1. Someone said that the theory of the definable reals is the theory of
> real closed fields. I'm still looking for a proof/reference.
I haven't checked it, but it seems to me that the proof must be quite
straightforward. For instance, if phi and psi define reals a and b,
respectively, then the formula (Ex) (Ey) (phi(x) & psi(y) & z=x+y)
defines their sum, and likewise for every real whose existence is
asserted by the axioms of RCF's.
>2. If "x is a definable subset of omega" is not expressible in the first-
> order language of sets, is it expressible in some other "reasonable"
> logic? The fact that there is no real problem with defining the truth
> of a given finite set of formulas, and that trouble arises only with
> trying to define the truth of all formulas simultaneously, has made me
> wonder whether allowing infinite disjunctions would circumvent the
> difficulty. But maybe the same liar-paradoxical argument used to
> prove Tarski's theorem still goes through.
I think L_{\omega_1\omega} can express "x is first-order definable". It
can't express "x is L_{\omega_1\omega} definable", though.
BTW, \Sigma^1_1 can define its own truth predicate in N, as observed by
G. Sandu. It's not closed under negation, hence no contradiction
arises.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPeuQrV+t0CYLfLaVEQKR7ACeJtTivEMuUVWzFQ22oEjihF2J+VcAnjZy
8s+XmSinjwmjDTo/fppzO/km
=rGK1
Taneli Huuskonen
Hash: SHA1
In <xeslm3a...@atlanta.cs.unc.edu> George Greene
<gre...@atlanta.cs.unc.edu> writes:
[a ranting reply to my admittedly rude comment]
OK. I'm convinced that you're not stupid at all and that you know a
fair deal about logic. However, I've quite a bit of trouble
understanding what you're trying to say. Would you mind answering a few
questions to clarify your position?
1. Do you feel you understand what people mean by "the language of set
theory", even though you object to such usage?
2. If yes, what would you propose they should say instead to convey the
same idea?
3. Do you believe that a significant number of sci.logic regulars are
unaware of the facts that you use to support your position that it's
"idiotic" to use the phrase "the language of set theory"?
4. Can you understand how an intelligent person can know those facts
yet disagree with your conclusion?
I'm genuinely interested in your answers.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPeu3ql+t0CYLfLaVEQJErQCg0v2jEhqQ3tvO3ne+lVau3iuPsrsAn1FI
9Q7V/5S7h+bn2Wz4+TWiWsXp
=YV5A
George Greene
huus...@cc.helsinki.fi (Taneli Huuskonen) writes:
: OK. I'm convinced that you're not stupid at all and that you know a
: fair deal about logic. However, I've quite a bit of trouble
: understanding what you're trying to say. Would you mind answering a few
: questions to clarify your position?
: 1. Do you feel you understand what people mean by "the language of set
: theory", even though you object to such usage?
Almost. The objection is vehemently ABOUT the very IDENTITY of
"the" language in question, so admitting that I understand what
their pointing at would be conceding too much.
: 2. If yes, what would you propose they should say instead to convey the
: same idea?
I am opposed to the concession of the idea as coherent, which is
why I have trouble with 1. Here is a *candidate* "first-order
language of set theory": assuming you know what a first-order
language is in general, the first-order language of set theory is
"the" (obviously it is NOT unique, which is why people shouldn't be
putting "the" in front of it) first-order language with: 1 binary
predicate denoting [something semantically CALLED] membership, and
one unary functor producing its argument's [so-CALLED] powerset.
There are at least 2 other binary predicates (subset and equality)
and one other functor (a 0-ary one denoting the empty set) that are
"normally" included in "the" language, but since all 3 of those
have axiomatic definitions, they are eliminable in principle, so
"the" language simply does not *need* to include them. Maybe
somebody wants to allege that "{" and "," and "}" are also "in"
this language, but the point is that ye{a,b,c} is just a macro for
yea v ye{b,c}, and the latter smaller bracketed expression is in
turn equivalent to yeb v yec, so my point is simply that everything
except e & p is eliminable. p has a definition but it actually
matters for first-order languages in general whether they do or
don't have a unary functor, so we will refrain from trying to
eliminate p in order to keep this language pinned in the family of
those rich enough to have one, since the foundational relevance of
the field came from iterated applications of p.
Whether I care enough to propose what "they" would say to convey
this idea depends, of course, on whether this language or
this idea is any good for anything.
It isn't.
In order for it to be any good for anything, it would have to
*matter* that you *could* have *models* over it that *don't*
conform to any particular set of axioms. And *that* is incoherent.
The ONLY way you can say WHICH model over this language you MEAN
*is* by stating some things that *have* to be true in it.
And if you're highlighting (as opposed to ignoring) a "model over"
this language where ExAy[~yex] comes up *false*, then what*ever*
language this is, calling it "the language of set theory" gets ridiculous
pretty fast, especially when it is isomorphic to every OTHER
language with 1 unary functor and 1 binary predicate that
does NOT spell them e and p (in ADDITION to not interpreting
them set-like-ly).
In order to make this *a* language of set theory, it has to
be defined IN TERMS OF SOME *AXIOMS* that guarantee that something
at least vaguely set-like is in fact going on among the truths
and elements of the model. In that case it becomes proper to
refer to the language as the one whose predicates and functors
are those occurring IN THE AXIOM-SET. So I would ask people to
talk about the language of ZFC or PA as *opposed* to the language
of set theory or arithmetic, for the simple reason that +
doesn't MEAN addition and O doesn't MEAN the empty set until
AFTER they occur in some AXIOMS that would constrain them to mean that.
Mike Oliver (who started it) had a REASON for NOT wanting to do
this. He was originally trying to be scrupulous enough NOT to do
this BECAUSE of the UNfortunate coincidence that THEORIES and
LANGUAGES are BOTH sets-of-strings. He didn't want to refer to
"the language of ZFC" because EVERY theory, being a set of strings,
is, coincidentally, ALSO, a language. So to him, "the language of
ZFC" and "the theory of ZFC" were supposed to MEAN THE SAME THING.
To me, they don't. "ZFC" doesn't want to occur UNqualified unless
context clearly disambiguates among the following 3 string-sets, in
increasing order of size: the axiom-set, its closure under
consequence (the theory), and the first-order langauge over the
predicates and functors occurring in the axioms&theory (which I
would call the language, or the 1st-order language, of/over ZFC).
If I had meant the THEORY I would've *said* the theory; the fact
that the theory is a language is simply not important or relevant
enough to create an ambiguity problematic enough for Mike to be
trying so hard to avoid it. Thinking that e & p are somehow
"inherently", in virtue of their shape or orthography, about sets,
is arguably the MORE dangerous mistake. What relates these
predicates and functors _to sets_ *IS* THE *AXIOMS*, NOT the kind
of linguistic convention that names tea "tea" and cups "cups".
THAT is arbitrary. The patterns in the axioms (up to commutativity
anyway) are not. They are the content/expression of the relevant
knowledge/structure.
: 3. Do you believe that a significant number of sci.logic regulars are
: unaware of the facts that you use to support your position that it's
: "idiotic" to use the phrase "the language of set theory"?
No.
: 4. Can you understand how an intelligent person can know those facts
: yet disagree with your conclusion?
I don't consider this a reasonable criterion for anything.
I don't know if you knew this or not, but America is currently
ruled by an illegitimate usurpational regime. This happened
because some intelligent people disagreed with each other
over how to interpret and apply our national constitutional
principles to state enforcement of election laws in Florida.
Smart people advocate indefensible positions ROUTINELY.
Smart people have agendas other than mere intellectual
consistency, especially if they are having any kind of
success in the real world. Academic arguments are so bitter
because the stakes are so SMALL.
: I'm genuinely interested in your answers.
That's much more than I deserve.
If it will make you feel better, I will concede that
your lecture on this point (the "teacup" analogy)
was more pedagogically effective, internally, for me,
than anybody else's has ever been on this issue.
I can quit tilting against this windmill with a clear
conscience, now, I suppose.
One thing I need from people who know more about this than
I do that I don't yet have is a better word than "model"
for use in scenarios like the following:
Consider the class of all "models" (all consistent
assignments of boolean-valued functions to predicates
and of d-valued functions on d^n, for relevant n, for a
domain d) "of"/over a first-order language L (identified,
as above, by the names and arities, or just how MANY of
each arity, of its predicates and functions). You might want
to consider this class IN RELATION TO some candidate axiom-set,
because you might want to know whether the axiom-set is consistent
(assuming the predicate- and function- names occurring in L
are the same as the ones occurring in the axiom-set,
if this class includes one "model" that assigns "true"
to all the axioms in the set, then the set is consistent).
If the axiom-set is consistent then the "model" existing above
is *a* model (*no* scare-quotes, canonical usage) OF the axiom-set.
Everybody *knows* what we mean by a model *of* this or that.
But what are we supposed to mean by a "model" in general,
"over" a "language" in general? My point being simply that
some of those "models" will in fact NOT be a model *of* anything
with an interesting (or even finitary) description.
Is "model over a language" (I *know* this is non-standard
terminology; I am *asking* for the standard) *really* the
foundational use? Is the concept of a model *of* some
conjunction of statements, of some axiom-set (the one I
have always heard as canonical) actually derivative from that?
Perhaps my question will be clearer if instead of talking about the
existence of a model connoting consistency, I talk about the
inverse of that and say instead that if *no* "model" assigns true
to all the axioms, then the axiom set _has no_ model (canonical
usage, no scare-quotes). In other words, as far as this axiom-set
is concerned, EVERY "model" is NOT a model! This is within 1 set
of quotes of violating reflexivity of equality. I mean, if I took
the gloves (quotes) off and said "this shows that every model is
not a model", it would be clear that I have the right to be
confused, right?
At the moment I am disambiguating this prepositionally via
"model over" a language vs. model *of* an axiom-set, but
I don't imagine that other people say "model over". So
what do they say? If they do in fact conventionally say
"model of" in BOTH cases then I am going to keep on whining
that it is confusing and that they could and should do better.
Mike Oliver
> Mike Oliver (who started it) had a REASON for NOT wanting to do
> this. He was originally trying to be scrupulous enough NOT to do
> this BECAUSE of the UNfortunate coincidence that THEORIES and
> LANGUAGES are BOTH sets-of-strings. He didn't want to refer to
> "the language of ZFC" because EVERY theory, being a set of strings,
> is, coincidentally, ALSO, a language.
No, unless I'm misunderstanding you, that is not what I meant
at all; that is not it, at all.
The reason I prefer the phrase "language of set theory" is
that "language of ZFC" gives an undue prominence to a particular
axiomatic fragment of set theory, namely ZFC. I see no good
reason to single out ZFC as opposed to weaker theories (say
KP or Z) or stronger ones (say ZFC+"measurables exist").
The point is that all these theories have the same intended
objects of discourse; they just make fewer or more claims
*about* them. They are all in the same language, which by
social convention has a preferred interpretation; calling the
language "the language of set theory" acknowledges this. But
if you call it "the language of ZFC", then why did you choose
that name instead of "the language of KP"?
Aatu Koskensilta
> huus...@cc.helsinki.fi (Taneli Huuskonen) writes:
> : OK. I'm convinced that you're not stupid at all and that you know a
> : fair deal about logic. However, I've quite a bit of trouble
> : understanding what you're trying to say. Would you mind answering a few
> : questions to clarify your position?
>
>
> : 1. Do you feel you understand what people mean by "the language of set
> : theory", even though you object to such usage?
>
> Almost. The objection is vehemently ABOUT the very IDENTITY of
> "the" language in question, so admitting that I understand what
> their pointing at would be conceding too much.
Could you elaborate on this? The identity of the language vis-a-vis the
set of strings or in more general sense?
Are you aware of the fact that at least in the context of axiomatic set
theory the term "the language of set theory" is taken to refer to the
first order language {\epsilon} (where \epsilon is a binary predicate
symbol)? I doubt that many set theorists would hold that such a language
being called "the language of set theory" has any philosophical or
general conceptual implications.
It is of course true that there are theories which may validly be called
set theories which are not directly (and possibly not even indirectly)
expressible in this language. This does not render the usage invalid;
it's merely a convention.
> Whether I care enough to propose what "they" would say to convey
> this idea depends, of course, on whether this language or
> this idea is any good for anything.
>
> It isn't.
>
> In order for it to be any good for anything, it would have to
> *matter* that you *could* have *models* over it that *don't*
> conform to any particular set of axioms. And *that* is incoherent.
> The ONLY way you can say WHICH model over this language you MEAN
> *is* by stating some things that *have* to be true in it.
But *not* necessarily stating these things in the logic <"language of
set theory", complete FO deductive system, Tarskian semantics>. Saying
that the ordinals in a model M are exactly the real ordinals can't be
done in that language. There is simply no sentence which would be
equivalent to this condition in the class of models we're interested in
(or in any other class for that matter).
> And if you're highlighting (as opposed to ignoring) a "model over"
> this language where ExAy[~yex] comes up *false*, then what*ever*
> language this is, calling it "the language of set theory" gets ridiculous
> pretty fast, especially when it is isomorphic to every OTHER
> language with 1 unary functor and 1 binary predicate that
> does NOT spell them e and p (in ADDITION to not interpreting
> them set-like-ly).
Uhm. Calling the (equivalence class of all) language(s) with one binary
predicate the language is not silly at all. It is the language set
theories that concern us most in the study of axiomatic set theory are
represented. The fact that it's also "the language of the theory of
addition" and "the language of the theory of some specific but arbitrary
binary relation" does not render calling it "the language of set theory"
stupid or invalid.
> In order to make this *a* language of set theory, it has to
> be defined IN TERMS OF SOME *AXIOMS* that guarantee that something
> at least vaguely set-like is in fact going on among the truths
> and elements of the model. In that case it becomes proper to
> refer to the language as the one whose predicates and functors
> are those occurring IN THE AXIOM-SET. So I would ask people to
> talk about the language of ZFC or PA as *opposed* to the language
> of set theory or arithmetic, for the simple reason that +
> doesn't MEAN addition and O doesn't MEAN the empty set until
> AFTER they occur in some AXIOMS that would constrain them to mean that.
In order for a language to be called *a* language of set theory it
suffices that it *be* a language of *some* set theory, e.g. ZFC or NBG
or MK or ML or NF or what-not.
Calling {\epsilon} "the" language of set theory is not meant to imply
that there is something magical about the language, merely that it in
fact is the language in which most theories of sets of interest are in
fact expressed. There are other considerations, for example that set
theory might be seen as the study of structures with a binary relation
(usually with certain constraints on this binary relation), and thus it
is sensible to identify a language with a single binary relation as "the
" language of this discipline.
> Mike Oliver (who started it) had a REASON for NOT wanting to do
> this. He was originally trying to be scrupulous enough NOT to do
> this BECAUSE of the UNfortunate coincidence that THEORIES and
> LANGUAGES are BOTH sets-of-strings. He didn't want to refer to
> "the language of ZFC" because EVERY theory, being a set of strings,
> is, coincidentally, ALSO, a language. So to him, "the language of
> ZFC" and "the theory of ZFC" were supposed to MEAN THE SAME THING.
> To me, they don't. "ZFC" doesn't want to occur UNqualified unless
> context clearly disambiguates among the following 3 string-sets, in
> increasing order of size: the axiom-set, its closure under
> consequence (the theory), and the first-order langauge over the
> predicates and functors occurring in the axioms&theory (which I
> would call the language, or the 1st-order language, of/over ZFC).
> If I had meant the THEORY I would've *said* the theory; the fact
> that the theory is a language is simply not important or relevant
> enough to create an ambiguity problematic enough for Mike to be
> trying so hard to avoid it. Thinking that e & p are somehow
> "inherently", in virtue of their shape or orthography, about sets,
> is arguably the MORE dangerous mistake.
That would be a dangerous mistake, true. However, I don't think set
theorists are guilty of that. It's just that the practice of set theory
is to constantly use the language {\epsilon} and not, for example, the
language {\plus}. It's merely a convention. If you want you could use
any other language, for example one with humongous array of superfluous
relations of any arity, and that wouldn't be "wrong" in any fundamental
sense. It would be simply going against the common practice in the field.
The fact that one uses the language {\epsilon} is usually a good
*indication* that he's going to do set theory, and not for example
theory of linear orderings. But that is nothing but a common practice
and implies nothing about the particular symbols or languages used.
As a somewhat streched analogy, if I say English is the language of
computer science, I don't mean to say that there is some inherent
property of computer science that determines English as its language. I
mean to say that most of the publications in the field of computer
science are as a matter of fact written in a specialised English jargon.
> What relates these
> predicates and functors _to sets_ *IS* THE *AXIOMS*, NOT the kind
> of linguistic convention that names tea "tea" and cups "cups".
> THAT is arbitrary. The patterns in the axioms (up to commutativity
> anyway) are not. They are the content/expression of the relevant
> knowledge/structure.
The theory ZFC is in all relevant senses equivalent to the theory ZFC'
which we get if we replace all occurances of \epsilon in the formulae of
ZFC with \plus. There is no relation but arbitrary convention that
relates \epsilon to the membership relation. (Taneli Huuskonen provided
a telling analogy for teacups, which I believe makes the point of my
post very succintly).
<snip questions 3 and 4 and their answers to which I have nothing to say>
There is *nothing* in the world preventing you from restricting your
class of possible models to get a class of "intended" models. For
example, you might wish to study the implications of certain
constructivistic positions and restrict the class of possible models to
recursive models. You then find that, for example PA is categorical.
You lose certain other features, for example FO ceases to have
completeness theorem.
This approach (which stems from the model theoretic view of logic) has
the "difficulty" that the class of models *determines* the semantic
logical notions (logically implies, logically true, &c), and thus you
(in general) get a different logic for a different class of models.
This is somewhat easy to get over with, since instead of restricting
your "base logic", you simply consider a "language with intended
meaning" to be a tuple (ordinary FO language, class of permissible
models) and when considering a "language with intended meaning" you let
the "base logic" induce a logic over the class of permissible models of
that "language with intended meaning". Notice that the induced logic
does not in general preserve the properties of the "base logic".
I myself would say that the model theoretic view of logic which sees a
full logic as a family of 4-tuples (language, deductive system, class of
possible models, the holds-in-a-model-relation \subseteq class of
possible models \cartesian-product-with language) and which lends
naturally to consideration of possibly "restricted" classes of possible
models as a natural starting point for the study of logic. I don't
consider myself a foundationalist, and since it thus is not important to
me, I really don't have an opinion as to what this has to say about
whether this or that is more suitable foundation.
--
Aatu Koskensilta (aa...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
tc...@lsa.umich.edu
Aatu Koskensilta <aatu.kos...@xortec.fi> wrote:
>George Greene wrote:
>> Thinking that e & p are somehow
>> "inherently", in virtue of their shape or orthography, about sets,
>> is arguably the MORE dangerous mistake.
>
>That would be a dangerous mistake, true. However, I don't think set
>theorists are guilty of that.
In general I am in agreement with the majority view here and opposed to
George Greene's position. *However*, I would say that for *pedagogical*
purposes, emphasizing George Greene's points is good. I know that when
I was learning the subject, I often got confused when people did things
like refer to such-and-such as the "first-order language of arithmetic,"
because I wasn't sure whether their use of the symbols "+" and "*" meant
that they were automatically assuming some axioms about those things
whether they were just arbitrary binary symbols that happened to be
shaped suggestively. Now you might say that if a student is confused
then he or she should ask someone, but the problem is that sometimes
(1) the student has nobody to ask, (2) the textbook doesn't make the
assumptions clear, and (3) the student may not even understand his own
confusion well enough to be able to articulate the right question.
tc...@lsa.umich.edu
Taneli Huuskonen <huus...@cc.helsinki.fi> wrote:
>In <asdafk$8ge$1...@galois.mit.edu> tc...@lsa.umich.edu writes:
>>1. Someone said that the theory of the definable reals is the theory of
>> real closed fields. I'm still looking for a proof/reference.
>
>I haven't checked it, but it seems to me that the proof must be quite
>straightforward. For instance, if phi and psi define reals a and b,
>respectively, then the formula (Ex) (Ey) (phi(x) & psi(y) & z=x+y)
>defines their sum, and likewise for every real whose existence is
>asserted by the axioms of RCF's.
I see. I guess I had misinterpreted the claim to be something like:
In any model of ZFC, the set of definable subsets of omega forms a field.
In this formulation it's not even immediately clear what the field
operations are or how one defines them.
>I think L_{\omega_1\omega} can express "x is first-order definable". It
>can't express "x is L_{\omega_1\omega} definable", though.
Then it would seem that one natural way to formalize Mike Oliver's
statement that "informally, it's clear that the set [of first-order
definable reals in V] exists" would be to use L_{omega_1 omega}, so that
the statement can actually be expressed. But then before one can *prove*
this statement, one needs to choose a sequent calculus, and as I recall
there is no completeness theorem for this logic. Yuck.
George Greene
: George Greene wrote:
: > Mike Oliver (who started it) had a REASON for NOT wanting to do
: > this. He was originally trying to be scrupulous enough NOT to do
: > this BECAUSE of the UNfortunate coincidence that THEORIES and
: > LANGUAGES are BOTH sets-of-strings. He didn't want to refer to
: > "the language of ZFC" because EVERY theory, being a set of strings,
: > is, coincidentally, ALSO, a language.
Mike Oliver <oli...@math.ucla.edu> writes:
: No, unless I'm misunderstanding you, that is not what I meant
: at all; that is not it, at all.
It is so, too, and you are reiterating your meaning it, below.
: The reason I prefer the phrase "language of set theory" is
: that "language of ZFC" gives an undue prominence to a particular
: axiomatic fragment of set theory, namely ZFC.
You are using "fragment" in a sense EXACTLY equivalent to
"subset", i.e., the theory, ZFC, is a language, and is a subset
of a bigger language, namely, the set of all strings in
"the language of set theory" that happen to come out "true in
[Platonic] real life", in the "noumenal reality" of sets.
"language of ZFC" doesn't give "undue" prominence to anything.
It isn't ABOUT the THEORY (THAT is the fragment)! It is about
THE AXIOM-SET! What (*my*) calling the language "the language
of ZFC" *does* do is ask you to name your membership-predicate
the same way Zermelo named his.
: I see no good reason to single out ZFC as opposed to weaker
: theories (say KP or Z) or stronger ones (say ZFC+"measurables exist").
When *I* say "the language of ZFC", the ZFC occurring in
that referring-expression IS NOT referring to the THEORY!
It is referring to the AXIOM-SET! The THEORY is a fragment!
The AXIOM-SET is something far too small to be confused with
that. The THEORY of ZFC *is* a language, so if YOU say
"the language of ZFC" in a context where you think "ZFC"
means a theory, it is OBVIOUS that you are risking confusion
(that's why you won't say it).
: The point is that all these theories have the same intended
: objects of discourse;
That's just a damn lie.
I *knew* there was a core philosophical disagreement under here
somewhere, and there it is.
First-order theories can have any old domains or any old
objects of discourse that you like, as long as the domains
have *enough* objects (denumerably many is ALWAYS enough).
They are NOT about any intended objects of discourse. The alleged
proposed intended objects of discourse are OFTEN discovered
never-to-have-even-existed in the first place (the set of all sets
that don't contain themselves, e.g.); and far more importantly, the
theory often turns out to have models that are provably DRASTICALLY
different from the alleged intended objects of discourse
(non-Euclidean geometry, non-standard integers in PA, etc.).
: they just make fewer or more claims *about* them.
Making fewer claims means that MORE objects than JUST
the original intended ones MIGHT turn out to be able to
participate in models of the theory (again, non-Euclidean
geometry).
: They are all in the same language, which by
: social convention has a preferred interpretation;
This is a complete crock of shit. The language does NOT NEED any
"preferred interpretation" in terms of its "intended objects of
discourse" IF it is derived FROM AN AXIOM-SET! In THAT case, ALL
objects that can occur in ANY models of the language are
LEGITIMATELY its "objects of discourse". As for "preferred
interpretations", you are JUST LYING. There is no unique preferred
interpretation. There are plenty of DIFFERENT interpretations
available EVEN if you *restrict* yourself to interpretations
satisfying the axioms! The kind of "restriction" that *I* am
trying to impose by asking for the language to be defined in terms
of the terms-occuring-in-some-axioms is simply one that justifies
(far better than any social convention ever could, other than the
social convention that got the axioms phrased with their particular
symbols in the first place, which convention was in fact usually
NOT social but AUTHORIAL) referring to the symbols in their usual
roles, i.e. thinking of epsilon as meaning membership and rho as
meaning powerset, as OPPOSED TO THE OTHER WAY AROUND, e.g.
: calling the language "the language of set theory" acknowledges this.
Of course it does, but since "this" is utter bullshit,
why would I want to be encouraging it?
: But if you call it "the language of ZFC", then why did you choose
: that name instead of "the language of KP"?
I haven't seen a full axiom-set for KP.
Isn't that really a DIFFERENT language? Isn't
THAT axiom-set normally phrased in terms including at
least one predicate or functor that DOESN'T occur in
the usual phrasing of ZFC?
Mike Oliver
> When *I* say "the language of ZFC", the ZFC occurring in
> that referring-expression IS NOT referring to the THEORY!
> It is referring to the AXIOM-SET!
I can't see how that's relevant to what I was saying. The language
is no more specifically connected to a set of axioms than it
is to that set's closure under logical consequence.
> The THEORY is a fragment!
> The AXIOM-SET is something far too small to be confused with
> that. The THEORY of ZFC *is* a language, so if YOU say
> "the language of ZFC" in a context where you think "ZFC"
> means a theory, it is OBVIOUS that you are risking confusion
> (that's why you won't say it).
No, that's not it, because it's quite rare for me to use
the word "language" in the (Post?) sense of "collection of
strings". I'm using it rather in the (Tarski?) sense
where a language has constant symbols, function symbols,
and relation symbols, which can be combined with the
logical symbols (quantifiers, variables, equals sign,
parentheses) in certain ways. "The theory of ZFC" is
not a language in the sense that I'm using the word "language",
so there's no risk of confusion there.
> First-order theories can have any old domains or any old
> objects of discourse that you like, as long as the domains
> have *enough* objects (denumerably many is ALWAYS enough).
> They are NOT about any intended objects of discourse.
Arbitrary first-order theories in general, no. But
number theory *is* and set theory *is*. You can strip
the meaning away from them and consider them simply
as formal theories, and this is sometimes useful when
you're doing metamathematics.
> The alleged
> proposed intended objects of discourse are OFTEN discovered
> never-to-have-even-existed in the first place
All that proves is that we can be wrong. I'm happy to
agree that we can be wrong. If you're looking for a priori
justified certainties, I have none to offer; my view is
that it is a grave error to consider mathematics to be made
up of such certainties.
> (the set of all sets
> that don't contain themselves, e.g.); and far more importantly, the
> theory often turns out to have models that are provably DRASTICALLY
> different from the alleged intended objects of discourse
> (non-Euclidean geometry, non-standard integers in PA, etc.).
PA has nonstandard models, ZFC has nonstandard models. They're
called "nonstandard" for a reason.
> I haven't seen a full axiom-set for KP.
> Isn't that really a DIFFERENT language?
You may be thinking of KM (Kelley-Morse), which is a theory
in second-order LST. KP is written in vanilla first-order LST;
it's like ZF(C?) except that the Separation schema is
restricted to Sigma_0 predicates and Replacement to Sigma_1,
or maybe it's the other way around.
George Greene
: Are you aware of the fact that at least in the context of axiomatic
: set theory the term "the language of set theory" is taken to refer
: to the first order language {\epsilon} (where \epsilon is a binary
: predicate symbol)?
This is a stupid question for you to be asking *me*. *I* was
the one who said that what people were calling "the language of
set theory" was *really* just a first-order language with one binary
predicate.
You, on the other hand, are assigning some sort of special
prominence to the one of those that uses epsilon to denote
the predicate. All I am saying is that without some sort
of context (e.g.: epsilon is the name for the predicate that
was used in the axiom-set that was explicitly designed and
promulgated to investigate the field, by somebody who was
smart enough and deservedly respected enough to get HIS names
for things RESPECTED), there is nothing especially set-like
about this language, or this symbol. It is trivially easy
to interpret it in ways that leave you talking about things
entirely non-set-like.
: I doubt that many set theorists would hold that
: such a language being called "the language of set theory" has any
: philosophical or general conceptual implications.
In the first place, they DON'T hold that "such a language"
is called anything: they hold that ONE PARTICULAR language
(the one where the predicate is NAMED epsilon) is called that.
"Such a" language could be any other first-order language with
one binary predicate, even if it was spelled "=". Considered
purely as languages they ARE *isomorphic*, you know.
: It is of course true that there are theories which may validly be
: called set theories which are not directly (and possibly not even
: indirectly) expressible in this language. This does not render the
: usage invalid; it's merely a convention.
It's also irrelevant. The relevant point is that set theories
can be expressed in an infinitude of OTHER langauges that just
happen to SPELL membership and powerset DIFFERENTLY. ALL THOSE
languages are EQUALLY entitled to be languages of set theory except
for the ones that have symbols that are traditionally busy being
interpreted in other ways (like =, although even that is curable
if you just migrate to first-order-logic-WITH-equality).
: > In order for it to be any good for anything, it would have to
: > *matter* that you *could* have *models* over it that *don't*
: > conform to any particular set of axioms. And *that* is incoherent.
: > The ONLY way you can say WHICH model over this language you MEAN
: > *is* by stating some things that *have* to be true in it.
:
: But *not* necessarily stating these things in the logic <"language
: of set theory", complete FO deductive system, Tarskian
: semantics>.
Of course not! For purposes of THIS part, it hardly MATTERS how
you state them. The point is simply that functionally, those
things are playing the role of axioms.
: Saying that the ordinals in a model M are exactly the
: real ordinals can't be done in that language.
You're right, and that is A GOOD THING, simply because
"the real ordinals" is just plain MEANINGLESS.
An ordinal is an object in a domain of a theory that
defines ordinals. None of those objects are any more
"real" as ordinals than any others.
: There is simply no
: sentence which would be equivalent to this condition in the class
: of models we're interested in (or in any other class for that
: matter).
What condition?
: Uhm. Calling the (equivalence class of all) language(s) with one
: binary predicate the language is not silly at all.
It IS SO TOO, dammit. The equivalence class of all x's is
OFTEN not an x, and in the case of languages, that's even truer.
More to the point, if you are going to say that the equivalence
class of all langauges with 1 binary predicate is "the" language
of set theory, what are you going to say vs. those who respond,
"no, by convention, tlost is only ONE of those languages, namely
the one that assigns the name epsilon to the predicate"? Since YOU
YOURSELF said that very thing at the beginning, you are looking
DAMN STUPID, here. *I*, *NOT* you, am the one who is taking the
side that the whole equivalence class of languages are all created
equal.
: It is the language set theories that concern us most in the study of
: axiomatic set theory are represented.
No, really, it isn't. The usual mode of representation does
NOT eliminate the definitions of equality, subset, or powerset
(powerset, for reasons you are overlooking, actually MUST not be
eliminated).
: The fact that it's also "the
: language of the theory of addition" and "the language of the theory
: of some specific but arbitrary binary relation" does not render
: calling it "the language of set theory" stupid or invalid.
Yes, actually, IT DOES, and you can DAMN WELL BETCHA that
if you started going around writing 1 e 1 = 2, or O + {O} = true,
that people would accuse you not only of violating social conventions,
but of speaking the wrong language.
: In order for a language to be called *a* language of set theory it
: suffices that it *be* a language of *some* set theory, e.g. ZFC or
: NBG or MK or ML or NF or what-not.
Exactly! But that is MY position, NOT YOURS.
In order to get to this position, you have to ask yourself,
what does it MEAN for ANY language to be a language "of"
ZFC, as opposd to of MK, ML, or NBG? Conventionally,
all 5 of these set theories might be in the SAME language;
epsilon might be the ONLY predicate needed by all 5 of them.
In practice, however, the languages could come up DIFFERENT
because they might be TRADITIONALLY PRESENTED using DIFFERENT
axiom-sets that use DIFFERENT names for certain things. In that
case, THAT social convention (of how NF usually spells things,
e.g) would start to MATTER.
: Calling {\epsilon} "the" language of set theory is not meant to
: imply that there is something magical about the language, merely
: that it in fact is the language in which most theories of sets of
: interest are in fact expressed.
No, you are lying.
What you *meant* to say was that "Calling epsilon "the"
language of set theory is not meant to imply that there is something
magical about the language, but merely that if you want to talk
about sets, you should name your binary predicate epsilon in
order to conform to social convention, so that people will legitimately
EXPECT you to be talking about sets as OPPOSED to Equality or some
other theory that ALSO only needs 1 binary predicate".
: There are other considerations, for
: example that set theory might be seen as the study of structures
: with a binary relation (usually with certain constraints on this
: binary relation), and thus it is sensible to identify a language
: with a single binary relation as "the " language of this discipline.
No, it is not sensible, since precisely as YOU Pointed out, ALL
those languages are in the SAME equivalence class, and YOU were just,
above, trying to defend the position that the WHOLE equivalence class
was THE language (when YOU said: "Uhm. Calling the (equivalence class
of all) language(s) with one binary predicate the language is not silly
at all."). In the praxis of mathematicians generally, that WOULD be
silly: to them, it is IMPORTANT that "the language of set theory"
and "the language of equality" be DIFFERENT languages EVEN though,
by virtue of needing only 1 binary predicate, they are isomorphic
and both in this equivalence class. You are STILL expected to
use = if you want to talk about equality and epsilon if you want
to talk about membership! Violating this expectation will get
your work almost completely ignored! If you submit a paper reversing
the convention they will just laugh at you and tell you to
conform! They may even publish it with the symbols corrected without
even asking your permission (assuming they are un-confused enough
to realize what you have done).
: > Thinking that e & p are somehow
: > "inherently", in virtue of their shape or orthography, about sets,
: > is arguably the MORE dangerous mistake.
: That would be a dangerous mistake, true. However, I don't think set
: theorists are guilty of that.
Well, YOU PERSONALLY are, otherwise you wouldn't be arguing with me.
: It's just that the practice of set
: theory is to constantly use the language {\epsilon} and not, for
: example, the language {\plus}.
That is not "*just*...the practice of set theory".
: It's merely a convention.
It is a convention but it is NOT *merely* a convention!
It CAME from somewhere! There is a CAUSAL explanation for it!
There is a REASON WHY set-theorists "always" use epsilon for
their binary relation as opposed to letting it change with
the phase of the moon, or "always" using something OTHER than
epsilon. And the REASON is that epsilon was what occurred
in ZFC *as* ZFC was being presented and *as* it was getting
*baptized* as ZFC! It is what occurred in Zermelo's papers in 1904-08.
: If you
: want you could use any other language, for example one with
: humongous array of superfluous relations of any arity, and that
: wouldn't be "wrong" in any fundamental sense.
It would be a completely different language. To the extent
that it had things that were superfluous, that were not NEEDED
for set theory, it WOULD be the WRONG language.
: The fact that one uses the language {\epsilon} is usually a good
: *indication* that he's going to do set theory, and not for example
: theory of linear orderings.
Exactly.
: But that is nothing but a common
: practice and implies nothing about the particular symbols or
: languages used.
It's really not possible to imply ANYthing relevant about a symbol.
In their roles as names for predicates, symbols are ARBITRARY.
: As a somewhat streched analogy, if I say English is the language of
: computer science, I don't mean to say that there is some inherent
: property of computer science that determines English as its
: language. I mean to say that most of the publications in the field
: of computer science are as a matter of fact written in a
: specialised English jargon.
That analogy is strecthed past breaking.
: > What relates these
: > predicates and functors _to sets_ *IS* THE *AXIOMS*, NOT the kind
: > of linguistic convention that names tea "tea" and cups "cups".
: > THAT is arbitrary. The patterns in the axioms (up to commutativity
: > anyway) are not. They are the content/expression of the relevant
: > knowledge/structure.
:
: The theory ZFC is in all relevant senses equivalent to the theory
: ZFC' which we get if we replace all occurances of \epsilon in the
: formulae of ZFC with \plus. There is no relation but arbitrary
: convention that relates \epsilon to the membership
: relation. (Taneli Huuskonen provided a telling analogy for teacups,
: which I believe makes the point of my post very succintly).
Then why are you taking 288 lines? For that much you had BETTER
have some newer, better points. I have already rebutted the teacup
analogy (in the small, anyway; in the large it is basically a well-
scored point).
Then, there follows a separate thread.
: > Perhaps my question will be clearer if instead of talking about
: > the
: > existence of a model connoting consistency, I talk about the
: > inverse of that and say instead that if *no* "model" assigns true
: > to all the axioms, then the axiom set _has no_ model (canonical
: > usage, no scare-quotes). In other words, as far as this axiom-set
: > is concerned, EVERY "model" is NOT a model! This is within 1 set
: > of quotes of violating reflexivity of equality. I mean, if I took
: > the gloves (quotes) off and said "this shows that every model is
: > not a model", it would be clear that I have the right to be
: > confused, right?
:
: There is *nothing* in the world preventing you from restricting
: your class of possible models to get a class of "intended"
: models.
The question was about an alternative to the *word* "model".
In the above, I talked about a model *of* an axiom-set, *without*
quotes around model, and conTRASTED that with a "model" *over*
a language. This is not a similar kind of use of "model" for
the simple reason that a model _of_, without quotes, must make
all the statements in the set-that-it's-a-model-of *true*, while
a "model" *over* (my poor locution; you were asked for a better one)
a *language* canNOT do that since first-order languages in general
include denial as a statement-constructor (they cannot make both
P *and* ~P true, even though P and ~P are both in the language
that the "model" is "over").
If we could shoehorn you into the framework of the question that
was actually posed, you would seem to be advocating christening
what-I-have-called-a-"model over" as a "possible model". This is
a little lame, simply because, for inconsistent axiom-sets,
NO "model" is even POSSIBLY a model *of* them. "Models" *over* the
whole language involve a slightly different use of the word,
from the one occuring when speaking of models (no quotes, possible
OR impossible) *of* particular axiom-sets.
: For example, you might wish to study the implications of
: certain constructivistic positions and restrict the class of
: possible models to recursive models. You then find that, for
: example PA is categorical.
This is ridiculous. The canonical non-standard model of PA
is certainly recursive in at least one typical usual sense.
It is N + Z. The integers are certainly simple enough to be recursive.
If constructivists mean something other than TM-decidable by
"recursive" then I *really* don't want to hear it.
: You lose certain other features, for example FO ceases to have
: completeness theorem.
I'm sorry; this is just plain not interesting to me;
I'm from a curmudgeonly school that insists that if it
doesn't have a completeness theorem then you shouldn't
be calling it a "logic" at all. The only reason for putting
up with all the rest of FOL's shortcomings is that it DOES
have a completeness theorem. If you are going to move to
something that doesn't then it better get you a lot more.
tc...@lsa.umich.edu
George Greene <gre...@swift.cs.unc.edu> wrote:
>This is ridiculous. The canonical non-standard model of PA
>is certainly recursive in at least one typical usual sense.
>It is N + Z. The integers are certainly simple enough to be recursive.
What is the "canonical nonstandard model of PA"? Neither + nor * is
recursive in any countable nonstandard model of PA, by Tennebaum's
theorem, so you must mean something else.
Aatu Koskensilta
> Aatu Koskensilta <aatu.kos...@xortec.fi> writes:
> : Are you aware of the fact that at least in the context of axiomatic
> : set theory the term "the language of set theory" is taken to refer
> : to the first order language {\epsilon} (where \epsilon is a binary
> : predicate symbol)?
>
> This is a stupid question for you to be asking *me*. *I* was
> the one who said that what people were calling "the language of
> set theory" was *really* just a first-order language with one binary
> predicate.
Getting into this thread in the middle I thought there might be some
reason you found saying that a language with a binary predicate usually
denoted by epsilon by convention being "the language of set theory"
> You, on the other hand, are assigning some sort of special
> prominence to the one of those that uses epsilon to denote
> the predicate. All I am saying is that without some sort
> of context (e.g.: epsilon is the name for the predicate that
> was used in the axiom-set that was explicitly designed and
> promulgated to investigate the field, by somebody who was
> smart enough and deservedly respected enough to get HIS names
> for things RESPECTED), there is nothing especially set-like
> about this language, or this symbol. It is trivially easy
> to interpret it in ways that leave you talking about things
> entirely non-set-like.
And? Saying that the language is "the language of set theory" does not
imply that there is something particularly "set-like" about it. It's
merely saying that it's the language in which most of the interesting
set theories *are* expressed.
And the reason people don't go about adding the qualification "And of
course we could use another predicate symbol and not epsilon, and we're
implicitly assuming here that when other people speak of the language of
set theory they're speaking about the same language as we're doing here"
is that *it simply does not matter*.
Perhaps you can think of it this way: pick a language with a binary
predicate symbol (any language will do), and start calling it the
canonical language of set theory and denoting the symbol with an
epsilon. Now we have a convenient arbitrarily specified common language,
and we needn't bother every time we do axiomatic set theory to state
that the language in which the theory we're working with is in fact
isomorphic in all relevant respects to all the languages other people's
set theories have been expressed in.
What's wrong with this?
> : I doubt that many set theorists would hold that
> : such a language being called "the language of set theory" has any
> : philosophical or general conceptual implications.
>
> In the first place, they DON'T hold that "such a language"
> is called anything: they hold that ONE PARTICULAR language
> (the one where the predicate is NAMED epsilon) is called that.
And they also hold that the ordinal 1 is {{}}. How evil.
> "Such a" language could be any other first-order language with
> one binary predicate, even if it was spelled "=". Considered
> purely as languages they ARE *isomorphic*, you know.
Oh for crying out loud. If this really bothers you, consider epsilon as
a *name* that stands for an arbitrary binady predicate symbol, not as
the symbol itself. For axiomatic set theory this makes absolutely no
difference. Or prepend the following to all set theoretic texts you read:
In what follows we shall use a language {\Phi} where \Phi is
an arbitrary binary predicate symbol. We shall refer to \Phi as
\epsilon.
> : It is of course true that there are theories which may validly be
> : called set theories which are not directly (and possibly not even
> : indirectly) expressible in this language. This does not render the
> : usage invalid; it's merely a convention.
>
> It's also irrelevant. The relevant point is that set theories
> can be expressed in an infinitude of OTHER langauges that just
> happen to SPELL membership and powerset DIFFERENTLY.
This *really* is irrelevant.
> ALL THOSE
> languages are EQUALLY entitled to be languages of set theory except
> for the ones that have symbols that are traditionally busy being
> interpreted in other ways (like =, although even that is curable
> if you just migrate to first-order-logic-WITH-equality).
Yes. You seem to have an uncommon fixation to symbols here. I have
always when reading texts on axiomatic set theory taken {\epsilon}
simply to mean some (unspecified) canonical language in which to do set
theory. It very seldom matters what the actual predicate symbols are,
apart from very elementary introductory FO. We could do with R_1^1,
R_1^2, ..., R_n^m (for all n and m \in N) where R is some specified
mathematical object, but even if we did, we'd soon be giving convenient
names to some of these, and others would follow (even though in their
particular expositions the name might not correspond to the exact same
R_i^k).
> : > In order for it to be any good for anything, it would have to
> : > *matter* that you *could* have *models* over it that *don't*
> : > conform to any particular set of axioms. And *that* is incoherent.
> : > The ONLY way you can say WHICH model over this language you MEAN
> : > *is* by stating some things that *have* to be true in it.
> :
> : But *not* necessarily stating these things in the logic <"language
> : of set theory", complete FO deductive system, Tarskian
> : semantics>.
>
> Of course not! For purposes of THIS part, it hardly MATTERS how
> you state them. The point is simply that functionally, those
> things are playing the role of axioms.
>
> : Saying that the ordinals in a model M are exactly the
> : real ordinals can't be done in that language.
>
> You're right, and that is A GOOD THING, simply because
> "the real ordinals" is just plain MEANINGLESS.
Do you think there is no set theory apart from axiomatic set theory in
the formal sense?
> An ordinal is an object in a domain of a theory that
> defines ordinals. None of those objects are any more
> "real" as ordinals than any others.
>
> : There is simply no
> : sentence which would be equivalent to this condition in the class
> : of models we're interested in (or in any other class for that
> : matter).
>
> What condition?
Containing the real ordinals.
> : Uhm. Calling the (equivalence class of all) language(s) with one
> : binary predicate the language is not silly at all.
>
> It IS SO TOO, dammit. The equivalence class of all x's is
> OFTEN not an x, and in the case of languages, that's even truer.
> More to the point, if you are going to say that the equivalence
> class of all langauges with 1 binary predicate is "the" language
> of set theory, what are you going to say vs. those who respond,
> "no, by convention, tlost is only ONE of those languages, namely
> the one that assigns the name epsilon to the predicate"? Since YOU
> YOURSELF said that very thing at the beginning, you are looking
> DAMN STUPID, here. *I*, *NOT* you, am the one who is taking the
> side that the whole equivalence class of languages are all created
> equal.
I do think that all of those languages are equal. We single implicitly
an arbitrary language out of the bunch for our purposes and call it
{\epsilon} or "the language of set theory" simply because it makes
things easier. We could speak of the equivalence class and denote *it*
by {\epsilon} if we for some bizarre reason wished to, and with trivial
modifications all proofs would come out valid.
> : It is the language set theories that concern us most in the study of
> : axiomatic set theory are represented.
>
> No, really, it isn't. The usual mode of representation does
> NOT eliminate the definitions of equality, subset, or powerset
> (powerset, for reasons you are overlooking, actually MUST not be
> eliminated).
Why?
> : The fact that it's also "the
> : language of the theory of addition" and "the language of the theory
> : of some specific but arbitrary binary relation" does not render
> : calling it "the language of set theory" stupid or invalid.
>
> Yes, actually, IT DOES, and you can DAMN WELL BETCHA that
> if you started going around writing 1 e 1 = 2, or O + {O} = true,
> that people would accuse you not only of violating social conventions,
> but of speaking the wrong language.
If you did this formally, i.e. introduced the language, provided the
axioms and presented those as theorems, I doubt no one would say you're
speaking the wrong language. If, however, in the middle of a paper of
axiomatic set theory you suddenly wrote "{a,b} + {a,b,{a,b}}" you would
surely be accused of idiosyncronic usage and asked why on earth are you
using such a strange symbolism.
I myself like to think of \subset, \in, \powerset, etc, as names for
arbitrary, but unspecified, predicate symbols. Thus I see the situation
being that mathematicians have agreed by convention on these names, and
couldn't care less about the actual willy-nilly predicate symbols they
happen to name. Really, why should they care?
> : In order for a language to be called *a* language of set theory it
> : suffices that it *be* a language of *some* set theory, e.g. ZFC or
> : NBG or MK or ML or NF or what-not.
>
> Exactly! But that is MY position, NOT YOURS.
I'm sorry I stole your position.
> In order to get to this position, you have to ask yourself,
> what does it MEAN for ANY language to be a language "of"
> ZFC, as opposd to of MK, ML, or NBG? Conventionally,
> all 5 of these set theories might be in the SAME language;
> epsilon might be the ONLY predicate needed by all 5 of them.
> In practice, however, the languages could come up DIFFERENT
> because they might be TRADITIONALLY PRESENTED using DIFFERENT
> axiom-sets that use DIFFERENT names for certain things. In that
> case, THAT social convention (of how NF usually spells things,
> e.g) would start to MATTER.
I don't see how this is relevant.
> : Calling {\epsilon} "the" language of set theory is not meant to
> : imply that there is something magical about the language, merely
> : that it in fact is the language in which most theories of sets of
> : interest are in fact expressed.
>
> No, you are lying.
> What you *meant* to say was that "Calling epsilon "the"
> language of set theory is not meant to imply that there is something
> magical about the language, but merely that if you want to talk
> about sets, you should name your binary predicate epsilon in
> order to conform to social convention, so that people will legitimately
> EXPECT you to be talking about sets as OPPOSED to Equality or some
> other theory that ALSO only needs 1 binary predicate".
Oh for fucks sake, for most mathematical purposes all languages with a
single binary predicate are equivalent, so saying that {\epsilon} is the
language of most set theories implies the module isomorphism
qualification. No one in his right mind would start quarreling about
whether it should be epsilon or some other greek letter. That would not
be considered a disagreement of substance but of notation.
> : There are other considerations, for
> : example that set theory might be seen as the study of structures
> : with a binary relation (usually with certain constraints on this
> : binary relation), and thus it is sensible to identify a language
> : with a single binary relation as "the " language of this discipline.
>
> No, it is not sensible, since precisely as YOU Pointed out, ALL
> those languages are in the SAME equivalence class, and YOU were just,
> above, trying to defend the position that the WHOLE equivalence class
> was THE language (when YOU said: "Uhm. Calling the (equivalence class
> of all) language(s) with one binary predicate the language is not silly
> at all."). In the praxis of mathematicians generally, that WOULD be
> silly: to them, it is IMPORTANT that "the language of set theory"
> and "the language of equality" be DIFFERENT languages EVEN though,
> by virtue of needing only 1 binary predicate, they are isomorphic
> and both in this equivalence class.
True. I should have thought more carefully. In contexts where you need
to distinct languages with a binary predicate you can't use the
equivalence class. But the more natural model of simply picking a
canonical (but unspecified, since specifics are not needed) arbitrary
language for, say, equality and {\epsilon} and such will do.
> You are STILL expected to
> use = if you want to talk about equality and epsilon if you want
> to talk about membership! Violating this expectation will get
> your work almost completely ignored! If you submit a paper reversing
> the convention they will just laugh at you and tell you to
> conform! They may even publish it with the symbols corrected without
> even asking your permission (assuming they are un-confused enough
> to realize what you have done).
And what's wrong with this? If an astronomer tried to publish a paper in
which he called Moon the Sun, Mars Mercurius and Earth Moon, he would be
laughed at and his paper would be rejected. Linguistic conventions are
not unimportant or useless even though they are to an extent arbitrary.
> : > Thinking that e & p are somehow
> : > "inherently", in virtue of their shape or orthography, about sets,
> : > is arguably the MORE dangerous mistake.
>
> : That would be a dangerous mistake, true. However, I don't think set
> : theorists are guilty of that.
>
> Well, YOU PERSONALLY are, otherwise you wouldn't be arguing with me.
I'm arguing with you because I'm stupid enough.
> : It's just that the practice of set
> : theory is to constantly use the language {\epsilon} and not, for
> : example, the language {\plus}.
>
> That is not "*just*...the practice of set theory".
What is it, then?
> : It's merely a convention.
>
> It is a convention but it is NOT *merely* a convention!
> It CAME from somewhere! There is a CAUSAL explanation for it!
> There is a REASON WHY set-theorists "always" use epsilon for
> their binary relation as opposed to letting it change with
> the phase of the moon, or "always" using something OTHER than
> epsilon. And the REASON is that epsilon was what occurred
> in ZFC *as* ZFC was being presented and *as* it was getting
> *baptized* as ZFC! It is what occurred in Zermelo's papers in 1904-08.
Epsilon was used *before* ZF and ZFC were born. I fail to see the
relevance, though.
> : If you
> : want you could use any other language, for example one with
> : humongous array of superfluous relations of any arity, and that
> : wouldn't be "wrong" in any fundamental sense.
>
> It would be a completely different language. To the extent
> that it had things that were superfluous, that were not NEEDED
> for set theory, it WOULD be the WRONG language.
No, it would not be the "wrong" language. It would be a silly choice for
a language of set theory, but not wrong in any sense.
I don't know if my points are newer or better. I'm beginning to wonder
why I ever bothered to reply to a post of yours again.
I don't see what this has to do with your orginal question and with my
attempt at answering it.
> If we could shoehorn you into the framework of the question that
> was actually posed, you would seem to be advocating christening
> what-I-have-called-a-"model over" as a "possible model". This is
> a little lame, simply because, for inconsistent axiom-sets,
> NO "model" is even POSSIBLY a model *of* them. "Models" *over* the
> whole language involve a slightly different use of the word,
> from the one occuring when speaking of models (no quotes, possible
> OR impossible) *of* particular axiom-sets.
I don't understand why there being inconsistent axiom sets renders the
suggestion that a "language with intended meaning" might be defined as
tuple <ordinary FO language, class of permitted models> invalid.
> : For example, you might wish to study the implications of
> : certain constructivistic positions and restrict the class of
> : possible models to recursive models. You then find that, for
> : example PA is categorical.
>
> This is ridiculous. The canonical non-standard model of PA
> is certainly recursive in at least one typical usual sense.
> It is N + Z.
Uhm. This is not a model of PA. It seems to me it is a ("nonstandard")
model of Presburger arithmetic.
> The integers are certainly simple enough to be recursive.
> If constructivists mean something other than TM-decidable by
> "recursive" then I *really* don't want to hear it.
For a model to be "recursive" it suffices that the relations that
interprete the predicate symbols be recursive. All such models of PA are
isomorphic.
> : You lose certain other features, for example FO ceases to have
> : completeness theorem.
>
> I'm sorry; this is just plain not interesting to me;
> I'm from a curmudgeonly school that insists that if it
> doesn't have a completeness theorem then you shouldn't
> be calling it a "logic" at all.
Well, you're entitled to that opinion.
> The only reason for putting
> up with all the rest of FOL's shortcomings is that it DOES
> have a completeness theorem. If you are going to move to
> something that doesn't then it better get you a lot more.
It usually does. For example, enough expressiveness to actually define
certain structures that are of interest to mathematics.
Mike Oliver
> In article <xes65ua...@swift.cs.unc.edu>,
> George Greene <gre...@swift.cs.unc.edu> wrote:
>> This is ridiculous. The canonical non-standard model of PA
>> is certainly recursive in at least one typical usual sense.
>> It is N + Z. The integers are certainly simple enough to be recursive.
>
> What is the "canonical nonstandard model of PA"? Neither + nor * is
> recursive in any countable nonstandard model of PA, by Tennebaum's
> theorem, so you must mean something else.
What I suspect George is slightly misremembering is that the
order type of the elements of a nonstandard countable model
of PA is always N + Q*Z, where by Q*Z I mean the lexicographic
order of pairs (q,n) where q is rational and n \in Z. Of
course that just gives you that the *elements* can be given
recursively and their *order* is a recursive predicate; doesn't
say anything about + or *.
I'm curious about this Tennenbaum thing, though; I never
got around to learning about that. Can the idea be boiled
down to a short post? Also, Hofstadter in _Goedel,Escher,Bach_
seems to say that either + or * can be recursive but not
both in the same model. Did he just get that wrong?
Mike Oliver
> Also, Hofstadter in _Goedel,Escher,Bach_
> seems to say that either + or * can be recursive but not
> both in the same model.
I probably should have said "not both with respect to the same
enumeration of the same model". What he writes, as I remember
it, suggests that there might be different enumerations of
the same model, with respect to one of which + is recursive,
and * recursive wrt the other.
tc...@lsa.umich.edu
Mike Oliver <oli...@math.ucla.edu> wrote:
>Mike Oliver wrote:
>> Also, Hofstadter in _Goedel,Escher,Bach_
>> seems to say that either + or * can be recursive but not
>> both in the same model.
He got it wrong. I haven't looked at the proof myself, and can only point
you to the following old articles for more info.
http://www.google.com/groups?selm=y8zn1xqm9ze.fsf%40orion.ai.mit.edu&oe=UTF-8
http://www.google.com/groups?selm=5vaiki%24h1o%40gap.cco.caltech.edu&oe=UTF-8
I'm not sure exactly how Hofstadter got the "Heisenberg uncertainty"
misstatement.
George Greene
: > that referring-expression IS NOT referring to the THEORY!
: > It is referring to the AXIOM-SET!
Mike Oliver <oli...@math.ucla.edu> writes:
: I can't see how that's relevant to what I was saying.
It's relevant in that something as small as an axiom-set
is not as likely to be thought of as a "language" (and
is therefore less likely to be dismissed as the "wrong"
language, which was your rationale for being unwilling
to say "the language of ZFC").
: The language is no more specifically connected to a set
: of axioms than it is to that set's closure under logical
: consequence.
That's MY point. It is in turn no more connected
to either of those THAN it is to whatever "Tarskian
mode of specification" you are going to describe below.
: > The THEORY is a fragment!
: > The AXIOM-SET is something far too small to be confused with
: > that. The THEORY of ZFC *is* a language, so if YOU say
: > "the language of ZFC" in a context where you think "ZFC"
: > means a theory, it is OBVIOUS that you are risking confusion
: > (that's why you won't say it).
:
: No, that's not it, because it's quite rare for me to use
: the word "language" in the (Post?) sense of "collection of
: strings".
No, really, it isn't. You do so immediately below.
: I'm using it rather in the (Tarski?) sense
: where a language has constant symbols, function symbols,
: and relation symbols, which can be combined
^^^^^^^^^^^^^^^ emphasis added...
: with the logical symbols (quantifiers, variables, equals sign,
: parentheses) in certain ways.
^^^^^^^^^^^^^^^ Emphasis added...
(actually, making = logical instead of definable moves
you to FOL-with-equality)
By asserting that combining will occur but that it will
be constrained, you OBLIGATE yourself to concede that
Those WAYS (of combining) produce STRINGS, produce the
STATEMENTS that constitute the language.
You cannot EQUATE the LANGUAGE with the legend of
names and arities for predicates and functors that
occur in it! That input (into some procedure named
"the first-order language generator", which adds some
logical connectives and grammatical constraints) will
yield an output that is the language, but the language IS
the resulting STRINGS, NOT *just* the list of ingredients
they are built from! You are practically confusing the
recipe with the cake, the genome with the organism!
: "The theory of ZFC" is not a language in the sense
: that I'm using the word "language",so there's no risk
: of confusion there.
Then there would be no risk of confusion if you were to
say "the language of ZFC". Yet you DID dismiss that locution
on the grounds that ZFC was a fragment. Well, guess what:
your Tarskian recipe is a MUCH SMALLER fragment.
: > First-order theories can have any old domains or any old
: > objects of discourse that you like, as long as the domains
: > have *enough* objects (denumerably many is ALWAYS enough).
: > They are NOT about any intended objects of discourse.
:
: Arbitrary first-order theories in general, no. But
: number theory *is*
Or WAS, UNTIL GODEL'S theorem and UNTIL the discovery of
non-standard models of PA and the discovery of the USEFULNESS
of infinitesimals and non-standard integers. AFTER that, PA
was just as divorced from any intended domain as GEOMETRY
became after the discovery of non-Euclidean geometries.
It is completely RIDICULOUS to say of ANY first-order
theory that it intends to be about natural numbers.
The whole import of Godel's theorem is that ALL first-order
theories MUST be COMPLETELY INadequate to that task! If
you intend to be talking about numbers then you DANG well
better be talking in something HIGHER than 1st-order!
: and set theory *is*.
No, really, it isn't; ZFC is *much* more complicated than PA
and the alleged intended domain is therefore just plain not
nearly well-enough *understood* by *anybody* for anybody
to be able claim to even know what he's talking about, if
talking about "set theory's intended domain".
: You can strip the meaning away from them and
: consider them simply as formal theories, and
: this is sometimes useful when you're doing
: metamathematics.
More to the point, that stripping is useful when you're doing
vanilla first-order PROOFS, IN the object-theory, since ALL the
proofs prove results about ALL the models, NOT just the intended ones!
The WHOLE point is that wherEVER you have logic and proof, that is
NECESSARILY INdependent of the meaning or interpretation, of
any particular model, or of any "intended" domain!
: > The alleged proposed intended objects of discourse are OFTEN
: > discovered never-to-have-even-existed in the first place
:
: All that proves is that we can be wrong.
But we CAN'T be wrong about the PROOFS! The PROOFS are all
STILL valid EVEN when they show that something we thought
had to exist (e.g. the Russell set) can't.
: I'm happy to agree that we can be wrong. If you're looking for
: a priori justified certainties, I have none to offer; my view is
: that it is a grave error to consider mathematics to be made up
: of such certainties.
Well, that view is hard to support. I mean, If you want to call
this view "a grave error" then you need to exhibit some grave
consequences. I concede that it is hard to say what you mean by
"is a prefix of", and it is arbitrary to attach that meaning to any
particular symbol, but if we could just concede THAT arbitrariness
(e.g. by adopting a TM programming language), then, that "ab" is a
substring of "abc" arguably IS one of the kind of certainties that math
is made up of.
: > (the set of all sets
: > that don't contain themselves, e.g.); and far more importantly, the
: > theory often turns out to have models that are provably DRASTICALLY
: > different from the alleged intended objects of discourse
: > (non-Euclidean geometry, non-standard integers in PA, etc.).
:
: PA has nonstandard models, ZFC has nonstandard models. They're
: called "nonstandard" for a reason.
Please. Not for any DEFENSIBLE reason.
I mean, Americans come in nonstandard races, too.
From the viewpoint of FOL itself, ALL models really
ARE created equal, at least up to cardinality.
Some models may be bigger than others, or more complex
than others, but really, more *standard* than others??
There WAS an intended domain of discourse, foundationally.
That is OLD history. The existence of the other models just
proves that the original purported 1st-order axiom-set was
JUST PLAIN *WRONG*, as far as being about the intended domain
was concerned. The language in which that axiom-set was
phrased arguably still deserves to be called that, though.
: > I haven't seen a full axiom-set for KP.
: > Isn't that really a DIFFERENT language?
:
: You may be thinking of KM (Kelley-Morse), which is a theory
: in second-order LST.
Oh, please.
Is the "real" "language of set theory" A FIRST-ORDER OR A SECOND-
ORDER language??
: KP is written in vanilla first-order LST;
: it's like ZF(C?) except that the Separation schema is
: restricted to Sigma_0 predicates and Replacement to Sigma_1,
: or maybe it's the other way around.
OK, I'm ready to quit. Obviously there is a problem with
my insisting on calling it "the langauge of ZFC" when it
is equally well the language of many other axiom-sets with
different assumptions and implications. But don't these
different assumptions and implications also wind up giving
you different set theories?
George Greene
But that means that + and * are recursively ENUMERABLE, then,
right?
Daryl McCullough
>I'm curious about this Tennenbaum thing, though; I never
>got around to learning about that. Can the idea be boiled
>down to a short post? Also, Hofstadter in _Goedel,Escher,Bach_
>seems to say that either + or * can be recursive but not
>both in the same model. Did he just get that wrong?
Hmm. Suppose we try to let our model be the set M of all
pairs <q,n> such that q is a nonnegative rational, and
n is an integer (with the further restriction that if
q=0, then n is nonnegative). Then wouldn't it work to
stipulate that
<q1,n1> + <q2,n2> = <q1+q2, n1+n2>
I don't see how that could possibly lead to a contradiction.
I'm wondering whether that stipulation, plus the usual
axioms relating multiplication and addition, uniquely
defines a multiplication operator, or whether there are
many different possible multiplication operators?
--
Daryl McCullough
Ithaca, NY
tc...@lsa.umich.edu
George Greene <gre...@eagle.cs.unc.edu> wrote:
< : Mike Oliver wrote:
< :
< : > Also, Hofstadter in _Goedel,Escher,Bach_
< : > seems to say that either + or * can be recursive but not
< : > both in the same model.
< :
< : I probably should have said "not both with respect to the same
< : enumeration of the same model". What he writes, as I remember
< : it, suggests that there might be different enumerations of
< : the same model, with respect to one of which + is recursive,
< : and * recursive wrt the other.
<
<But that means that + and * are recursively ENUMERABLE, then,
<right?
As noted elsewhere, Hofstadter has misstated Tennenbaum's theorem.
As for whether + and * are recursively enumerable, there certainly are
countable nonstandard models of PA in which they are *not* r.e., or even
arithmetical. I don't know whether there are any in which + and * are r.e.
tc...@lsa.umich.edu
Daryl McCullough <da...@cogentex.com> wrote:
[Re: nonstandard models of PA]
>Hmm. Suppose we try to let our model be the set M of all
>pairs <q,n> such that q is a nonnegative rational, and
>n is an integer (with the further restriction that if
>q=0, then n is nonnegative). Then wouldn't it work to
>stipulate that
>
> <q1,n1> + <q2,n2> = <q1+q2, n1+n2>
>
>I don't see how that could possibly lead to a contradiction.
How do you see this so easily?
>I'm wondering whether that stipulation, plus the usual
>axioms relating multiplication and addition, uniquely
>defines a multiplication operator, or whether there are
>many different possible multiplication operators?
Or none? For your construction to be a model of PA there has to exist at
least one multiplication operator consistent with the addition as you have
defined it. How do you see that it exists?
Daryl McCullough
>Daryl McCullough <da...@cogentex.com> wrote:
>> <q1,n1> + <q2,n2> = <q1+q2, n1+n2>
>>
>>I don't see how that could possibly lead to a contradiction.
>
>How do you see this so easily?
You are asking how I can so easily see that I don't see
how that could lead to a contradiction? It's perfectly
clear to *me* that I don't see how it could lead to a
contradiction.
Taneli Huuskonen
Hash: SHA1
In <asldj...@drn.newsguy.com> da...@cogentex.com (Daryl McCullough)
writes:
>Mike Oliver says...
>>I'm curious about this Tennenbaum thing, though; I never
>>got around to learning about that. Can the idea be boiled
>>down to a short post? Also, Hofstadter in _Goedel,Escher,Bach_
>>seems to say that either + or * can be recursive but not
>>both in the same model. Did he just get that wrong?
I seem to remember that it was first proved that not both of them can be
recursive in the same model (and with respect to the same enumeration),
and the theorem saying that neither of them can be recursive was more
recent. Maybe GEB was written in between.
>Hmm. Suppose we try to let our model be the set M of all
>pairs <q,n> such that q is a nonnegative rational, and
>n is an integer (with the further restriction that if
>q=0, then n is nonnegative). Then wouldn't it work to
>stipulate that
> <q1,n1> + <q2,n2> = <q1+q2, n1+n2>
>I don't see how that could possibly lead to a contradiction.
>I'm wondering whether that stipulation, plus the usual
>axioms relating multiplication and addition, uniquely
>defines a multiplication operator, or whether there are
>many different possible multiplication operators?
That'd uniquely define multiplication by a standard natural number, but
you'd have nowhere to place the product of two non-standard ones.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPe5yxl+t0CYLfLaVEQKwjgCdGp9iqdOtmogQ4gG5c2EvKkwWI2MAn1ye
r9LqwcYuRsYCxZ9bfvWmIjDi
=lhWo
Pierre Asselin
>I'm curious about this Tennenbaum thing, though; I never
>got around to learning about that. Can the idea be boiled
>down to a short post? Also, Hofstadter in _Goedel,Escher,Bach_
>seems to say that either + or * can be recursive but not
>both in the same model. Did he just get that wrong?
A quick look in Boolos and Jeffrey reveals that:
A theorem due to Stanley Tennenbaum asserts that there are
no recursive non-standards models of arithmetic. We shall
demonstrate an extension of Tennenbaum's theorem due to
Georg Kreisel and Kenneth McAloon: in no non-standard model
of Z is either (+) (Kreisel) or (x) (McAloon) recursive.
We'll also show that in no non-standard model of arithmetic
is either (+) or (x) definable in arithmetic
This is the opener to chapter 29, if you need to check. Z is
first-order PA, arithmetic is Skolem arithmetic.
tc...@lsa.umich.edu
Taneli Huuskonen <huus...@cc.helsinki.fi> wrote:
>I seem to remember that it was first proved that not both of them can be
>recursive in the same model (and with respect to the same enumeration),
>and the theorem saying that neither of them can be recursive was more
>recent. Maybe GEB was written in between.
Ah, now that's an interesting theory. But I think that the fact that they
cannot both be recursive was proved in 1959, while GEB was published in
1981. I'll try to remember to verify these dates.
Mike Oliver
George Greene wrote:
> Mike Oliver wrote:
> : I probably should have said "not both with respect to the same
> : enumeration of the same model". What he writes, as I remember
> : it, suggests that there might be different enumerations of
> : the same model, with respect to one of which + is recursive,
> : and * recursive wrt the other.
>
> But that means that + and * are recursively ENUMERABLE, then,
> right?
No. For total functions there is no distinction between recursive
and recursively enumerable. If the graph of f is r.e., here's
how you compute f(n), given n: Start enumerating pairs <m,f(m)>
from the graph, until you find one such that m=n. This is
guaranteed to terminate (by totality), and then you know
the value of f(n).
George Greene
: : it's like ZF(C?) except that the Separation schema is
: : restricted to Sigma_0 predicates and Replacement to Sigma_1,
: : or maybe it's the other way around.
George Greene <gre...@eagle.cs.unc.edu> writes:
: OK, I'm ready to quit. Obviously there is a problem with
: my insisting on calling it "the langauge of ZFC" when it
: is equally well the language of many other axiom-sets with
: different assumptions and implications.
But it's *not* like that means I never had a point.
ZFC has a much stronger claim to foundationality,
to seminality, to being the prototype (among
all those other axiom-sets over the same language), THAN any
alleged "standard" model of it has to being "standard".
There is a REASON WHY other axiomatizations were written
in the same language as ZFC and it is *not* *just* because
they were both trying to be about "true" set theory.
It is because ZFC was the first sufficiently important one.
In any case, the question of whether there is a "noumenal
reality of sets" for ANY set theory to be "about" is completely
independent of anyone's rationale for referring to a given
first-order language in a given way. All these first-order
languages are specifiable in principle by a list of relation-
(name,-arity) pairs. But any two lists with the same number of names
and the same number of names-with-each-arity are isomorphic, so
if you are citing one as preferred, you NEED a rationale.
"It's standard" or "it's the conventional one" are in my
opinion *weaker* rationales than "it's the one that author
<x> chose in her axiom-set that is named after her." For
one thing, the last criterion is factually determinable.
Appealing to either a standard or a convention raises the
philosophical question of why that phrasing as opposed to some
other *deserves* to be the conventional standard. Appealing to
the fact of authorship changes that question into whether the
author deserves respect, or whether we're talking about the same
issues she was talking about. Both of those questions are going
to have answers that are a lot closer to objective and that
interact with the entirely proper question of evaluating the
theoretical significance of the author's contributions.
That and NOT "these are our conventions" is actually what
ANY field would *rather* be *about*.
Mike Oliver
> No. For total functions there is no distinction between recursive
> and recursively enumerable. If the graph of f is r.e., here's
> how you compute f(n), given n: Start enumerating pairs <m,f(m)>
> from the graph, until you find one such that m=n. This is
> guaranteed to terminate (by totality), and then you know
> the value of f(n).
On reflection I find that the same argument works just fine
for partial functions. The algorithm is no longer guaranteed
to terminate, but it fails to terminate precisely when n is
not in the domain, which is exactly the behavior you want.
So r.e. is just the same as recursive for arithmetical functions,
partial or total. Unless someone can think of a meaning for
calling a function r.e. other than that its graph is r.e.
George Greene
: On reflection I find that the same argument works just fine
: for partial functions. The algorithm is no longer guaranteed
: to terminate, but it fails to terminate precisely when n is
: not in the domain, which is exactly the behavior you want.
It matters how LONG it takes to fail to terminate.
If the function is recursive on its non-total domain,
then it is bounded above, ON its domain, by a total
recursive function. Therefore, there *exists* an algorithm
that computes the function and DOES terminate, namely, it
just runs the non-terminating algorithm for a time longer-
than-the-total-function-bounding-above, and at that point,
it knows the original algorithm is never going to terminate,
so IT (the overall algorithm) CAN halt.
: So r.e. is just the same as recursive for arithmetical functions,
: partial or total.
Well, maybe "arithmetical" functions can't grow fast enough
or chaotically enough to fall into this crack. I guess
some known r.e. function (like proof-length) is not
"arithmetical"?
: Unless someone can think of a meaning for
: calling a function r.e. other than that its graph is r.e.
--
George Greene
: A quick look in Boolos and Jeffrey reveals that:
:
: A theorem due to Stanley Tennenbaum asserts that there are
: demonstrate an extension of Tennenbaum's theorem due to
: Georg Kreisel and Kenneth McAloon: in no non-standard model
: of Z is either (+) (Kreisel) or (x) (McAloon) recursive.
: We'll also show that in no non-standard model of arithmetic
: is either (+) or (x) definable in arithmetic
:
: This is the opener to chapter 29, if you need to check. Z is
: first-order PA, arithmetic is Skolem arithmetic.
is this the same as primitive-recursive arithmetic?
George Greene
: > : I probably should have said "not both with respect to the same
: > : enumeration of the same model". What he writes, as I remember
: > : it, suggests that there might be different enumerations of
: > : the same model, with respect to one of which + is recursive,
: > : and * recursive wrt the other.
I asked a stupid question--
: George Greene wrote:
: > But that means that + and * are recursively ENUMERABLE, then,
: > right?
Mike Oliver <oli...@math.ucla.edu> writes:
: No. For total functions there is no distinction between recursive
: and recursively enumerable.
<sigh> I knew that. If it's rec.env. and total then it's recursive.
But I was misled for a *reason*: if you say, "there might be
different enumerations of the smae model, with respect to one
of which + is recursive, and * recursive wrt the other", that
at least suggests that "there exists an enumeration with
respect to which f/+/* whatever is recursive". Isn't that
the definition of rec.env.?
Shouldn't the fact that both + and * are total mean that
this actually can't happen? Did we finally resolve this
that neither of them is ever recursive?
This is frankly confusing me more as every day goes by,
since if a model is not at least as simple as recursively
enumerable, there arises a very serious question about
how you ever managed to specify it in the first place.
Rec.env. sets can be specified by finite TM programs.
I suppose you could hope to specify some non-rec.env.
sets finitarily if their complements were rec.env.
I would expect all these non-standard models to be well-
understood enough that they do in fact get presented finitarily
to people studying them. So how is that even being managed?
George Greene
: > In article <xes65ua...@swift.cs.unc.edu>,
: > George Greene <gre...@swift.cs.unc.edu> wrote:
: >> This is ridiculous. The canonical non-standard model of PA
: >> is certainly recursive in at least one typical usual sense.
: >> It is N + Z. The integers are certainly simple enough to be recursive.
: tc...@lsa.umich.edu wrote:
: > What is the "canonical nonstandard model of PA"? Neither + nor * is
: > recursive in any countable nonstandard model of PA, by Tennebaum's
: > theorem, so you must mean something else.
:
Mike Oliver <oli...@math.ucla.edu> writes:
: What I suspect George is slightly misremembering is that the
: order type of the elements of a nonstandard countable model
: of PA is always N + Q*Z, where by Q*Z I mean the lexicographic
: order of pairs (q,n) where q is rational and n \in Z. Of
: course that just gives you that the *elements* can be given
: recursively and their *order* is a recursive predicate; doesn't
: say anything about + or *.
Thank you kindly for bailing me out here.
I said something stupid and you just corrected
me informatively instead of assaulting my character
for having flaunted my ignorance. The people in the JSH
thread should observe and emulate.
so, for sufficiently simple non-standard models of PA:
domain: recursive
< : recursive
+ : not r.e.
* : not r.e.
I guess my next question would be, if + and * in this
model are not TM-computable, why are people sure they
even exist at all? One kind of non-r.e. set for which
it is clearly meaningful to speak of its existence is
the kind that has an r.e. complement; I mean if "there
is a TM such that it's in the set iff the TM halts on it"
is a meaningful pointer at a set then "there is a TM
such that it's in the set iff the TM loops on it" has
to be equally meaningful. But I don't have any intuition
for what existence-proofs for complex/choatic non-r.e. sets
look like.
Back in standard PA, the 0th-order truths about + and *
are recursive but the 1st-order ones with universal
quantifiers are not; they are not r.e. either, although
the provable and disprovable ones are. This raises
the question: is there some sort of natural mapping between
the non-r.e. class of truths of first-order PA in the
standard model, and the non-r.e. class of 0th-order truths
about + and * in [an appropriate class of] non-standard models?
Mike Oliver
> Mike Oliver <oli...@math.ucla.edu> writes:
> : On reflection I find that the same argument works just fine
> : for partial functions. The algorithm is no longer guaranteed
> : to terminate, but it fails to terminate precisely when n is
> : not in the domain, which is exactly the behavior you want.
>
> It matters how LONG it takes to fail to terminate.
> If the function is recursive on its non-total domain,
> then it is bounded above, ON its domain, by a total
> recursive function. Therefore, there *exists* an algorithm
> that computes the function and DOES terminate, namely, it
> just runs the non-terminating algorithm for a time longer-
> than-the-total-function-bounding-above, and at that point,
> it knows the original algorithm is never going to terminate,
> so IT (the overall algorithm) CAN halt.
I may be making some silly mistake, a long time since I've
done recursion theory, but I don't think this can be right.
If every partial recursive function could be bounded by
a total recursive function, then you could bound the running
time of the algo computing the partial function, exactly
as above, and decide whether a given n were in the domain
of the partial function. But that says every r.e. set is
recursive (because every r.e. set equals the domain of
some partial recursive function).
I may not be responding for a week or so; going out of town.
Mike Oliver
> : George Greene wrote:
> : > But that means that + and * are recursively ENUMERABLE, then,
> : > right?
>
> Mike Oliver <oli...@math.ucla.edu> writes:
> : No. For total functions there is no distinction between recursive
> : and recursively enumerable.
>
> <sigh> I knew that. If it's rec.env. and total then it's recursive.
>
> But I was misled for a *reason*: if you say, "there might be
> different enumerations of the smae model, with respect to one
> of which + is recursive, and * recursive wrt the other", that
> at least suggests that "there exists an enumeration with
> respect to which f/+/* whatever is recursive". Isn't that
> the definition of rec.env.?
No, I think possibly I didn't manage to convey to you what I meant
by "enumeration" here. Here's the question: Given a countable
nonstandard model M, what does it mean to ask if the + and *
of M are recursive functions? We know what "recursive function"
means on the natural numbers, but the elements of M *aren't*
natural numbers, or at least might not be.
So the question makes sense only if we have a way of naming
the elements of M by natural numbers; that is, a bijection
(or at the very least a surjection) f : omega --> M .
This f is what I'm calling an enumeration. Then, say, + is
recursive wrt f if and only if there's some recursive
function G : omega x omega --> omega such that, for all n,m,
f(n) + f(m) = f(G(n,m))
where the + on the left is that interpreted in M.
Now at least prima facie, the recursiveness of + wrt f does
not seem to imply the recursiveness of + wrt some different
enumeration g.
> Shouldn't the fact that both + and * are total mean that
> this actually can't happen? Did we finally resolve this
> that neither of them is ever recursive?
We did, if I understand correctly, but I don't think
that that's the *reason* that neither of them is ever
recursive. You have to do more work than that; this
sense of "enumeration" has little to do with "recursively
enumerable". The enumeration f need not be recursive
(in fact, it's not clear what it would *mean* for it
to be recursive, given that the elements of M are not
natural numbers).
tc...@lsa.umich.edu
George Greene <gre...@eagle.cs.unc.edu> wrote:
>This is frankly confusing me more as every day goes by,
>since if a model is not at least as simple as recursively
>enumerable, there arises a very serious question about
>how you ever managed to specify it in the first place.
I don't know if this remark helps, but the usual proof of the compactness
theorem (which many of these facts, like the existence of nonstandard
models, derive from) uses the axiom of choice.
I confess that I have been vaguely puzzled for a while why you seem to
accept the completeness/compactness theorems for first-order logic so
unquestioningly while foaming at the mouth at (what seem to me to be)
other things that are far less tainted by non-effectiveness. This
article of yours suggests that maybe you haven't thought through this
point to your own satisfaction yet.
tc...@lsa.umich.edu
Daryl McCullough <da...@cogentex.com> wrote:
>You are asking how I can so easily see that I don't see
>how that could lead to a contradiction? It's perfectly
>clear to *me* that I don't see how it could lead to a
>contradiction.
Touche! :-)
On further reflection I suspect you were trying to say that if we delete *
from the set of binary relations, along with all formulas and axioms
involving it, then we can get recursive nonstandard models. Moreover,
your construction is a candidate. This seems plausible to me, though it
still seems like a pain to check the induction axiom.
Hey, maybe *that's* what Hofstadter was trying to say! That the natural
numbers with addition has recursive nonstandard models, and that the natural
numbers with multiplication has recursive nonstandard models, but that PA
has no recursive nonstandard models?
tc...@lsa.umich.edu
>In article <aslrss$53b$1...@sirppi.helsinki.fi>,
>Taneli Huuskonen <huus...@cc.helsinki.fi> wrote:
>>I seem to remember that it was first proved that not both of them can be
>>recursive in the same model (and with respect to the same enumeration),
>>and the theorem saying that neither of them can be recursive was more
>>recent. Maybe GEB was written in between.
>
>Ah, now that's an interesting theory. But I think that the fact that they
>cannot both be recursive was proved in 1959, while GEB was published in
>1981. I'll try to remember to verify these dates.
I believe that what I said above is correct, but---duh---it doesn't
address Taneli Huuskonen's point about whether GEB was written
in between, because I didn't give a date for the stronger theorem!
What was I thinking? Anyway, elsewhere in this thread someone said that
B&J attribute the stronger result to Kreisel and McAloon, but I couldn't
find any paper on MathSciNet matching that description. So when was
that proved?
Hofstadter still isn't vindicated, unfortunately, because he does say
that one or the other *can* be recursive, which isn't right.
Peter G. Hancock
>>>>> tchow wrote (on Thu, 05 Dec 2002 at 09:55):
> I don't know if this remark helps, but the usual proof of the compactness
> theorem (which many of these facts, like the existence of nonstandard
> models, derive from) uses the axiom of choice.
I'm far from sure about this, but I think that people in reverse
mathematics, (eg. Steve Simpson) have in some sense established rather
precisely the strength of reasoning (over primitive recursive
arithmetic) required to prove (a suitably formulated version of) the
completeness theorem for first order classical logic (if not also the
compactness theorem).
Something vastly less than the full strength of the axiom of choice is
required. I might make a small wager that it's something called "weak
König's lemma". In the 50's Kreisel and Dyson showed (I think) that
this principle was sufficient to obtain a completeness theorem for
first order intuitionistic logic w.r.t. Beth trees.
Sorry if this is a rat-hole.
Peter Hancock
H. Enderton
Pierre Asselin <p...@panix.com> wrote:
>A quick look in Boolos and Jeffrey reveals that:
> A theorem due to Stanley Tennenbaum asserts that there are
> no recursive non-standards models of arithmetic. We shall
> demonstrate an extension of Tennenbaum's theorem due to
> Georg Kreisel and Kenneth McAloon: in no non-standard model
> of Z is either (+) (Kreisel) or (x) (McAloon) recursive.
> We'll also show that in no non-standard model of arithmetic
> is either (+) or (x) definable in arithmetic
>This is the opener to chapter 29, if you need to check. Z is
>first-order PA, arithmetic is Skolem arithmetic.
Thanks, Pierre. The original Tennenbaum result that + and x cannot
*both* be recursive in a non-standard model of PA can be found in
(of all places) Paul Cohen's 1966 book, Set Theory and the Continuum
Hypothesis, pages 48-49.
--Herb Enderton
Daryl McCullough
>On further reflection I suspect you were trying to say that if we delete *
>from the set of binary relations, along with all formulas and axioms
>involving it, then we can get recursive nonstandard models. Moreover,
>your construction is a candidate. This seems plausible to me, though it
>still seems like a pain to check the induction axiom.
>
>Hey, maybe *that's* what Hofstadter was trying to say! That the natural
>numbers with addition has recursive nonstandard models, and that the natural
>numbers with multiplication has recursive nonstandard models, but that PA
>has no recursive nonstandard models?
Hmm. How would one define multiplication without using addition?
Taneli Huuskonen
Hash: SHA1
In <xesbs41...@eagle.cs.unc.edu> George Greene
<gre...@eagle.cs.unc.edu> writes:
[...]
>This is frankly confusing me more as every day goes by,
>since if a model is not at least as simple as recursively
>enumerable, there arises a very serious question about
>how you ever managed to specify it in the first place.
>Rec.env. sets can be specified by finite TM programs.
>I suppose you could hope to specify some non-rec.env.
>sets finitarily if their complements were rec.env.
>I would expect all these non-standard models to be well-
>understood enough that they do in fact get presented finitarily
>to people studying them. So how is that even being managed?
With recursively axiomatizable first-order theories, for instance.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPe+7/V+t0CYLfLaVEQKoeQCfYdtCifZhE+KAaTc3hEpIYBd3FmcAoMGl
08/KJQvHKb7vZwhTqSFZb81F
=j+da
David Libert
> George Greene wrote:
> > : George Greene wrote:
> > : > But that means that + and * are recursively ENUMERABLE, then,
> > : > right?
> >
> > Mike Oliver <oli...@math.ucla.edu> writes:
> > : No. For total functions there is no distinction between recursive
> > : and recursively enumerable.
> >
> > <sigh> I knew that. If it's rec.env. and total then it's recursive.
So this must be about recursively enumerable, but where does the
abbreviation "rec.env." come from?
> > But I was misled for a *reason*: if you say, "there might be
> > different enumerations of the smae model, with respect to one
> > of which + is recursive, and * recursive wrt the other", that
> > at least suggests that "there exists an enumeration with
> > respect to which f/+/* whatever is recursive". Isn't that
> > the definition of rec.env.?
>
> No, I think possibly I didn't manage to convey to you what I meant
> by "enumeration" here. Here's the question: Given a countable
> nonstandard model M, what does it mean to ask if the + and *
> of M are recursive functions? We know what "recursive function"
> means on the natural numbers, but the elements of M *aren't*
> natural numbers, or at least might not be.
>
> So the question makes sense only if we have a way of naming
> the elements of M by natural numbers; that is, a bijection
> (or at the very least a surjection) f : omega --> M .
>
> This f is what I'm calling an enumeration. Then, say, + is
> recursive wrt f if and only if there's some recursive
> function G : omega x omega --> omega such that, for all n,m,
>
> f(n) + f(m) = f(G(n,m))
>
> where the + on the left is that interpreted in M.
>
> Now at least prima facie, the recursiveness of + wrt f does
> not seem to imply the recursiveness of + wrt some different
> enumeration g.
Yes. The G induced by f could be further perturbed by another
bijection of omega to iteself, ie pre and post compose G with the
bijection and its inverse. This would correspond to using f composed
with the bijection on omega.
There are continuum many bijections, so this must be able to induce
continuum many alternate versions of G, and only countably many can be
recursive. Or there must be a way to fiddle with explicit
non-recurusive bijections and see the changed G is not recursive.
Anyway, in this thread Herbert Enderton posted that Cohen's
Set Theory and the Continuum Hypothesis has the proof of the original
Tennebaum result, pp 48-49.
I looked that up. It has a simple statement of the result, which
avoids all these issues about enuerations and alternative enumerations
by avoiding all that in the phrasing.
Namely the result is that if f_1 and f_2 are two total binary
functions on omega to itself, such that the model with underlying set
omega, with f_1 interpreting "+" and with f_2 interpreting "*"
is a model of PA, then either the model is isomorphic to the standard
PA model, or else at least one of f_1, f_2 are not recursive.
Actually Cohen states that (on page 48) for his system Z_1, defined
on page 21, which is his phrasing of PA, using ternary relations
instead of function symbols to code addition and multiplication.
Also, Cohen's Z_1 has constant symbols 0 and 1, but his stated
result in page 48 does not mentions those constants for the model.
So you could just state there are interpretations for 0,1 in the
model, so the entire structure satisfies PA.
So this statement just works with models on underlying set omega
directly.
I will sketch the proof from Cohen's book. As a motivating first
pass that will have to be fixed in a moment, let S be a subset of the
usual intergers which is r.e. but not recursive in the usual sense.
More literally, let S be the actual r.e. definition, which in the
standard PA model defines an r.e. non-recursive set.
Let M be a PA model with f_1 and f_2 as discussed above.
Let S' be the S r.e. definition as interpreted in M, ie a subset of
M.
Suppose M is non-standard, ie not isomorphic to the usual integers.
Let c be an infinite element of M, ie an element greater than all
iterations of f_1 on the constant 1 interpreted in M.
Since M |= PA, by the Chinease remainder theorem in M (a PA
theorem), there is y in M which codes S' membership for all M
members i < c, codes i membership in S' by having being congruent to 0
or 1 mod the i'th prime. (Ie: by S' being definable in M).
If f_1 and f_2 were both recursive, we could use them and the y
above to recursively decide i membership in S' for i < c : namely
search through all members z of M (ie searching over omega) to find a
z so that f_2(p_i, z) = y or f_1(f_2(p_i, z), "1) = y.
For j a standard integer, we can find the i in M representing the
j'th integer by iterating f_2 with "1" over "0". So for j, we find
the i representing it, and run that last test.
By choice of y, the search always finally finds a z, and so gives
back an answer.
So there would be a recursive procedure to decide S' membership in M
of all standard integers from the initial standard part of M. Ie, y
coded S' membership below c, and c was infinite.
But this is not yet a contradiction. S was picked to be r.e. but
not recursive. But our recursive test is for S' membership, instead
of S membership, ie we have to apply that r.e. definition in M.
Any witness to the unbounded quantifier in standard integers has a
corresponding witness in M, so S subset S'.
It is possible S' is strictly bigger than S, because S' is doing the
unbounded existential in the bigger M universe, ie bigger than
standard in the sense of the embedding of standard into M.
So S' might not = S, so getting a recursive test for S' is not yet a
contradiction.
Now the fix mentioned at the outset. On page 49 Cohen gives
explicit definitions and a PA proof that there are r.e. sets S and
T which are disjoint but recursively inseparable, ie there is no
recursive partitioning of omega into two recursive pieces such that S
and T are each contained in different pieces.
So redo the entire earlier not with an arbitrary non-recursive
r.e. S but instead with S from such an S,T pair.
Then M has S', T' the corresponding definitions in M. These are
still disjoint, since PA proved that about the original S,T
definitions.
Redo the recursive test of S' membership on standard integers. For
general integers we have the old problem of this S' test giving false
positives for S membership.
But when you consider standard integers that were in T, the
corresponding calculation in M working with the M's version of those
(build from f_1), still gets those in T', ie T' superset T just
like S' superset S. And S' disjoint from T', so for these the test
answers not in S'.
So this recursive procedure though it is unknown action from the
proof so far outside of S union T, we know on S union T as
interpreted into the initial standard part of M, this procedure has
provided a recursive separation. This contra the choice of S,T.
The escape is at least one of f_1, f_2 is not recursive, so when we
tested S' membership by testing the Chinease remainder calculation for
i using y: when we calculated f_1(f_2(p_i, z), "1") it is not
recursive.
Well to even get "p_i". Because we have to calculate that using f_1
and f_2.
--
David Libert ah...@FreeNet.Carleton.CA
tc...@lsa.umich.edu
Daryl McCullough <da...@cogentex.com> wrote:
>Hmm. How would one define multiplication without using addition?
I think maybe one could use the order relation "<" as a partial surrogate
for addition, so that you could have axioms like "if a_1 < b_1 and a_2 < b_2
then a_1*a_2 < b_1*b_2." Admittedly I don't think I've seen this done so
maybe it's not actually so easy.
Bennett Standeven
I was going to object that you don't know which function is the upper
bound, but it doesn't matter: letting g be a timebound for f, we can
always define the domain of f recursively in f and g. So if f has
nonrecursive domain, it cannot have a total recursive timebound g.
Bennett Standeven
> In article <aso7d...@drn.newsguy.com>,
> Daryl McCullough <da...@cogentex.com> wrote:
> >Hmm. How would one define multiplication without using addition?
>
> I think maybe one could use the order relation "<" as a partial surrogate
> for addition, so that you could have axioms like "if a_1 < b_1 and a_2 < b_2
> then a_1*a_2 < b_1*b_2." Admittedly I don't think I've seen this done so
> maybe it's not actually so easy.
I seem to recall that there is a way to define addition in terms of
multiplication and order; the key tricks were that x + 1 is definable
using only the order relation, and (a+1)(b+1) = ab + a + b + 1. I
can't see how the full definition would work, though.
David Libert
> Namely the result is that if f_1 and f_2 are two total binary
> functions on omega to itself, such that the model with underlying set
> omega, with f_1 interpreting "+" and with f_2 interpreting "*"
> is a model of PA, then either the model is isomorphic to the standard
> PA model, or else at least one of f_1, f_2 are not recursive.
The above puts a lower bound on the complexity of f_1 or f_2.
Given any model as above, you could induce another such model by a
complex bijection on omega, so f_1 and f_2 could be complex. Tom
Chow mentioned in this thread it need not be arithmetical.
But there is another way to put upper bounds on the complexity of
f_1 and f_2, namely how low can the complexity be made in some models
as above.
It turns our we can bound it quite low in that sense above the lower
bound above.
Namely we can get a model as above, ie f_1 and f_2 interpreting
"+" and "*" respectively on underlying set omega, the model not
isomorphic to the standard model, with f_1 and f_2 both Turing
reducible to 0', the Turing degree of the halting problem.
Namely, take a Skolemized theory of PA, ie PA with Skokem function
symbols and Skolem axioms, and also a new constant c with an axiom
schematum saying c is not a standard integer. This theory is
consistent since PA is (we are working in strong enough meta-theory to
have Con(PA)).
We seek to extend this to a complete theory, which will be Turing
reducible to 0'. We do this in omega many stages, at stage n
deciding whether to add as axiom the n'th sentence or its negation (in
some recursive omega listing of sentences of this language).
So far we have accumulated finitely many added axioms over the base
theory, which by inductive hypothesis as to be maintained in a
momement are consistent over that base theory. We have to decide
which sentence (n'th versus n'th 's negation) to add. At least one of
these must be consistent, since the last step was.
We want to add the n'th sentence if that stays consistent over the
last step, else add the negation of the n'th. If the n'th was
inconsistent over the previous step, its negation must be consistent
over the previous step, else the previous step was inconsistent contra
the induction hypothesis.
So if we could know which choice to make, we maintain the induction
hypothesis.
And we can decide which to pick by consulting a 0' oracle, checking
the consistency of n'th over previous by asking if a search for an
inconsistency halts.
So we can get a complete extension of the Skolemized theory
recursive in 0'.
We take the Godel numbers of all Skolem terms in our theory. We
define g_1 and g_2 mapping from pairs of Godel numbers of Skolem
terms into Godel numbers of Skolem terms, to correspond to "+" and
"*". For example for g_1 representing "+", given Godel numbers of two
Skolem terms t1 and t2, form the Skolem term "t1 + t2" ie the
Skolem term with the "+" function symbol applied to t1 and t2 Skolem
terms.
Now compute the least Godel number of any Skolem term which the
complete Skolem theory proves = to "t1 + t2". Ie, search through all
Skolem terms in order, for each one t looking among the theorems of
the complete theory for the theorems t = t1 + t2 or for
~(t = t1 + t2). Since theory was complete this search halts in finite
time for each term t, and then iterating through all t we finally
find a term making the =, ie t1 + t2 itself if nothing before.
This entire calculation is recursive in 0', since it only depends on
positively recognizing theorems of the complete theory, and that was
recursive in 0'.
So this g_1 is sort of like an AC style choice picking a unique
representing Skolem term for each equivalence class of provabably =
Skolem terms.
Similarly define g_2 for "*".
Now consider g_1 and g_2 restricted to the union of the ranges
of g_1 and g_2.
This union of ranges is recursive in 0', ie recognizing something in
it amounts to checking = of fintely many Skolem terms as theorems of
the theory.
So reindex that union of ranges back to omega, and pull back g_1 and
g_2 on that union of ranges to be f_1 and f_2 on omega induced by
such a reindexing.
These induced f_1 and f_2 are recursive in 0', since g_1 and g_2
were, and the reindexing was.
So this makes our required model, and it is not isomorphic to the
standard model, by the c axioms.
So at least one of f_1 or f_2 are not recursive from the last
post. And by later theorems of Kreisel and McAloon according to
Pierre Asselin's article in this thread, both f_1 and f_2 are not
recursive. Ie, in Turing degree language, they are not Turing degree
0.
But by the above, they can both be arranged to be Turing reducible
to 0', not so high above 0.
--
David Libert ah...@FreeNet.Carleton.CA
George Greene
> > > : On reflection I find that the same argument works just fine
> > > : for partial functions. The algorithm is no longer guaranteed
> > > : to terminate, but it fails to terminate precisely when n is
> > > : not in the domain, which is exactly the behavior you want.
Some context has been cut here, so it is no longer exactly clear
*which* argument or algorithm is the "same" one, but I am thinking
that "the same" *anything* will *not* work for describing recursively
enumerable functions as opposed to just-plain-recursive ones.
The class of "partial recursive functions" seems sort of ambiguous.
Some partial recursive functions are partial AND just-plain-recursive
(take any total recursive function and obliterate a recursive
set of args from its domain). Others are partial and recursively
enumerable but NOT just-plain-recursive.
be...@pop.networkusa.net (Bennett Standeven) wrote in message >
> I was going to object that you don't know which function is the upper
> bound, but it doesn't matter: letting g be a timebound for f, we can
> always define the domain of f recursively in f and g. So if f has
> nonrecursive domain, it cannot have a total recursive timebound g.
Right. But aren't there cases when it is *hard* to even *tell* whether
f has a non-recursive domain? Does tangent have a recursive domain?
Is tangent a recursive function?
It is partial and it is not bounded by any total recursive
function, but the partiality is curable; you could just define
a "total" version of it as 0 at the asymptotes. The set of
points where tangent is undefined seems plenty regular enough
to be recursive { (2n+1)*pi/2 : forall natural n },
but representational issues for transcendental args in a finitary
TM alphabet could change that, somehow, possibly, I suppose....
tc...@lsa.umich.edu
George Greene <gre...@cs.unc.edu> wrote:
>Some context has been cut here, so it is no longer exactly clear
>*which* argument or algorithm is the "same" one, but I am thinking
>that "the same" *anything* will *not* work for describing recursively
>enumerable functions as opposed to just-plain-recursive ones.
Well, I think that the confusion stems from what an "r.e. partial function"
is supposed to mean. I don't think I've seen this term before, and Mike
Oliver's definition looks awfully like the definition I've seen of
"recursive partial function," so it's not surprising that he's concluding
that they're the same thing. But maybe this just means that his definition
of "r.e. partial function" isn't right.
On the other hand, I believe it's a standard fact that r.e. total functions
and recursive total functions are the same. Of course this doesn't mean
that r.e. *sets* and recursive *sets* are the same.
>Right. But aren't there cases when it is *hard* to even *tell* whether
>f has a non-recursive domain? Does tangent have a recursive domain?
>Is tangent a recursive function?
>
>It is partial and it is not bounded by any total recursive
>function, but the partiality is curable; you could just define
>a "total" version of it as 0 at the asymptotes. The set of
>points where tangent is undefined seems plenty regular enough
>to be recursive { (2n+1)*pi/2 : forall natural n },
>but representational issues for transcendental args in a finitary
>TM alphabet could change that, somehow, possibly, I suppose....
I think you need to be clearer about what you mean by the "tangent
function." If you're using the adjective "recursive" then a priori
one expects you to be talking about a function from N to N, but your
other comments make it sound like you're thinking of tangent as a
function from R to R. But then one has to specify what one means
by a recursive function from R to R. Perhaps you want to think of
tangent as a function from recursive reals to recursive reals? In
that case I'm not sure why you're saying that it's not bounded by
any total recursive function (from the recursive reals to the
recursive reals, presumably?).
Michael Oliver
> The class of "partial recursive functions" seems sort of ambiguous.
> Some partial recursive functions are partial AND just-plain-recursive
> (take any total recursive function and obliterate a recursive
> set of args from its domain). Others are partial and recursively
> enumerable but NOT just-plain-recursive.
"Partial recursive function" is a locution with an entirely
standard meaning; there's no ambiguity at all. It's true
that you wouldn't necessarily guess what that meaning
is, just from knowing what "partial", "recursive" and
"function" mean, separately.
BTW total recursive functions are also partial recursive --
the "partial" is a liberalization of the notion and
does not imply that the domain is a proper subset
of the naturals.
Anyway, to get the class of partial recursive functions
(from the naturals to the naturals), start with the primitive
recursive functions and close under minimization (one application
of minimization is enough). That is, every partial recursive
function f : N -> N can be written in the form
"f(n) is the least m such that g(m,n) holds",
where g : NxN -> N is primitive recursive. If
there is no such m, then n is not in the domain.
George Greene
> Well, I think that the confusion stems from what an "r.e. partial function"
> is supposed to mean. I don't think I've seen this term before,
Oh, come on. A function is r.e. iff it is TM-computable.
If it is not also recursive then it must also be partial and
not recursively time-boundable even on the class of inputs
that it halts on.
> and Mike
> Oliver's definition looks awfully like the definition I've seen of
> "recursive partial function,"
That is not a standard term; the standard term is
"partial recursive function". It wouldn't be the
first time that the usual parlance had obscured a nuance.
> so it's not surprising that he's concluding
> that they're the same thing. But maybe this just means that his definition
> of "r.e. partial function" isn't right.
Typically, the TM-computable functions and the "partial
recursive functions" are equated as the same class. I
am trying to partition the *usual* class of "partial recursive
functions" into some that "really" are just-plain-recursive
and some others that are recursively-enumerable-but-not-just-
plain-recursive. In normal parlance this latter class are
called recursive anyway, at least if you scan phrases like
"partial recursive function" according to the usual rules
of English. Yellow bananas HAVE to be yellow.
> On the other hand, I believe it's a standard fact that r.e. total functions
> and recursive total functions are the same.
That would seem to imply that since you could turn tangent
into a total function just by defining it arbitrarily
at its asymptotes, it must not be recursive, if the set
of asymptotes is recursive.
> Of course this doesn't mean
> that r.e. *sets* and recursive *sets* are the same.
Well, obviously, some sets are r.e. but not recursive.
But you've dropped the "total" axis. I think totality
for sets has to do with halting, totally.
> I think you need to be clearer about what you mean by the "tangent
> function." If you're using the adjective "recursive" then a priori
> one expects you to be talking about a function from N to N,
Aww, c'mon. Obviously, any other denumerable domain will do.
Obviously, you can encode arbitrarily huge countable ordinals
AS naturals, so really, you're NOT talking about N to N.
You are rather talking about ANY denumerable domain with
a standard encoding, as a domain, to boolean (halts, or doesn't)
as a range.
> but your other comments make it sound like you're thinking of
> tangent as a function from R to R. But then one has to specify
> what one means by a recursive function from R to R.
A function that is computable by a TM that always halts.
> Perhaps you want to think of
> tangent as a function from recursive reals to recursive reals?
Not necessarily. At this point I was just hoping that somebody
who actually already knew how people who have already written papers
in the field would *typically* address the representational
issue, and just chime in.
> In that case I'm not sure why you're saying that it's not bounded by
> any total recursive function (from the recursive reals to the
> recursive reals, presumably?).
Because tangent is not bounded by any total function PERIOD,
THAT'S why.
tc...@lsa.umich.edu
>
>> Well, I think that the confusion stems from what an "r.e. partial function"
>> is supposed to mean. I don't think I've seen this term before,
>
>Oh, come on. A function is r.e. iff it is TM-computable.
>If it is not also recursive then it must also be partial and
>not recursively time-boundable even on the class of inputs
>that it halts on.
Well, yeah, if I *did* see the term "r.e. partial function" then I would
probably try to interpret it along the lines that I think you're suggesting,
which is also how Mike Oliver defined it, but all I'm saying is that I don't
think I've seen the term before. And now I think that the reason is that
there's no need for a new name for something that already has a name, so
people don't use it.
>> Oliver's definition looks awfully like the definition I've seen of
>> "recursive partial function,"
>
>That is not a standard term; the standard term is
>"partial recursive function".
That's what I'd thought too, but I happen to have been looking at Enderton's
book recently, where he calls it a "recursive partial function," so I
thought maybe I'd misremembered.
>> On the other hand, I believe it's a standard fact that r.e. total functions
>> and recursive total functions are the same.
>
>That would seem to imply that since you could turn tangent
>into a total function just by defining it arbitrarily
>at its asymptotes, it must not be recursive, if the set
>of asymptotes is recursive.
I just don't see the chain of logic that you're using to get to that
conclusion. You dismissed the issues I raised; I admit that they *seem*
to be nitpicky things at first glance, but I'm convinced that they're at
the heart of the issue. For example:
>> but your other comments make it sound like you're thinking of
>> tangent as a function from R to R. But then one has to specify
>> what one means by a recursive function from R to R.
>
>A function that is computable by a TM that always halts.
How are you specifying your real numbers? By an infinite decimal expansion?
And the output is also presumably an infinite decimal expansion? So how can
the TM halt? Sorry again to *sound* nitpicky, but I believe that these are
actually the real issues here.
H. Enderton
Bennett Standeven <be...@pop.networkusa.net> wrote:
>I seem to recall that there is a way to define addition in terms of
>multiplication and order; the key tricks were that x + 1 is definable
>using only the order relation, and (a+1)(b+1) = ab + a + b + 1. I
>can't see how the full definition would work, though.
Yes, addition is definable from multiplication and successor.
And as you point out, successor S is definable from ordering.
To see how to define addition, look at the equation:
S(xz)S(yz) = S(zzS(xy)).
This hold iff either z = 0 or z = x + y.
I stole the equation from a Julia Robinson 1949 JSL paper.
--Herb Enderton
tc...@lsa.umich.edu
>Well, yeah, if I *did* see the term "r.e. partial function" then I would
>probably try to interpret it along the lines that I think you're suggesting,
>which is also how Mike Oliver defined it, but all I'm saying is that I don't
>think I've seen the term before. And now I think that the reason is that
>there's no need for a new name for something that already has a name, so
>people don't use it.
On reflection I think that what I was saying here was dumb. Just because
"r.e. partial function" comes out to the same thing as "partial recursive
function" doesn't mean that "r.e. partial function" doesn't have a natural
meaning. So ignore what I was blathering about here.
>>That would seem to imply that since you could turn tangent
>>into a total function just by defining it arbitrarily
>>at its asymptotes, it must not be recursive, if the set
>>of asymptotes is recursive.
>
>I just don't see the chain of logic that you're using to get to that
>conclusion.
Let me try a little harder to sound less nitpicky.
According to you, the tangent function is not bounded by a recursive
function. Presumably this intuition comes from the fact that recursive
functions are typically defined on the integers, and hence they are bounded
on any bounded interval, while the tangent function is unbounded on a
bounded interval? But when people talk about a "partial recursive
function f being bounded by a total recursive function g," they are
talking about f and g being defined on the *same domain*. If we restrict
the tangent function to the integers, then it is no longer unbounded on
a bounded interval, so your objection disappears.
But you may object that this is cheating; the thing to do is not to restrict
the tangent function to the integers but to pick some countable domain that
lets us continue to assert that "tan is unbounded on a bounded interval."
For example, we could choose our domain to be the set of rational multiples
of pi (which of course can be recursively enumerated). Then the tangent
function is indeed unbounded on (some) bounded intervals, and is a partial
function. But now there is no reason to think that tan is not bounded by
any total recursive function, because on the new domain there are plenty of
total recursive functions that are unbounded on bounded intervals.
That's the most sense I can make of your objection. If you still feel that
I'm missing the point, then please specify (1) exactly what domain you're
considering and (2) why you think that the tangent function is not bounded
by any total recursive function on that domain.
tc...@lsa.umich.edu
H. Enderton <h...@sonia.math.ucla.edu> wrote:
>To see how to define addition, look at the equation:
> S(xz)S(yz) = S(zzS(xy)).
>This hold iff either z = 0 or z = x + y.
>I stole the equation from a Julia Robinson 1949 JSL paper.
Clever! So that ruins (at least partially) my idea of trying to
axiomatize multiplication without bringing addition into the picture.
There might still be a way of doing it, but I no longer believe that
this is what Hofstadter was thinking. The other suggestion, that GEB
(1981) was written after Tennenbaum's theorem (1959) but before the
stronger Kreisel/McAloon result was proved (or at least before it
became widely known), and that Hofstadter read a little more into
Tennenbaum's theorem than was there, seems more plausible. For example,
the Kreisel/McAloon result is not in the 2nd edition of Boolos and
Jeffrey (1980) but was added in the 3rd edition (1989).
Taneli Huuskonen
Hash: SHA1
In <992b156f.02121...@posting.google.com>
gre...@cs.unc.edu (George Greene) writes:
[...]
>Because tangent is not bounded by any total function PERIOD,
>THAT'S why.
Maybe you forgot something like "continuous"? Otherwise, just add 1 to
it and extend arbitrarily to integer multiples of pi.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPfeEEV+t0CYLfLaVEQLfGgCg+8ZvXOv0AT2PqWgKceCKT+JEhAcAnRGx
DfKd1nL6qN5ncPa0LRhu7wxU
=2/k5
Taneli Huuskonen
Hash: SHA1
In <3DF658C4...@fields.utoronto.ca> Michael Oliver
<mol...@fields.utoronto.ca> writes:
[...]
>Anyway, to get the class of partial recursive functions
>(from the naturals to the naturals), start with the primitive
>recursive functions and close under minimization (one application
>of minimization is enough). That is, every partial recursive
>function f : N -> N can be written in the form
>"f(n) is the least m such that g(m,n) holds",
>where g : NxN -> N is primitive recursive. If
>there is no such m, then n is not in the domain.
Actually, you need another primitive recursive function that's applied
after the minimization. For every partial recursive function f there
are primitive recursive g and h such that f(n)=h(m_0), where m_0 is
the least m such that g(m,n) holds.
You can prove this by defining g(m,n) to be true iff m codes a
successful computation of f(n).
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPfeBF1+t0CYLfLaVEQJN9gCghJnLk5STK18QkfaTQBKbCA6sE20AoJSL
jw2cntpIY5zsemFm9SliVVA/
=fpNn
tc...@lsa.umich.edu
>In article <at5qlq$j8a$1...@zinnia.noc.ucla.edu>,
>H. Enderton <h...@sonia.math.ucla.edu> wrote:
>>To see how to define addition, look at the equation:
>> S(xz)S(yz) = S(zzS(xy)).
>>This hold iff either z = 0 or z = x + y.
>>I stole the equation from a Julia Robinson 1949 JSL paper.
>
>Clever! So that ruins (at least partially) my idea of trying to
>axiomatize multiplication without bringing addition into the picture.
Looking through Boolos and Jeffrey, I see that in chapter 21 they define
"arithmetic without addition" to be the theorems of arithmetic that do
not contain either "+" or "S". They mention that Skolem proved that this
is a decidable theory, but don't give any further info. They also state
the equation above (that Herb Enderton attributes to Julia Robinson).
George Greene
> if [whatever] is not at least as simple as recursively
> >enumerable, there arises a very serious question about
> >how you ever managed to specify it in the first place.
> >Rec.env. sets can be specified by finite TM programs.
> >I suppose you could hope to specify some non-rec.env.
> >sets finitarily if their complements were rec.env.
> >I would expect all these non-standard models to be well-
> >understood enough that they do in fact get presented finitarily
> >to people studying them. So how is that even being managed?
huus...@cc.helsinki.fi (Taneli Huuskonen) wrote in message
> With recursively axiomatizable first-order theories, for instance.
I don't see how that's an answer; I mean, for example,
PA itself is a recursively axiomatizable first-order theory.
It is easy to present its axioms finitely, using simple schemata.
But this presentation does not constitute *any* sort of presentation
(finitary or otherwise) of any non-standard model of PA, with its
non-recursive definitions of + and *.
If a recursively axiomatizable first-order theory happened
to be categorical, then I suppose you could say that just
the finitary presentation of the axioms counted as a presentation
of the model, since there is only one model to refer to and this
axiom-set in some sense defines it. But when there are multiple
non-isomorphic models, and some of them are recursive and some aren't,
then cleary the recursive specification of the axiom-set is NOT
sufficient as a specification for any non-recursive model.
tc...@lsa.umich.edu
>> With recursively axiomatizable first-order theories, for instance.
>
>I don't see how that's an answer; I mean, for example,
>PA itself is a recursively axiomatizable first-order theory.
>It is easy to present its axioms finitely, using simple schemata.
>But this presentation does not constitute *any* sort of presentation
>(finitary or otherwise) of any non-standard model of PA, with its
>non-recursive definitions of + and *.
Here's what I suspect Taneli Huuskonen is saying. A big part of
Hilbert's program was to show that infinitary, non-constructive
mathematical reasoning could be justified, by formalizing the
reasoning into a finitary system and then proving that finitary
system consistent. Now of course the "proving consistency" part
of the program fell through, but the first part was largely
successful, in the sense that even when mathematicians toss around
large cardinals and nonconstructive choice functions, we understand
that their reasoning can in principle be formalized in ZFC, which
is a recursively axiomatizable first-order theory.
Now nonstandard models of PA cannot be "directly" presented in any
recursive way. Your question was, then how do we "manage" nonstandard
models? The answer is that we manage them using nonconstructive
principles such as the axiom of choice (or weaker---but still
"nonrecursive"---principles that suffice for the argument at hand).
If the nonconstructiveness makes you giddy, then you can formalize
the argument in ZFC. This still won't give you a recursive presentation
of the nonstandard model, but it's best one can do, unless one is willing
to dismiss all talk of nonstandard models as nonsense.
George Greene
> gre...@cs.unc.edu (George Greene) blundered:
> >Because tangent is not bounded by any total function PERIOD,
> >THAT'S why.
huus...@cc.helsinki.fi (Taneli Huuskonen) wrote in message
> Maybe you forgot something like "continuous"?
Yeah, more than just maybe, I forgot.
: Otherwise, just add 1 to
: it and extend arbitrarily to integer multiples of pi.
But my WHOLE point was that the MERE fact that
you *CAN* "extend arbitrarily" (in English, anyway) calls
the whole partial/total dichotomy into QUESTION as an alias
for the dichotomy between total-recursive and recursively-
enumerable-but-NOT-recursive functions.
Just how dis-continuous or chaotic does a total
function have to get before it stops being recursive?
Just how unbounded and discontinuous does
a partial RECURSIVE function have to get before it STOPS
being just-plain-recursive?
There are a lot of partial recursive functions that are
not recursive. I am still trying to figure out whether
tangent is one of them.
To the previous objection that it has the wrong domain,
there are a lot of answers involving approximating real
arguments by arbitrarily-nearby rational ones. I didn't present
one simply because I figured somebody else already knew the
real answer to the representational question (I don't).
Here is one possible way.
Let your TM's input language be finite tuples
of finite digit strings, always representing natnums.
You can approximate any real arbitrarily closely
by a triple of the form (s,n,d) where s is the sign,
n is the numerator, and d is the denominator. Just for
fun we could even say that n is meant to represent
the nth prime (n=0 represents a numerator of 1),
similarly for d (all representations of integers would
have d=0, since that 0 would represent 1).
You could then have a TM that expects its input to be
in the form
sa,na,da,st,nt,dt,en,ep
It reject-halts on all inputs that aren't 6 naturals
with signs in front of the first two. It accept-halts
iff the rational number whose sign is st, whose numerator
is the (nt)th prime, and whose denominator is the (dt)th prime,
differs from the tangent of the rational argument whose
sign is sa, whose numerator is the (na)th prime, and whose
denominator is the (da)th prime, by an amount less than
the (en)th prime raised to the negative (ep)th power.
I expect that this is a valid description of a TM and that
this is therefore a total recursive function.
But does the fact that this TM exists say anything
about whether the original tangent is recursive?
The partiality has been completely lost in this formulation
since neither pi/2 nor any other transcendental number can
be represented exactly as an input. Or even any irrational
number like sqrt(2), for that matter. But the input language
specified here is sufficiently restrictive that just by expanding
it, one could throw in whole countable subdomains of originally
"missing" arguments, including all the rest of the rationals,
the algebraic irrationals, and (for grins) all args of the form
(s)(pi)*n/d where s encodes both the sign and pi, and n and d are
#'s of primes, as above.
Please let me try to re-phrase this question intelligently, one last time.
Every total recursive function, by definition, is computable by
a TM that halts on any input in recursive time.
(Put these functions into "class 1".)
Some other functions and sets, by contrast, are alleged to be
defined by TMs that always accept-halt when the input/argument
belongs to the set (or, for functions, when it belongs to the
domain; or just represent the function as a set of ordered pairs,
in which case they halt iff the input is x,f(x)), but will fail
to halt (instead of reject-halting) in most failure-cases,
and do not have a recursive timebound even on successes.
These sets and functions are recursively enumerable but not recursive.
(Put these functions into "class 2".)
Then, consider a third and a fourth class of functions.
For our next class, take a function in class 2 (a function which
basically *had* to be partial) and just define it arbitrarily
as 0 on all its "missing" arguments. All these functions in
class 3 are total. Is one of them recursive? --none of the
functions in class 2 was. Is one of them recursively
enumerable? --every function in class 2 was.
For our fourth class, take an arbitrary function from class 1
and obliterate a recursive set of points from its domain.
The functions in this class are computable by TMs that always
halt but they are also partial. The question arising from
class 4 (which is disjoint from class 3) is, by the phrase
"partial recursive function", *should* we mean something
from class 2, Xor something from class 4? Yes, I know,
in the real world, the answer is "2", but the prior question
is, does anybody CARE?
George Greene
> > Some partial recursive functions are partial AND just-plain-recursive
> > (take any total recursive function and obliterate a recursive
> > set of args from its domain). Others are partial and recursively
> > enumerable but NOT just-plain-recursive.
Michael Oliver <mol...@fields.utoronto.ca> wrote in message >
> "Partial recursive function" is a locution with an entirely
> standard meaning; there's no ambiguity at all.
You're about to refute yourself again.
> It's true
> that you wouldn't necessarily guess what that meaning
> is, just from knowing what "partial", "recursive" and
> "function" mean, separately.
Therefore, there is TOTAL ambiguity. Even AFTER
you know the standard meaning, knowing it means you
know it is ambiguous; you know it requires a suspension
of the usual rules of parsing English.
I VERY OBVIOUSLY ALREADY KNEW that there was a standard
interpretation. There is a standard interpretation for
"the language of set theory" and "Con(PA)", too, you know.
And I know. And you know I know. My POINT IN GENERAL is
about confusing or imprecise aspects of things that are
UNfortunately standard. I mean, IN the STANDARDS, EVEN if
nowhere else, you OUGHT to be able to get it RIGHT.
Much more to the point, clarifying what the standard
standardly means AS OPPOSED to what you might EXPECT
it to mean FROM THE DICTIONARY is pedagogically valuable
at low levels. We get a lot of people in here seeking
education on those levels.
tc...@lsa.umich.edu
>(Put these functions into "class 2".)
>
>Then, consider a third and a fourth class of functions.
>For our next class, take a function in class 2 (a function which
>basically *had* to be partial) and just define it arbitrarily
>as 0 on all its "missing" arguments. All these functions in
>class 3 are total. Is one of them recursive?
No. Perhaps the following observation may help. The naive way to try to
define a TM to compute a class 3 function is to simulate a class 2 function
when the class 2 function already had a value, and to compute some other
arbitrary function on the "missing" arguments. But in order to do this,
the TM has to figure out *where* the class 2 function is undefined, which
amounts to solving the halting problem.
> --none of the functions in class 2 was. Is one of them recursively
>enumerable? --every function in class 2 was.
Again, no. Total + r.e. = recursive. We run into the same problem as
before; the superficial "added flexibility" of not having to return an
answer is useless because here we *do* have to return an answer for all
arguments.
>For our fourth class, take an arbitrary function from class 1
>and obliterate a recursive set of points from its domain.
>The functions in this class are computable by TMs that always
>halt but they are also partial. The question arising from
>class 4 (which is disjoint from class 3) is, by the phrase
>"partial recursive function", *should* we mean something
>from class 2, Xor something from class 4? Yes, I know,
>in the real world, the answer is "2", but the prior question
>is, does anybody CARE?
Well, I can see an argument for calling class 4 "partial recursive
functions." But then you would need a name for what currently goes
by the name of "partial recursive functions," since they're an
important class, more important than class 4.
George Greene
: >(Put these functions into "class 2".)
: >
: >Then, consider a third and a fourth class of functions.
: >For our next class, take a function in class 2 (a function which
: >basically *had* to be partial) and just define it arbitrarily
: >as 0 on all its "missing" arguments. All these functions in
: >class 3 are total. Is one of them recursive?
tc...@lsa.umich.edu writes:
: No. Perhaps the following observation may help. The naive way to try to
: define a TM to compute a class 3 function is to simulate a class 2 function
: when the class 2 function already had a value, and to compute some other
: arbitrary function on the "missing" arguments. But in order to do this,
: the TM has to figure out *where* the class 2 function is undefined, which
: amounts to solving the halting problem.
True, in the general case, but NOT in this specific case:
In this specific case, the proposed class 2 function is
tangent, and EVERYBODY ALREADY KNOWS where tangent is undefined.
You can't always actually *tell*, just from the halting/
non-halting behavior of the *particular* TM you are using
for your function, whether it is in class 2 or class 4
(here is the definition of class 4 again):
: >For our fourth class, take an arbitrary function from class 1
: >and obliterate a recursive set of points from its domain.
: >The functions in this class are computable by TMs that always
: >halt but they are also partial. The question arising from
: >class 4 (which is disjoint from class 3) is, by the phrase
: >"partial recursive function", *should* we mean something
: >from class 2, Xor something from class 4?
: Well, I can see an argument for calling class 4 "partial recursive
: functions." But then you would need a name for what currently goes
: by the name of "partial recursive functions," since they're an
: important class, more important than class 4.
Well, OF COURSE they are important. That was MY WHOLE POINT.
It is precisely BECAUSE they are so important that they deserve
a name that says what it means, as opposed to saying something
that sounds like it ought to mean class 4. While it goes without
saying that any technical area will always have "technical terms",
will always have terms that experts in the area will interpret
via academic meanings that are specialized to the area, AS OPPOSED
to the meanings that the dictionary would give to the words in
their usage in natural language, technical terms don't have
to be willfully, wantonly, or even commonly, misleading.
Even if it is utterly hopeless to try to purge one's technical
language of all the usages that would seem misleading in
natural language, one can STILL MANAGE it for A FEW IMPORTANT
CASES. And the partial recursive functions are obviously
a VERY important case. Important enough that it would be
worth the effort. But I digress. I was trying to talk
about the tangent function.
As I was saying, you can't *easily* TELL, JUST from looking at
ONE TM, whether the function it represents is from class 2 or
class 4. Observing that it sometimes doesn't halt does NOT
tell you whether ALL TMs that compute the same function MUST
fail to halt for some inputs. Conversely, just because THIS
particular TM loops on infinitely many inputs does NOT mean
that there is not ANOTHER TM, computing the same function,
that simply reject-halts on those inputs (outputting something
meaning "undefined"). Since tangent only has a countable number
of asymptotes, and their pattern is regular, we could add something
to the input-language that WOULD allow us to recognize and define all
the arguments for which tangent is undefined.
So, I reiterate, is tangent recursively enumerable or TM-computable
at all, in any sense, and if it is, is it in class 2 or class 4?
--
---
"It's difficult ... you need to be united to have any
strength, but internal issues have to be addressed."
--- E. Ray Lewis, on liberalism in America
George Greene
: >> On the other hand, I believe it's a standard fact that r.e. total functions
: >> and recursive total functions are the same.
: >
: >That would seem to imply that since you could turn tangent
: >into a total function just by defining it arbitrarily
: >at its asymptotes, it must not be recursive, if the set
: >of asymptotes is recursive.
:
: I just don't see the chain of logic that you're using to get to that
: conclusion.
Are you willing to retract this?
You argued the very same thing yourself, after I phrased the questions
in terms of classes 2,3, and 4. When I defined a function in
class 3 by adding an arbitrary definition-on-missing-args to
a partial recursive function from class 2, YOU said, in
answer to the question of whether it could remain r.e.,
> No. Perhaps the following observation may help. The naive way to try to
> define a TM to compute a class 3 function is to simulate a class 2 function
> when the class 2 function already had a value, and to compute some other
> arbitrary function on the "missing" arguments. But in order to do this,
> the TM has to figure out *where* the class 2 function is undefined, which
>amounts to solving the halting problem.
Well, you were talking about the case where the set of asymptotes
is NOT recursive, but with reals, that almost doesn't matter;
you're still basically agreeing with me.
: You dismissed the issues I raised; I admit that they *seem*
: to be nitpicky things at first glance, but I'm convinced that they're at
: the heart of the issue.
"the issues I raised" is VERY ambiguous, but as you continue,
it is clear that locally, you want to raise the representational
issue, which may well be salient. I just don't know. I really
thought someone who did would've said something by now.
: For example:
:
: >> but your other comments make it sound like you're thinking of
: >> tangent as a function from R to R. But then one has to specify
: >> what one means by a recursive function from R to R.
: >
: >A function that is computable by a TM that always halts.
:
: How are you specifying your real numbers?
Given that TM input tapes are only denumerably long and have
a finite alphabet, I *cannot*possibly* be specifying "all"
of the usual real numbers in general. But I probably CAN
get *close*enough*. There is, for example, a countable
model of your favorite first-order axiomatization of the
reals. I could specify them THAT way. Or I could just
approximate them arbitrarily closely. I gave a candidate
representation in another message.
: By an infinite decimal expansion?
That is allowable but obviously undesirable since it goes without
saying that on "most" reals, you *cannot* halt.
: And the output is also presumably an infinite decimal expansion?
No, that is NOT even presumable; as even you noted, the TM in that
case will not be able to halt unless most of the finishing output-digits
of the expansion match the input-digits (which it wouldn't be able
to confirm *even* when it was in fact happening).
In any case, I proposed a representation that, though inexact,
gets arbitrarily close to exact. And it's not special about
transcendental numbers as arguments around that, either;
it can't exactly represent 4/9 either.
In any case, my underlying point here is that the math
involved in computing tangent in general is sufficiently
simple that you would NOT expect THAT to make it non-
recursive. And while you might expect the partiality and
the unboundedness to have that effect, the fact that
the set of undefined arguments is so regular means
that THAT set looks like it might be recursive (and if
it is, then it is not capable of generating non-
recursivity in the partial function).
I mean, consider f(x)=x^2 made partial by undefining
it at the integers. If its domain is the rationals
(since there are only countably many of these, the
representation problem becomes easy), this is obviously
partial-despite-being-Just-PLAIN-recursive (class 4 -- as
opposed to partial-because-it-is-recursively-
enumerable-AND-NOT-recursive, which would've been class 2).
But if the domain is reals, is the problem seriously
more difficult? Well, yes, but it is it SO much more
difficult that the question has a different answer?
Squaring is a simple operation and the integers are
a simple set of exceptions. To say of this function
that it was too complex to have a TM or to be partial-
recursive in the usual broad sense strikes me as counter-
intuitive to put it mildly.
George Greene
: Let me try a little harder to sound less nitpicky.
:
: According to you, the tangent function is not bounded by a recursive
: function.
No, NOT according to me, at least not eventually.
The problem with that is it's circular. As TH already
pointed out, tan+1 +<define it as 0 where it's undefined>
is a total function that bounds tan. If tan is recursive
then this function is, too, (especially if the set of exceptions is
recursive, which it intuitively seems regular enough to be).
So I *don't* say for sure that tan is not bounded by a
recursive function; that DEPENDS on whether it is or
isn't (partial-)recursive itself. The question is threatening
to get begged, here.
: Presumably this intuition comes from the fact that recursive
: functions are typically defined on the integers, and hence they are bounded
: on any bounded interval, while the tangent function is unbounded on a
: bounded interval? But when people talk about a "partial recursive
: function f being bounded by a total recursive function g," they are
: talking about f and g being defined on the *same domain*. If we restrict
: the tangent function to the integers, then it is no longer unbounded on
: a bounded interval, so your objection disappears.
: But you may object that this is cheating;
Indeed.
: the thing to do is not to restrict
: the tangent function to the integers but to pick some countable domain that
: lets us continue to assert that "tan is unbounded on a bounded interval."
Indeed.
: For example, we could choose our domain to be the set of rational multiples
: of pi (which of course can be recursively enumerated).
Are you sure? Pi is transcendental; representational issues
will remain relevant.
: Then the tangent
: function is indeed unbounded on (some) bounded intervals, and is a partial
: function. But now there is no reason to think that tan is not bounded by
: any total recursive function, because on the new domain there are plenty of
: total recursive functions that are unbounded on bounded intervals.
No, there aren't, not if the intervals include their endpoints;
leaving them out would be cheating; it would just be hiding the
fact that the partiality occurs AT the endpoints. Worse, this winds
up begging the question. tan is bounded by tan+1; that is recursive if tan
is, but that doesn't HELP.
tc...@lsa.umich.edu
George Greene <gre...@eagle.cs.unc.edu> wrote:
>tc...@lsa.umich.edu writes:
> : I just don't see the chain of logic that you're using to get to that
> : conclusion.
>
>Are you willing to retract this?
The context of my remark is complicated, so I'm not sure what I'd
be retracting, but let me say this. At first I didn't understand
what you were saying about the tangent function at all. After your
clarifications, I understand better, but what I still don't see is why
you thought that the tangent function was problematic in the first place.
The way you're thinking about the function, it's clearly recursive.
(Yes, it's true that there are representational issues, but you can
get around them---at least for the purposes at hand---in various ways,
including the way you sketched. See also my final paragraph below.)
The only thing I can guess is that somehow the fact that the tangent
function is unbounded on bounded intervals and cannot be extended to
a *continuous* total function led you to suspect that somehow it is
not bounded by a recursive total function. This logic I still don't
see.
It may not be important to clarify this logic...perhaps by now your
questions have been answered? If so, then we don't need to beat a
dead horse.
>"the issues I raised" is VERY ambiguous, but as you continue,
>it is clear that locally, you want to raise the representational
>issue, which may well be salient. I just don't know. I really
>thought someone who did would've said something by now.
My guess is that the reason the "experts" haven't chimed in is that until
your recent article about class 1-4 functions, which was very clear, it
wasn't clear what you were asking.
>In any case, my underlying point here is that the math
>involved in computing tangent in general is sufficiently
>simple that you would NOT expect THAT to make it non-
>recursive. And while you might expect the partiality and
>the unboundedness to have that effect, the fact that
>the set of undefined arguments is so regular means
>that THAT set looks like it might be recursive (and if
>it is, then it is not capable of generating non-
>recursivity in the partial function).
Yes, I think we're in agreement. Probably the only thing we don't share is
the intuition that "partiality and unboundedness" would lead one to suspect
non-recursiveness. Maybe your intuition comes from the linguistic fact that
the word "unbounded" has different meanings in different contexts ("not
bounded by a continuous(?) function" versus "not bounded by a recursive
function").
>But if the domain is reals, is the problem seriously
>more difficult? Well, yes, but it is it SO much more
>difficult that the question has a different answer?
I think this is a separate question from your other questions, but it is
of independent interest. Various people have introduced "models of real
computation" which lets one ask questions such as "Is the Mandelbrot set
decidable?" The one I'm most familiar with is described in the book
_Complexity_and_Real_Computation_ by Blum et al. According to their
model, squaring is a computable function from R to R, but the Mandelbrot
set is undecidable. So, questions like that *can* be given a precise
meaning, but one needs to create definitions *over and above* the standard
definitions of "recursive" to make sense of them. There isn't a unique
way to pass from the concept of recursive functions on N to the concept
of recursive functions on all of R.
tc...@lsa.umich.edu
George Greene <gre...@eagle.cs.unc.edu> wrote:
>So, I reiterate, is tangent recursively enumerable or TM-computable
>at all, in any sense, and if it is, is it in class 2 or class 4?
I think I addressed this in my other article, but to be completely clear:
It is TM-computable, and is in class 4.
Caveat: Your classes were defined in terms of recursive functions on N;
you are tacitly assuming that there ought to exist corresponding classes
of functions on R. I'm not saying this tacit assumption is false, but
one needs to do considerable work in order to get a good definition of
a "computable function from R to R," and there is no unique way of doing
it. And even after it's done, one cannot assume that every definition
and every theorem about recursive functions on N will carry over to R;
most of them ought to, if the definition is any good, but replacing N
with R leads to logically different question, which has to be analyzed
separately.
However, if we just want to address your worry about the tangent function
being unbounded and partial yet intuitively easy to compute, we can ignore
most of these niceties. The usual way our computers calculate the tangent
function is fine, and the "partialness" of tangent is no obstacle.
Taneli Huuskonen
Hash: SHA1
In <xes8yyt...@eagle.cs.unc.edu> George Greene
<gre...@eagle.cs.unc.edu> writes:
[...]
>So, I reiterate, is tangent recursively enumerable or TM-computable
>at all, in any sense, and if it is, is it in class 2 or class 4?
I'm far from an expert, but now that I've given it a little thought, I'm
impressed by the size of the can of worms you're opening with that
question. It's like trying to improve your understanding of the square
root by asking what the square root of an n-by-n identity matrix is.
There is a fairly standard notion of computability on the reals,
according to which tangent is computable. It is, however, different
from ordinary TM-computability in very essential ways. For instance,
every computable function is continuous in its domain, which has to be
an open set.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPfuldV+t0CYLfLaVEQKqjgCfZ+X97w6V/2R1GXZ2nJhogYbc7m4AoKvG
A4WPVFvVyc/ZxeUVxSrj+gjK
=qvNn
George Greene
: There is a fairly standard notion of computability on the reals,
: according to which tangent is computable. It is, however, different
: from ordinary TM-computability in very essential ways.
Well, thank you, that is sort of what I came to get.
The fact that I suspected that something like that was lurking
out there is the main reason I was slow to address the
representational issue for reals in the TM framework.
: For instance, every computable function is continuous in its
: domain, which has to be an open set.
Again, the question of technical meanings for terms that already
had a natural one sort of arises -- why did the real-functions
people choose "computable" as the name for this property if it
was in fact so essentially *different* from ordinary TM-computability?
Wouldn't the whole reason for choosing *that* adjective be that
despite the odd differences like open domains and continuity, the
concept/criterion *resulting* from those constraints winds up
having a *lot* of things in *common* with the prior notion
of "computability"?
George Greene
: The only thing I can guess is that somehow the fact that the tangent
: function is unbounded on bounded intervals and cannot be extended to
: a *continuous* total function led you to suspect that somehow it is
: not bounded by a recursive total function. This logic I still don't
: see.
I'm not using any logic, because I'm not proving anything:
the burden of proof IS ON YOU!
: Probably the only thing we don't share is the intuition that
: "partiality and unboundedness" would lead one to suspect
: non-recursiveness.
Don't be ridiculous. You share that. Just think of any
function that actually IS in class 2 (tangent was problematic;
I didn't know which class it was in; but for all the functions
that clearly ARE there, e.g., proof-length as a function of
theorem-length, the "intuition" is in fact a theorem).
: Maybe your intuition comes from the
: linguistic fact that the word "unbounded" has different meanings
: in different contexts ("not bounded by a continuous(?) function"
: versus "not bounded by a recursive function").
"recursive function" is ambiguous here.
Tangent doesn't even fit into the traditional paradigm
since the domain is wrong. For functions on N into N,
if they are recursive AS OPPOSED TO RECURSIVELY ENUMERABLE
then THEY ARE, ALL OF THEM, bounded by total recursive
functions, and their computation times are as well.
It is hard to see what continuity could even mean for
the usual class of functions on N into N.
tc...@lsa.umich.edu
George Greene <gre...@eagle.cs.unc.edu> wrote:
>Again, the question of technical meanings for terms that already
>had a natural one sort of arises -- why did the real-functions
>people choose "computable" as the name for this property if it
>was in fact so essentially *different* from ordinary TM-computability?
>Wouldn't the whole reason for choosing *that* adjective be that
>despite the odd differences like open domains and continuity, the
>concept/criterion *resulting* from those constraints winds up
>having a *lot* of things in *common* with the prior notion
>of "computability"?
The answer to your second question is yes. Some things have to give,
though. On the other hand, I'm not sure what property you're referring
to when you say that it is "essentially different from ordinary TM-
computability"?
I want to emphasize again that there is more than one way to approach
the subject of "computable" functions of real numbers. I mentioned the
model of Blum et al., but see also
http://www.cs.bham.ac.uk/~mhe/issac/node2.html
for some other references.
tc...@lsa.umich.edu
>The answer to your second question is yes. Some things have to give,
>though. On the other hand, I'm not sure what property you're referring
>to when you say that it is "essentially different from ordinary TM-
>computability"?
On re-reading, I see that I should have directed this question at Taneli
Huuskonen, not George Greene (sorry). Perhaps the "essential differences"
you refer to are just things like open sets and so on that come with
the territory? Also, which model of real computation are you thinking of?
Taneli Huuskonen
Hash: SHA1
In <ati3qt$gb3$1...@galois.mit.edu> tc...@lsa.umich.edu writes:
>In article <ati3f2$g6n$1...@galois.mit.edu>, I wrote:
>>The answer to your second question is yes. Some things have to give,
>>though. On the other hand, I'm not sure what property you're referring
>>to when you say that it is "essentially different from ordinary TM-
>>computability"?
>On re-reading, I see that I should have directed this question at Taneli
>Huuskonen, not George Greene (sorry). Perhaps the "essential differences"
>you refer to are just things like open sets and so on that come with
>the territory? Also, which model of real computation are you thinking of?
Yes, exactly. My point was that you'll end up VERY confused if you try
to treat the two subjects as one. I don't recommend even learning them
side by side.
I don't even remember where I first learned about the model of real
computation I was talking about, but I've seen it mentioned in several
articles. We say that a sequence of rationals <r_i : i \in N>
_converges quickly_ if |r_i - r_j| < 1/i for all 0 < i < j. A real
function f is said to be computable if there is a Turing machine that
outputs a sequence that converges quickly towards f(x) whenever it is
given a sequence that converges quickly towards x as input, where x is
any value in the domain of f; on other inputs, it fails to produce an
infinite output string. In this formulation, the output tape has to be
write-only.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPf04QV+t0CYLfLaVEQIPSwCgt1Md6n646qMZUQLi2HDQya7dHI0An2VJ
SeSTbEx3a7mNmOXbyj0BoJ6h
=QwRH
Taneli Huuskonen
Hash: SHA1
In <xessmwz...@eagle.cs.unc.edu> George Greene
<gre...@eagle.cs.unc.edu> writes:
[...]
>For functions on N into N,
>if they are recursive AS OPPOSED TO RECURSIVELY ENUMERABLE
>then THEY ARE, ALL OF THEM, bounded by total recursive
>functions, and their computation times are as well.
Umm... so far in this thread, I've assumed that by a "recursive
function" you mean one that's recursive as a set of ordered pairs, in
other words, a function f such that "f(x)=y" is decidable. If I
interpreted you correctly, then the above statement is simply wrong.
For instance, if we let f(x) to be the (unique) code of a terminating
computation of Turing machine x with empty input, then given x and y,
it's easy to check whether f(x)=y. However, given just x, it's
undecidable whether there exists y such that f(x)=y. And, of course,
f isn't bounded by any total recursive function.
>It is hard to see what continuity could even mean for
>the usual class of functions on N into N.
The usual topology of N is discrete, hence every function is continuous.
I don't know of any other topologies of N with direct relevance to
computability.
Taneli Huuskonen
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBPf1GzV+t0CYLfLaVEQIL/ACg5hCYwC3ahw/9sXy+ZOHIuyregrsAoIFH
4QYLMEXb9zOIYkHsPmdtckrr
=o73h