Groups

Question 1

Injective

Answer 1

one-to-one
(if f(x)=f(y) implies x=y for all x,y in A)

Question 2

Surjective

Answer 2

all used or onto
(for any b in B, there exists a in A such that f(a)=b

Question 3

Bijective

Answer 3

one-to-one and all used
(injective and surjective)

Question 4

Group (G,*)

Answer 4

A set G together with a binary operation * such that:

1) is associative, meaning for a,b,c in G we have
(ab)c=a(bc).

2) there exists an identity element e such that for all a in G we have
ae=a=ea.

3) each element has an inverse, meaning for any g in G there exists g^(-1) in G such that
gg^(-1)=g^(-1)g.

Note: Check that it is a binary operation (for closure).

Question 5

Sym(x)

Answer 5

Symmetric group on n letter denoted Sn

Question 6

Permutations

Answer 6

Elements of Sn
(bijection or relabeling of those elements)

Question 7

Function Composition

Answer 7

Product in S3
(applying one function to the results of another)

Question 8

Cycle Notation

Answer 8

A permutation consisting of a single cycle. Example:
(1)(2)(3)
(12)(3)
(123)

Question 9

a|b

Answer 9

notation for a divides b.
a|b if there exists x in the integers such that ax=b

Question 10

a≅b mod m

Answer 10

If a and b are integers, we say that a is congruent to b modulo m if m|(a-b)

a is the same as b (up to) skip counting by m (not actually the same but the same answer; ex: mod 12 –> 1am and 1pm)

Question 11

modulo

Answer 11

Two numbers are congruent modulo a given number if they give the same remainder when divided by that number.
Ex. 19 and 64 are congruent modulo 5

Question 12

Theorem: Congruence as an Equivalence Relation

Answer 12

Let m be a positive integer. Congruence modulo m satisfies the following properties:

1) Reflexivity
2) Symmetry
3) Transitivity

Question 13

Partitioning Integers

Answer 13

Define the congruence class of n mod m by:

[n]m:={a:a≅n mod m}

give one that does live there: n
ex. m=2:
[0]2 ={…,-6,-4,-2,0,2,4,6,…}
[6]2={…,-6,-4,-2,0,2,4,6,…}
[3]2={…,-5,-3,-1,1,3,5,…}

Question 14

Least nonnegative residue

Answer 14

M is a positive integer. The division algorithm gives:

a=bm+r with 0 < or = r < or = m-1

We call the remainder (r) the least nonnegative residue of a modulo m

Question 15

Theorem: Modular Arithmetic

Answer 15

Let a,b,c,d,m be integers with m>0, a≅b mod m and c≅d mod m
a+c ≅ b+d mod m [a+c]m=[b+d]m
a-c ≅ b-d mod m [a-c]m=[b-d]m
ac ≅ bd mod m [ac]m=[bd]m

Z/mZ:={[0]m,…,[m-1]m} where:
[a]m+[c]m= [a+c]m
[a]m-[c]m= [a-c]m
[a]m([c]m)= [ac]m