FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Undergraduate
Strong homomorphism
Post new topic   Reply to topic Page 1 of 1 [9 Posts] View previous topic :: View next topic
Author Message
un student
science forum addict


Joined: 21 Jan 2006
Posts: 80

PostPosted: Mon Apr 17, 2006 10:54 am    Post subject: Strong homomorphism Reply with 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_{n-1}) in
R^A it holds that ( h(a_0), ..., h(a_{n-1}) ) in R^B

iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n-1} )) = f^B (h(a_0), ..., h(a_{n-1} ) )

If condition ii is stated in stronger form:

ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n-1}) in R^A <=> (h(a_0), ...., h(a_{n-1})) 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

PostPosted: Mon Apr 17, 2006 11:24 am    Post subject: Re: Strong homomorphism Reply with quote

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_{n-1}) in
R^A it holds that ( h(a_0), ..., h(a_{n-1}) ) in R^B

iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n-1} )) = f^B (h(a_0), ..., h(a_{n-1} ) )

If condition ii is stated in stronger form:

ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n-1}) in R^A <=> (h(a_0), ...., h(a_{n-1})) 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

PostPosted: Mon Apr 17, 2006 1:16 pm    Post subject: Re: Strong homomorphism Reply with quote

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

PostPosted: Mon Apr 17, 2006 2:48 pm    Post subject: Re: Strong homomorphism Reply with quote

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

PostPosted: Mon Apr 17, 2006 2:53 pm    Post subject: Re: Strong homomorphism Reply with quote

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_{n-1}) in
R^A it holds that ( h(a_0), ..., h(a_{n-1}) ) in R^B

iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n-1} )) = f^B (h(a_0), ..., h(a_{n-1} ) )

If condition ii is stated in stronger form:

ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n-1}) in R^A <=> (h(a_0), ...., h(a_{n-1})) 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 n-tuples that are not images
under h of n-tuples 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

PostPosted: Mon Apr 17, 2006 4:26 pm    Post subject: Re: Strong homomorphism Reply with quote

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 Smile It seems clear now.

Thanks!
Back to top
un student
science forum addict


Joined: 21 Jan 2006
Posts: 80

PostPosted: Mon Apr 17, 2006 5:24 pm    Post subject: Re: Strong homomorphism Reply with quote

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_{n-1}) in
R^A it holds that ( h(a_0), ..., h(a_{n-1}) ) in R^B

iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n-1} )) = f^B (h(a_0), ..., h(a_{n-1} ) )

If condition ii is stated in stronger form:

ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n-1}) in R^A <=> (h(a_0), ...., h(a_{n-1})) 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, ..., n-1} and alphabet {S}. Let S^T be relation
S^T = { (k, k+1) | k in {0, ..., n-2} }

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
m-1 ordered pairs? And S^{T_n} has n-1 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

PostPosted: Mon Apr 17, 2006 5:51 pm    Post subject: Re: Strong homomorphism Reply with quote

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_{n-1}) in
R^A it holds that ( h(a_0), ..., h(a_{n-1}) ) in R^B

iii) For every f in Function(S), #(f) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
h( f^A( a_0, ..., a_{n-1} )) = f^B (h(a_0), ..., h(a_{n-1} ) )

If condition ii is stated in stronger form:

ii) For every R in Relation(S), #(R) = n and (a_0, ..., a_{n-1}) in
Domain(A)^n it holds that
(a_0, ..., a_{n-1}) in R^A <=> (h(a_0), ...., h(a_{n-1})) 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, ..., n-1} and alphabet {S}. Let S^T be relation
S^T = { (k, k+1) | k in {0, ..., n-2} }

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 m-1 ordered pairs?

Yes.

Quote:
And S^{T_n} has n-1 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

PostPosted: Tue Apr 18, 2006 7:21 am    Post subject: Re: Strong homomorphism Reply with quote

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 n-tuples 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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [9 Posts] View previous topic :: View next topic
The time now is Fri Dec 14, 2018 5:57 am | All times are GMT
Forum index » Science and Technology » Math » Undergraduate
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Aqua Regia, how strong is it? nebx123 Chem 4 Thu Jul 13, 2006 3:40 am
No new posts Homomorphism Hatto von Aquitanien Math 21 Sun Jun 11, 2006 2:05 pm
No new posts how strong is liouville's theorem? jkramar@gmail.com Math 3 Wed May 24, 2006 1:59 am
No new posts Does strong Markov property impley Markov property? comtech Math 2 Mon May 22, 2006 10:07 pm
No new posts extention of homomorphism to place - help Michael11 Math 0 Mon May 22, 2006 3:48 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0172s ][ Queries: 16 (0.0021s) ][ GZIP on - Debug on ]