Lecture 1 Set Theory

Sets
A set is a collection of "things" called the elements or members of the set.
• Common forms of describing sets are:
? List all the elements, e.g. {a, b, c, d}
? Form new sets by combining sets through operators (see next page).
Terminology and Notation:
• To indicate that x is a member of set S, we write x?S.
• We denote the empty set (the set with no members) as {} or ?.
• If every element of set A is also an element of set B, we say that A is a subset of B, and write A? B
• If every element of set A is also an element of set B, but B also has some elements not contained in A, we say that A is a proper subset of B, and write A?B
• We may also use the inverse notation: B?A and B?A for B is a (proper) superset of A.
Note: It is essential to have a criterion for determining, for any appropriate “thing”, whether it is or is not a member of the given set. This is called the membership criterion. Languages – which we will introduce later - are sets. These sets contain specific strings over an alphabet, according to certain specifications or conditions, which describe the language. Grammars and automata can be used to describe languages (and therefore also sets). Membership criteria and appropriate decision algorithms are a central topic in the study of formal languages.