TEST 1

Question 1

Relation from set A to set B

Answer 1

a subset R of AxB

Question 2

Properties of a relation R on a set A

Answer 2

R is reflexive if aRa for all a in A
R is symmetric if aRb then bRa for all a,b in A
R is transitive if aRb and bRc then aRc for all a,b,c in A

Question 3

Equivalence Relation on a set A

Answer 3

a relation on A that is reflexive, symmetric, and transitive

Question 4

Equivalence Class of s in set S under equivalence relation ~

Answer 4

[s] = {x in S | x ~ s} where S is a set and ~ is an equivalence relation on S.

Question 5

Binary Operation on set S

Answer 5

a function *: SxS -> S

Question 6

Commutative Binary Operation * on set S

Answer 6

s * t = t * s for all s,t in set S

Question 7

Associative Binary Operation * on set S

Answer 7

(a * b) * c = a * (b * c) for all a,b,c in set S

Question 8

Closed Under Binary Operation *

Answer 8

Let T be a subset of set S and * a binary operation on S. Then t1 * t2 is in T for all t1,t2 in T.

Question 9

Group

Answer 9

an ordered pair (G, *) such that

0. • is a binary operation on the set G
1. • is associative on G
2. There exists an element e (identity) in G such that e * x = x and x * e = x for every x in G.
3. For every x in G there exists y (inverse of x) in G such that x * y = e and y * x = e.

Question 10

Abelian group

Answer 10

a group with a commutative binary operation

Question 11

Binary Algebraic Structure

Answer 11

(S, *) where * is a binary operation on a set S

Question 12

Isomorphism from (S1, *) to (S2, *’)

Answer 12

a function f: S1->S2 satisfying:

1. f is bijective (injective/1-1 and surjective/onto)
2. f(a) *’ f(b) = f(a * b) for all a,b in S1

Question 13

Structural Properties

Answer 13

1. operation is commutative
2. operation is associative
3. cardinality of the set (ex. set has 11 elements)

Question 14

Supgroup

Answer 14

a subset H of G where (G, * ) is a group such that H is also a group with the “same” binary operation

Question 15

Criterion to be a Subgorup

Answer 15

Suppose (G, * ) is a group and H is a subset of G.

1. H is closed under * (h1,h2 in H implies h1 * h2 in H)
2. e is in H
3. If h is in H, then h^(-1) is in H (H is closed under inverses)

Question 16

Cyclic group G

Answer 16

there exists g in G such that =G

NOTE: g is a generator of G (***there is usually more than one generator)

Question 17

Cyclic Subgroup Generated by g

Answer 17

Given G a group and g in G:

H = {g^n | n is an integer} = is a subgroup of G

Question 18

Division Algorithm

Answer 18

Let m be a positive integer. For every n in Z there exist unique integers q,r satisfying n = mq + r for 0<=r<=m

Question 19

Order of a group G

Answer 19

the cardinality of a group G, |G|

Question 20

Order of an element g of group G

Answer 20

the smallest positive integer n such that g^n = e, if such n exists, otherwise it is infinity. (where g is an element of group G)

Question 21

Greatest Common Divisor

Answer 21

If a,b in Z, not both 0, the greatest common divisor of a and b is GCD(a,b)

Question 22

Bezout’s Theorem

Answer 22

If a,b in Z, not both zero, there exist integers x,y such that GCD(a,b)=ax+by

Question 23

Relatively Prime

Answer 23

two integers a,b are relatively prime if GCD(a,b)=1

Question 24

Cayleys Theorem

Answer 24

Suppose G is a finite group of order n. Then G is isomorphic to a subgroup of Sn

Question 25

Transposition

Answer 25

A transposition in Sn is a permutation of the form (a,b)

Question 26

Even Permutation

Answer 26

a permutation is even if it can be written as a product of an even number of transpositions

Question 27

Orbits

Answer 27

Equivalence classes under ~ are called orbits of sigma

Question 28

Cycle Structure

Answer 28

the cycle structure of a permutation pi is the number of cycles of pi and the lengths of its cycles

Question 29

Conjugate to H

Answer 29

If G is a group and g,h in G, then g is conjugate to h if there exists x in G such that g = xh(x^-1)

Question 30

Alternating Group

Answer 30

The alternating group on n symbols is An={pi in Sn | pi is even}