Exam 1 Flashcards
Every set contains the empty set and itself.
Theorem 2.2.2, page 42
For sets X, A, and B, X is a subset of A intersect B iff X is a subset of A and X is a subset of B.
Exercise 2.3.8, pg. 44
Definition of a subset
S is a subset of A if every element of S is in A pg. 42
Definition of set equality
A = B if A is a subset of B and vice versa pg. 43
If A is a subset of B, and B is a subset of C, then A is a subset of C.
Exercise2.24, pg. 42
Definition of proper subset
B is a subset of X and B neq X
Definition of “the union over alpha in the lambda of the B-alpha’s”
The set of elements x such that x is an element of any B-alpha for all alphas in lambda
Definition of “the intersection over alpha in the lambda of the B-alphas”
The set of elements x such that x is an element of every B-alpha for all alphas in lambda
A union (B intersect C)=(A union B) intersect (A union C)
Theorem 2.4.2, pg. 48
A intersect (B union C)=(A intersect B) union (A intersect C)
Exercise 2.4.4, pg. 48
C union (the intersection over alpha in the lambda of the B-alphas) = the intersection over alpha in the lambda of (the B-alphas union C)
Theorem 2.4.5 pg 49
C intersect (the union over alpha in the lambda of the B-alphas) = the union over alpha in the lambda of (the B-alphas intersect C)
Theorem 2.4.5 pg 49
C union (the union over alpha in the lambda of the B-alphas) = (the union over alpha in the lambda of the B-alphas union C)
Theorem 2.4.6 pg 49
C intersect (the intersection over alpha in the lambda of the B-alphas) = (the intersection over alpha in the lambda of the B-alphas intersect C)
Theorem 2.4.6 pg. 49
Definition of set complement
The set containing all the elements in U not in S, 2.3.1 pg 43
The complement of (A union B) = The complement of A intersect the complement of B
Problem 2.4.8 pg. 49
The complement of (A intersect B)=The complement of A union the complement of B
Problem 2.4.8 pg 49
Definition of set difference
A\B is the set containing those elements of A that are not elements of B; is the same thing as A intersect the complement of B; 2.4.10 pg 50
C(A union B)=(C\A) intersect (C\B)
Theorem 2.4.11.1 pg 50
C(A intersect B)=(C\A) union (C\B)
Theorem 2.4.11.2 pg 50
B(B\A)= A intersect B
Theorem 2.4.11.3 pg 50
(A\B) union (B\A)=(A union B)(A intersect B)
Theorem 2.4.11.4 pg 50
Definition of symmetric difference
(A union B)(A intersect B) or A delta B pg 50
Definition of a power set
The power set of A is the set of all subset of A.
A is a subset of B iff P(A) is a subset of P(B)
Theorem 2.5.4 pg 51
P(A intersect B)=P(A) intersect P(B)
Theorem 2.5.5.1 pg 51
P(A) union P(B) is a subset of P(A union B)
Theorem 2.5.5.2 pg 51
Adding one element to a set doubles the size of the power set
Problem 2.5.7 pg 51x
The Axiom of Induction
Let S be a subset of the natural numbers such that 1 is an element of S and, if k is an element of S, then k+1 is an element of S for some arbitrary k. Then S is the natural numbers.
Principle of Mathematical Induction
Suppose that P(1) is true and, if P(k) is true, then P(k+1) is true. Then P(n) is true for all n in the natural numbers. 3.1.2 pg 60
If S is a set with n elements, then the power set of S has 2^n elements
3.2.1 pg 61
Principle of Complete Induction
Suppose that P(1) is true and, if P(j) is true for all j≤k, then P(k+1) is true. Then P(n) is true for all n in the natural numbers. 3.3.1 pg. 62