Exam 1 Study Guide Flashcards
3.1 even
an integer is called even provided it is divisible by two
3.2 divisible
let a and b be integers. we say that a is divisible by b provided there is an integer c such that bc=a. we also say b divides a, or b is a factor of a, or b is a divisor of a. the notation for this is b|a.
3.4 odd
an integer a is called odd provided there is an integer x such that a = 2x + 1.
3.5 prime
an integer p is called prime provided that p > 1 and the only positive divisors of p are 1 and p.
3.6 composite
a positive integer a is called composite provided there is an integer b such that 1 < b < a and b|a.
10.2 subset
suppose A and B are sets. we say that A is a subset of B provided every element of A is also an element of B. the notation A ⊆ B means A is a subset of B.
10.8 power set
let A be a set. The power set of A is the set of all subsets of A
12.1 union and intersection
let A and B be sets.
the union of A and B is the set of all elements that are in A or B (or both). the union of A and B is denoted A ∪ B.
the intersections of A and B is the set of all elements that are in both A and B. the intersection of A and B is denoted A ∩ B.
12.3 theorem
let A, B, and C denote sets. the following are true:
1. A ∪ B = B ∪ A and A ∩ B = B ∩ A (commutative properties)
2. A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
3. A ∪ Ø = A and A ∩ Ø = Ø
4. A ∪ (B ∩ C) = ( A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). (distributive properties)
12.6 disjoint, pairwise disjoint
let A and B be sets. we call A and B disjoint provided A ∩ B = Ø.
let A1, A2, … , An be a collection of sets. these sets are called pairwise disjoint provided Ai ∩ Aj = Ø whenever i ≠ j. in other words, they are pairwise disjoint provided no two of them have and element in common.
12.9 set difference
let A and B be sets. the set difference, A - B, is the set of all elements of A that are not in B:
A - B = {x: x ∈ A and x ∉ B}
the symmetric difference of A and B, denoted A ∆ B, is the set of all elements in A but not B or in B but not A. that is,
A ∆ B = (A - B) ∪ (B - A)
12.13 cartesian product
let A and B be sets. the cartesian product of A and B, denoted A x B, is the set of all ordered pairs (two-element lists) formed by taking an element from A together with and element from B in all possible ways. that is,
A x B = {(a,b) : a ∈ A, b ∈ B}
14.1 relation
a relation is a set of ordered pairs
14.2 relation on, between sets
let R be a relation and let A and B be sets. we say R is a relation on A provided R ⊆ A x A, and we say R is a relation from A to B provided R ⊆ A x B.
14.4 inverse relation
let R be a relation. the inverse of R, denoted R^-1, is the relation formed by reversing the order of all the ordered pairs in R.
14.7 properties of relations
let R be a relation defined on a set A.
- if for all x ∈ A we have xRx, we call it reflexive
- if for all x ∈ A we have xRx, we call it irreflexive
- if for all x, y ∈ A we have xRy ⇒ yRx, we call R symmetric
- if x, y ∈ A we have (xRy ^ yRx) x = y, we call R antisymmetric
- if for all x, y, z ∈ A we have (xRy ^ yRz) ⇒ xRz, we call R transitive
15.1 equivalence relation
let R be a relation on a set A. we say R is an equivalence relation provided it is reflexive, symmetric, and transitive
15.3 congruence modulo n
let n be a positive integer. we say that integers x and y are congruent modulo n, and we write: x ≡ y (mod n) provided n|(x - y)
15.6
16.1
24.1
24.3
24.5
24.8
24.15
24.18
24.22
if-then
if-and-only-if
disproof by counterexample
a set is a subset proof
sets are equal
existential and universal proofs
induction proof
truth tables
set-builder notation
negate/write quantified statements
