1c. Problems: Functions, Relations, Binary, Equivalent

Question 1

z->x, x^2

Injective, surjective, neither, both?

Answer 1

Not injective, + and - numbers that have same magnitude point to same output (1 and -1 map the same)
not surjective, can’t get certain values in the codomain of ints (ex, can’t get 5)

Question 2

S = Students, C = Courses, R = someone registered for course

Form set R of ordered pairs (s,c) ∈ S x C, property = student registered for c

Answer 2

R = {(s,c) ∈ S x C | s registered for c}

subset of S x C captures relationship registered for

Question 3

aRb if a < b

Reflexive, Symmetric, Transitive, Equivalence?

Answer 3

Transitive only bc…
Not symmetric bc don’t know if bRa holds
Not reflexive bc don’t know if equal

Question 4

aRb if a <= b

Reflexive, Symmetric, Transitive, Equivalence?

Answer 4

Reflexive bc…
Transitive bc…
Not symmetric bc don’t know if bRa holds

Question 5

aRb if a = b

Reflexive, Symmetric, Transitive, Equivalence?

Answer 5

Equivalence relation

Question 6

aRb if |a - b|

Reflexive, Symmetric, Transitive, Equivalence?

Answer 6

Reflexive bc …
Not Symmetric bc…
Not Transitive bc…

Question 7

aRb if |a| = |b|

Answer 7

Equivalence relation bc …

Question 8

aRb if a = |b|

Answer 8

Transitive bc …
Not reflexive bc…
Not symmetric bc (-1, 1 counter example)

Question 9

aRb if a and b are relatively prime

Answer 9

Not reflexive because there are two different prime numbers
Symmetric…?
Not transitive bc there are no common factors

Question 10

Relation R on non-zero ints given by xRy if xy > 0 creates what equivalence classes?

Answer 10

A = {...-3, -2, -1, 1, 2, 3...}
A1 = {...3, -2, -1,} negatives
A2 = {1,2,3...) positives

Question 11

the relation that has the same age on a set of people creates what equivalence classes?

Answer 11

groups of people who have the same age

Question 12

On set of Natural numbers, a ≡4 b if (a mod 4) = (b mod 4)

Answer 12

are both equivalent if a%4 = b%4
[0] = {0,4,8,12,...} (4%4=0)
[1] = {1,5,9,13...}
[2] = {2,6,10,14...}
[3] = {3,7,11,15...}
[4]= ?
same equivalent class as 0 (4 divisible by 4)

Question 13

A={x ∈ N | x is even and 1

Answer 13

A=2,4,6,8
B = 5,7
C = 3,5,7

1) 2,4,6,8,5,7
2) 2,4,6,8 (B-C = Ø)
3) B⋂~A = 5,7 A∆C = Ø

Question 14

A = finite set, has k elements. How many elements does AxAxAxAxA

Answer 14

k^5

Question 15

f: Z->Z given by f(x) = x^2+1
Injective or Surjective?
Think: is there any number I’m not gonna get?

Answer 15

Not Injective:1 and -1 have same output

Not surjective: 3, 7, 15… cannot be mapped, not using all of range

Question 16

g: N->N given by g(x) = 2^x

Answer 16

Injective: no duplicate values for any input

Not surjective: not using odd numbers in range

Question 17

h: R->R given by h(x) = 5x-1

Answer 17

Injective: no duplicate values for any input
Surjective: bc…
both

Question 18

A = finite set. |A| = k. How many injections from A to A are there?

Answer 18

k -> k: 4 options for 1st element
k -> k-1: 3 options for 2nd element
k -> k-2: 2 options for 3rd element
k -> k-3: 1 option for 4th element

Question 19

A = {1,3,5,7}
B={2,4,6}
V={(x,y) ∈ A x B | x < y}

Answer 19

1 2 1 -> 2,3,6
3 4 3 -> 4,6
5 6 5 -> 6
7