Set theory

(Redirected from 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

edit

The 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

edit

Example 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

edit

There 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

edit
 
A is a subset of B.  

Formal 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

edit

Let 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

edit

The cardinality of a set is the number of elements in the set. The cardinality of a set   is denoted  .

Types of Sets by Cardinality

edit

A 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
 
Diagram to demonstrate the number systems ℝ, ℚ, ℤ and ℕ as sub-sets of each other.
  •   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

edit

2 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

edit

In 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

edit

The 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  

 

Learning resources

edit

Wikiversity

edit

Wikipedia

edit

See also

edit