##### Document Text Contents

Page 141

In: Mathematics and Mathematical Logic: New Research

Editors: Peter Milosav and Irene Ercegovaca

ISBN 978-1-60692-862-2

c© 2010Nova Science Publishers, Inc.

Chapter 6

ALGEBRAIC TOPICS ON DISCRETE

M ATHEMATICS *

Gloria Gutiérrez Barranco, Javier Martínez,

Salvador Merino and Francisco J. Rodríguez

Departamento de Matemática Aplicada.

E.T.S.I. Telecomunicación. Universidad de Málaga.

Campus de Teatinos. 29071 Málaga. (Spain)

Abstract

Many applications of discrete mathematics for science, medicine, industry and

engineering are carried out using algebraic methods, such as group theory, polynomial

rings or finite fields.

This chapter is intended as a survey of the main algebraic topics used for devel-

oping methods in ambit of combinatorial theory. Pólya’s enumeration method, Latin

squares, patterns design or block design are examples of this usage. Others applica-

tions can be seen in Section 5, about foundation design, RNA patterns or octonions.

1. Elemental Concepts

1.1. Equivalence Relations

A binary relation on a setA is a subsetR ⊆ A×A. If (a, b) ∈ R, we say that the element

a is related tob and we will denoteaRb. Equivalence relations are binary relations that

formalize the natural process of classification of the elements in a set. Formally:

Definition 1.1. A binary relationR on a setA is an equivalence relationif it is reflexive

(aRa for all a ∈ A), symmetric (aRb impliesbRa for all a, b ∈ A), and transitive (aRb

andbRc implyaRc for all a, b, c ∈ A).

Equivalence relations are usually denoted by∼ or≡.

Definition 1.2. LetA be a set,∼ be an equivalence relation onA anda ∈ A. Theequiva-

lence classof a, denoted by[a], is the set

[a] = {b ∈ A | a ∼ b}

Page 142

130 Gloria Gutiérrez Barranco, Javier Martínez, Salvador Merino et al.

Thequotient set, denotedA/∼, is the set of all the equivalence classes ofA, that is,A/∼ ={

[a] | a ∈ A

}

.

Definition 1.3. LetA be a set. ApartitionofA is a family of subsets, namedparts, that are

disjoint by pairs and whose union isA.

Obviously the quotient setA/∼ is a partition ofA. Conversely, if a partitionP is given

onA, we can define an equivalence relation onA asx ∼ y iff there exists a part ofP which

contains bothx andy. “Equivalence relation” and “partition” are thus essentially the same

notion.

1.2. Groups

The idea of operating the elements of a set arises in a natural way. Thus, for example, with

numbers it is possible to add, to multiply, etc; with sets it is possible to join, to meet, etc.

Binary operations are the keystone of the algebraic structures studied in abstract algebra1.

Definition 1.4. A magmais a pair (A, ∗) whereA is a set and∗ is a binary operation on

A, that is, a function∗ : A× A→ A.

Binary operations are often written using infix notation such asa ∗ b, a+ b, a · b or a � b

rather than by functional notation of the formf(a, b). Sometimes they are even written just

by juxtaposition:ab.

Example 1.5. The sum of natural numbers is a binary operation. Nevertheless the sub-

traction of natural elements is not a binary operation because for example if we consider

2, 3 ∈ N it verifies that2 − 3 = −1 6∈ N.

The binary operations on a setA, do not have to verify any property in particular.

However, the fact that these binary operations verify certain properties is going to play a

very outstanding role.

Definition 1.6. Let∗ be a binary operation on a setA. It is said that:

1. ∗ is associativeif it satisfies thata ∗ (b ∗ c) = (a ∗ b) ∗ c for all a, b, c ∈ A.

2. ∗ is commutativeif it satisfies thata ∗ b = b ∗ a for all a, b ∈ A

3. e ∈ A is anidentity elementor neutral elementfor ∗ if it satisfies thata∗e = e∗a = a

for all a ∈ A.

4. a′ ∈ A is an inverse elementof a ∈ A if it satisfies that a ∗ a′ = a′ ∗ a = e being

e ∈ A the identity element.

Many binary operations of interest in the algebraic environment are commutative or

associative. Many of them also have identity elements and inverse elements.

Typical examples of associative and commutative binary operations are the addition

(+) and multiplication(·) of numbers. The product of matrixes and the composition of

functions are associative but not commutative. The subtraction(−) and the division(/) of

numbers are neither associative nor commutative.

The following result is an immediate consequence of the definition.

1All basic results about algebra can be found in several algebra books like [5].

Page 282

Index 270

tangible, 12

TCP, 191, 199

teaching, 3, 26

technological developments, ix

technology, ix, 203, 204, 227, 228, 230, 231, 232,

240

telecommunication, ix, 179, 180, 183, 198, 199,

203

telecommunication networks, 183, 198, 199

telephone, 234

telephony, 182, 183, 184

temperature, 63, 203

Tesla, 13

tetrad, 40

textbooks, 207, 255

Theory of Everything, 39

thinking, 2, 18, 27, 36

third order, x, 243, 249, 255

Thomson, 53

threat, 9

threshold, 78, 229, 231, 232, 252, 253, 254, 255,

256

tics, 199

time, ix, 2, 4, 5, 11, 13, 16, 17, 22, 23, 25, 30, 32,

35, 36, 40, 46, 50, 57, 154, 174, 179, 180, 181,

182, 183, 184, 190, 195, 196, 197, 198, 224,

244

tolerance, 58

topological, vii, 43, 170

topology, 170, 180, 183, 186, 188, 231

Topos, 19, 55

total utility, 190

traction, 130

traffic, 14, 180, 181, 182, 183, 184, 185, 186,

196, 197, 198, 199, 200, 241

traffic flow, 182, 183, 184

training, 16, 18

traits, 34

trans, 17, 31, 53, 54, 195

transfer, 62, 180, 181, 184, 186, 187

transformation, 70, 71, 257

transformations, 24, 41, 42

transistor, 227, 229, 230, 231

transistors, 227, 229

transition, 57, 58, 70, 248, 257

transitions, 96

translation, 70

transmission, 15, 164, 165, 181, 183, 191, 195,

197, 227

transparent, 30, 251

transport, 183

transportation, 47

Transylvania, 170

trees, 31, 166, 167, 168, 169, 170

Trinidad and Tobago, 57

two-dimensional, 41, 43, 108

two-dimensional space, 43

U

UMTS, 182, 200

uncertainty, viii, 2, 23, 28, 34, 58, 67, 68, 69, 71,

181, 198

uniform, 8

universal grammar, 26

universality, 16, 238

universe, 31, 68

unpredictability, 184, 185

utilitarianism, 51

V

vacuum, 229

validity, 5, 38, 68, 186

values, 15, 57, 58, 63, 72, 73, 77, 93, 97, 99, 108,

111, 112, 187, 204, 210, 251

variability, 161

variables, 33, 58, 63, 77, 115, 116, 118, 119, 120,

121, 122, 123, 126, 140, 161, 188, 189, 194,

210, 216, 224, 227, 231

variation, 180, 190, 246

vector, 43, 73, 74, 173, 187, 193, 194

vehicles, 154

vertebrates, 18

virus, 170

visible, 26, 52, 256

vision, 41

visuospatial, 12

vocabulary, 115, 116

voice, 5, 182, 184

voids, 10

VoIP, 182

W

wealth, 15, 207

web, 182, 184

wells, 252, 255, 257

West Indies, 57

Western societies, 17

winning, 174

wireless, ix, 179, 184, 198, 201

wireless networks, ix, 184, 201

wires, 15, 221, 234

wisdom, vii, 1, 3

withdrawal, 162

women, 15

wood, 177

Page 283

Index 271

World Wide Web, 175

Y

yield, 88, 105, 112, 150, 208, 220, 227, 236

Z

zeitgeist, 51

Zen, 50

In: Mathematics and Mathematical Logic: New Research

Editors: Peter Milosav and Irene Ercegovaca

ISBN 978-1-60692-862-2

c© 2010Nova Science Publishers, Inc.

Chapter 6

ALGEBRAIC TOPICS ON DISCRETE

M ATHEMATICS *

Gloria Gutiérrez Barranco, Javier Martínez,

Salvador Merino and Francisco J. Rodríguez

Departamento de Matemática Aplicada.

E.T.S.I. Telecomunicación. Universidad de Málaga.

Campus de Teatinos. 29071 Málaga. (Spain)

Abstract

Many applications of discrete mathematics for science, medicine, industry and

engineering are carried out using algebraic methods, such as group theory, polynomial

rings or finite fields.

This chapter is intended as a survey of the main algebraic topics used for devel-

oping methods in ambit of combinatorial theory. Pólya’s enumeration method, Latin

squares, patterns design or block design are examples of this usage. Others applica-

tions can be seen in Section 5, about foundation design, RNA patterns or octonions.

1. Elemental Concepts

1.1. Equivalence Relations

A binary relation on a setA is a subsetR ⊆ A×A. If (a, b) ∈ R, we say that the element

a is related tob and we will denoteaRb. Equivalence relations are binary relations that

formalize the natural process of classification of the elements in a set. Formally:

Definition 1.1. A binary relationR on a setA is an equivalence relationif it is reflexive

(aRa for all a ∈ A), symmetric (aRb impliesbRa for all a, b ∈ A), and transitive (aRb

andbRc implyaRc for all a, b, c ∈ A).

Equivalence relations are usually denoted by∼ or≡.

Definition 1.2. LetA be a set,∼ be an equivalence relation onA anda ∈ A. Theequiva-

lence classof a, denoted by[a], is the set

[a] = {b ∈ A | a ∼ b}

Page 142

130 Gloria Gutiérrez Barranco, Javier Martínez, Salvador Merino et al.

Thequotient set, denotedA/∼, is the set of all the equivalence classes ofA, that is,A/∼ ={

[a] | a ∈ A

}

.

Definition 1.3. LetA be a set. ApartitionofA is a family of subsets, namedparts, that are

disjoint by pairs and whose union isA.

Obviously the quotient setA/∼ is a partition ofA. Conversely, if a partitionP is given

onA, we can define an equivalence relation onA asx ∼ y iff there exists a part ofP which

contains bothx andy. “Equivalence relation” and “partition” are thus essentially the same

notion.

1.2. Groups

The idea of operating the elements of a set arises in a natural way. Thus, for example, with

numbers it is possible to add, to multiply, etc; with sets it is possible to join, to meet, etc.

Binary operations are the keystone of the algebraic structures studied in abstract algebra1.

Definition 1.4. A magmais a pair (A, ∗) whereA is a set and∗ is a binary operation on

A, that is, a function∗ : A× A→ A.

Binary operations are often written using infix notation such asa ∗ b, a+ b, a · b or a � b

rather than by functional notation of the formf(a, b). Sometimes they are even written just

by juxtaposition:ab.

Example 1.5. The sum of natural numbers is a binary operation. Nevertheless the sub-

traction of natural elements is not a binary operation because for example if we consider

2, 3 ∈ N it verifies that2 − 3 = −1 6∈ N.

The binary operations on a setA, do not have to verify any property in particular.

However, the fact that these binary operations verify certain properties is going to play a

very outstanding role.

Definition 1.6. Let∗ be a binary operation on a setA. It is said that:

1. ∗ is associativeif it satisfies thata ∗ (b ∗ c) = (a ∗ b) ∗ c for all a, b, c ∈ A.

2. ∗ is commutativeif it satisfies thata ∗ b = b ∗ a for all a, b ∈ A

3. e ∈ A is anidentity elementor neutral elementfor ∗ if it satisfies thata∗e = e∗a = a

for all a ∈ A.

4. a′ ∈ A is an inverse elementof a ∈ A if it satisfies that a ∗ a′ = a′ ∗ a = e being

e ∈ A the identity element.

Many binary operations of interest in the algebraic environment are commutative or

associative. Many of them also have identity elements and inverse elements.

Typical examples of associative and commutative binary operations are the addition

(+) and multiplication(·) of numbers. The product of matrixes and the composition of

functions are associative but not commutative. The subtraction(−) and the division(/) of

numbers are neither associative nor commutative.

The following result is an immediate consequence of the definition.

1All basic results about algebra can be found in several algebra books like [5].

Page 282

Index 270

tangible, 12

TCP, 191, 199

teaching, 3, 26

technological developments, ix

technology, ix, 203, 204, 227, 228, 230, 231, 232,

240

telecommunication, ix, 179, 180, 183, 198, 199,

203

telecommunication networks, 183, 198, 199

telephone, 234

telephony, 182, 183, 184

temperature, 63, 203

Tesla, 13

tetrad, 40

textbooks, 207, 255

Theory of Everything, 39

thinking, 2, 18, 27, 36

third order, x, 243, 249, 255

Thomson, 53

threat, 9

threshold, 78, 229, 231, 232, 252, 253, 254, 255,

256

tics, 199

time, ix, 2, 4, 5, 11, 13, 16, 17, 22, 23, 25, 30, 32,

35, 36, 40, 46, 50, 57, 154, 174, 179, 180, 181,

182, 183, 184, 190, 195, 196, 197, 198, 224,

244

tolerance, 58

topological, vii, 43, 170

topology, 170, 180, 183, 186, 188, 231

Topos, 19, 55

total utility, 190

traction, 130

traffic, 14, 180, 181, 182, 183, 184, 185, 186,

196, 197, 198, 199, 200, 241

traffic flow, 182, 183, 184

training, 16, 18

traits, 34

trans, 17, 31, 53, 54, 195

transfer, 62, 180, 181, 184, 186, 187

transformation, 70, 71, 257

transformations, 24, 41, 42

transistor, 227, 229, 230, 231

transistors, 227, 229

transition, 57, 58, 70, 248, 257

transitions, 96

translation, 70

transmission, 15, 164, 165, 181, 183, 191, 195,

197, 227

transparent, 30, 251

transport, 183

transportation, 47

Transylvania, 170

trees, 31, 166, 167, 168, 169, 170

Trinidad and Tobago, 57

two-dimensional, 41, 43, 108

two-dimensional space, 43

U

UMTS, 182, 200

uncertainty, viii, 2, 23, 28, 34, 58, 67, 68, 69, 71,

181, 198

uniform, 8

universal grammar, 26

universality, 16, 238

universe, 31, 68

unpredictability, 184, 185

utilitarianism, 51

V

vacuum, 229

validity, 5, 38, 68, 186

values, 15, 57, 58, 63, 72, 73, 77, 93, 97, 99, 108,

111, 112, 187, 204, 210, 251

variability, 161

variables, 33, 58, 63, 77, 115, 116, 118, 119, 120,

121, 122, 123, 126, 140, 161, 188, 189, 194,

210, 216, 224, 227, 231

variation, 180, 190, 246

vector, 43, 73, 74, 173, 187, 193, 194

vehicles, 154

vertebrates, 18

virus, 170

visible, 26, 52, 256

vision, 41

visuospatial, 12

vocabulary, 115, 116

voice, 5, 182, 184

voids, 10

VoIP, 182

W

wealth, 15, 207

web, 182, 184

wells, 252, 255, 257

West Indies, 57

Western societies, 17

winning, 174

wireless, ix, 179, 184, 198, 201

wireless networks, ix, 184, 201

wires, 15, 221, 234

wisdom, vii, 1, 3

withdrawal, 162

women, 15

wood, 177

Page 283

Index 271

World Wide Web, 175

Y

yield, 88, 105, 112, 150, 208, 220, 227, 236

Z

zeitgeist, 51

Zen, 50