Search   Memberlist   Usergroups
 Page 1 of 1 [9 Posts]
Author Message
un student

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_{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?
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_{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.
un student

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.

Thanks!
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>

 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
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>

 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
un student

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!
un student

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_{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?
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>

 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
un student

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 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!

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [9 Posts]
 The time now is Fri Dec 14, 2018 5:57 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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

Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters