Set theory
Type classification: this is a lesson resource. |
Educational level: this is a tertiary (university) resource. |
Wikibooks has more on the topic of Set theory. |
Basic Definition
editThe term "set" can be thought as a well-defined collection of objects. In set theory, These objects are often called "elements".
- We usually use capital letters for the sets, and lowercase letters for the elements.
- If an element belongs to a set , we can say that " is a member of the set ", or that " is in ", or simply write .
- Similarly, if is not in , we would write .
(Example) . In this case, is the element and is the set of all real numbers.
Notation
editExample of a common notation style for the definition of a set:
- is a set
- is a property (The elements of may or may not satisfy this property)
- Set can be defined by writing:
This would read as "the set of all in , such that of ."
Elements
editThere are two ways that we could show which elements are members of a set: by listing all the elements, or by specifying a rule which leaves no room for misinterpretation. In both ways we will use curly braces to enclose the elements of a set. Say we have a set that contains all the positive integers that are smaller than ten. In this case we would write . We could also use a rule to show the elements of this set, as in .
In a set, the order of the elements is irrelevant, as is the possibility of duplicate elements. For example, we write to denote a set containing the numbers 1, 2 and 3. Or, .
Subsets
editFormal universal conditional statement: "set A is a subset of a set B"
- , if , then
Negation:
- such that and
If and only if: for all : If: ( is an element of A) then: ( is an element of B) then: set A is a subset of set B
Truth Table Example:
if , then | and | ||
---|---|---|---|
1 | 1 | 1 | 0 |
1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 |
0 | 0 | 1 | 0 |
A proper subset of a set is a subset that is not equal to its containing set. Thus
A is a proper subset of B
Set Identities
editLet all sets referred to below be subsets of a universal set U.
(a) A ∪ ∅ = A and (b) A ∩ U = A.
5. Complement Laws:
(a) A ∪ A c = U and (b) A ∩ A c = ∅.
6. Double Complement Law:
(A c ) c = A.
7. Idempotent Laws:
(a) A ∪ A = A and (b) A ∩ A = A.
8. Universal Bound Laws:
(a) A ∪ U = U and
(b) A ∩ ∅ = ∅.
Identity | For all sets A | |||
---|---|---|---|---|
Identity Laws: |
|
| ||
Complement Laws: |
|
|||
Double Complement Law: | ||||
Idempotent Laws: |
|
|||
Universal Bound Laws: |
Identity | For all sets A and B |
---|---|
Commutative Laws: | |
2. Associative Laws: For all sets A, B, and C,
(a) (A ∪ B) ∪ C = A ∪ (B ∪ C) and
(b) (A ∩ B) ∩ C = A ∩ (B ∩ C).
3. Distributive Laws: For all sets, A, B, and C,
(a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and
(b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
For all sets A and B,
De Morgan’s Laws:
(a) (A ∪ B) c = A c ∩ B c and (b) (A ∩ B) c = A c ∪ B c .
Absorption Laws:
(a) A ∪ (A ∩ B) = A and (b) A ∩ (A ∪ B) = A.
Set Difference Law:
- A − B = A ∩ B c .
Complements of U and ∅:
Cardinality
editThe cardinality of a set is the number of elements in the set. The cardinality of a set is denoted .
Types of Sets by Cardinality
editA set can be classified as finite, countable, or uncountable.
- Finite Sets are sets that have finitely many elements, is a finite set of cardinality 3. More formally, a set is finite if a bijection exists between and a set for some natural number . is the said set's cardinality.
- Countable Sets are sets that have as many elements as the set of natural numbers. As since , the set of rational numbers is countable.
- Uncountable Sets are sets that have more elements than the set of natural numbers. As since , the set of real numbers is uncountable.
Common Sets of Numbers
edit- is the set of Naturals
- is the set of Integers
- is the set of Rationals
- is the set of Reals
- is the set of Complex Numbers
Comparison of Sets
edit2 sets and have the same cardinality (i.e. ), if there exists a bijection from to . In the case of , they are the same cardinality as there exists a bijection from to .
Partitions of Sets
editIn many applications of set theory, sets are divided up into non-overlapping (or disjoint) pieces. Such a division is called a partition.
Two sets are called disjoint if, and only if, they have no elements in common.
A and B are disjoint ⇔ A ∩ B = ∅.
Sets are mutually disjoint (or pairwise disjoint or nonoverlapping)
if, and only if, no two sets and with distinct subscripts have any elements in
common. More precisely, for all
whenever .
Power Sets
editThe power set of a set A is all possible subsets of A, including A itself and the empty set. Which can be represented:
For the set