Midterm 2 Flashcards
the well-ordering principle
every nonempty subset of the set of all natural numbers has a smallest element.
what states that every subset of the set of all natural numbers has a smallest element?
the well-ordering principle
fundamental theorem of arithmetic
any natural number greater than 1 is prime or can be expressed uniquely as the product of primes.
what states that any natural number greater than 1 is prime or can be expressed uniquely as the product of primes?
the fundamental theorem of arithmetic
how can a relation be defined?
as an ordered pair, like (x,y)
R is a relation from A to B if…
R is a subset of AxB
(a,b) ∈ R
or
a R b
“a is R-related (related) to b”
a is R-related (related) to b
(a,b) ∈ R
or
a R b
a relation from A to A
“a relation on A”
what is every subset of AxB?
a relation from A to B
identity relation IA
for any set A, the identity relation on A is IA = {(a,a): a ∈ A}
if A = {1, 2, a, b}, what is the identity relation on A?
IA = {(1,1), (2,2), (a,a), (b,b)}
given the relation R from A to B, what is the domain of R?
Dom(R) = {x ∈ A: there exists y ∈ B such that x R y}
given the relation R from A to B, what is the range of R?
Rng(R) = {y ∈ B: there exists x ∈ A such that x R y}
what is Dom(R)?
the set of all first coordinates of ordered pairs in R
what is Rng(R)?
the set of all second coordinates of ordered pairs in R
how can we prove that a given x ∈ A is contained in Dom(R)?
must show there exists an element y ∈ B such that x R y
how can we prove that y ∈ B is in Rng(R)?
must show that there exists x ∈ A such that x R y
what is a digraph?
a directed graph, which can be used to represent a relation R on a small finite set A
______ are also relations from A to B
unions and intersections of two relations from A to B are also relations from A to B
what is the inverse of a relation?
R^-1 = {(y,x): (x,y) ∈ R}
basically, flip x and y
if R is the relation from A to B, what is R^-1?
R^-1 is the relation from B to A
what is composition?
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
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?
S o R = {(a,c): there exists b ∈ B such that (a,b) ∈ R and (b,c) ∈ S}
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?
three sets, all paths from A to C gives S o R
(R^(-1))^(-1) = ?
R
T o (S o R) = ?
(T o S) o R (because composition is associative)
Let R be a relation from A to B.
IB o R = ?
R o IA = ?
Both equal R
(S o R) ^ (-1) = ?
R^(-1) o S^(-1)
what does it mean for R to be reflexive?
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.
what does it mean for R to be symmetric?
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.
what does it mean for R to be transitive?
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.
what is an equivalence relation?
an equivalence relation is a relation R on a set A that is reflexive on A, symmetric, and transitive.
what is an equivalence class?
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}
what is each element of x bar called?
a representative of the equivalence class.
what is A/R?
A modulo R: A/R = {x bar: x ∈ A}
the set of all equivalence classes
how else can A/R be written?
[x], x/R
equivalence classes are____
equivalence classes are never empty
any two equivalence classes are either ____ or ____
any two equivalence classes are either equal or disjoint
objects are related iff _____
objects are related iff their equivalence classes are identical
objects are unrelated iff _____
objects are related iff their equivalence classes are disjoint
Let R be an equivalence relation on a nonempty set A. For all x and y in A…
a) x ∈ x̄ and x̄ ⊆ A
b) x R y iff x̄ = ȳ
c) x is not related to y iff x̄ ∩ ȳ = Ø
x = y (mod m) if…
x = y (mod m) if f divides x-y or if the remainder of x mod m = remainder of y mod m
in x = y (mod m), what is m called?
the modulus of the congruence
ℤm
ex. m = 4
the set of equivalence classes for the relation congruence modulo m (the set of all remainders of m)
ℤ4 = {0, 1, 2, 3}
