|
|
| 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_{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
|
| 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. |
|
| 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_{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
|
| 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_{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
|
| 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_{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
|
| 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! |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Sep 04, 2010 12:29 am | All times are GMT
|
|
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
|
| |
|
Ipod Touch 64gb | House Insurance | ESW5080 | Breast Enlargement | Cheap Home Insurance
|
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Undergraduate
