Set Theory Key Concepts: Subsets, Operations, and Principles

Subset

If A and B are sets, then A is called a subset of B, written A ⊆ B, if and only if every element of A is also an element of B.

Not a Subset

The notation A ⊈ B means 'A is not a subset of B,' which means that there is an element in A that is not in B.

Cardinality

The number of elements within a set Denoted by the absolute value sign: |A|.

Proper Subset

Then A is called a proper subset of B, written A ⊂ B or A ⊊ B, if and only if A is a subset of B, but they are not equal.

Union

The union of A and B, denoted A∪B, is the set of all elements that are in at least one of A or B.

Intersection

The intersection of A and B, denoted A ∩ B, is the set of all elements that are common to both A and B.

Difference

The difference between A and B, denoted A \ B, is the set of all elements that are in A and not in B.

Complement

The complement of a set A in X, denoted by A with a line on top or A^c, is the set of all elements in X that are not in A.

Associative Laws

1. (A ∩ B) ∩ C = A ∩ (B ∩ C). 2. (A ∪ B) ∪ C = A ∪ (B ∪ C).

Distributive Laws

1. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). 2. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Partition

Basically, you must have every element of the set, no repetition.

Power Set

The power set of a set A, denoted P(A), is the set of all subsets of A.

Cardinality of Power Set

For a finite set A, the cardinality of P(A) is 2|A|.

Cartesian Product

Essentially an ordered pair created out of the 2 sets given.

Multiplicative Principle

Use it to count the # of elements in a cartesian product.

Example of Multiplicative Principle

Let A={a,b,c}, B={1,2,3}, How many elements are in A×B: (3)(3) = 9 elements.

Pigeonhole Principle

If more than n pigeons fly into n pigeonholes, then at least one pigeonhole will contain at least two pigeons.