Knowledge Node - Sets

return to Knowledge Node index

The way I understand it now, sets are left loosely defined; however, there are a few basic rules about sets. There is no order within a set, as the set { 0, 1 } is the same as the set { 1, 0 }.

Suppose you wanted a set of responses from a computer. A nice simple set could be as follows:

A = { 0, 1 }

Where A is the set comprised of the numbers 0 and 1.

Definition. A member or an element of a set is an item within the set. For a given set A and an element n, we write n A, if n is a member of A.
Ex. Using the set A = { 0, 1 }, we let n A. Our member n is either equal to 0 or 1.

Definition. The cardinality of a set, which can be denoted as |A|, is the number of elements in a set. Given a set A = { 0, 1, 2 }, the cardinality of A is three. The cardinality of a set with ten elements is ten. The cardinality of the null set (empty set) is zero.

Another way to express a set of Real numbers would be through listing bounds, such as B = [0, 5]. If we wish to exclude the ending or beginning number, we write D = ( 0, 5], which is the set of all positive real numbers up to and including 5. Note that 0 is not included in D.

A third way to build a set is to use set builder notation. The following four statements all say the exact same thing.

E = { x : x2 = n, n , x }

E is equal to the set of all x, such that x squared is equal to n, where n is a member of the natural numbers, and x is a member of the real numbers.

E = the set of all real numbers who's square is equal to a whole natural number.

E is the set of all square roots of positive whole numbers.

Definition. The union of two sets A and B, written A B, is the set as follows:

A B = { x : x A or x B }

The intersect of two sets A and B, written A B, is the set as follows:

A B = { x : x A and x B }

Ex. Suppose A = { 1, 2 } and B = { 2, 3}.
A B = { 1, 2, 3}.
A B = { 2 }.

Definition. Suppose we have two sets, A = { 0, 1, 2 } and B = { 0, 1, 2, 3 }. A is a subset of B, and we write this as A B. This means the following (the two terms below mean the same thing):

n A, n B

All elements of A exist in B.

Definition. Using the same sets A and B, A is a proper subset of B if A is a subset of B and the cardinality of A is less than the cardinality of B. This is written as A B.

I like to think of proper subset and subset as "less than" and "less than or equal to", respectively.

Note the following set rules:
A (A B) and B (A B)
(A B) A and (A B) B

Definition. A set is empty if its cardinality is equal to zero.
Ex. The empty set, , is empty.

Definition. A set is finite if its cardinality is equal to a natural number.
Ex. { 0, 1, 2, 3 } is a finite set.

Definition. A set is infinite if its cardinality is not a member of the natural numbers.
Ex. , [0, 1] are examples of infinite sets.

Definition. A set is countable if it's cardinality is the same as the cardinality of . Basically this means that a bijection, a function that is both one-to-one and onto, can be formed between the elements of the natural numbers and the countable set. Under this definition, if a set is countable, it is infinite.
Ex. , , and are all countable sets.

Definition. A set is uncountable if it is both infinite and not countable. This mans that if the set is infinite and a bijection cannot be formed between the set and , it is uncountable.
Ex. is an uncountable set.

Let B be an uncountable set. Let A B. Then A is either uncountable, countable, finite, or empty.
Let B be a countable set. Let A B. Then A is either countable, finite, or empty.
Let B be a finite set. Let A B. Then A is either finite, or empty.
Let B be an empty set. Let A B. Then A is empty.

Definition. An upper bound is a value such that it is greater than or equal to all other values within a given set. An upper bound n for a set A is as follows:

a A, n > a.

"For all a in A, n is greater than or equal to a."

Ex. Suppose we had the set A = (0, 1), all the numbers between 0 and 1, but excluding 0 and 1 from the set. One upper bound could be 99. Another upper bound could be 100. In fact, the smallest upper bound possible for the given set A is 1.

Definition. A set is bounded above if there exists at least one upper bound. If a set is bounded above, an infinite number of upper bounds exist. Give me any upper bound, and I can give you an upper bound +1 bigger. Upper bounds need not be integers or natural numbers. An upper bound to the set A could be 1.5, or even an irrational number like the sqrt(2).

Definition. The smallest upper bound, the least upper bound, the supremum, is the smallest possible upper bound that is still an upper bound.

A lower bound, greatest lower bound, bounded below, and similar definitions should be intuitive.

just curious... added 5/4/04

return to Knowledge Node index


return to the main page