Ch 1-6

Question 1

What is a relation from set A to set B?

Answer 1

A relation is a subset from A x B

Question 2

What is a function from set A to set B?

Answer 2

A function is a relation satisfying the following properties:

Dom(f)=A

For all x€A and y,z€B if (x,y)€f and (x,z)€f
then y=z

Question 3

What is a binary operation on a set S?

Answer 3

A function from S x S * S. In other words, it is a function from S x S to S.

Ex: addition and mult. on: N, Z, Q, R, C

Must be every and well defined as well as closed by definition.

Question 4

What does it mean if an operation is not everywhere defined?

Answer 4

If some element of S x S is not assigned anywhere then the operation is not everywhere defined.

Question 5

What does it mean that an operation is not well defined?

Answer 5

If an element of S x S is assigned to more than one place then the operation is not well defined.

Question 6

What does it mean if an operation is closed?

Answer 6

If all assigned elements are elements of S then S is closed under the operation.

Question 7

What does it mean if an operation is associative on a set S?

Answer 7

For all a,b,c€S (ab)c=a(bc)

Question 8

What does it mean if an operation is commutative on a set S?

Answer 8

For all a,b€S ab=ab

Question 9

What does it mean if a function f is 1-1?

Answer 9

If f is a function from A to B, for all a,b€A, if f(a)=f(b) then a=b

To prove: choose two elements of A, assume f(a)=f(b) and show a=b

Question 10

What does it mean that a function (f) is onto?

Answer 10

A function from A to B is onto if for all b€B there’s exists an a€A such that f(a)=b

To prove:

Question 11

What is a group?

Answer 11

A set G closed under a binary operation * defined on G such that:
For all a,b,c€g (ab)c=a(bc) (associative)

For all a€G, there exists e€G s.t. ae=ea=a
(identity element of G)

For all a€G, there exists an a’€G such that
aa’=a’a=e where e is the identity element of
G (*-inverse)

Question 12

What is left and right cancellation for a group ?

Answer 12

If ab=ac then b=c (left)

If ba=ca then b=c (right)

Question 13

Hat is a subgroup?

Answer 13

If G is a group, then H is a subgroup iff
For all a,b€H, ab€H
e€H (where e is the identity of G)
For all a€H, a’€H (where a’ is the inverse)

To prove: assume G is a group and H is a subset of G, check three properties above.
Then assume G is a group and H is a subgroup of G, check the three properties of a group for H.

Question 14

What does it mean that a group is abelian?

Answer 14

For all a,b€G, if ab=ba (commutative) then G is an abelian group.

Question 15

What does it mean that a group is cyclic?

Answer 15

For a group G there exists an a€G such that <a>=G</a>

Question 16

What is the decision algorithm?

Answer 16

If a,b€Z(integers) and b does not = 0 then there exists q,r€Z s.t. a=bq+r and 0 <= r < |b|