Chapter 4 notes Flashcards
What is the basic definition of Relations between sets when: Suppose A and B are sets. then A is called a subset of B: A subset B
Suppose A and B are sets. then A is called a subset of B: A subset B
iff every element of A is also an element of B
Example: A subset B, For all x , if x E A then x E B
Example 2: A not subset B, There exists x such that x E A and x E! B
What is the definition when A and B are sets and A = B?
This is true iff every element of A is in B and every element of B is in A
What is the definition of Union of A and B ( A U B)
Normally U stands for Universal set.
x exists U | x exists A or x exists B
The U is essentially an ‘or’ statement. Looks like up facing horseshoe
What is the definition of the Intersection of A and B
x exists U | x exists A and x exists B
This is essentially an and statement. Looks like down facing horseshoe
What is the definition of: Difference of set B minus A?
x exists U | x exists B and x doesn’t exist A
What is the definition of the Complement of set A, A^c
x exists U | x doesn’t exist A
What is A intersection B a subset of?
This is a theorem and is always a subset of A
What is A always a subset of?
A is always a subset of A union B (theorem)
If A subset B and B subset C, then _____?
A subset C (theorem)
What is the distributive law in Set Theory
For any sets A,B and C:
A union (B inter C)= (A union B) inter (A union C)
What are the commutative Laws in Set Theory
A inter. B = B inter A
A union b = B union A
What are the Associative Laws in Set Theory
( A inter B) intersection C = A inter (B inter C)
A union B) union C = A union (B union C
What are the distributive Laws in Set Theory
A union (B inter. C) = (A union B) inter. (A union C)
A inter. ( B union C) = (A inter. B) union ( A inter. C)
What is the double Complement Law in Set Theory
(A^c)^c = A
What is De Morgan’s Law in Set Theory
( A inter B)^c = A^c union B^c
(A union B)^c = A^c inter B^c
What is the absorption Law in Set Theory
A union ( A inter B) = A
A inter (A union B) = A
What is an Empty Set
The unique set with no elements is called the Empty set and denoted by 0 with a slash through it.
For all sets A
- 0 is a subset of A
- A union 0 = A
- A inter 0 = 0
- A inter A^c = 0
When are A and B called disjointed sets
They are disjointed iff A inter B = 0
ex. A = (1,2) B= (3,4)
When are sets A1, A2,…An considered mutually disjoint?
IFF for all sets Ai inter Aj = o whenever i =! j
ex. A = (1,4) B=(2,5), C=(3)
What is a Partition in set theory
A collection of nonempty sets.
A1,A2,…,An are mutually disjoint
What is a Power Set
Given a set A, the power set of A, denoted P(A) is the set of all subsets of A.
Ex. P(a,b) = (0, a, b, (a,b))
Properties:
If A subset B then P(A) subset P(B)
If a set A has n elements then P(A) has 2^n elements
What is the Cartesian product of 2 sets A and B
A x B= {(a,b) | a exists A, B exists B}
What is the inclusion-exclusion principle of a Set
|A union B| = |A| + |B| - | A int. B|
Ex. A, B, C
|A union B union C| = |A| + |B| +|C| - |A int B| - |A int C| - |B int C| + |A int B int C|
What does |A| indicate
The number of elements in the set
