Finite Mathematics

Robert S. Wilson

1. Definitions and Axioms

Primitive notion: A set is a collection of objects. The objects in the collection are called elements of the set. constructed using the following definitions and axioms.

This is not a definition because we do not define "collection" or "object". Not all collections are sets. Sets will be collections which can be constructed from the following definitions and axioms.

Definition 1.1: Let A and B be two sets. If every element of A is also an element of B then we say that A is a subset of B, denoted by.

Axiom 1: If A is a set and B is a subset of A, then B is also a set.

Definition 1.2: Let A and B be two sets. A = B if and only if

Theorem 1.1: If A is a set then

Definition 1.3: Let A and B be two sets. The union of A and B, denoted by

is the set of things that are either elements of A or elements of B.

Axiom 2: If A and B are sets then so is their union.

Theorem 1.2: Let A and B be two sets, then

Definition 1.4: Let A and B be two sets. The intersection of A and B denoted by

is the set of things which are elements of both A and B.

Theorem 1.3: Let A and B be two sets.

Theorem 1.4: If A and B are two sets, the so is their intersection.

Definition 1.5: Let A and B be two sets. The difference of A and B is the set of things which are in A but not in B. The difference of A and B is denoted by A - B.

Definition 1.6: Let U be a universal set and let A be a subset of U. Then the complement of A with respect to U is U - A. The notation for the complement of A will be A'

Theorem 1.5: If A and B are sets then so is A - B.

Theorem 1.6: The complement of a set is a set.

Definition 1.7: Let S be a set. The set of all subsets of S is called the power set of S and is denoted by P(S).

Axiom 3: If S is a set then so is its power set.

Definition 1.8: Let a and b be two elements. The ordered pair of a and b denoted by (a, b ) is defined to be

(a, b ) = {{ a }, { a, b }}

Theorem 1.7: (a, b ) = (c, d ) if and only if a = c and b = d.

Definition 1.9: Let A and B be two sets. The Cartesian product of A and B, denoted by A x B is the set of all ordered pairs whose first coordinate comes from A and whose second coordinate comes from B.

Theorem 1.8: The Cartesian product of two sets is a set.

Convention: Order of operations: If you have a procedure where new sets are being produced from existing sets by taking unions, intersections, differences, and Cartesian products, then we will agree that unless there are parentheses, we will take

If there are parentheses they tell us to do the operations in parentheses in the order specified above before doing anything else.

Theorem 1.9: Let A be a set. Then

Theorem 1.10: Let A be a set. Then

2. Set Operations