Exam 1 Study Guide

Question 1

3.1 even

Answer 1

an integer is called even provided it is divisible by two

Question 2

3.2 divisible

Answer 2

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.

Question 3

3.4 odd

Answer 3

an integer a is called odd provided there is an integer x such that a = 2x + 1.

Question 4

3.5 prime

Answer 4

an integer p is called prime provided that p > 1 and the only positive divisors of p are 1 and p.

Question 5

3.6 composite

Answer 5

a positive integer a is called composite provided there is an integer b such that 1 < b < a and b|a.

Question 6

10.2 subset

Answer 6

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.

Question 7

10.8 power set

Answer 7

let A be a set. The power set of A is the set of all subsets of A

Question 8

12.1 union and intersection

Answer 8

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.

Question 9

12.3 theorem

Answer 9

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)

Question 10

12.6 disjoint, pairwise disjoint

Answer 10

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.

Question 11

12.9 set difference

Answer 11

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)

Question 12

12.13 cartesian product

Answer 12

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}

Question 13

14.1 relation

Answer 13

a relation is a set of ordered pairs

Question 14

14.2 relation on, between sets

Answer 14

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.

Question 15

14.4 inverse relation

Answer 15

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.

Question 16

14.7 properties of relations

Answer 16

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

Question 17

15.1 equivalence relation

Answer 17

let R be a relation on a set A. we say R is an equivalence relation provided it is reflexive, symmetric, and transitive

Question 18

15.3 congruence modulo n

Answer 18

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)

Question 19

15.6

Question 20

16.1

Question 21

24.1

Question 22

24.3

Question 23

24.5

Question 24

24.8

Question 25

24.15

Question 26

24.18

Question 27

24.22

Question 28

if-then

Question 29

if-and-only-if

Question 30

disproof by counterexample

Question 31

a set is a subset proof

Question 32

sets are equal

Question 33

existential and universal proofs

Question 34

induction proof

Question 35

truth tables

Question 36

set-builder notation

Question 37

negate/write quantified statements