I search for intermediate results for the following:
If one has an homomorphism between two structures in the
language of first-order logic with equality, say
A and B, then (it is well-known that) for all positive
formulas F, it holds that A |= F implies B |= F
(where positive formulae means, formulae built up from
‘or’, ‘and’, existential and universal quantifiers).
On the other side if there is an isomorphism between
A and B, then for any formulae F, A |= F iff B |= F.
In Gallier’s book "Logic for Computer Science", one
can find definitions and intermediate results, but
unfortunately incorrect (pp. 182 (problem 5.3.15. (c)).
M. Ayala
ay…@informatik.uni-kl.de
In article <1993May14.151342.19…@uklirb.informatik.uni-kl.de> ay…@uklirb.informatik.uni-kl.de (Mauricio Ayala R.) writes:
- Hide quoted text — Show quoted text -
>I search for intermediate results for the following:
>If one has an homomorphism between two structures in the
>language of first-order logic with equality, say
>A and B, then (it is well-known that) for all positive
>formulas F, it holds that A |= F implies B |= F
>(where positive formulae means, formulae built up from
>’or’, ‘and’, existential and universal quantifiers).
>On the other side if there is an isomorphism between
>A and B, then for any formulae F, A |= F iff B |= F.
>In Gallier’s book "Logic for Computer Science", one
>can find definitions and intermediate results, but
>unfortunately incorrect (pp. 182 (problem 5.3.15. (c)).
I couldn’t find Gallier’s book in the library, and I’m still puzzled
by what you mean for intermediate results [ and I guess I'm not alone in
this one ]. Could you, or any other netter post the examples of that sort of
results [ or the ones in Gallier's, even if as you say are not correct ].
The original questioner posted an explanation, and send me along a copy of it;
however it has not appeared in the net yet, so I’m reposting it. [ hoping it
will only reach the connected component of my site... ]
=============================================================================
From ay…@informatik.uni-kl.de
From: "Mauricio Ayala R." <ay…@informatik.uni-kl.de>
To: wjcas…@magnus.acs.ohio-state.edu
Subject: Ints. Homomorphisms first-order structures…
I thank very much your efforts to understand mine
puzzled question.
First of all a homomorphism between structures (in the first-order logic
with equality) A and B is a surjective function h : A -> B such that
-For every n-ary function symbol f, and for every n-tuple (a1,…,an) in
A^n, h(f^A(a1,…,an))=f^B(h(a1),…,h(an));
-For every n-ary predicate symbol p, and for every n-tuple (a1,…,an) in
A^n, if p^A(a1,…,an) then p^B(h(a1),…,h(an)).
RESULT1: (preservation under homomorphism of positive formulae).
It is easy to show (by structural induction) that for any positive
formulae F[x1,...,xn] (i. e., a formula built up from atomic formulae
using only the logical connectives v,^, \forall and \exists), for
every (a1,…,an) in A^n, if A |= F[a1,...,an] then B |= F[h(a1),...,h(an)],
where h is a homomorphism from A onto B. It is usually said that positive
formulae are preserved under homomorphisms.
An isomorphism between A and B is a bijective homomorphism h : A -> B
such that for any n-ary predicate symbol p and any n-tuple (a1,…,an) in
A^n, p^A(a1,…,an) iff p^B(h(a1),…,h(an)).
RESULT2: (isomorphic structures are elementary equivalent).
It is easy to show that for any formulae F[x1,...,xn] and for every
(a1,…,an) in A^n, A |= F[a1,...,an] iff B |= F[h(a1),...,h(an)].
In effect isomorphic structures are elementary equivalent.
By "intermediate" results I mean ones which combine, avoid, enlarge, etc.
hypothesis of the last two results given rise to preservation of validity
for some type of formulae in the homomorphic|isomorphic structures.
In Gallier’s book, as was mentioned, there is an "intermediate" result,
which establishes that for first-order languages without
equality, for any formula F[x1,...,xn] and any n-tuple (a1,…,an) in
A^n, if h is a homomorphism of A onto B then A |= F[a1,...,an] iff
B |= F[h(a1),...,h(an)].
This cannot be correct since, for example, for the language which
consists of a unary predicate symbol p and a nullary function
symbol (or constant) c one can have two structures A =<{a},pa>
and B=<{b},pb> such that pa(a) is false and pb(b) is true.
Obviously, the function h : A -> B, defined by h(a)=b is a homo-
morphism of A onto B, since p^A(c^A) = pa(a) implies pb(b) = p^B(c^B);
but note that pb(b) does not imply pa(a).
The role of the equality is not essential in this counterexample and
additionally I cannot find a way to obtain a coherent modification
of the Gallier’s hypothesis (or result) to obtain an "intermediate"
correct result.
Thanks in advance for your time,
M. Ayala.
===========================================================================
end of message.
Nice exercise for the mind… I agree that it doesn’t seem simple to obtain
a correct, non-trivial version. I’ll post if I can come up with something.
[ three general notes, not related to this thread: 1. I dont post unsolved
problems, unless explicitly stated; 2. I make email contact before posting;
3. Thanks for the nice feedback ]
In article <1t6kv0$…@charm.magnus.acs.ohio-state.edu> wjcas…@magnus.acs.ohio-state.edu (W. Jose Castrellon G.) writes:
The original questioner posted an explanation, and send me along a copy of it;
however it has not appeared in the net yet, so I’m reposting it. [ hoping it
will only reach the connected component of my site... ]
=============================================================================
From ay…@informatik.uni-kl.de
From: "Mauricio Ayala R." <ay…@informatik.uni-kl.de>
To: wjcas…@magnus.acs.ohio-state.edu
Subject: Ints. Homomorphisms first-order structures…
I thank very much your efforts to understand mine
puzzled question.
In Gallier’s book, as was mentioned, there is an "intermediate" result,
which establishes that for first-order languages without
equality, for any formula F[x1,...,xn] and any n-tuple (a1,…,an) in
A^n, if h is a homomorphism of A onto B then A |= F[a1,...,an] iff
B |= F[h(a1),...,h(an)].
Is this meant to be part (a) of the exercise that your question arose from?
If so, it is misstated, as it should be about the denotation of terms
being preserved under homomorphisms.
–
Alan Smaill, JANET: A.Sma…@uk.ac.ed
Department of Artificial ARPA: A.Smaill%uk.ac…@nsfnet-relay.ac.uk
Intelligence, UUCP: …!uknet!ed.ac.uk!A.Smaill
Edinburgh University.
In article 19…@uklirb.informatik.uni-kl.de, ay…@uklirb.informatik.uni-kl.de (Mauricio Ayala R.) writes:
>I search for intermediate results for the following:
>If one has an homomorphism between two structures in the
>language of first-order logic with equality, say
>A and B, then (it is well-known that) for all positive
>formulas F, it holds that A |= F implies B |= F
>(where positive formulae means, formulae built up from
>’or’, ‘and’, existential and universal quantifiers).
This question is covered by the following triple publication of
Roger C. Lyndon in 1959. The first paper gives as basis an interpolation
theorem, the second applies this theorem to your problem:
@ARTICLE{lyndon:59,
AUTHOR = {Roger C. Lyndon},
JOURNAL = {Pacific Journal of Mathematics},
PAGES = {129–142},
TITLE = {An interpolation theorem in the predicate calculus},
VOLUME = {9},
YEAR = {1959}
}
@ARTICLE{lyndon:59a,
AUTHOR = {Roger C. Lyndon},
JOURNAL = {Pacific Journal of Mathematics},
PAGES = {143–154},
TITLE = {Properties preserved under homomorphism},
VOLUME = {9},
YEAR = {1959}
}
@ARTICLE{lyndon:59b,
AUTHOR = {Roger C. Lyndon},
JOURNAL = {Pacific Journal of Mathematics},
PAGES = {143–154},
TITLE = {Properties preserved in subdirect products},
VOLUME = {9},
YEAR = {1959}
}
>On the other side if there is an isomorphism between
>A and B, then for any formulae F, A |= F iff B |= F.
I have no source for that, but it is an easy induction on the size of
first order formulae.
Peter Niebert
In article <1993May14.151342.19…@uklirb.informatik.uni-kl.de>,
ay…@uklirb.informatik.uni-kl.de (Mauricio Ayala R.) wrote:
- Hide quoted text — Show quoted text -
> I search for intermediate results for the following:
> If one has an homomorphism between two structures in the
> language of first-order logic with equality, say
> A and B, then (it is well-known that) for all positive
> formulas F, it holds that A |= F implies B |= F
> (where positive formulae means, formulae built up from
> ‘or’, ‘and’, existential and universal quantifiers).
> On the other side if there is an isomorphism between
> A and B, then for any formulae F, A |= F iff B |= F.
> In Gallier’s book "Logic for Computer Science", one
> can find definitions and intermediate results, but
> unfortunately incorrect (pp. 182 (problem 5.3.15. (c)).
I write this posting coscious that I may have misunderstood the way
logicians use the word "homomorphism", and seeking illumination.
Given a (many-sorted) vocabulary, I understand a homomorphism from one
structure, A, to another, B, to be a family of functions f_s: A_s -> B_s
(A_s the carrier of sort s in A) such that for all x, y, … –
a(f(x), f(y), …) = f(a(x, y, …))
P(x, y, …) => P(f(x), f(y), …)
for all function symbols f and predicate symbols P in the vocabulary. (I’ve
dropped the sort subscripts – if this isn’t clear, think of the
single-sorted case.)
Given this definition, I can say –
* If F is a sentence built up from ‘or’, ‘and’, and existential
quantifiers, then A |= F implies B |= F.
* More generally, if F has free variables but is still built up from ‘or’,
‘and’, and existential quantifiers, then the carrier functions f_s extend
to a function f_F from {A|F} to {B|F}, where
{A|F} = {(x, y, …) in appropriate product of carriers A_s | F(x, y,
…)}
* If you admit universal quantification, then this is spoiled. For
instance, consider the language for monoids (one sort, one constant 1, one
binary operator .) A homomorphism as defined above is just what the
algebraists would say it is – a function that preserves 1 and .. Consider
F =_def (all)x,y. x.y = y.x
Then A |= F iff A is commutative, but there can easily be a homomorphism
from a commutative monoid to a non-commutative one.
I think the point is that universal quantification is "not as positive" as
existential. It may look like just a big conjunction (of properties for all
the elements there are), but there’s an implicit negative aspect saying
"and there’s nothing else".
Steve Vickers.
In article <1t6kv0$…@charm.magnus.acs.ohio-state.edu>,
wjcas…@magnus.acs.ohio-state.edu (W. Jose Castrellon G.) wrote:
> …
> First of all a homomorphism between structures (in the first-order logic
> with equality) A and B is a surjective function h : A -> B such that
> -For every n-ary function symbol f, and for every n-tuple (a1,…,an) in
> A^n, h(f^A(a1,…,an))=f^B(h(a1),…,h(an));
> -For every n-ary predicate symbol p, and for every n-tuple (a1,…,an) in
> A^n, if p^A(a1,…,an) then p^B(h(a1),…,h(an)).
> …
This answers completely a previous posting of mine about the original
question – thanks.
But, coming from an algebraic background, I’m puzzled by the insistence on
surjectiveness. Can anyone explain why logicians do this? Or confirm that
it is indeed the standard definition in logic?
Steve Vickers.
Sorry about this – the newsserver requires me to be less brief. I think the
easiest thing is if I repeat what I said above but you can save yourself
some trouble by not reading it…
———————————————————-
This answers completely a previous posting of mine about the original
question – thanks.
But, coming from an algebraic background, I’m puzzled by the insistence on
surjectiveness. Can anyone explain why logicians do this? Or confirm that
it is indeed the standard definition in logic?
Steve Vickers.
In article <sjv-200593124…@macvickers.doc.ic.ac.uk>, I wrote:
> But, coming from an algebraic background, I’m puzzled by the insistence on
> surjectiveness. Can anyone explain why logicians do this? Or confirm that
> it is indeed the standard definition in logic?
I’ve discovered now that Chang and Keisler too require in their definition
of homomorphism between first order structures that the carrier functions
should be surjective (for them, the more general, possibly non-surjective
notion is "homomorphic embedding").
Can anyone explain why?
No Humpty Dumpty answers ("because they choose to, as is their right"),
please. I can imagine historical reasons – I believe the word has evolved
somewhat since it was first used. But it would also be interesting to hear
mathematical reasons for taking the surjective version as more fundamental.
In my own work on geometric logic I need to use the more general notion,
and I’d certainly prefer to use the word "homomorphism" for it, the way the
algebraists do. But if the Chang and Keisler definition is absolutely
standard amongst logicians I obviously need to be careful.
Steve Vickers.
Here’s one "intermediate result" I happen to have looked at recently.
Call a homomorphism h: <A, R^A> -> <B, R^B> (where R is binary, for
simplicity) _strong_ iff for all a1, a2 in A,
R^A(a1, a2) <=> R^B(h(a1), h(a2))
A sentence is preserved under strong homomorphisms of relational
structures of this similarity type iff it is equivalent to a sentence of
the form
(E x_1)(y_1)(z_1)(E x_2)(y_2)(z_2) … (E x_n)(y_n)(z_n) F
where F is a conjunction of disjunction of formulas that are either
atomic (i.e., R(u, v) for some variables u and v) or have the form
-R(y_k, z_k) for some positive k less than or equal to n. (I believe
the result is due to Keisler, and that it can be found in Chang and
Keisler.)
— rar