Skip to main content

Laws of composition

A non-empty subset H of M is called a stable part with respect to the law of composition "*" if ∀x,y∈H,x∗y∈H\forall x,y\in H,x*y\in H.

Properties. The law of composition M×M→M, (x,y)→x∗yM\times M\to M,\text{ }(x,y)\to x*y

  • Is commutative if: x∗y=y∗x,∀x,y∈Mx*y=y*x, \forall x,y\in M

  • Is associative if: (x∗y)∗z=x∗(y∗z),∀x,y,z∈M(x*y)*z=x*(y*z),\forall x,y,z\in M

  • Has an identity element if: ∀x∈M e∗x=x∗e=x\forall x\in M\text{ }e*x=x*e=x. The identity element, if it exists, is unique.

  • An associative law with an identity element has invertible elements if there exists x′∈Mx'\in M such that x′∗x=x∗x′=ex'*x=x*x'=e

If x,y∈Mx,y\in M are invertible with respect to a law of composition "*" (associative and with an identity element), then x*y and x′x' are invertible. Moreover:

1) (x∗y)′=y′∗x′(x*y)'=y'*x' 2) (x′)′=x(x')'=x

Let n∈N,n≥2n\in \mathbb{N},n\ge 2. On Zn{{\mathbb{Z}}_{n}} we define the operations called addition and multiplication of residue classes modulo n as follows: α^+β^=α+β^,α^β^=αβ^,∀α^,β^∈Zn\hat{\alpha }+\hat{\beta }=\widehat{\alpha +\beta }, \hat{\alpha }\hat{\beta }=\widehat{\alpha \beta }, \forall \hat{\alpha },\hat{\beta }\in {{\mathbb{Z}}_{n}} with α,β∈Tn\alpha ,\beta \in {{T}_{n}}.

Addition of residue classes modulo n is associative and commutative, has 0^\hat{0} as identity element, and every residue class has an opposite. Multiplication of residue classes modulo n is associative, commutative, has 1^\hat{1} as identity element, and is distributive over addition: a^(b^+c^)=a^b^+a^c^,∀a^,b^,c^∈Zn\hat{a}(\hat{b}+\hat{c})=\hat{a}\hat{b}+\hat{a}\hat{c}, \forall \hat{a}, \hat{b}, \hat{c}\in {{\mathbb{Z}}_{n}}

Groups

A pair (G,*), consisting of a non-empty set G and a law of composition "*" on G, is a group if the following conditions hold:

G1) ∀x,y,z∈G,(x∗y)∗z=x∗(y∗z)\forall x,y,z\in G,(x*y)*z=x*(y*z)

G2) ∃e∈G\exists e\in G, such that e*x=x*e=x, ∀x∈G\forall x\in G

G3) ∀x∈G,∃x′∈G\forall x\in G,\exists x'\in G with x′∗x=x∗x′=ex'*x=x*x'=e

If in addition axiom G4 ∀x,y∈G,x∗y=y∗x\forall x,y\in G,x*y=y*x holds, then G is called a commutative or abelian group.

A pair (M,*) consisting of a non-empty set M and a law of composition "*" on M is called a monoid if:

M1: ∀x,y,z∈M,(x∗y)∗z=x∗(y∗z)\forall x,y,z\in M,(x*y)*z=x*(y*z)

M2: ∃e∈M\exists e\in M such that e∗x=x∗e=x,∀x∈Me*x=x*e=x,\forall x\in M

Cancellation rules in a group*.*

Let (G,*) be a group. For any a,b,c∈Ga,b,c\in G we have:

1) a∗b=a∗c⇒b=ca*b=a*c\Rightarrow b=c 2) b∗a=c∗a⇒b=cb*a=c*a\Rightarrow b=c

Let (G,*) be a group, a,b∈Ga,b\in G and a′a' the inverse of a. The equation a*x=b has the unique solution x=a′∗bx=a'*b in G, and the equation y*a=b has the unique solution y=b∗a′y=b*a' in G.

Let (G,∘)(G,\circ ) and (G′,∗)(G',*) be two groups. A function f:G→G′f:G\to G' is called a group isomorphism if:

1) f(x∘y)=f(x)∗f(y) ∀x,y∈Gf(x\circ y)=f(x)*f(y)\text{ }\forall x,y\in G 2) f is bijective

The group G is isomorphic to the group G′(G≃G′)G'(G\simeq G') if there exists an isomorphism f:G→G′f:G\to G'.

Let (G,∘)(G,\circ ) and (G′,∗)(G',*) be two groups. If f:G→G′f:G\to G' is an isomorphism, then f−1:G′→G{{f}^{-1}}:G'\to G is an isomorphism.

Let the groups (G,∘)(G,\circ ) and (G′,∗)(G',*). The function f:G→G′f:G\to G' is called a group homomorphism if:

f(x∘y)=f(x)∗f(y),∀x,y∈Gf(x\circ y)=f(x)*f(y), \forall x,y\in G

Let the groups (G,∘)(G,\circ ) and (G′,∗)(G',*) have identity elements e and e′e'. If f:G→G′f:G\to G' is a group homomorphism, then:

1) f(e)=e′f(e)=e'

2) f(x−1)=f(x)−1∀x∈Gf({{x}^{-1}})=f{{(x)}^{-1}} \forall x\in G

Let (G,*) be a group and H a subset of G.

(H,*) is called a subgroup of G if (H,*) is a group.

Let (G,*) be a group with identity element e and H a subgroup of G. Then e∈He\in H.

Let (G,*) be a group; H⊂G,H≠∅.(H,∗)H\subset G,H\ne \emptyset .(H,*) is a subgroup of G if and only if ∀x,y∈H,x∗y∈H\forall x,y\in H,x*y\in H, where y′y' is the inverse of y in G.

Let (G, ⋅\cdot) be a group with identity element e and a∈Ga\in G. We say a is an element of finite order of the group G if there exists m>0 such that am=e.

If a is of finite order, then the smallest number m>0 with the property am=e is called the order of a, written orda=m.

If a is an element of order m of the group G, then H={e,a,a2,...,am−1}H=\{e,a,{{a}^{2}},...,{{a}^{m-1}}\} is a subgroup of order m of G.

Let (G, ⋅\cdot) be a group, a∈Ga\in G and n∈N∗n\in {{\mathbb{N}}^{*}}. The following are equivalent:

  1. orda=m

  2. ∀k∈Z,ak=e⇒m∣k\forall k\in \mathbb{Z},{{a}^{k}}=e\Rightarrow \left. m \right|k and am=e.

Rings and fields

A triple (R,+, ⋅\cdot), where R is a non-empty set and "+" and "⋅\cdot" are two laws of composition on R (called addition and multiplication), is a ring if:

(G) (R,+) is an abelian group

(G) (R, ⋅\cdot) is a monoid

(D) multiplication is distributive over addition:

∀x,y,z∈R\forall x,y,z\in \mathbb{R}, x⋅(y+z)=x⋅y+z⋅x,(y+z)⋅x=y⋅x+z⋅xx\cdot (y+z)=x\cdot y+z\cdot x, (y+z)\cdot x=y\cdot x+z\cdot x

The ring R has no zero divisors if x≠0, y≠0 ⇒x⋅y≠0\Rightarrow x\cdot y\ne 0

A ring R is called commutative if it also satisfies the axiom: (M3) xy=yx, ∀x,y∈R\forall x,y\in \mathbb{R}.

A commutative ring R with at least two elements and no zero divisors is called an integral domain.

Let Z[i]={a+bi∣a,b∈Z}.\mathbb{Z}[i]=\{a+bi\left| a,b\in \mathbb{Z}\}. \right. (Z[i],+,∗)(\mathbb{Z}[i],+,*) be called the ring of Gaussian integers.

Let (R,+,∗)(\mathbb{R},+,*) be a ring. The operation y−z=y+(−z),y,z∈Ry-z=y+(-z), y,z\in \mathbb{R} is called subtraction.

In a ring (R,+,∗)(R,+,*) the following properties hold:

1) ∀x∈R,x0=0x=0\forall x\in \mathbb{R},x0=0x=0

2) In a ring with at least two elements we have 1≠0.

3) The rule of signs: ∀x,y∈R,(−x)y=x(−y)=−xy\forall x,y\in \mathbb{R},(-x)y=x(-y)=-xy and (-x)(-y)=xy

4) Distributivity of multiplication over subtraction: ∀x,y,z∈R,x(y−z)=xy−xz\forall x,y,z\in \mathbb{R},x(y-z)=xy-xz and (y−z)x=yx−zx(y-z)x=yx-zx.

5) In a ring R without zero divisors we may cancel by elements different from 0, that is ∀x,y,z∈R,x≠0,xy=xz\forall x,y,z\in \mathbb{R}, x\ne 0, xy=xz or yx=zx⇒y=zyx=zx\Rightarrow y=z

The invertible elements of a ring R are called the units of R. We write U(R) for the set of units of the ring R. U(R) is a group under the operation induced by the multiplication of R, called the group of units of R.

If R is an integral domain, then R[X] is an integral domain and ∀f,g∈R[X],f≠0,g≠0\forall f, g\in R[X], f\ne 0, g\ne 0 degfg=degf+degg.

Let R be a commutative ring, f=a0+a1X+...+anXn∈R[X]f={{a}_{0}}+{{a}_{1}}X+...+{{a}_{n}}{{X}^{n}}\in \mathbb{R}[X] and α∈R\alpha \in R. The element f(α)=a0+a1α+a2α2+...+anαn∈Rf(\alpha )={{a}_{0}}+{{a}_{1}}\alpha +{{a}_{2}}{{\alpha }^{2}}+...+{{a}_{n}}{{\alpha }^{n}}\in R is called the value of the polynomial f at α. The value of the sum and of the product of the polynomials f,g∈Rf,g\in R at α∈R\alpha \in R equals the sum, respectively the product, of the values of f and g at α: (f+g)(α)=f(α)+g(α),.(f+g)(\alpha )=f(\alpha )+g(\alpha ),. (fg)(α)=f(α)g(α)(fg)(\alpha )=f(\alpha )g(\alpha ).

Let f∈R[x].f\in \mathbb{R}[x].. The function f∗:R→Rf*:R\to R defined by f∗(x)=f(x)∈R,∀x∈Rf*(x)=f(x)\in \mathbb{R},\forall x\in \mathbb{R} is the polynomial function associated with the polynomial f. We shall also write f for the function f∗f*.

The zeros of the polynomial function f are called the roots (in R) of the polynomial f. Thus an element α∈R\alpha \in R is a root (in R) of the polynomial f∈R[x].f\in \mathbb{R}[x]. if f(α)=0.

Let R be a commutative ring, f=a0+a1X+...+anXn∈R[X],an≠0f={{a}_{0}}+{{a}_{1}}X+...+{{a}_{n}}{{X}^{n}}\in \mathbb{R}[X], {{a}_{n}}\ne 0 and α∈R\alpha \in R. There exist uniquely determined c0,c1,...,cn−1{{c}_{0}},{{c}_{1}},...,{{c}_{n-1}} and r in R with f=(X−α)(cn−1Xn−1+...+c1X1+c0)+rf=(X-\alpha )({{c}_{n-1}}{{X}^{n-1}}+...+{{c}_{1}}{{X}^{1}}+{{c}_{0}})+r. Moreover, r=f(α).

The remainder theorem. The remainder on dividing the polynomial f∈R[X]f\in \mathbb{R}[X] by X−α∈R[X]X-\alpha \in \mathbb{R}[X] is f(α).

Bézout's theorem. The polynomial f∈R[X]f\in \mathbb{R}[X] is divisible by X−α∈R[X]X-\alpha \in \mathbb{R}[X] if and only if f(α)*=*0.

A ring K is called a field if 0≠1 and every non-zero element of K is invertible with respect to multiplication. If multiplication is commutative, K is called a commutative field.

Properties

  1. A field has no zero divisors

  2. The non-zero elements of a field form a group under multiplication

  3. Every finite integral domain is a field

Let the rings (R,+,*) and (R′,⊕,⊙)(R',\oplus ,\odot ). A function f:R→R′f:R\to R' is called a ring homomorphism if, ∀x,y∈R\forall x,y\in R;

1) f(x+y)=f(x)⊕f(y)f(x+y)=f(x)\oplus f(y) 2) f(x∗y)=f(x)⊙f(y)f(x*y)=f(x)\odot f(y) 3) f(1)=1′f(1)=1'

where 1 is the unit of the ring R and 1′1' the unit of R′R'.

A bijective ring homomorphism is called an isomorphism. The ring R is isomorphic to the ring R′R'.

Let f:R→R′f:R\to R' be a ring homomorphism. Then:

  • f(0)=0′f(0)=0', 0 being the zero element of R and 0′0' that of R′R'.

  • f(−x)=−f(x),∀x∈Rf(-x)=-f(x), \forall x\in R.

  • If x∈Rx\in \mathbb{R} is invertible in the ring R, then f(x) is an invertible element of the ring R′R' and f(x−1)=f(x)−1f({{x}^{-1}})=f{{(x)}^{-1}}.

A function f:K→K′f:K\to K' from a field K to K′K' is called a field homomorphism if it is a homomorphism from K to K′K' regarded as rings.

Every field homomorphism f:K→K′f:K\to K' is injective.

There exist uniquely determined polynomials q,r∈K[X]q,r\in K[X] satisfying the division equation f=g⋅q+rf=g\cdot q+r, where degr<degg if r≠0r\ne 0

  • f is divisible by g, written g∣f\left. g \right|f or g⋮fg\vdots f, if there exists h∈K[X]h\in K[X] with f=ghf=gh

  • let a∈Ka\in K and n∈Nn\in \mathbb{N}, n≥2; a is a root of multiplicity n if (X−a)n∣f{{(X-a)}^{n}}\left| f \right. and ff is not divisible by (X−a)n+1{{(X-a)}^{n+1}}

Let K be a commutative field, f∈K[X]f\in K[X], a∈Ka\in K and n∈Nn\in \mathbb{N}, n≥2. The polynomial f has a root of multiplicity n if and only if f(a)=0; f′(a)=0;f(n)(a)≠0f'(a)=0; {{f}^{(n)}}(a)\ne 0

Let K be a commutative field, f∈K[X]f\in K[X] and a,b∈K[X]a,b\in K[X],a≠ba\ne b. The polynomial f⋮(X−a)(X−b)f\vdots (X-a)(X-b) if and only if f(a)=f(b)=0.

Let K be a commutative field and f∈K[X]f\in K[X] a polynomial of degree f=n. We say the polynomial f is reducible over K if there exist polynomials g,h∈K[X]g,h\in K[X], of degrees strictly less than n, with f=ghf=gh. Otherwise we say f is irreducible over K.

Let K be a commutative field and f,h∈K[X]f,h\in K[X]. We say f is associated in divisibility with g, written f∼gf\sim g, if f∣gf\left| g \right. and g∣fg\left| f \right..

Every polynomial f∈C[X]f\in \mathbb{C}[X] of degf>0 can be written as a finite product of degree-1 polynomials from C[X]\mathbb{C}[X], uniquely determined up to the order of the factors and association in divisibility.

Vector spaces

Let V and K be non-empty sets. A map ψ>K×V→V\psi >K\times V\to V is called an external law of composition on V with scalars (or operators) in K.

Let (K,+,*) be a commutative field. A vector space over K is an abelian group (V,+) equipped with an external law of composition with scalars in K, (α,u)→αu(\alpha ,u)\to \alpha u, satisfying the axioms:

S1) ∀α,β∈K,∀u∈V,(α+β)u=αu+βu\forall \alpha ,\beta \in K, \forall u\in V, (\alpha +\beta )u=\alpha u+\beta u (distributivity of scalar multiplication over addition of scalars)

S2) ∀α∈K,∀u,v∈V,α(u+v)=αu+αv\forall \alpha \in K, \forall u,v\in V, \alpha (u+v)=\alpha u+\alpha v (distributivity of scalar multiplication over addition of vectors)

S3) ∀α,β∈K,∀u∈V,α(βu)=(αβ)u\forall \alpha , \beta \in K, \forall u\in V, \alpha (\beta u)=(\alpha \beta )u (commutativity of multiplication of scalars and vectors)

S4) ∀u∈V,1⋅u=u\forall u\in V, 1\cdot u=u (1, the unit of K, is the identity element for scalar multiplication)

Properties

  1. Let α∈K\alpha \in K and v∈V,αv=0⇔α=0v\in V, \alpha v=0\Leftrightarrow \alpha =0 or v=0

  2. For any α∈K\alpha \in K and v∈Vv\in V, we have: (−α)v=α(−v)=−αv,(−α)(−v)=αv(-\alpha )v=\alpha (-v)=-\alpha v,(-\alpha )(-v)=\alpha v (the rule of signs)

  3. For any α,β∈K\alpha ,\beta \in K and u,v∈Vu,v\in V we have: (α−β)v=αv−βv,α(u−v)=αu−αv(\alpha -\beta )v=\alpha v-\beta v,\alpha (u-v)=\alpha u-\alpha v

Let V be a vector space over the field K, v1,v2,...,vp din V{{v}_{1}},{{v}_{2}},...,{{v}_{p}}\text{ din }V and λ1,λ2,...,λp∈K{{\lambda }_{1}},{{\lambda }_{2}},...,{{\lambda }_{p}}\in K. A vector of the form v=λ1v1+λ2v2+...+λpvpv={{\lambda }_{1}}{{v}_{1}}+{{\lambda }_{2}}{{v}_{2}}+...+{{\lambda }_{p}}{{v}_{p}} is a linear combination of the vectors v1,v2,...,vp{{v}_{1}},{{v}_{2}},...,{{v}_{p}}.

The vectors v1,v2,...,vp{{v}_{1}},{{v}_{2}},...,{{v}_{p}} are linearly independent if ∀\forall λ1,λ2,...,λp∈K{{\lambda }_{1}},{{\lambda }_{2}},...,{{\lambda }_{p}}\in K, λ1v1+λ2v2+...+λpvp=0{{\lambda }_{1}}{{v}_{1}}+{{\lambda }_{2}}{{v}_{2}}+...+{{\lambda }_{p}}{{v}_{p}}=0 implies λ1=...=λp=0{{\lambda }_{1}}=...={{\lambda }_{p}}=0.

Let V be a vector space over K. A system B=(v1...vn)B=({{v}_{1}}...{{v}_{n}}) of vectors vi∈V,1≤i≤n{{v}_{i}}\in V,1\le i\le n is a basis of V if:

1) (∀)x∈V, (∃)λ1,λ2,...,λp∈K(\forall )x\in V,\text{ (}\exists ){{\lambda }_{1}},{{\lambda }_{2}},...,{{\lambda }_{p}}\in K such that x=λ1v1+λ2v2+...+λnvnx={{\lambda }_{1}}{{v}_{1}}+{{\lambda }_{2}}{{v}_{2}}+...+{{\lambda }_{n}}{{v}_{n}};

2) v1,v2,...,vn{{v}_{1}},{{v}_{2}},...,{{v}_{n}} are linearly independent.

In this case, every vector v of V has a unique representation as a linear combination of the basis vectors B, v=λ1v1+λ2v2+...+λnvnv={{\lambda }_{1}}{{v}_{1}}+{{\lambda }_{2}}{{v}_{2}}+...+{{\lambda }_{n}}{{v}_{n}}.

Let V and V′V' be two vector spaces over the same field K. A map f:V→V′f:V\to V' is called a linear map from the vector space V to V′V' if:

1) f(x+y)=f(x)+f(y)∀x,y∈Vf(x+y)=f(x)+f(y) \forall x,y\in V 2) f(λx)=λf(x),∀λ∈K,∀x∈Vf(\lambda x)=\lambda f(x), \forall \lambda \in K, \forall x\in V

If V=V′V', then f is also called a linear operator on V, or an endomorphism of V.

If f:V→V′f:V\to V' is a linear map, then f is in particular a homomorphism from the group (V,+) to the group (V′V',+). Then:

f(0)=0′f(0)=0' f(−x)=−f(x),∀x∈V, f(∑i=1nλivi)=∑i=1nλif(vi),∀λi∈K,vi∈V\displaystyle f(-x)=-f(x), \forall x\in V,\text{ }f(\sum\limits_{i=1}^{n}{{{\lambda }_{i}}{{v}_{i}})=\sum\limits_{i=1}^{n}{{{\lambda }_{i}}f({{v}_{i}}), \forall {{\lambda }_{i}}\in K, {{v}_{i}}\in V}}

Let V and V′V' be vector spaces over a field K, λ∈K\lambda \in K and f:V→V′f:V\to V', g:V→V′g:V\to V' linear maps. The map f+g:V→V′f+g:V\to V', (f+g)(x)=f(x)+g(x)(f+g)(x)=f(x)+g(x) is the sum of f and g, and equation, (λf)(x)=λf(x)(\lambda f)(x)=\lambda f(x) is the product of λ\lambda with f.

If V, V′,V′′V',V'' are vector spaces over K and g:V→V′g:V\to V',f:V′→V′′f:V'\to V'' are linear maps, then the map f∘g:V→V′′f\circ g:V\to V'' defined by (f∘g)(x)=f(g(x))(f\circ g)(x)=f(g(x)) is the composition of f with g.