Sets

Sets are a collection of members.

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 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:

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:

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 countable 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|.

  • More formally: if injective functions f : A -> B and g : B -> A exist, then |A| ≤ |B| and |B| ≤ |A|, and finally |A| = |B|. This is the Cantor-Schröder-Bernstein theorem.

• If |A| ≤ |B| but |A| != |B|, then clearly |A| < |B|.

If |A| = |N| (i.e., A can be mapped to the natural numbers), then A is countably infinite. Otherwise an infinite set is uncountable.

Properties

Cardinality is...

• commutative: |A| = |B| -> |B| = |A|

• transitive: |A| = |B| and |B| = |C| -> |A| = |C|

CategoryRicottone