Midterm 2

Question 1

the well-ordering principle

Answer 1

every nonempty subset of the set of all natural numbers has a smallest element.

Question 2

what states that every subset of the set of all natural numbers has a smallest element?

Answer 2

the well-ordering principle

Question 3

fundamental theorem of arithmetic

Answer 3

any natural number greater than 1 is prime or can be expressed uniquely as the product of primes.

Question 4

what states that any natural number greater than 1 is prime or can be expressed uniquely as the product of primes?

Answer 4

the fundamental theorem of arithmetic

Question 5

how can a relation be defined?

Answer 5

as an ordered pair, like (x,y)

Question 6

R is a relation from A to B if…

Answer 6

R is a subset of AxB

Question 7

(a,b) ∈ R
or
a R b

Answer 7

“a is R-related (related) to b”

Question 8

a is R-related (related) to b

Answer 8

(a,b) ∈ R
or
a R b

Question 9

a relation from A to A

Answer 9

“a relation on A”

Question 10

what is every subset of AxB?

Answer 10

a relation from A to B

Question 11

identity relation IA

Answer 11

for any set A, the identity relation on A is IA = {(a,a): a ∈ A}

Question 12

if A = {1, 2, a, b}, what is the identity relation on A?

Answer 12

IA = {(1,1), (2,2), (a,a), (b,b)}

Question 13

given the relation R from A to B, what is the domain of R?

Answer 13

Dom(R) = {x ∈ A: there exists y ∈ B such that x R y}

Question 14

given the relation R from A to B, what is the range of R?

Answer 14

Rng(R) = {y ∈ B: there exists x ∈ A such that x R y}

Question 15

what is Dom(R)?

Answer 15

the set of all first coordinates of ordered pairs in R

Question 16

what is Rng(R)?

Answer 16

the set of all second coordinates of ordered pairs in R

Question 17

how can we prove that a given x ∈ A is contained in Dom(R)?

Answer 17

must show there exists an element y ∈ B such that x R y

Question 18

how can we prove that y ∈ B is in Rng(R)?

Answer 18

must show that there exists x ∈ A such that x R y

Question 19

what is a digraph?

Answer 19

a directed graph, which can be used to represent a relation R on a small finite set A

Question 20

______ are also relations from A to B

Answer 20

unions and intersections of two relations from A to B are also relations from A to B

Question 21

what is the inverse of a relation?

Answer 21

R^-1 = {(y,x): (x,y) ∈ R}
basically, flip x and y

Question 22

if R is the relation from A to B, what is R^-1?

Answer 22

R^-1 is the relation from B to A

Question 23

what is composition?

Answer 23

given that A is related to B, and B is related to C, composition is a method of constructing a relation from A to C

Question 24

let R be a relation from A to B, and S be a relation from B to C. what is the composite of S and R?

Answer 24

S o R = {(a,c): there exists b ∈ B such that (a,b) ∈ R and (b,c) ∈ S}

Question 25

if R is a relation from A to B, and S is a relation from B to C, then how would we graphically describe S o R?

Answer 25

three sets, all paths from A to C gives S o R

Question 26

(R^(-1))^(-1) = ?

Answer 26

R

Question 27

T o (S o R) = ?

Answer 27

(T o S) o R (because composition is associative)

Question 28

Let R be a relation from A to B.

IB o R = ?
R o IA = ?

Answer 28

Both equal R

Question 29

(S o R) ^ (-1) = ?

Answer 29

R^(-1) o S^(-1)

Question 30

what does it mean for R to be reflexive?

Answer 30

if R is a relation on A, then R is reflexive on A if for all x ∈ A, x R x.

graphically, this means there is a loop on every vertex in R.

Question 31

what does it mean for R to be symmetric?

Answer 31

if R is a relation on A, then R is symmetric if for all x and y ∈ A, if x R y, then y R x.

graphically, this means between any two vertices, there are either no arcs or an arc in each direction.

Question 32

what does it mean for R to be transitive?

Answer 32

if R is a relation on A, then R is transitive if, for all x, y, and z ∈ A, if x R y and y R z, then x R z.

graphically, this means whenever there is an arc from vertex x to y, and an arc from vertex y to z, there is an arc from x to z.

Question 33

what is an equivalence relation?

Answer 33

an equivalence relation is a relation R on a set A that is reflexive on A, symmetric, and transitive.

Question 34

what is an equivalence class?

Answer 34

let R be an equivalence relation on a set A. for x ∈ A, the equivalence class of x modulo R (or x mod R) is the set x bar = {y ∈ A: x R y}

Question 35

what is each element of x bar called?

Answer 35

a representative of the equivalence class.

Question 36

what is A/R?

Answer 36

A modulo R: A/R = {x bar: x ∈ A}
the set of all equivalence classes

Question 37

how else can A/R be written?

Answer 37

[x], x/R

Question 38

equivalence classes are____

Answer 38

equivalence classes are never empty

Question 39

any two equivalence classes are either ____ or ____

Answer 39

any two equivalence classes are either equal or disjoint

Question 40

objects are related iff _____

Answer 40

objects are related iff their equivalence classes are identical

Question 41

objects are unrelated iff _____

Answer 41

objects are related iff their equivalence classes are disjoint

Question 42

Let R be an equivalence relation on a nonempty set A. For all x and y in A…

Answer 42

a) x ∈ x̄ and x̄ ⊆ A
b) x R y iff x̄ = ȳ
c) x is not related to y iff x̄ ∩ ȳ = Ø

Question 43

x = y (mod m) if…

Answer 43

x = y (mod m) if f divides x-y or if the remainder of x mod m = remainder of y mod m

Question 44

in x = y (mod m), what is m called?

Answer 44

the modulus of the congruence

Question 45

ℤm
ex. m = 4

Answer 45

the set of equivalence classes for the relation congruence modulo m (the set of all remainders of m)

ℤ4 = {0, 1, 2, 3}