# Set theory

(Redirected from Set Theory)
 Type classification: this is a lesson resource.
 Educational level: this is a tertiary (university) resource.
 Wikibooks has more on the topic of Set theory.

## Basic Definition

The term "set" can be thought as a well-defined collection of objects. In set theory, These objects are often called "elements".

• We usually use capital letters for the sets, and lowercase letters for the elements.
• If an element ${\displaystyle a}$  belongs to a set ${\displaystyle A}$ , we can say that "${\displaystyle a}$  is a member of the set ${\displaystyle A}$ ", or that "${\displaystyle a}$  is in ${\displaystyle A}$ ", or simply write ${\displaystyle a\in A}$ .
• Similarly, if ${\displaystyle a}$  is not in ${\displaystyle A}$ , we would write ${\displaystyle a\notin A}$ .

(Example) ${\displaystyle x\in \mathbb {R} }$ . In this case, ${\displaystyle x}$  is the element and ${\displaystyle \mathbb {R} }$  is the set of all real numbers.

### Notation

Example of a common notation style for the definition of a set:

• ${\displaystyle S}$  is a set
• ${\displaystyle P(x)}$  is a property (The elements of ${\displaystyle S}$  may or may not satisfy this property)
• Set ${\displaystyle A}$  can be defined by writing:

${\displaystyle A=\{x\in S\mid P(x)\}}$

This would read as "the set of all ${\displaystyle x}$  in ${\displaystyle S}$ , such that ${\displaystyle P}$  of ${\displaystyle x}$ ."

### Elements

There are two ways that we could show which elements are members of a set: by listing all the elements, or by specifying a rule which leaves no room for misinterpretation. In both ways we will use curly braces to enclose the elements of a set. Say we have a set ${\displaystyle A}$  that contains all the positive integers that are smaller than ten. In this case we would write ${\displaystyle A=\{1,2,3,4,5,6,7,8,9\}}$ . We could also use a rule to show the elements of this set, as in ${\displaystyle A=\{a:{\text{ }}a{\text{ positive integer less than 10}}\}}$ .

In a set, the order of the elements is irrelevant, as is the possibility of duplicate elements. For example, we write ${\displaystyle X=\{1,2,3\}}$  to denote a set ${\displaystyle X}$  containing the numbers 1, 2 and 3. Or,${\displaystyle X=\{1,2,3\}=\{3,2,1\}=\{1,1,2,3,3\}}$ .

## Subsets

Formal universal conditional statement: "set A is a subset of a set B"

• ${\displaystyle A\subseteq B\Leftrightarrow \forall x}$ , if ${\displaystyle x\in A}$ , then ${\displaystyle x\in B.}$

Negation:

• ${\displaystyle A\nsubseteq B\Leftrightarrow \exists x}$  such that ${\displaystyle x\in A}$  and ${\displaystyle x\notin B.}$
If and only if:
for all ${\displaystyle x}$ :
If: (${\displaystyle x}$  is an element of A)
then: (${\displaystyle x}$  is an element of B)
then:
set A is a subset of set B


Truth Table Example:

${\displaystyle x\in A}$  ${\displaystyle x\in B.}$  if ${\displaystyle x\in A}$ , then ${\displaystyle x\in B.}$  ${\displaystyle x\in A}$  and ${\displaystyle x\notin B}$
1 1 1 0
1 0 0 1
0 1 1 0
0 0 1 0

A proper subset of a set is a subset that is not equal to its containing set. Thus

A is a proper subset of B ${\displaystyle \iff }$

### Set Identities

Let all sets referred to below be subsets of a universal set U.

(a) A ∪ ∅ = A and (b) A ∩ U = A.

5. Complement Laws:

(a) A ∪ A c = U and (b) A ∩ A c = ∅.

6. Double Complement Law:

(A c ) c = A.

7. Idempotent Laws:

(a) A ∪ A = A and (b) A ∩ A = A.

8. Universal Bound Laws:

(a) A ∪ U = U and

(b) A ∩ ∅ = ∅.

${\displaystyle A\cap U=A}$  ${\displaystyle A\cap U=A}$
Identity For all sets A
Identity Laws:

${\displaystyle A\cup \emptyset =A}$

${\displaystyle A\cap U=A}$  ${\displaystyle A\cap U=A}$
Complement Laws:

${\displaystyle A\cup A^{c}=U}$

${\displaystyle A\cap A^{c}=\emptyset }$

Double Complement Law: ${\displaystyle \left(A^{c}\right)^{c}=A}$
Idempotent Laws: ${\displaystyle A\cup A=A}$

${\displaystyle A\cap A=A}$

Universal Bound Laws:
Identity For all sets A and B
Commutative Laws: ${\displaystyle A\cup B=B\cup A}$ ${\displaystyle A\cap B=B\cap A}$

2. Associative Laws: For all sets A, B, and C,

(a) (A ∪ B) ∪ C = A ∪ (B ∪ C) and

(b) (A ∩ B) ∩ C = A ∩ (B ∩ C).

3. Distributive Laws: For all sets, A, B, and C,

(a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and

(b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

For all sets A and B,

De Morgan’s Laws:

(a) (A ∪ B) c = A c ∩ B c and (b) (A ∩ B) c = A c ∪ B c .

Absorption Laws:

(a) A ∪ (A ∩ B) = A and (b) A ∩ (A ∪ B) = A.

Set Difference Law:

• A − B = A ∩ B c .

Complements of U and ∅:

• ${\displaystyle U^{c}=\emptyset }$
• ${\displaystyle \emptyset ^{c}=U}$

## Cardinality

The cardinality of a set is the number of elements in the set. The cardinality of a set ${\displaystyle A}$  is denoted ${\displaystyle |A|}$ .

### Types of Sets by Cardinality

A set can be classified as finite, countable, or uncountable.

• Finite Sets are sets that have finitely many elements, ${\displaystyle A=\{1,2,3\}}$  is a finite set of cardinality 3. More formally, a set ${\displaystyle A}$  is finite if a bijection exists between ${\displaystyle A}$  and a set ${\displaystyle \{1,\ldots ,n\}}$  for some natural number ${\displaystyle n}$ . ${\displaystyle n}$  is the said set's cardinality.
• Countable Sets are sets that have as many elements as the set of natural numbers. As since ${\displaystyle |\mathbb {Q} |=|\mathbb {N} |}$ , the set of rational numbers is countable.
• Uncountable Sets are sets that have more elements than the set of natural numbers. As since ${\displaystyle |\mathbb {R} |>|\mathbb {N} |}$ , the set of real numbers is uncountable.

### Common Sets of Numbers

• ${\displaystyle \mathbb {N} }$  is the set of Naturals
• ${\displaystyle \mathbb {Z} }$  is the set of Integers
• ${\displaystyle \mathbb {Q} }$  is the set of Rationals
• ${\displaystyle \mathbb {R} }$  is the set of Reals
• ${\displaystyle \mathbb {C} }$  is the set of Complex Numbers

### Comparison of Sets

2 sets ${\displaystyle A}$  and ${\displaystyle B}$  have the same cardinality (i.e. ${\displaystyle |A|=|B|}$ ), if there exists a bijection from ${\displaystyle A}$  to ${\displaystyle B}$ . In the case of ${\displaystyle |\mathbb {Q} |=|\mathbb {N} |}$ , they are the same cardinality as there exists a bijection from ${\displaystyle \mathbb {Q} }$  to ${\displaystyle \mathbb {N} }$ .

## Partitions of Sets

In many applications of set theory, sets are divided up into non-overlapping (or disjoint) pieces. Such a division is called a partition.

Two sets are called disjoint if, and only if, they have no elements in common.

A and B are disjoint ⇔ A ∩ B = ∅.

Sets ${\displaystyle A_{1},A_{2},A_{3},\ldots }$  are mutually disjoint (or pairwise disjoint or nonoverlapping)

if, and only if, no two sets ${\displaystyle A_{i}}$  and ${\displaystyle A_{j}}$  with distinct subscripts have any elements in

common. More precisely, for all ${\displaystyle i,j=1,2,3,\ldots }$

${\displaystyle A_{i}\cap A_{j}=\emptyset }$  whenever ${\displaystyle i\not =j}$ .

## Power Sets

The power set of a set A is all possible subsets of A, including A itself and the empty set. Which can be represented: ${\displaystyle P_{(A)}=\{\emptyset ,\{1\},\{2\},\ldots \}}$

For the set ${\displaystyle A=\{1,2,3\}}$

${\displaystyle P_{(A)}=\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}}$