|
Size: 1219
Comment: Initial commit
|
Size: 3193
Comment: Notes
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 45: | Line 45: |
| ''A ⊆ B'' means that ''A'' is a '''subset''' of ''B''. This can be formally expressed as ''∀ a ((a ∈ A) -> (a ∈ B))''. | ''A ⊆ B'' means that ''A'' is a '''subset''' of ''B''. ''∀ a ((a ∈ A) -> (a ∈ B))''. |
| Line 47: | Line 47: |
| This gives a test for set equality: if ''A ⊆ B'' and ''B ⊆ A''. | This leads to a test for set equality: if ''A ⊆ B'' and ''B ⊆ A''. |
| Line 55: | Line 55: |
| === Complements === The '''complement''' of ''A'' contains all elements that are not members of ''A''. This is usually notated as ''A^c^''. Taking the complement is an involution: ''(A^c^)^c^ = A''. ---- == Operations == The '''union''' of two sets contains all members of both. ''A ⋃ B = {x | x ∈ A or x ∈ B}''. The union of all subsets ''A,,i,,'' can be expressed as: {{attachment:union.svg}} The '''intersection''' of two sets contains all members that are common between the two. ''A ⋂ B = {x | x ∈ A and x ∈ B}''. The intersection of all subsets ''A,,i,,'' can be expressed as: {{attachment:intersection.svg}} A pair of sets are '''disjoint''' if there is no intersection, i.e., ''A ⋂ B = ∅''. The '''set difference''' of ''A'' with respect to ''B'' contains all members in ''A'' that are not in ''B''. ''A \ B = {x ∈ A | x ∉ B}''. === Properties === Let ''U'' be the universe of set ''A''. It is always true that ''A ⋂ A^c^ = ∅'' and ''A ⋃ A^c^ = U''. Furthermore, ''∅^c^ = U'' and ''U^c^ = ∅''. De Morgan's laws prove that: * ''(A ⋂ B)^c^ = A^c^ ⋃ B^c^'' * ''(A ⋃ B)^c^ = A^c^ ⋂ B^c^'' For set differences, ∅ has an identity property. ''A \ ∅ = A''. Lastly, note that ''A^c^ \ B^c^ = B \ A''. ---- == Cardinality == '''Cardinality''' is an extension of the concept of size, such that it is applicable to infinite sets. The finite case is intuitive. Consider the finite set ''A'' which contains natural numbers up to ''n'' (i.e., ''{1,2,...,n}''. The cardinality of ''A'' is ''n'': ''|A| = n''. This is generalized to infinite sets by [[Analysis/Functions|functions]]. Given two sets ''A'' and ''B'': * If an [[Analysis/Injectivity|injective]] function exists such that ''f : A -> B'', then ''A ≤ B''. * If a [[Analysis/Surjectivity|bijective]] function exists such that ''f : A -> B'', then ''A = B''. * If ''A ≤ B'' but ''A != B'', then clearly ''A < B''. |
Sets
Sets are a collection of members.
Contents
Description
A set is a collection of members. Generally, sets are defined and notated like {a,b,c}.
A set can also be defined by a condition. For example, {x ∈ R | x > 0} should be read as the set of all real values greater than 0.
The empty set is notated Ø.
Commonly Used Sets
The commonly re-used notations for basic sets of numbers are:
Natural numbers (N)
Integers (Z)
Rational numbers (Q)
Real numbers (R)
Logic
Membership
a ∈ A means a is a member of A. Conversely, a ∉ A means a is not a member of A.
Subsets
A ⊆ B means that A is a subset of B. ∀ a ((a ∈ A) -> (a ∈ B)).
This leads to a test for set equality: if A ⊆ B and B ⊆ A.
If A ⊆ B and A != B, then A is a proper subset of B. This is notated as either A ⊂ B or A ⊊ B.
The reverse relation could be notated as B ⊇ A, B ⊃ A, and so on.
Complements
The complement of A contains all elements that are not members of A. This is usually notated as Ac.
Taking the complement is an involution: (Ac)c = A.
Operations
The union of two sets contains all members of both. A ⋃ B = {x | x ∈ A or x ∈ B}.
The union of all subsets Ai can be expressed as:
The intersection of two sets contains all members that are common between the two. A ⋂ B = {x | x ∈ A and x ∈ B}.
The intersection of all subsets Ai can be expressed as:
A pair of sets are disjoint if there is no intersection, i.e., A ⋂ B = ∅.
The set difference of A with respect to B contains all members in A that are not in B. A \ B = {x ∈ A | x ∉ B}.
Properties
Let U be the universe of set A. It is always true that A ⋂ Ac = ∅ and A ⋃ Ac = U. Furthermore, ∅c = U and Uc = ∅.
De Morgan's laws prove that:
(A ⋂ B)c = Ac ⋃ Bc
(A ⋃ B)c = Ac ⋂ Bc
For set differences, ∅ has an identity property. A \ ∅ = A.
Lastly, note that Ac \ Bc = B \ A.
Cardinality
Cardinality is an extension of the concept of size, such that it is applicable to infinite sets.
The finite case is intuitive. Consider the finite set A which contains natural numbers up to n (i.e., {1,2,...,n}. The cardinality of A is n: |A| = n.
This is generalized to infinite sets by functions. Given two sets A and B:
If an injective function exists such that f : A -> B, then A ≤ B.
If a bijective function exists such that f : A -> B, then A = B.
If A ≤ B but A != B, then clearly A < B.