Can one define "field" without using quantifiers? -- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
On Mon, 09 Nov 2009 10:37:11 +0000, Frederick Williams
<frederick.willia...@tesco.net> wrote: >Can one define "field" without using quantifiers?
Surely we need to define "define without using quantifiers" before we can answer this.
In particular, are we allowed constant symbols? And are we supposed to interpret something like "x + y = y + x" to mean that the identity holds for all x and y?
David C. Ullrich
"Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.)
> On Mon, 09 Nov 2009 10:37:11 +0000, Frederick Williams > <frederick.willia...@tesco.net> wrote:
> >Can one define "field" without using quantifiers?
> Surely we need to define "define without using > quantifiers" before we can answer this.
Agreed.
> In particular, are we allowed constant symbols?
My question becomes two questions: with and without. Let's say constant symbols allowed initially.
> And are we supposed to interpret something like > "x + y = y + x" to mean that the identity holds > for all x and y?
Yes, that is I think the usual understanding of free variable expressions.
I might have asked: can 'field' be defined without using 'there exists...', but naturally I don't want to use
'it's not the case that for all... such and such is false'.
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
> > On Mon, 09 Nov 2009 10:37:11 +0000, Frederick Williams > > <frederick.willia...@tesco.net> wrote:
> > >Can one define "field" without using quantifiers?
> > Surely we need to define "define without using > > quantifiers" before we can answer this.
> Agreed.
> > In particular, are we allowed constant symbols?
> My question becomes two questions: with and without. Let's say constant > symbols allowed initially.
> > And are we supposed to interpret something like > > "x + y = y + x" to mean that the identity holds > > for all x and y?
> Yes, that is I think the usual understanding of free variable > expressions.
> I might have asked: can 'field' be defined without using 'there > exists...', but naturally I don't want to use
> 'it's not the case that for all... such and such is false'.
The only place where you must write "there exists" in the definition of a field is where you state that an additive and multiplicative inverse operation exist for the field. So if you don't want to say "there exists," make the additive inverse map (sending x to -x) and the multiplicative inverse map (sending x to 1/x) part of the data of the field, i.e., they are structure maps of the field, like the addition and multiplication maps, instead of simply stating that they must exist. This gives you exactly the same category of fields as before.
> -- > Which of the seven heavens / Was responsible her smile / > Wouldn't be sure but attested / That, whoever it was, a god / > Worth kneeling-to for a while / Had tabernacled and rested.
With the explanation of "without quantifiers" specified there, your answer is "no", which we can see by noting that the cartesian product of two fields may fail to be a field.
> With the explanation of "without quantifiers" specified there, your > answer is "no", which we can see by noting that the cartesian product > of two fields may fail to be a field.
> > With the explanation of "without quantifiers" specified there, your > > answer is "no", which we can see by noting that the cartesian product > > of two fields may fail to be a field.
> The linked artcile is so imprecise that it's worthless. > The appropriate theorem is Birkhoff's HSP theorem. > See this prior thread for further discussion. > http://google.com/group/sci.math/msg/4dc8c979a6597bbd
Thank you. So when I wrote in my op 'Can one define "field" without using quantifiers?' I meant 'Can one define "field" equationally?'? I suppose that equational implies without quantifiers, but without quantifiers doesn't necessarily imply equational. E'en now I am rummaging about in Gr\"atzer's Universal Algebra.
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
> On Nov 9, 9:35 am, Frederick Williams <frederick.willia...@tesco.net> > wrote: > > "David C. Ullrich" wrote:
> > > On Mon, 09 Nov 2009 10:37:11 +0000, Frederick Williams > > > <frederick.willia...@tesco.net> wrote:
> > > >Can one define "field" without using quantifiers?
> > > Surely we need to define "define without using > > > quantifiers" before we can answer this.
> > Agreed.
> > > In particular, are we allowed constant symbols?
> > My question becomes two questions: with and without. Let's say constant > > symbols allowed initially.
> > > And are we supposed to interpret something like > > > "x + y = y + x" to mean that the identity holds > > > for all x and y?
> > Yes, that is I think the usual understanding of free variable > > expressions.
> > I might have asked: can 'field' be defined without using 'there > > exists...', but naturally I don't want to use
> > 'it's not the case that for all... such and such is false'.
> The only place where you must write "there exists" in the definition > of a field is where you state that an additive and multiplicative > inverse operation exist for the field. So if you don't want to say > "there exists," make the additive inverse map (sending x to -x) and > the multiplicative inverse map (sending x to 1/x) part of the data of > the field, i.e., they are structure maps of the field, like the > addition and multiplication maps, instead of simply stating that they > must exist. This gives you exactly the same category of fields as > before.
Does it matter that x |-> 1/x is not total?
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
> > > With the explanation of "without quantifiers" specified there, your > > > answer is "no", which we can see by noting that the cartesian product > > > of two fields may fail to be a field.
> > The linked artcile is so imprecise that it's worthless. > > The appropriate theorem is Birkhoff's HSP theorem. > > See this prior thread for further discussion. > > http://google.com/group/sci.math/msg/4dc8c979a6597bbd
> Thank you. So when I wrote in my op 'Can one define "field" without > using quantifiers?' I meant 'Can one define "field" equationally?'? I > suppose that equational implies without quantifiers, but without > quantifiers doesn't necessarily imply equational. E'en now I am > rummaging about in Gr\"atzer's Universal Algebra.
I guess that universal quantifiers are sufficient if you allow the inequality not(0 = 1).
> > On Nov 9, 9:35 am, Frederick Williams <frederick.willia...@tesco.net> > > wrote: > > > "David C. Ullrich" wrote:
> > > > On Mon, 09 Nov 2009 10:37:11 +0000, Frederick Williams > > > > <frederick.willia...@tesco.net> wrote:
> > > > >Can one define "field" without using quantifiers?
> > > > Surely we need to define "define without using > > > > quantifiers" before we can answer this.
> > > Agreed.
> > > > In particular, are we allowed constant symbols?
> > > My question becomes two questions: with and without. Let's say constant > > > symbols allowed initially.
> > > > And are we supposed to interpret something like > > > > "x + y = y + x" to mean that the identity holds > > > > for all x and y?
> > > Yes, that is I think the usual understanding of free variable > > > expressions.
> > > I might have asked: can 'field' be defined without using 'there > > > exists...', but naturally I don't want to use
> > > 'it's not the case that for all... such and such is false'.
> > The only place where you must write "there exists" in the definition > > of a field is where you state that an additive and multiplicative > > inverse operation exist for the field. So if you don't want to say > > "there exists," make the additive inverse map (sending x to -x) and > > the multiplicative inverse map (sending x to 1/x) part of the data of > > the field, i.e., they are structure maps of the field, like the > > addition and multiplication maps, instead of simply stating that they > > must exist. This gives you exactly the same category of fields as > > before.
> Does it matter that x |-> 1/x is not total?
> -- > Which of the seven heavens / Was responsible her smile / > Wouldn't be sure but attested / That, whoever it was, a god / > Worth kneeling-to for a while / Had tabernacled and rested.
Obviously one needs to ask that the multiplicative inverse map only be defined on the nonzero elements.
Okay here's the definition: a FIELD is a set X together with two distinguished elements 0,1 in X, and four maps: a: X \times X \rightarrow X ("addition"), m: X \times X \rightarrow X ("multiplication"), i: X \rightarrow X ("additive inverse"), and r: X - {0} \rightarrow X - {0} ("reciprocal" or "multiplicative inverse"), such that, for all elements x,y,z of X: a(x,a(y,z)) = a(a(x,y),z) (addition is associative) a(x,y) = a(y,x) (addition is commutative) a(0,x) = x (0 is the additive identity element) a(i(x),x) = 0 (i(x) is the additive inverse of x) m(x,m(y,z)) = m(m(x,y),z) (multiplication is associative) m(x,y) = m(y,x) (multiplication is commutative) m(1,x) = x (1 is the multiplicative identity element) if x is nonzero then m(r(x),x) = 1 (r(x) is the multiplicative inverse of x) m(x,a(y,z)) = a(m(x,y),m(x,z)) (multiplication distributes over addition).
I think that's it, unless I missed an axiom somewhere.
>>>> With the explanation of "without quantifiers" specified there, your >>>> answer is "no", which we can see by noting that the cartesian product >>>> of two fields may fail to be a field.
>>> The linked article is so imprecise that it's worthless. >>> The appropriate theorem is Birkhoff's HSP theorem. >>> See this prior thread for further discussion. >>> http://google.com/group/sci.math/msg/4dc8c979a6597bbd
>> Thank you. So when I wrote in my op 'Can one define "field" without >> using quantifiers?' I meant 'Can one define "field" equationally?'? I >> suppose that equational implies without quantifiers, but without >> quantifiers doesn't necessarily imply equational. E'en now I am >> rummaging about in Gr\"atzer's Universal Algebra.
> I guess that universal quantifiers are sufficient > if you allow the inequality not(0 = 1).
I don't think so. Precisely what axioms do you have in mind?
> Can one define "field" without using quantifiers?
How do we reconcile A's "yes" and G. A. Edgar's "no"?
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
Frederick Williams <frederick.willia...@tesco.net> wrote: > Frederick Williams wrote:
>> Can one define "field" without using quantifiers?
> How do we reconcile A's "yes" and G. A. Edgar's "no"?
Because your query was imprecise, you should not be surprised that you've received answers based upon different interpretations of it. GAE interpreted "without quantifiers" to mean equational logic, whereas A interpreted it more generally as permitting implications (e.g. Horn logic, see the link in my prior post here). It is not possible to give a purely equational axiomatization of fields simply because the existence of such would imply that fields were closed under products - which they clearly are not, e.g. (1,0)*(0,1) = (0,0) => (0,1) is a zero-divisor if 1 != 0 e.g. 3 * 4 = 0 in Z/2 x Z//3 = Z/6.
> Frederick Williams <frederick.willia...@tesco.net> wrote: > > Frederick Williams wrote:
> >> Can one define "field" without using quantifiers?
> > How do we reconcile A's "yes" and G. A. Edgar's "no"?
> Because your query was imprecise, you should not be surprised > that you've received answers based upon different interpretations > of it. GAE interpreted "without quantifiers" to mean equational > logic, whereas A interpreted it more generally as permitting > implications
Right. Thank you. I meant just without quantifiers(*) but all other symbols of FOL allowed. Both answers are interesting.
So to the next question: is an axiomatization of the reals possible without quantifiers? I think completeness needs "there exists".
> (e.g. Horn logic, see the link in my prior post here). > It is not possible to give a purely equational axiomatization of > fields simply because the existence of such would imply that > fields were closed under products - which they clearly are not, > e.g. (1,0)*(0,1) = (0,0) => (0,1) is a zero-divisor if 1 != 0 > e.g. 3 * 4 = 0 in Z/2 x Z//3 = Z/6.
(* As I wrote, so I don't think I was being imprecise.)
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
Frederick Williams <frederick.willia...@tesco.net> wrote: >Bill Dubuque wrote: >> Frederick Williams <frederick.willia...@tesco.net> wrote: >>> Frederick Williams wrote:
>>>> Can one define "field" without using quantifiers?
>>> How do we reconcile A's "yes" and G. A. Edgar's "no"?
>> Because your query was imprecise, you should not be surprised >> that you've received answers based upon different interpretations >> of it. GAE interpreted "without quantifiers" to mean equational >> logic, whereas A interpreted it more generally as permitting >> implications
> Right. Thank you. I meant just without quantifiers(*) but all > other symbols of FOL allowed. Both answers are interesting. > (* As I wrote, so I don't think I was being imprecise.)
No, that's not what you mean since it would disallow equational identities (which are implicitly universally quantified). Nor did you specify if you are working in first order or higher order logic, with total or partial operations, etc. So your query was most definitely very imprecise. If you desire to understand the interplay between syntax and semantics, you should delve into a good textbook on model theory.
Bill Dubuque <w...@nestle.csail.mit.edu> wrote: > Marc Olschok <nob...@nowhere.invalid> wrote: > > Frederick Williams <frederick.willia...@tesco.net> wrote: > >> Bill Dubuque wrote:
> >>>> With the explanation of "without quantifiers" specified there, your > >>>> answer is "no", which we can see by noting that the cartesian product > >>>> of two fields may fail to be a field.
> >>> The linked article is so imprecise that it's worthless. > >>> The appropriate theorem is Birkhoff's HSP theorem. > >>> See this prior thread for further discussion. > >>> http://google.com/group/sci.math/msg/4dc8c979a6597bbd
> >> Thank you. So when I wrote in my op 'Can one define "field" without > >> using quantifiers?' I meant 'Can one define "field" equationally?'? I > >> suppose that equational implies without quantifiers, but without > >> quantifiers doesn't necessarily imply equational. E'en now I am > >> rummaging about in Gr\"atzer's Universal Algebra.
> > I guess that universal quantifiers are sufficient > > if you allow the inequality not(0 = 1).
> I don't think so. Precisely what axioms do you have in mind?
Actually I had at first thought of allowing partial maps in order to use a function symbol for the multiplicative inverse. But that is probably not what the OP wanted anyway.
Right now I have the following in mind:
Language function symbols of arity 0: 0 , 1 function symbols of arity 1: n (for additive inverse) function symbols of arity 2: + , -, * predicate symbol of arity 1: I
Axioms (universal quantification implicitely assumed) first the usual axioms for commutative rings with 1.
(1) I(x) or I(1-x) (2) I(x-y) --> I(x) or I(y) (3) I(xy) <--> I(x) and I(y) (4) I(1) (5) not I(0) (6) (x=0) or I(x)
The idea is, that (1)-(5) should give commutative local rings, where I describes the invertible elements (i.e. the complement of the maximal ideal). Then (6) just states that the maximal ideal is in fact 0.
I am not sure if it works this way. Also the OP might object against negation, because once you use negation you might as well simulate the existencial quantifiers wit univeral ones, which he did not want to do.
> Bill Dubuque <w...@nestle.csail.mit.edu> wrote: > > Marc Olschok <nob...@nowhere.invalid> wrote: > > > Frederick Williams <frederick.willia...@tesco.net> wrote: > > >> Bill Dubuque wrote:
> > >>>> With the explanation of "without quantifiers" specified there, your > > >>>> answer is "no", which we can see by noting that the cartesian product > > >>>> of two fields may fail to be a field.
> > >>> The linked article is so imprecise that it's worthless. > > >>> The appropriate theorem is Birkhoff's HSP theorem. > > >>> See this prior thread for further discussion. > > >>> http://google.com/group/sci.math/msg/4dc8c979a6597bbd
> > >> Thank you. So when I wrote in my op 'Can one define "field" without > > >> using quantifiers?' I meant 'Can one define "field" equationally?'? I > > >> suppose that equational implies without quantifiers, but without > > >> quantifiers doesn't necessarily imply equational. E'en now I am > > >> rummaging about in Gr\"atzer's Universal Algebra.
> > > I guess that universal quantifiers are sufficient > > > if you allow the inequality not(0 = 1).
> > I don't think so. Precisely what axioms do you have in mind?
> Actually I had at first thought of allowing partial maps in order > to use a function symbol for the multiplicative inverse. > But that is probably not what the OP wanted anyway.
> Right now I have the following in mind:
> Language > function symbols of arity 0: 0 , 1 > function symbols of arity 1: n (for additive inverse) > function symbols of arity 2: + , -, * > predicate symbol of arity 1: I
> Axioms (universal quantification implicitely assumed) > first the usual axioms for commutative rings with 1.
> (1) I(x) or I(1-x) > (2) I(x-y) --> I(x) or I(y) > (3) I(xy) <--> I(x) and I(y) > (4) I(1) > (5) not I(0) > (6) (x=0) or I(x)
> The idea is, that (1)-(5) should give commutative local rings, where > I describes the invertible elements (i.e. the complement of the maximal > ideal). Then (6) just states that the maximal ideal is in fact 0.
> I am not sure if it works this way. Also the OP might object against > negation, because once you use negation you might as well simulate > the existencial quantifiers wit univeral ones, which he did not > want to do.
I want _no_ quantifiers, free variables only. That was just so Ux wouldn't get replaced with ~Ex~.
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
> With the explanation of "without quantifiers" specified there, your > answer is "no", which we can see by noting that the cartesian product > of two fields may fail to be a field.
I am now led to wonder what an equation _is_. E.g.
x = 0 or y = 0
doesn't look like an equation, it looks like a disjunction, but where fields are concerned it is interdeducible with
xy = 0
which certainly looks like an equation. Who's to say that
x = 0 -> y = 0
cannot (in some context) be replaced by an equation also?
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
>> With the explanation of "without quantifiers" specified there, your >> answer is "no", which we can see by noting that the cartesian product >> of two fields may fail to be a field.
> I am now led to wonder what an equation _is_. E.g.
> x = 0 or y = 0
> doesn't look like an equation, it looks like a disjunction, > but where fields are concerned it is interdeducible with
> xy = 0
Yes, but that's only because one has another disjunctive axiom that implies such. The theory of integral domains, i.e. rings satisfying xy = 0 => x = 0 /\ y = 0 is not equational for the same reason as fields, namely they are not closed under products, e.g. (1,0)(0,1) = (0,0) but neither factor is (0,0). Further some authors exclude the zero ring via the inequation 1 != 0.
> which certainly looks like an equation. Who's to say that
> x = 0 -> y = 0
> cannot (in some context) be replaced by an equation also?
The reason xy = 0 => x = 0 /\ y = 0 cannot be replaced by some equations is precisely as mentioned above. Namely if that were true then one would have a purely equational axiomatization of integral domains. This implies that they would be closed under products - which they are not. Is it not obvious to you that equational identities are preserved in products? Have you studied abstract algebra?
Bill Dubuque wrote: > Is it not obvious to you that equational identities are > preserved in products? Have you studied abstract algebra?
That can only be obvious if one knows what the definition of equational identity is.
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
Frederick Williams <frederick.willia...@tesco.net> wrote: > Marc Olschok wrote: >[...] > > I am not sure if it works this way. Also the OP might object against > > negation, because once you use negation you might as well simulate > > the existencial quantifiers wit univeral ones, which he did not > > want to do.
> I want _no_ quantifiers, free variables only. That was just so Ux > wouldn't get replaced with ~Ex~.
I guess you have to sort this out with an earlier incarnation of yourself. In message <4AF828AF.EC2D3...@tesco.net> you wrote
| "David C. Ullrich" wrote: |[...] | > And are we supposed to interpret something like | > "x + y = y + x" to mean that the identity holds | > for all x and y? | | Yes, that is I think the usual understanding of free variable | expressions. |
This means that you want e.g. "x + y = y + x" as a shorthand for "forall x: forall y: x + y = y + x". Actually this is not how free variables are understood in logic, but the use of this shorthand is widespread and convenient once it is understand that it is a shorthand.
> Frederick Williams <frederick.willia...@tesco.net> wrote: > > Marc Olschok wrote: > >[...] > > > I am not sure if it works this way. Also the OP might object against > > > negation, because once you use negation you might as well simulate > > > the existencial quantifiers wit univeral ones, which he did not > > > want to do.
> > I want _no_ quantifiers, free variables only. That was just so Ux > > wouldn't get replaced with ~Ex~.
> I guess you have to sort this out with an earlier incarnation > of yourself. In message <4AF828AF.EC2D3...@tesco.net> you wrote
> | "David C. Ullrich" wrote: > |[...] > | > And are we supposed to interpret something like > | > "x + y = y + x" to mean that the identity holds > | > for all x and y? > | > | Yes, that is I think the usual understanding of free variable > | expressions. > |
> This means that you want e.g. "x + y = y + x" as a shorthand > for "forall x: forall y: x + y = y + x".
Not at all. That suggests to me that 'forall' is in the language and one is just omitting it for brevity's sake. Rather I envisage a language that doesn't have 'forall' in it (and if it has 'not', it doesn't have 'exists' either).
> Actually this is not how free variables are understood in logic, > but the use of this shorthand is widespread and convenient once > it is understand that it is a shorthand.
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
Frederick Williams <frederick.willia...@tesco.net> wrote: > Marc Olschok wrote: >> Frederick Williams <frederick.willia...@tesco.net> wrote: >>> Marc Olschok wrote: >>>[...] >>>> I am not sure if it works this way. Also the OP might object against >>>> negation, because once you use negation you might as well simulate >>>> the existencial quantifiers wit univeral ones, which he did not >>>> want to do.
>>> I want _no_ quantifiers, free variables only. That was just so Ux >>> wouldn't get replaced with ~Ex~.
>> I guess you have to sort this out with an earlier incarnation >> of yourself. In message <4AF828AF.EC2D3...@tesco.net> you wrote
>> | "David C. Ullrich" wrote: >> |[...] >> | > And are we supposed to interpret something like >> | > "x + y = y + x" to mean that the identity holds >> | > for all x and y? >> | >> | Yes, that is I think the usual understanding of free variable >> | expressions.
>> This means that you want e.g. "x + y = y + x" as a shorthand >> for "forall x: forall y: x + y = y + x".
> Not at all. That suggests to me that 'forall' is in the language and > one is just omitting it for brevity's sake. Rather I envisage a > language that doesn't have 'forall' in it (and if it has 'not', it > doesn't have 'exists' either).
The universally quantified version is the definition of what you mean in first-order logic - which is the standard logical language for such matters. If your language omits the explicit universal quantifiers then you have to explicitly define how to interpret such identities, and doing so ends up being the same as saying that the free variables are universally quantified, so that your definition is equivalent to the first-order logic version with the explicit universal quantifiers. I suggest that you peruse a textbook on universal algebra or model theory.
Can 'field' be defined without the use of an existential quantifier?
But some wag might have replied 'yes' and taken a definition with (Ex) and replaced (Ex) with ~(Ux)~. Hence my asking about no quantifiers at all.
I think the question is interesting even if you don't.
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
> [...] If your language omits the explicit universal > quantifiers then you have to explicitly define how to interpret > such identities,
Not necessarily. I could remain in the domain of pure syntax, I don't know if that would be sensible, but it would be possible.
-- Which of the seven heavens / Was responsible her smile / Wouldn't be sure but attested / That, whoever it was, a god / Worth kneeling-to for a while / Had tabernacled and rested.
