Sets

• Importance: languages are sets

• A set is a collection of "things," called the elements or members of the set. It is essential to have a criterion for determining, for any given thing, whether it is or is not a member of the given set. This criterion is called the membership criterion of the set.

• There are two common ways of indicating the members of a set:
  • List all the elements, e.g. {a, e, i, o, u}
  • Provide some sort of an algorithm or rule, such as a grammar

• 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