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
What is the definition of Function pertaining to Set theory
a relationship between elements of 2 sets such that no element of the first set is related to more than once element of the second set.
What is the Domain of sets
the set which contains the values to which the function is applied.
What is the Co-domain of a sets
the set which contains the possible values (results) of the function
What is the Range of Sets
the set of actual values produced when applying the function to the values of the domain.
When talking about functions in Set theory define the following:
- f
- X
- Y
- x exists X y exists Y
- f(x) = y
- the function name
- the domain
- the co-domain
- f sends x to y
- f of x; the value of f at x; the image of x under f
