0.4 Discrete structures set theory

Set theory

Basics

Introduction to set theory

The concept of set is fundamental to mathematics and computer science. Everything mathematical starts with sets. For example, relationships between two objects are represented as a set of ordered pairs of objects, the concept of ordered pair is defined using sets, natural numbers, which are the basis of other numbers, are also defined using sets, the concept of function, being a special type of relation, is based on sets, and graphs and digraphs consisting of lines and points are described as an ordered pair of sets. Though the concept of set is fundamental to mathematics, it is not defined rigorously here. Instead we rely on everyone's notion of "set" as a collection of objects or a container of objects. In that sense "set" is an undefined concept here. Similarly we say an object "belongs to" or "is a member of" a set without rigorously defining what it means. "An object (element) x belongs to a set A" is symbolically represented by "x ∈ A". It is also assumed that sets have certain (obvious) properties usually associated with a collection of objects such as the union of sets exists, for any pair of sets there is a set that contains them etc.

This approach to set theory is called "naive set theory" as opposed to more rigorous "axiomatic set theory". It was first developed by the German mathematician Georg Cantor at the end of the 19th century. Though the naive set theory is not rigorous, it is simpler and practically all the results we need can be derived within the naive set theory. Thus we shall be following this naive set theory in this course.

Representation of set

A set can be described in a number of different ways. The simplest is to list up all of its members if that is possible. For example {1, 2, 3} is the set of three numbers 1, 2, and 3. { indicates the beginning of the set, and } its end. Every object between them separated by commas is a member of the set. Thus {{1, 2}, {{3}, 2}, 2}, {1 } } is the set of the elements {1, 2}, {{3}, 2} and {1}.

A set can also be described by listing the properties that its members must satisfy. For example, { x| 1 ≤x ≤2 and x is a real number. } represents the set of real numbers between 1 and 2, and { x| x is the square of an integer and x ≤100 } represents the set { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }.

A third way to describe a set is to give a procedure to generate the members of the set. The recursive/inductive definition is an example and it is going to be studied later. In this representation, first, basic elements of the set are presented. Then a method is given to generate elements of the set from known elements of the set. Thirdly a statement is given that excludes undesirable elements (which may be included in the set otherwise) from the set. For example the set of natural numbers N can be defined recursively as the set that satisfies the following (1), (2), and (3):

(1) 0 ∈ N

(2) For any number x if x ∈N, then x + 1 ∈N.

(3) Nothing is in N unless it is obtained from (1) and (2).