Can field be defined using free variables?
Frederick Williams
--
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.
David C. Ullrich
<frederick...@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.)
Frederick Williams
>
> On Mon, 09 Nov 2009 10:37:11 +0000, Frederick Williams
> <frederick...@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'.
A
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.
G. A. Edgar
<frederick...@tesco.net> wrote:
> Can one define "field" without using quantifiers?
Birkhoff's completeness theorem is related to this.
http://www.encyclopedia.com/doc/1O11-Birkhoffscompletenessthrm.html
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.
--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/
Bill Dubuque
> <frederick...@tesco.net> wrote:
>>
>> Can one define "field" without using quantifiers?
>
> Birkhoff's completeness theorem is related to this.
>
> http://www.encyclopedia.com/doc/1O11-Birkhoffscompletenessthrm.html
>
> 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
--Bill Dubuque
Frederick Williams
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.
Frederick Williams
Does it matter that x |-> 1/x is not total?
Marc Olschok
> Bill Dubuque wrote:
> >
> > "G. A. Edgar" <ed...@math.ohio-state.edu.invalid> wrote:
> > > <frederick...@tesco.net> wrote:
> > >>
> > >> Can one define "field" without using quantifiers?
> > >
> > > Birkhoff's completeness theorem is related to this.
> > >
> > > http://www.encyclopedia.com/doc/1O11-Birkhoffscompletenessthrm.html
> > >
> > > 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).
--
Marc
A
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.
Bill Dubuque
> Frederick Williams <frederick...@tesco.net> wrote:
>> Bill Dubuque wrote:
>>>
>>> "G. A. Edgar" <ed...@math.ohio-state.edu.invalid> wrote:
>>>> <frederick...@tesco.net> wrote:
>>>>>
>>>>> Can one define "field" without using quantifiers?
>>>>
>>>> Birkhoff's completeness theorem is related to this.
>>>>
>>>> http://www.encyclopedia.com/doc/1O11-Birkhoffscompletenessthrm.html
>>>>
>>>> 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 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?
--Bill Dubuque
Frederick Williams
>
> Can one define "field" without using quantifiers?
How do we reconcile A's "yes" and G. A. Edgar's "no"?
Bill Dubuque
> 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.
--Bill Dubuque
Frederick Williams
>
> Frederick Williams <frederick...@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.)
Bill Dubuque
>Bill Dubuque wrote:
>> Frederick Williams <frederick...@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.
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.
Marc Olschok
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.
--
Marc
Frederick Williams
I want _no_ quantifiers, free variables only. That was just so Ux
wouldn't get replaced with ~Ex~.
Frederick Williams
>
> In article <4AF7F0D7...@tesco.net>, Frederick Williams
> <frederick...@tesco.net> wrote:
>
> > Can one define "field" without using quantifiers?
>
> Birkhoff's completeness theorem is related to this.
>
> http://www.encyclopedia.com/doc/1O11-Birkhoffscompletenessthrm.html
>
> 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?
Bill Dubuque
> "G. A. Edgar" wrote:
>> Frederick Williams <frederick...@tesco.net> wrote:
>>>
>>> Can one define "field" without using quantifiers?
>>
>> Birkhoff's completeness theorem is related to this.
>> http://www.encyclopedia.com/doc/1O11-Birkhoffscompletenessthrm.html
>>
>> 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
Frederick Williams
> 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.
Marc Olschok
> 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...@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.
--
Marc
Frederick Williams
>
> Frederick Williams <frederick...@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...@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.
--
Bill Dubuque
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.
Frederick Williams
>
> The [...]
What I was originally going to ask was
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.
Frederick Williams
>
> [...] 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.