Set Theory/Sets

Sets and elements

A mathematical set is defined as an unordered collection of distinct elements. That is, elements of a set can be listed in any order and elements occurring more than once are equivalent to occurring only once.

We say that an element is a member of a set. An element of a set can be anything. It's easiest to begin with only numbers as elements. For that reason, most of the examples in this book will only include numbers, but this is only a technique to make the topic less abstract.

Terminology

For a set y having an element x, the following are all used synonymously:

x is a member of y

x is contained in y

x is included in y

y contains x

y includes x

Notation

We specify a set by specifying its members. The curly brace notation is used for this.

$\{1,2,3\}$

is the set containing 1, 2, and 3 as members. The curly brace notation can be extended to specify a set by specifying a rule for set membership.

$\{x:x=1\mathrm{o}\mathrm{r}x=2\mathrm{o}\mathrm{r}x=3\}$

is again the set containing 1, 2, and 3 as members.

$\{x:x\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\}$

$\{1,2,3,...\}$

both specify the set having the members 1, 2,3, etc.

A modified epsilon notation is used for set membership. Thus

$x\in y$

says that x is a member of y. We can also say that x is not a member of y:

$x\notin y$

Characteristics of sets

A set is uniquely identified by its members. The expressions

$\{x:x\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{n}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\}$

$\{x:x\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{s}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{f}4\}$

$\{2\}$

all specify the same set even though the concept of an even prime is different from the concept of a positive square root. Repetition of members is inconsequential in specifying a set. The expressions

$\{1,2,3\}$

$\{1,1,1,1,2,3\}$

$\{x:\mathrm{x}\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{n}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{o}\mathrm{r}x\mathrm{i}\mathrm{s}\mathrm{a}\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{s}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{o}\mathrm{f}4\mathrm{o}\mathrm{r}x=1\mathrm{o}\mathrm{r}x=2\mathrm{o}\mathrm{r}x=3\}$

all specify the same set.

Sets are unordered. The expressions

$\{1,2,3\}$

$\{3,2,1\}$

$\{2,1,3\}$

all specify the same set.

Sets can have other sets as members. There is, for example, the set

$\{\{1,2\},\{2,3\},\{1,\mathrm{G}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{W}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{o}\mathrm{n}\}\}$

Some special sets

As stated above, sets are defined by their members. However some sets are given names to ease referencing them.

The set with no members is the empty or null set. The expressions

$\{\}$

$\varnothing$

$\{x:x\ne x\}$

all specify the empty set.

A set with exactly one member is called a singleton. A set with exactly two members is called a pair. Thus {1} is a singleton and {1, 2} is a pair.

Subsets, power sets, set operations

Subsets

A set S is a subset of set A if every member of S is a member of A. We use the horseshoe notation to indicate subsets. The expression

$\{1,2\}\subseteq \{1,2,3\}$

says that {1, 2} is a subset of {1, 2, 3}. The empty set is a subset of every set. Every set is a subset of itself. A proper subset of A is a subset of A that is not identical with A. The expression

$\{1,2\}\subset \{1,2,3\}$

says that {1, 2} is a proper subset of {1, 2, 3}.

Power sets

A power set of a set is the set of all its subsets. A script 'P' is used for the power set. Note that the empty set and the set itself are members of the power set.

$𝒫\{1,2,3\}=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

Union

The union of two sets A and B, written A ∪ B, is the set that contains all the members of A and all the members of B (and nothing else). That is,

$A\cup B=\{x:x\in A\mathrm{o}\mathrm{r}x\in B\}$

As an example,

$\{1,2,3\}\cup \{2,3,4\}=\{1,2,3,4\}$

Intersection

The intersection of two sets A and B, written A ∩ B, is the set that contains everything that is a member of both A and B (and nothing else). That is,

$A\cap B=\{x:x\in a\mathrm{a}\mathrm{n}\mathrm{d}x\in b\}$

As an example,

$\{1,2,3\}\cap \{2,3,4\}=\{2,3\}$

Two sets are disjoint if their intersection is empty. That is, if A and B are disjoint sets,

$A\cap B=\varnothing$

Relative complement

The relative complement of A and B, written B − A, is the set containing all the members of B that are not members of A. That is,

$B-A=\{x:x\in B\mathrm{a}\mathrm{n}\mathrm{d}x\notin A\}$

As an example,

$\{2,3,4\}-\{1,3\}=\{2,4\}$

Absolute complement

If we define a universe, or a set containing all of the elements we wish to consider, then we can discuss the absolute complement of a set. For a universe U, define the absolute complement of a subset A of U to be

$U-A$

The absolute complement of A is denoted by $A^C$.

Some properties of set operations

Union and intersection

Based on the preceeding definitions, we can derive some useful properties for the operations on sets. The proofs of these properties are left as an exercise to the reader.

The union and intersection operations are symmetric. That is, if A and B are sets,

$A\cap B=B\cap A$

$A\cup B=B\cup A$

Furthermore, they are associative. That is, if A, B, and C are sets,

$(A\cap B)\cap C=A\cap (B\cap C)$

$(A\cup B)\cup C=A\cup (B\cup C)$

Furthermore, union distributes over intersection and and intersection distributes over union. That is, if A, B, and C are sets,

$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

$A\cup (B\cap C)=(A\cup B)\cap (B\cup C)$

De Morgan's laws

Two important propositions for sets are De Morgan's laws. They state that, for sets A, B, and C,

$A-(B\cup C)=(A-B)\cap (A-C)$

$A-(B\cap C)=(A-B)\cup (A-C)$

When A is a universe to which B and C belong, De Morgan's laws can be stated more simply as,

$(B\cup C{)}^C=B^C\cap C^C$

$(B\cap C{)}^C=B^C\cup C^C$

Families of sets

A set of sets is usually referred to as a family or collection of sets. Often, families of sets are written with a script or Fraktur font to easily distinguish them from other sets. For a family of sets $𝔄$, define the union and intersection of the family by,

$\bigcup 𝔄=\bigcup _{A\in 𝔄}A=\{x:x\text{ is in some }A\in 𝔄\}$

$\bigcap 𝔄=\bigcap _{A\in 𝔄}A=\{x:x\text{ is in }A\text{ for all }A\in 𝔄\}$

For a family of sets, we say that it is pairwise disjoint if any two distinct members we choose from the family are disjoint.