Author 
Message 
un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Mon Apr 17, 2006 10:54 am Post subject:
Strong homomorphism



Let S be a finite alphabet. Let A and B finite models for S. Let
Constant(S), Relation(S) and Function(S) denote constant, relation and
function symbols of S. For c in S, c^A means c's interpretation on
model A. Function h: Domain(A) > Domain(B) is homomorphism from model
A to model B if it satisfies:
i) For every c in Constant(S) h(c^A) = c^B
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
R^A it holds that ( h(a_0), ..., h(a_{n1}) ) in R^B
iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n1} )) = f^B (h(a_0), ..., h(a_{n1} ) )
If condition ii is stated in stronger form:
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n1}) in R^A <=> (h(a_0), ...., h(a_{n1})) in R^B
the homomorphism is said to be a strong one.
The problem is that I don't get any intuitive feeling on the difference
between "normal" and strong versions of homomorphisms. What is the
"actual" difference? How it could be described? 

Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Mon Apr 17, 2006 11:24 am Post subject:
Re: Strong homomorphism



On Mon, 17 Apr 2006, un student wrote:
Quote:  Let S be a finite alphabet. Let A and B finite models for S. Let
Constant(S), Relation(S) and Function(S) denote constant, relation and
function symbols of S. For c in S, c^A means c's interpretation on
model A. Function h: Domain(A) > Domain(B) is homomorphism from model
A to model B if it satisfies:
i) For every c in Constant(S) h(c^A) = c^B
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
R^A it holds that ( h(a_0), ..., h(a_{n1}) ) in R^B
iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n1} )) = f^B (h(a_0), ..., h(a_{n1} ) )
If condition ii is stated in stronger form:
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n1}) in R^A <=> (h(a_0), ...., h(a_{n1})) in R^B
the homomorphism is said to be a strong one.
The problem is that I don't get any intuitive feeling on the difference
between "normal" and strong versions of homomorphisms. What is the
"actual" difference? How it could be described?
In weak version it's possible for R^B to have relations in addition to 
relations given to it from R^A thru h. In strong version, if h is
bijection, then h would be isomorphism but not so for weak version.
Compare groups where weak homomorphsim is into while strong
homomorphism is onto to make similar usages of words. 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Mon Apr 17, 2006 1:16 pm Post subject:
Re: Strong homomorphism



William Elliot wrote:
Quote:  In weak version it's possible for R^B to have relations in addition to
relations given to it from R^A thru h. In strong version, if h is
bijection, then h would be isomorphism but not so for weak version.

I see. What if strong homomorphism is injective but not bijection? Then
it could be the case that #Dom(B) >= #Dom(A), but otherwise the
structures would be the same?
Quote:  Compare groups where weak homomorphsim is into while strong
homomorphism is onto to make similar usages of words.

I have to think about this for a while, but I think I'll get it.
Thanks! 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Mon Apr 17, 2006 2:48 pm Post subject:
Re: Strong homomorphism



On 17 Apr 2006 06:16:50 0700, un student <un.student@gmail.com>
wrote in alt.math.undergrad:
Quote:  William Elliot wrote:

[...]
Quote:  Compare groups where weak homomorphsim is into while strong
homomorphism is onto to make similar usages of words.
I have to think about this for a while, but I think I'll get it.

It isn't true: there are no relation symbols in the language of
group theory.
Brian 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Mon Apr 17, 2006 2:53 pm Post subject:
Re: Strong homomorphism



On 17 Apr 2006 03:54:15 0700, un student <un.student@gmail.com>
wrote in alt.math.undergrad:
Quote:  Let S be a finite alphabet. Let A and B finite models for S. Let
Constant(S), Relation(S) and Function(S) denote constant, relation and
function symbols of S. For c in S, c^A means c's interpretation on
model A. Function h: Domain(A) > Domain(B) is homomorphism from model
A to model B if it satisfies:
i) For every c in Constant(S) h(c^A) = c^B
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
R^A it holds that ( h(a_0), ..., h(a_{n1}) ) in R^B
iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n1} )) = f^B (h(a_0), ..., h(a_{n1} ) )
If condition ii is stated in stronger form:
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n1}) in R^A <=> (h(a_0), ...., h(a_{n1})) in R^B
the homomorphism is said to be a strong one.
The problem is that I don't get any intuitive feeling on the difference
between "normal" and strong versions of homomorphisms. What is the
"actual" difference? How it could be described?

As William said, R^B can contain ntuples that are not images
under h of ntuples in R^A. An example might be helpful.
Suppose that S = {R}, R in Relation(S), #(R) = 2. Let A be the
model with domain Z, the integers, and relation <, and let B be
the model with domain Z and relation <=. Let h : Z > Z be the
identity map. Then h is a weak homomorphism, since for all n, m
in Z, n < m implies that n <= m, but h is not a strong
homomorphism, because for any n in Z we have h(n) <= h(n) but not
n < n.
Brian 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Mon Apr 17, 2006 4:26 pm Post subject:
Re: Strong homomorphism



Brian M. Scott wrote:
Quote:  Suppose that S = {R}, R in Relation(S), #(R) = 2. Let A be the
model with domain Z, the integers, and relation <, and let B be
the model with domain Z and relation <=. Let h : Z > Z be the
identity map. Then h is a weak homomorphism, since for all n, m
in Z, n < m implies that n <= m, but h is not a strong
homomorphism, because for any n in Z we have h(n) <= h(n) but not
n < n.

You're correct, good example certainly helps It seems clear now.
Thanks! 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Mon Apr 17, 2006 5:24 pm Post subject:
Re: Strong homomorphism



I have a second question about imbedding. Since it is closely related
to my previous question I reply here.
Quote:  Let S be a finite alphabet. Let A and B finite models for S. Let
Constant(S), Relation(S) and Function(S) denote constant, relation and
function symbols of S. For c in S, c^A means c's interpretation on
model A. Function h: Domain(A) > Domain(B) is homomorphism from model
A to model B if it satisfies:
i) For every c in Constant(S) h(c^A) = c^B
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
R^A it holds that ( h(a_0), ..., h(a_{n1}) ) in R^B
iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n1} )) = f^B (h(a_0), ..., h(a_{n1} ) )
If condition ii is stated in stronger form:
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n1}) in R^A <=> (h(a_0), ...., h(a_{n1})) in R^B
the homomorphism is said to be a strong one.

If a strong homomorphism is injective it is called imbedding (is this
term correct?) from model A to model B. Let T_n be a model with
universe {0, ..., n1} and alphabet {S}. Let S^T be relation
S^T = { (k, k+1)  k in {0, ..., n2} }
The question is for which pair (m,n) there exists imbedding from T_m to
T_n?
Since the imbedding has to be injective n must be greater than or equal
to m. This is obvious. If m = n the imbedding clearly exists (identity
mapping) so suppose n > m. Now for T_m the relation S^{T_m} must have
m1 ordered pairs? And S^{T_n} has n1 ordered pairs? And since the
imbedding is strong homomorphism there must exist equal amount of
ordered pairs in relations S^{T_m} and S^{T_n} in order for the
imbedding to exist and hence n must be equal to m?
Well, no but I fail to see why not. Could someone explain where the
error in my reasoning is? 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Mon Apr 17, 2006 5:51 pm Post subject:
Re: Strong homomorphism



On 17 Apr 2006 10:24:26 0700, un student <un.student@gmail.com>
wrote in alt.math.undergrad:
Quote:  I have a second question about imbedding. Since it is closely related
to my previous question I reply here.
Let S be a finite alphabet. Let A and B finite models for S. Let
Constant(S), Relation(S) and Function(S) denote constant, relation and
function symbols of S. For c in S, c^A means c's interpretation on
model A. Function h: Domain(A) > Domain(B) is homomorphism from model
A to model B if it satisfies:
i) For every c in Constant(S) h(c^A) = c^B
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
R^A it holds that ( h(a_0), ..., h(a_{n1}) ) in R^B
iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n1} )) = f^B (h(a_0), ..., h(a_{n1} ) )
If condition ii is stated in stronger form:
ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n1}) in R^A <=> (h(a_0), ...., h(a_{n1})) in R^B
the homomorphism is said to be a strong one.
If a strong homomorphism is injective it is called imbedding (is this
term correct?)

'Embedding' is more usual.
Quote:  from model A to model B. Let T_n be a model with
universe {0, ..., n1} and alphabet {S}. Let S^T be relation
S^T = { (k, k+1)  k in {0, ..., n2} }
The question is for which pair (m,n) there exists imbedding from T_m to
T_n?
Since the imbedding has to be injective n must be greater than
or equal to m. This is obvious. If m = n the imbedding clearly
exists (identity mapping) so suppose n > m. Now for T_m the
relation S^{T_m} must have m1 ordered pairs?

Yes.
Quote:  And S^{T_n} has n1 ordered pairs?

Yes.
Quote:  And since the imbedding is strong homomorphism there must exist
equal amount of ordered pairs in relations S^{T_m} and S^{T_n}
in order for the imbedding to exist and hence n must be equal
to m?

No, this is wrong. Let h be the identity map from T_3 into T_5.
S^{T_3} = {(0, 1), (1, 2)} and S^{T_5} = {(0, 1), (1, 2), (2, 3),
(3, 4)}. Consider a pair that's in S^{T_5} but not in h[S^{T_3}]
= S^{T_3}, for instance (2, 3). This pair is not of the form
(h(k), h(j)), since 3 isn't in the range of h, so its existence
doesn't violate the definition of strong homomorphism. If
S^{T_5} contained the pair (0, 2), on the other hand, h would be
a weak homomorphism but not a strong one, because we'd have
(h(0), h(2)) in S^{T_5} but not (0, 2) in S^{T_3}. Similarly,
the fact that (3, 4) is in S^{T_5} isn't a problem. In fact, h
is an embedding of T_3 into T_5. The example now generalizes
easily to give the correct answer to the question.
(I'm afraid that explanation's a bit clumsy, but I'm a bit rushed
right now.)
[...]
Brian 

Back to top 


un student science forum addict
Joined: 21 Jan 2006
Posts: 80

Posted: Tue Apr 18, 2006 7:21 am Post subject:
Re: Strong homomorphism



Brian M. Scott wrote:
Quote:  No, this is wrong. Let h be the identity map from T_3 into T_5.
S^{T_3} = {(0, 1), (1, 2)} and S^{T_5} = {(0, 1), (1, 2), (2, 3),
(3, 4)}. Consider a pair that's in S^{T_5} but not in h[S^{T_3}]
= S^{T_3}, for instance (2, 3). This pair is not of the form
(h(k), h(j)), since 3 isn't in the range of h, so its existence
doesn't violate the definition of strong homomorphism. If

Ok, now I see. I thought that only under weak homomorphism (from A to
B) relation R^B can contain ntuples which are not images under h of
R^A.
Quote:  S^{T_5} contained the pair (0, 2), on the other hand, h would be
a weak homomorphism but not a strong one, because we'd have
(h(0), h(2)) in S^{T_5} but not (0, 2) in S^{T_3}. Similarly,
the fact that (3, 4) is in S^{T_5} isn't a problem. In fact, h
is an embedding of T_3 into T_5. The example now generalizes
easily to give the correct answer to the question.

Yes, n >= m.
Thank you! 

Back to top 


Google


Back to top 



The time now is Tue Feb 19, 2019 5:07 am  All times are GMT

