Math1 Notes

University of the Philippines, Manila College of Arts and Sciences Department of Physical Sciences and Mathematics MATH 1: General Mathematics

ABSTRACT ALGEBRA NOTES

Definition: A Relation is any well-defined rule that associates the elements of a set X to another set Y (X and Y not necessarily unique). We say that “X is mapped to Y ”; X → Y

One special type of relation is the Equivalence Relation:

Definition: A relation “∼” is said to be an Equivalence Relation over a set S, if it satisifies the following conditions ∀a, b, c ∈ S 1. Reflexivity: a ∼ a 2. Symmetry: If a ∼ b then b ∼ a. 3. Transitivity: If a ∼ b And b ∼ c, Then a ∼ c.

Exercises: For each of the following, determine if the relation as defined is an equivalence on the given set. If not, show or explain which of the conditions is/are not satisfied by giving a counterexample: 1. On set S= a set of people, where a ∼ b : “a and b have a mutual friend” 2. On set S= a set of people, where “a and b have the same favorite movie” 3. On Z, where a ∼ b : “a is divisible by b” 4. On Z, where a ∼ b : “a + b is even” 5. On N, where a ∼ b : “

a = 2k for some integer k” b

6. On Z, where a ∼ b : “a + b is divisible by 3” 7. On R, where a ∼ b : “a − b is negative” 8. On R, where a ∼ b : “a + b < 10” 9. On Z − {0}, where a ∼ b : “ab is a square in Z” 10. On R − {0}, where a ∼ b : “ab is a square in R”

Definition: A Binary Operation, *, on a set S, is a rule mapping S × S → S. That is, we take two elements from the set S, giving us the unique result a ∗ b which is also in S.

1

Note that the following characteristics are true for any Binary Operation ∗ on a set S: • Closure: The result a ∗ b, ∀a, b ∈ S remains in the set S. • The operation ∗ is Ordered. That is, we CANNOT assume the operation is commutative. (i.e. a ∗ b = b ∗ a) • The operation is Well-Defined. That is, the result of a ∗ b is unique. Some Examples: • Ordinary +, × over R, Q, Z, N. • Subtraction over R, Q, Z. (explain why subtraction is not a binary operation over N) • Division over R- {0}, and Q- {0}

Also, we have the following definitions: 1. We say ∗ is Associative if ∀a, b, c ∈ S, (a ∗ b) ∗ c = a ∗ (b ∗ c) 2. We say ∗ is Commutative if ∀a, b ∈ S, a ∗ b = b ∗ a 3. We say an element e ∈ S is an Identity Element of S over ∗ if ∀a ∈ S, we have a∗e=a∧e∗a=a 4. We say an element a0 ∈ S is Inverse Element of a ∈ S over ∗ if a ∗ a0 = e ∧ a0 ∗ a = e

NOTE: In order to show that an operation ∗ is NOT associative or commutative, it is enough to show one case that does not satisfy the condition. However, in order to show that ∗ IS associative or commutative, we must show that the results of applying the operation on both sides are in fact the same.

We define a set Zn = {0, 1, 2, · · · n − 1} Define: Modular Addition, a +n b = the remainder when a + b is divided by n Modular Multiplication, a •n b = the remainder when a · b is divided by n Note that +n and •n are Binary Operations on the set Zn . Also, both Modular Addition and Multiplication are Associative and Commutative.

2

Exercises: For each of the following, determine if the operation ∗ (as defined) is a binary operation on the given set. If so, determine if the operation is associative and/or commutative. If ∗ is not a binary operation, explain why not and (when possible) give a set where ∗ is a binary operation. 1. on S= {set of odd integers}; a ∗ b = ab. 2. on S= {set of odd integers}; a ∗ b = a + b. 3. on N; a ∗ b = ab 4. on N; a ∗ b = the largest integer less than ab 5. on N; a ∗ b = the largest integer less than a + b ( a + b if a is even 6. on Z; a ∗ b = ab if b is odd 7. on Z; a ∗ b = 2a + 4ab + 5 8. on Z; a ∗ b = 3a + 3b − 2ab + 1 9. on Q; a ∗ b =

3(a + b) 2

10. on R-{0}; a ∗ b =

2a + 4b 3

More Exercises: 1. Construct the operation tables for Z15 over +15 and •15 . Determine the identity element, and the inverses for each of the elements in Z15 . 2. Consider the set S = {a, b, c, d, e} and the operation ∗ on S with the following operation table: ∗ a b c d f

a c f a b d

b d c b f a

c a b c d f

d f a d c b

f b d f a c

• Is ∗ a binary operation? If so, is it commutative and/or associative? • What is the identity element of S over ∗? What are the inverses of each element? • Simplify: (((a ∗ f ) ∗ (d ∗ (b ∗ c))) ∗ (c ∗ (f ∗ a))) ∗ b

3