Proofs 2 Flashcards
(24 cards)
Domain from A to B
Dom(R) for every x in A: there exists y in B s.t xRy
Range from A to B
Rng(R) for every y in B: there exists a in A s.t xRy
Equivalence Relations
Reflexive, Symmetric, Transitive
Reflexive
For every x in A, xRx
Symmetric
For every x and y in A, if xRy then yRx
Transitive
For every x,y,z in A, if xRy and yRz, then xRz
x congruent to y (mod) iff
m divides x-y
Partition Definition
If x in P, then x does not equal the empty set
If x in P and y in P, then x = y or x and y = empty set
Union of x in P = A
Anti-Symmetric
A relation R on a set A is anti-symmetric iff for every x,y in A, if xRy and yRx then x=y
Well Ordering Principle
If A subset Naturals and A doesn’t equal empty set then A contains a smallest element
If a within D, then
f(a) within f(D)
If a within inverse f(E)
then f(a) within E
If f(a) within E
then a within inverse f(E)
If f(a) within f(D)
then a within D
F(X) = image of set X is
{ y e B: y = f(x) for some x e X}
Inverse image F(Y) is
{ x e A: f(x) e Y}
f(C n D) subset of
f(C) n f(D)
f(C u D) equals
f(C) u f(D)
inverse f( E n F) equals
inverse f(E) n inverse f(F)
inverse f(E u F) equals
inverse f(E) u inverse f(F)
a set S is countable if and only if
S is finite or denumerable
S is finite or denumerable
set S is countable
Denumerable
Bijective / one to one correspondence to the sets of Naturals; able to be counted by bijection with the infinite sets of integers
Bijective / one to one correspondence to the sets of Naturals; able to be counted by bijection with the infinite sets of integers
Denumerable
