(2) Properties of homomorphisms, Congruence Relation (Complementary Equivalence Relation)

The notes are based on teacher Yu Liang’s lecture of Discrete Mathematics II in Xidian University

The math level of the blogger is quite ordinary, the content may be quite inaccurate or even fallacious from the point of view of mathematics, just for reference.

Welcome advice

Let’s start with a graph to review the relationship between homomorphism, homomorphism image and subalgebra

Theorems (properties of homomorphisms)

Set FFF from A = < S, ∗, ∘ > A = < S, *, / circ > A = < S, ∗, ∘ > to A ‘= < S’, ∗ ‘, ∘ ‘> A’ = < S ‘*’, CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD: CVD A ‘ ‘= < f (S), ∗’, ∘ ‘> A’ ‘= < f (S), *’ \ circ ‘>’ A ‘= < f (S), ∗’, ∘ ‘> is AAA homomorphic image under homomorphic mapping FFF. There are:

If ∗*∗ is interchangeable in AAA, ∗ ‘*’∗’ is also interchangeable in A”A ”A ”
If ∗*∗ can be combined in AAA, ∗ ‘*’∗’ can also be combined in A”A ”A ”
If in AAA, ∗ ∗ * for ∘ \ circ ∘ can be assigned, in A ‘ ‘A’ A ‘in’ ∗ ‘*’ ∗ ‘for ∘’ \ circ ‘∘’ can be allocated

If ∗*∗ is CVD/circ∘, ∗*∗ is CVD/CVD outside the parentheses of the distributive equation. Such as:

A ∗ (b ∘ c) = (a ∗ b) ∘ (a ∗ c) : ∗ a * (b \ c circ) = (a * b) \ the circ (a * c) \ space: \ space * a ∗ ∘ c (b) = (a ∗ b) ∘ (a ∗ c) : ∗ to ∘ \ circ ∘ left can be allocated
If the eee is about ∗ ∗ * MAO yuan in AAA, then f (e) f (e) f (e) is A ‘ ‘A’ A ‘in the’ about ∗ ‘*’ ∗ ‘identity element
If theta \ theta theta is about ∗ ∗ * zero element in AAA, then f (theta) f (\ theta) f (theta) is A ‘ ‘A’ A ‘in the’ about ∗ ‘*’ ∗ ‘zero dollars
If ∀x∈S\forall x \in S∀x∈S, XXX has an inverse element x−1x^{-1}x−1 for the ∗*∗, then, in F (S)f(S)f(S) F (S), F (x) f (x) f (x) is also about ∗ ∗ ‘*’ ‘inverse f (x – 1) f (x ^ {1}) f (x – 1)

To sum up, it is: the commutability, associability and distributability of operations in the original algebra can be “retained” in the homomorphism image, and the identity, zero and inverse elements in the original algebra can also be “corresponding” to the homomorphism image after mapping. The first three sections of the theorem can be used to discuss all the properties of binary operations in homomorphic images

Proof:

Proof:

\ forall a, b \ in S, f (a) * f (b) = f (a * b) = f (b * a) = f (b) * ‘f (a)

Proof:

\ begin} {aligned to \ space \ forall & a, b, c \ S, in \ \ & f * (a) ‘[f * (b) (c)] \ \’ f = & f * ‘(a) (b * c) \ \ f = & f (a * b * c)) \ \ = & f (() a * b * c) \ \ =&f(a*b)*’f(c)\\ =&[f(a)*’f(b)]*’f(c) \end{aligned}

Proof:

\ begin} {aligned to \ space \ forall & a, b, c \ S, in \ \ & f * (a) ‘[f (b) \ the circ’ f (c)] \ \ = & f * (a) ‘(b \ c circ) \ \ = f & f (a) * (b \ c circ) \ \ = & f ((a * b) \ the circ (a * c)) \ \ = (a * b) & f \ circ ‘(a * c) \ \ = f & [f (a) * f (b)] \ circ’ [f (a) * f (c)] \ \ ∴ & * ‘of \ the circ’ left distributable \ \ ∵ & * ‘ Exchangeable \ \ ∴ & [f (b) \ the circ ‘(c)] f * f \ \ = & [f (a) (b) * f (a)] \ circ’ [f (c) * f (a)] \ \ ∴ & * ‘of \ the circ’ right can be allocated \ \ ∴ & * ‘to \ circ’ distributable \ \ \end{aligned}

Proof:

\ begin} {aligned ∵ & \ space e \ \ \ S in ∴ & \ space f (e) \ in f (S) \ \ & \ forall a \ in S, are: \ \ & f * (a) (e) \ \ ‘f = (a * e) \ \ & f = & f (a) \ \ ∴ & \ space f (e) is a’ ‘about *’ in the right MAO yuan \ \ ∵ & \ space * ‘exchangeable \ \ ∴ & \ space f (e) *’ F = f (a) (a) * f (e) = f (a) \ \ ∴ & \ space f (e) is a ‘ ‘about *’ in the left MAO yuan \ \ ∴ & \ space f (e) is a ‘*’ in the MAO yuan \ end} {aligned

Proof:

\ begin} {aligned ∵ & \ space \ theta \ S \ \ in ∴ & \ space f (\ theta) \ in f (S) \ \ & \ forall a \ in S, are: \ \ & f * (a) ‘(\ \ \ theta) = f & f \ \ \ theta (a *) = & f (\ \ \ theta) ∴ & \ space (\ theta) is a’ f ‘about *’ in the right zero yuan \ \ ∵ & \ space * ‘exchangeable \ \ ∴ & \ space F (\ theta) * ‘f’ (a) = f (a) * f (\ theta) = f (\ \ \ theta) ∴ & \ space f (\ theta) is about in a ‘ ‘*’ left zero yuan \ \ ∴ & \ space (\ theta) is a ‘f’ on * ‘zero dollars \end{aligned}

Proof:

\begin{aligned} & Given the conditions, get: \ \ and \ \ forall x in A, A * x x ^ {1} = e \ \ & ∴, space, space f (x) * ‘f (x ^ {1}) \ \ &, space, space = f (x * x ^ {1}) \ \ &, space, space = F (e) \ \ & ∵ f (e) is A ‘*’ in the MAO yuan \ \ & ∴ f (x ^ {1}) f (x) is the inverse of \ end} {aligned

sample

set $h$ from $A=<S, *, k>$ 到 $A’=<S’, *’, k’>$ Homomorphic mapping of. Please prove: if $<T, *’, k’>$ 是 $A’$ The subalgebra of phi, then $<h^{-1}(T), *, k>$ 是 $A$ (The gray dashed line boxes are problem solving and annotation/analysis, the black words are serious problem solving process, other colored parts are analysis, illustration, etc.)

Supplementary: equivalence relation

Equivalence relation is a relation, which is also a set equivalence relation satisfies reflexivity, symmetry and transitive (the relation is also a set, and the elements of the set are order pairs). For the equivalence of AAA and BBB, it is generally written as a ~ ba\sim BA ~ B.

Reflexion-based: ∀ A ∈A, there is A ~ A \forall A \in A, there is a\sim A ∀ A ∈A, there is A ~ A
Symmetry: for a, B ∈Aa, b\ in Aa, B ∈A, if a ~ ba\sim ba ~ b, then B ~ ab\sim ab ~ a

,a>
,b>
,b>
,a>
,b>
Transfer: for a, B, C ∈Aa,b,c\in Aa,b, C ∈A, if a ~ b, b ~ ca\sim b, space b\sim ca ~ b, b ~ C, a ~ CA \sim ca ~ c

Sunday afternoon a, namely: < b > ∈ R > < b, c ∈ R ⇒ < > a, c ∈ R < a, b > \ R \ space \ wedge in < b, c > \ R \ Rightarrow in < > a, c \ in R < a, b > Sunday afternoon ∈ R > < b, c ∈ R ⇒ < > a, c ∈ R

Every partial graph of a digraph of equivalence relation is a complete graph (every node of a complete graph has a self-loop, and every two nodes have two edges in different directions)

Equivalence relation can divide a set, and each partition is an equivalence class. If two elements are equivalent, they belong to the same equivalence class.

About the relationship between the RRR equivalence class aaa elements, can be described as: {x ∣ xRa} \ {x | xRa \} {x ∣ xRa}, as [a] R [a] _R [a] R, shorthand for [a] [a], [a] of aaa is referred to as the equivalence class 】【 said element, the number of equivalence class is known as the “rank”

Congruence relations

Congruence relations: set A = < S, ∗, Δ > A = < S, *, / Delta > A = < S, ∗, Δ > is an algebraic system,…… \ sim…… is the equivalence relation on the SSS. Adopt ∀ A, B, C ∈S\forall A, B, C \in S∀ A, B, C \in S ∈S, then:

When a ~ ba\sim ba ~ b, if δ a ~ δ b ~ Delta a\sim \Delta b δ a ~ δ b, then ~ \sim ~ is “holdable” under δ \Delta δ. It is called “congruent relation of operation δ \Delta δ”.

Aaa and BBB belong to one equivalence class before the operation, and another equivalence class after the operation. The two equivalence classes may be the same or different
When a ~ b, c ~ da\sim b, space C \sim da ~ b, c ~ D, if a∗c ~ b∗da*c\sim b*da∗c ~ b∗d, then ~ \sim ~ is “containable” for ∗*∗. Call ~ \sim ~ “Congruence relation for operation ∗*∗”

A ~ B, c ~ da\sim b, space c\sim da ~ b, c ~ D mean that AAA and BBB are in the same equivalence class, CCC and DDD are in the same equivalence class;

A ∗ C ~ b∗da*c\sim b*da∗ C ~ b∗ D means that a∗ CA * CA ∗ C and B ∗db*db∗ D are also in an equivalence class.

These three equivalence classes can be the same equivalence class or they can be completely different equivalence classes.

To put it bluntly, if two elements are in the same equivalence class before the operation, the result of the operation is still in the same equivalence class, then the equivalence relation is said to be congruence for the operation.

The following is a graphical representation of this abstract concept. In the figure below, each cell represents an equivalence class (that is, elements in the same cell belong to the same equivalence class) Note that the equivalence class after the operation can coincide with the equivalence class of the element before the operation

There are two ways to prove that equivalence relation is congruence relation for binary operation. One method is to take two elements from each of the two equivalence relations and get the result that is still in the same equivalence class, as mentioned above, which directly states congruence. The other is to use three elements: Take ∀ a, b, c ∈ S, a ~ b \ forall. A, b, c \ S, in a \ sim b ∀ a, b, c ∈ S, a ~ b, if a c ~ b ∗ ∗ ca * c \ sim c ~ * ca ∗ ∗ b c b and c ∗ a ~ c ∗ BC * a \ sim c * BC a ~ c ∗ ∗ b, Is the equivalence relation is the congruence relation.

As an example, the following examples will prove it in two ways.

Example to prove congruence relation (method 2, with three elements)

Case 1

The fraction is defined as integer order even

and written as PQ\frac{P}{Q}QP (Q≠0Q\neq 0Q=0). ⋅\cdot⋅ and −-− are ordinary multiplication and unary subtraction. Try to prove the equivalence relation ~ \sim ~ is the congruence relation for multiplication and unary subtraction: Establish the equivalence relation on F:

,q>
,q>
,q>
,q>
,q>

\frac{P}{Q}\sim \frac{R}{S}\Leftrightarrow PS=RQ

Two fractions are equivalent to each other by cross multiplying the numerator and denominator. For ∀ A, B, C ∈F\forall A, B, C \in F∀ A, B, C,c∈F, they can be expressed as follows:

a=\frac{P}{Q},b=\frac{R}{S},c=\frac{T}{U}

To prove that equivalence relation is congruence relation about operation, we need to prove that the equivalence relation can be maintained under this operation, that is, to prove that the element which is in the same equivalence class before operation is still in the same equivalence class after operation. So our idea here is to take any two elements belonging to the same equivalence class in the carrier set of operation, perform operations on them and get the result still in the same equivalence class

Here we assume that two elements a, BA, ba, and b in the same equivalence class have an equivalence relation A ~ ba\sim ba ~ b (that is, PQ ~ RS\frac{P}{Q}\sim \frac{R}{S}QP ~ SR). If we can show that for ∀ C ∈F, there is AC ~ BC to \forall C \in F, and ac\sim BC to ∀ C ∈F, there is AC ~ BC, it shows that elements that were in the same equivalence class before the operation are still in the same equivalence class after the operation. It is proved that the equivalence relation ~ \sim ~ is congruence relation about multiplication

\begin{aligned} \frac{P}{Q}\sim \frac{R}{S}&\Rightarrow PS=RQ\\ &\Rightarrow PS\cdot TU=RQ\cdot TU\\ &\Rightarrow PT\cdot SU=RT\cdot QU\\ &\Rightarrow \frac{PT}{QU}\sim \frac{RT}{SU}\\ &\Rightarrow (\frac{P}{Q})\cdot(\frac{T}{U})\sim (\frac{R}{S})\cdot (\frac{T}{U}) \end{aligned}

namely

\frac{P}{Q}\sim \frac{R}{S}\Rightarrow (\frac{P}{Q})\cdot(\frac{T}{U})\sim (\frac{R}{S})\cdot (\frac{T}{U})

⋅ C ~ B ca\cdot c\sim b\cdot ca⋅ C ~ B c Since multiplication is commutative, the equivalence relation ~ \sim ~ is the congruence relation about multiplication.

The proof for unary subtraction is similar to the above:

\begin{aligned} \frac{P}{Q}\sim \frac{R}{S}&\Rightarrow PS=RQ\\ &\Rightarrow -PS=-RQ\\ &\Rightarrow \frac{-P}{Q}\sim \frac{-R}{S} \end{aligned}

That is, when a ~ ba\sim ba ~ b, there is − A ~ − B-a \ SIM-b − A ~ B. Therefore, the equivalence relation ~ \sim ~ is the congruence relation about unary subtraction

The proof of addition is not too far off:

\begin{aligned} \frac{P}{Q}+\frac{T}{U}\sim \frac{R}{S}+\frac{T}{U}=\frac{PU+TQ}{QU}\sim \frac{RU+ST}{SU}&\Rightarrow QU(RU+ST)=SU(PU+TQ)\\ &\Rightarrow QURU+QUST=SUPU+SUTQ\\ &\Rightarrow QRU^2=SPU^2\\ &\Rightarrow QR=SP\\ &\Rightarrow PS=RQ\\ &\Rightarrow \frac{P}{Q}\sim \frac{R}{S} \end{aligned}

Case 2

Given the algebra A = < I, – > A = < I, – > A = < I, – > and III modulus k (k ∈ I +) k \ space \ + in I_ (k), k (k ∈ I +) relationship…… \ sim…… X ≡y(mod k)x\sim y, text{iff}. \space x\equiv y(mod space k)x ~ y,iff. X ≡y(mod k). Show that ~ \sim ~ is congruent with the “− −” operation

Add: theorem: A module K is an equivalence relation on any A⊆ \subseteq IA⊆I. Judge: 12. If a−b=m ka-b=m\cdot ka−b=m \ k, then aaa and BBB modular KKK are equivalent, denoted as a≡b(mod k)a\equiv b(mod space k)a≡b(mod k), Where k∈I+,m∈Ik\in I^+,m\in Ik∈I+,m∈I

It can also be proved that the modulo K relation is congruence relation with respect to +, · and unary subtraction

Example 3

Given the algebra A = < I, Δ > A = < I, \ Delta > A = < I, Δ >, Δ A = a2 \ Delta A = A ^ 2 Δ A = a2. Let ~ \sim ~ be the modulo KKK equivalence relation on III

\begin{aligned} &∵ space a\sim b \Leftrightarrow a-b=nk(n\in I)\\ & space \Delta a-\Delta b= a^2 – B ^ 2 = (a + b) (a – b) = k \ cdot n \ cdot (a + b) \ \ &, space, space, namely the Delta Delta – \ b \ \ cdot cdot n = k (a + b) \ \ & ∴ \ space \ \ sim \ Delta Delta a B \\ & \space \sim is the congruence of the operation \Delta \end{aligned}

More examples (Method 1, proof with four elements)

Case 1

set $+$ Is an integer $I$ The ordinary addition operation on, $\sim$ 是 $I$ On the mold $k$ Equality relation ( $k\in I^+$ ), and asked $\sim$ In the operation $+$ On whether $I$ Congruence relation on?

Case 2

set $\Delta$ 是 $I$ The unary operation on $\forall a\in I, \Delta a=a^2$ ， $\sim$ 是 $I$ On the mold $k(k\in I)$ Student: Equality $\sim$ In the operation $\Delta$ Whether it is $I$ Congruence relation on? $\sim$ Algebraic system $A=<I, +, \Delta>$ 上 $A$ Congruence relation of?

Congruence relations on algebraic systems

Set A = < S, ∗, Δ > A = < S, *, / Delta > A = < S, ∗, Δ > is an algebraic system,…… \ sim…… is the carrier of the equivalence relation on the SSS. If ~ \sim ~ is holdable under all operations on AAA, it is said to be congruential over AAA in an algebraic system.

(2) Properties of homomorphisms, Congruence Relation (Complementary Equivalence Relation)

Theorems (properties of homomorphisms)

sample

Supplementary: equivalence relation

Congruence relations

Example to prove congruence relation (method 2, with three elements)

Case 1

Case 2

Example 3

More examples (Method 1, proof with four elements)

Case 1

Case 2

Congruence relations on algebraic systems

Related Posts

SpringMVC- Implemented using annotations

You can’t learn Markdown without knowing the HTML associated with it

Node.js-based priority asynchronous queue