Flashcards in Proofs 2 Deck (24):
1
Domain from A to B
Dom(R) for every x in A: there exists y in B s.t xRy
2
Range from A to B
Rng(R) for every y in B: there exists a in A s.t xRy
3
Equivalence Relations
Reflexive, Symmetric, Transitive
4
Reflexive
For every x in A, xRx
5
Symmetric
For every x and y in A, if xRy then yRx
6
Transitive
For every x,y,z in A, if xRy and yRz, then xRz
7
x congruent to y (mod) iff
m divides x-y
8
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
9
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
10
Well Ordering Principle
If A subset Naturals and A doesn't equal empty set then A contains a smallest element
11
If a within D, then
f(a) within f(D)
12
If a within inverse f(E)
then f(a) within E
13
If f(a) within E
then a within inverse f(E)
14
If f(a) within f(D)
then a within D
15
F(X) = image of set X is
{ y e B: y = f(x) for some x e X}
16
Inverse image F(Y) is
{ x e A: f(x) e Y}
17
f(C n D) subset of
f(C) n f(D)
18
f(C u D) equals
f(C) u f(D)
19
inverse f( E n F) equals
inverse f(E) n inverse f(F)
20
inverse f(E u F) equals
inverse f(E) u inverse f(F)
21
a set S is countable if and only if
S is finite or denumerable
22
S is finite or denumerable
set S is countable
23
Denumerable
Bijective / one to one correspondence to the sets of Naturals; able to be counted by bijection with the infinite sets of integers
24