Set Theory

A set is a well-defined, unordered collection of distinct objects. Each object that appears in this collection is called an element (or member) of the set.

The cardinality of a set is the number of elements in a finite set, denoted with magnitude or absolute value bars, denoted as or

The empty set is a set whose cardinality is 0. We denote the empty set as:

(see negation, universal qlantifier)

1. Intersection:
2. Union:
3. Set difference:
4. Set difference:
5. Complement:

A singleton set is a set whose cardinality is 1

The universe of discourse, or just "the universe", denoted by or "univ", is a set that contains all the objects that might be encountered in a given situation (usually ).

E.g when working with divisibility, we assume is the universe, even if not explicitly stated

1. Intersection:
2. Union:
3. Set difference:
4. Set difference:
5. Complement:

A set that is countable is either finite, or it can be made in one-to-one correspondence with the set of natural numbers. That is, there exists an injective function from it into the natural numbers.

This means each element in the set may be associated with a unique natural number, or that the elements of the set can be counted one at a time, though counting may never finish due to an infinite number of elements.

For every set , the following are equivalent:

• is countable
• There exists an injective function from to
• is empty or there exists a surjective function from to
• There exists a bijective mapping between and a subset of
• is either finite or countably infinite

The following are equivalent (with each other, not the previous statements):

• is countably infinite
• There exists a bijective mapping between and
• These elements of can be arranged in an infinite sequence where is distinct from for and every element of is listed

A partition of a set is a collection of disjoint subsets of whose union is all of . Consider a partition of , . Thus:

Consider the set . An example partition is , , and .