Relations

Question 1

Answer 1

Question 2

Answer 2

Question 3

Answer 3

Question 4

b basically means describe the function of R inverse (doesn't need to be fully words)

Answer 4

Question 5

Answer 5

Make sure to remember that when talking about cartesian planes in 1061, it is not referred with x and y but instead 1st coordinate and 2nd coordinate. 1st coordinate = x and 2nd coordinate = y.

Question 6

Given a relation R acting on set A

When is R described as reflexive?

Answer 6

R is relexive if and only if ∀ x ∈ A, xRx

Similar to relexive property of functions

The relation is relexive if and only if every element of it is in the form (x,x).
Or it can be said that each element is related to itself

Question 7

Given a relation R acting on set A

When is R described as symmetrical?

Answer 7

R is symmetrical if and only if ∀ x,y ∈ A, xRy and yRx

Similar to symmetrical property of functions

The relation is symmetrical iff the relation has tuple pairs of the form (x, y) and (y, x).
Or it can be said that if any element is related to another element, then the second element is related to the first

Question 8

Given a relation R acting on set A

When is R described as transisitive?

Answer 8

R is transisitive if and only if ∀ x,y,z ∈ A, if xRy and yRz then xRz

Similar to transistivity property of functions

The relation is transisitive iff the relation has tuple triplets of the form (x, y), (y, z) and (x, z).
Or it can be said that if one element is related to a second element and the second element is related to a third element, then the first element is related to the second element.

Question 9

Answer 9

Question 10

Answer 10

Question 11

Answer 11

For the transistivity part, basically the statement says nothing about what would happen if the hypothesis isn’t true, which is the situation for this case.

Question 12

Answer 12

Question 13

Answer 13

Question 14

Answer 14

Question 15

Just revision

Question 16

Answer 16

Question 17

Given a set A and a relation R that acts on A

When is R called an equivalence relation?

Answer 17

R is called an equivalence relation iff R is relfexive, symetric and transisitive.

Question 18

Answer 18

Question 19

Answer 19

Question 20

True or false?

All relations acting on partitions of a set are equivalence relations

Answer 20

True. All relations that act on paritions of any set are equivalence relations

Remember that a partition is the set of some subsets who’s union is the whole set. (Or dividing a set into mutally disjoint parts)

Question 21

Given a set A and a particular element of A, x

Does [x] refer to a set or relation?

[x]=’equivalence class of x’

Answer 21

It refers to a set. Because it means the set of all values of x that is related to an element of A by a relation, R.

Meaning [x] is a set not a relation

Question 22

Givena particular element x, of the set A and a relation acting on A.

Define what is meant by the equivalence class x

equivalence class of x is also referred to as [x]

Answer 22

[x] is the set of all elements in A such that the element is related to x.

For example, given A={0, 1, 2, 3, 4} and a relation R={(1, 0), (0, 4), (4, 0)}.
[0]={1, 4} because elements 1 and 4 are related to 0

Question 23

Givena particular element x, of the set A and a relation acting on A.

What is the formal definition of [x]

Answer 23

[x]={∀y∈A | yRx}
“The set of all elements in A such that that element is related to x”

Question 24

Answer 24

Question 25

Answer 25

Question 26

Answer 26

Question 27

# True or false? The set of distinct equivalence class of any relation is always a partition? ## Footnote Meaning the set of distinct equivalence class of any relation is a set who's union is the original set

Answer 27

True

Question 28

# Given a elements a, b of any set A and a relation, R, acting on A True or false? If aRb then [a]=[b] | (Where R is an equivalence relation)

Answer 28

True | **NOTE:** This is only true for equivalence relations

Question 29

Prove this lemma

Answer 29

Question 30

# True or false? Equivalence class only exits on equivalence relations

Answer 30

True. | Its obvious by the name *Equivalence* class

Question 31

Answer 31

Question 32

Answer 32

Question 33

Define what is meant by m≡n(`mod` d)

Answer 33

"m is congurent to n modulo d". The definition is d | (m-n)

Question 34

# True or false? m≡n(`mod` d) means: m `mod` d = n `mod` d

Answer 34

True. Meaning the remainder of m/d is the same as n/d

Question 35

Answer 35

Question 37

# Given a relation R, that acts on the set A Define the term 'antisymmetric' in formal defnition

Answer 37

∀ a, b ∈ A if aRb and bRa then

Question 38

Answer 38

Question 39

Answer 39

Question 40

What is a partial order relation?

Answer 40

A relation that is reflexive, antisymmetric and transisitive ## Footnote Note that it is similar to equivalence relation but it is antisymmetric instead of symmetric

Question 41

# Given a set A and a relation R When R acts on a subset of A, it is antisymmetric. Does this mean that R is antisymmetric if it acts on the whole set of A.

Answer 41

No. In the example below, you will find that R acting on positive integers is antisymetric but R acting on all integers is not.

Question 42

Answer 42

If U⊆V and V⊆U then U=V. This is just known to be true. | You need to treat ⊆ as a relation variable like R

Question 43

Answer 43

Question 44

# Given a relation R that acts on a set A and a, b ∈ A When are arbitrary elements, a and b said to be comparable? When are these elements said to be incomparable?

Answer 44

a and b are said to be comparable iff aRb or bRa. They are called incomparable otherwise.

Question 45

# Given a relation R that acts on the set A When is R said to be a total order relation?

Answer 45

R is said to be a total order relation iff ∀a, b ∈ A, aRb or bRa ## Footnote In words, it is a total order relation iff all elements of A are comparable.

Question 46

What are binary operations?

Answer 46

A relation between two numbers. | For example: addition, substraction, multiplication, division ## Footnote Other Examples: union, intersection, cartesian product etc.

Question 47

# Let S be a any set and * be any binary operation What does (S, *\) denote?

Answer 47

A group. ## Footnote Note: when the binary operation has been clearly defined, we simply denote the semigroup by S instead of writing (S, *)

Question 48

Just revision

Question 49

# For any set S What is the closure property of (S, *) | That is, what is the closure property of any group?

Answer 49

∀ x, y ∈ S, x\*y ∈ S ## Footnote Given any two elements of S, the binary operation that acts on those two elements is an element of S

Question 50

# For any set S What is the associative property of (S, *) | That is, what is the associative property of any group?

Answer 50

∀ x,y, z ∈ S, x\*(y\*z) = (x\*y)\*z | Bracketing doesn't matter

Question 51

# For any set S What is the identity property of (S, *) | That is, what is the identity property of any group?

Answer 51

∀ x ∈ S, ∃ e ∈ S such that x\*e = g = x\*e | Like the identity matrix

Question 52

# For any set S What is the inverse propert of (S, *) | That, is what is the inverse property of any group?

Answer 52

Question 53

# Given any binary operation * and any set S How would you prove that (S, \*) is a group

Answer 53

It must satisfy all 4 properties 1. Closure 2. Associative 3. Identity 4. Inverse

Question 54

# Given + is a relation relating two integers through addition Prove that (ℤ, +) is a group

Answer 54

Question 55

# Given ⋅ is a relation relating two integers through multiplication Is (ℝ, ⋅) a group?

Answer 55

Question 56

What is the set of all integers modulo 6?

Answer 56

{0, 1, 2, 3, 4, 5} ## Footnote Think of it as all the possible remainders when any integer is divided by 6.

Question 57

What is the set of all integers modulo 3?

Answer 57

{0, 1, 2} ## Footnote Think of it as all the possible remainders when any integer is divided by 3.

Question 58

Define what is meant by "the set of all integers modulo n" for any integer n

Answer 58

{0,...,(n-1)} ## Footnote Basically, it is the possible remainders when any integer is divided by n.

Question 59

What does ℤ₃ mean?

Answer 59

The equivalence classes of integers modulo 3 ## Footnote The set would be {[0], [1], [2]}

Question 60

Define what is meant by "ℤ_n" for any integer n

Answer 60

The equivalence classes of integers modulo n ## Footnote The set would look like {[0], [1], [2],...,[n-1]}

Question 61

Given the relation **⋅** : ℤ_n x ℤ_n → ℤ_n by [a]⋅[b]=[a⋅b]. What is meant by this relation being unambiguous?

Answer 61

It means that given any [a]=[a'] and [b]=[b'] then [a]⋅[b]=[a'⋅b']. *Basically, its not like a quadratic that might have multiple x values.* | Remember that "⋅" denotes the relation like how R would denote a relatio ## Footnote Wven if we pick different representatives of the equivalence class of a and the equivalence class of b, we will end up with the same answer.

Question 62

A relation "⋅" is defined by **⋅** : ℤ_n x ℤ_n → ℤ_n by [a]⋅[b]=[a⋅b]. Is (ℤ₄, ⋅) a group or not?

Answer 62

No it is not a group ## Footnote Recall that ℤ_n means the possible remainders when any integer is divided by n but in an equivalence class

Question 63

What is an abelian group? | With formal defintion

Answer 63

Given a group (S, \*), this group is considered abelian iff it satisfies the properties of groups and it is **commutative**. That is, ∀ x, y ∈ S, x\*y=y\*x ## Footnote non-abelian means the opposite

Question 64

# True or false? Given n is an integer For n≥3, the group S_n consisting of all bijections from {1,2,...,n} to {1,2,...,n} together with the binary operation composition of functions is a non-abelian group. | Remember that a bijection also known as one-to-one correspondence.

Answer 64

True. Note this the group is read as (S_n, ∘)

Question 65

Define a Cayley table

Answer 65

Given that n is the number of elements in any group and \* is the binary opertation of the group. A Cayley table is defined as having an array of nxn. Where each element of the table with row x and column y, (x, y) is defined as x*\y

Question 66

# Given any group (S, \*) Prove that the identity element is unqiue for any group

Answer 66

Question 67

# True or false? Every element in a group only has one inverse

Answer 67

True

Question 68

# Given (S, \*) If H⊆S, what can be said about the group (H, \*)

Answer 68

(H, \*) is a sub-group of S | Sometimes denoted as H≤S if the context is clear. (not less equal to)

Question 69

What properties must a subgroup satisfy?

Answer 69

1) closure 2) identity 3) inverse Note it doesn't need to satisfy associativity because it is inherited

Question 70

# True or false? All groups are sub-groups of itself

Answer 70

True

Question 71

# Given any group (S, \*) What properties must a sub-group H satisfy for it to be called a "proper subgroup"

Answer 71

H is a proper sub-group of S iff H≤S and H≠S

Question 72

# Given any group (S, \*) What properties must a sub-group H satisfy for it to be called a "trivial subgroup"

Answer 72

H is a trivial subgroup of S iff H≤S and H={e} where e is the identity element of S ## Footnote In other words, a trivial subgroup is one that only contains the identity element

Question 73

Find all the subgroups of (ℤ₆, +)

Answer 73

## Footnote Remember that ℤ₆ means the equivalence class of all integers modulo 6 (all the possible remainders when an integer is divided by 6)

Question 74

# Given any group (S, \*) and an element x∈S Expand x³

Answer 74

x * x * x | And note since its associative, the order of

Question 75

# Given any group (S, \*) and an element x∈S Expand x^k

Answer 75

x₁ \* x₂ \* x₃ \* ... * x_k

Question 76

# Given any group (S, \*) and an element x∈S Expand x^-k

Answer 76

x^-1₁ \* x^-1₂ \* x^-1₃ \* ... * x^-1_k

Question 77

# Given any group (S, \*) and an element x∈S What does x⁰

Answer 77

It equals the identity element

Question 78

# True or false? All groups only have one inverse element?

Answer 78

False

Question 79

# Let a∈S be an element of the group (S, \*) What is the formal definition of a cyclic group?

Answer 79

\={a^k | k∈ℤ} | \ means cyclic group

Question 80

# True or false? Let a∈S be an element of the group (S, \*) \ is a sub-group of (S, \*)

Answer 80

True | THis sub-group callled the _cyclic subgroup_ of S generated by a

Question 81

# True or false? Let a∈S be an element of the group (S, \*) How would you describe S=\

Answer 81

We say that S is cyclic and a is a generator of S

Question 82

# Given groups (G, \*) and (H, ∘) Define when the two groups are called "isomorphic"

Answer 82

The two groups are called isomorhpic iff there exists a bijection, f: G → H such that for x, y ∈ G, f(x \* y) = f(x) ∘ f(y) | Such a bijection is called an isomorphism ## Footnote Basically isomorphic means "essential the same"

Question 83

# True or false? Given an isomorphism function, f If f maps from a group G to a group H, then the identity element of group G must have a relation to the identity element of group H

Answer 83

True. | Remember that the function will not map all elements

Question 84

# True or false? If groups G and H are isomorphic, then they must have the same properties | Such as number of elements, abelian or not, same n# of sub-groups, etc.

Answer 84

True

Question 85

Show that (ℤ₄, +) and (ℤ₅ - {0}, ⋅) are isomorphic ## Footnote Given that a the Cayley table for (ℤ₅ - {0}, ⋅) can be represented as shown above

Answer 85

Question 86

# True or false? For any prime p, (ℤ_p-1, +) and (ℤ_p - {0}, ⋅) are isomorphic

Answer 86

True. | (ℤ₄, +) and (ℤ₅ - {0}, ⋅) are isomorphic

Question 87

Why is (ℤ₁₂, +) and (ℤ₁₁ - {0}, ⋅) not isomorphic?

Answer 87

They don't have the same number of elements. (ℤ₁₂, +) has 12 elements while (ℤ₁₁ - {0}, ⋅) has 10 elements.

Question 88

# Given ([a], [b]), ([c], [d]) ∈ ℤ_k x ℤ_n What is ([a], [b]) + ([c], [d]) equal to?

Answer 88

([a + c], [b+d]) | A tuple where you add the componenets

Question 89

# Define f: ℤ₆→ℤ₂xℤ₃ by f([x])=([x], [x])

Answer 89

Question 90

Draw a Cayley table for (ℤ₂xℤ₃, +)

Answer 90