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

[edit | edit source]

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  a {\displaystyle a} belongs to a set  A {\displaystyle A} , we can say that " a {\displaystyle a} is a member of the set  A {\displaystyle A} ", or that " a {\displaystyle a} is in  A {\displaystyle A} ", or simply write  a ∈ A {\displaystyle a\in A} .
* Similarly, if  a {\displaystyle a} is not in  A {\displaystyle A} , we would write  a ∉ A {\displaystyle a\notin A} .

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

### Notation

[edit | edit source]

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

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

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

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

### Elements

[edit | edit source]

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  A {\displaystyle A} that contains all the positive integers that are smaller than ten. In this case we would write  A = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } {\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  A = { a : a positive integer less than 10 } {\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  X = { 1 , 2 , 3 } {\displaystyle X=\\{1,2,3\\}} to denote a set  X {\displaystyle X} containing the numbers 1, 2 and 3. Or, X = { 1 , 2 , 3 } = { 3 , 2 , 1 } = { 1 , 1 , 2 , 3 , 3 } {\displaystyle X=\\{1,2,3\\}=\\{3,2,1\\}=\\{1,1,2,3,3\\}} .

## Subsets

[edit | edit source]

A is a subset of B.  ( A ⊆ B ) {\displaystyle \left(A\subseteq B\right)}

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

* A ⊆ B ⇔ ∀ x {\displaystyle A\subseteq B\Leftrightarrow \forall x} , if  x ∈ A {\displaystyle x\in A} , then  x ∈ B . {\displaystyle x\in B.}

Negation:

* A ⊈ B ⇔ ∃ x {\displaystyle A\nsubseteq B\Leftrightarrow \exists x} such that  x ∈ A {\displaystyle x\in A} and  x ∉ B . {\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:

x ∈ A {\displaystyle x\in A} |  x ∈ B . {\displaystyle x\in B.} | if  x ∈ A {\displaystyle x\in A} , then  x ∈ B . {\displaystyle x\in B.} |  x ∈ A {\displaystyle x\in A} and  x ∉ B {\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

[edit | edit source]

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 ∩ ∅ = ∅.

A ∩ U = A {\displaystyle A\cap U=A} |  A ∩ U = A {\displaystyle A\cap U=A}

|

Identity  | For all sets A  |

|
|

Identity Laws:  |

A ∪ ∅ = A {\displaystyle A\cup \emptyset =A}

|  |  A ∩ U = A {\displaystyle A\cap U=A} |  A ∩ U = A {\displaystyle A\cap U=A}

|

Complement Laws:  |

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

* * *

A ∩ A c = ∅ {\displaystyle A\cap A^{c}=\emptyset }

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

* * *

A ∩ A = A {\displaystyle A\cap A=A}

Universal Bound Laws:  |  |
Identity  | For all sets A and B

|

Commutative Laws:  |  A ∪ B = B ∪ A {\displaystyle A\cup B=B\cup A} A ∩ B = B ∩ 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 ∅:

* U c = ∅ {\displaystyle U^{c}=\emptyset }
* ∅ c = U {\displaystyle \emptyset ^{c}=U}

## Cardinality

[edit | edit source]

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

### Types of Sets by Cardinality

[edit | edit source]

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

* Finite Sets are sets that have finitely many elements,  A = { 1 , 2 , 3 } {\displaystyle A=\\{1,2,3\\}} is a finite set of cardinality 3. More formally, a set  A {\displaystyle A} is finite if a bijection exists between  A {\displaystyle A} and a set  { 1 , … , n } {\displaystyle \\{1,\ldots ,n\\}} for some natural number  n {\displaystyle n} .  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  | Q | = | N | {\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  | R | > | N | {\displaystyle |\mathbb {R} |>|\mathbb {N} |} , the set of real numbers is uncountable.

### Common Sets of Numbers

[edit | edit source]

Diagram to demonstrate the number systems ℝ, ℚ, ℤ and ℕ as sub-sets of each other.

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

### Comparison of Sets

[edit | edit source]

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

## Partitions of Sets

[edit | edit source]

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  A 1 , A 2 , A 3 , … {\displaystyle A_{1},A_{2},A_{3},\ldots } are mutually disjoint (or pairwise disjoint or nonoverlapping)

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

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

A i ∩ A j = ∅ {\displaystyle A_{i}\cap A_{j}=\emptyset } whenever  i ≠ j {\displaystyle i\not =j} .

## Power Sets

[edit | edit source]

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

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

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

## Learning resources

[edit | edit source]

### Wikiversity

[edit | edit source]

* Introduction_to_set_theory/Lecture_1

### Wikipedia

[edit | edit source]

* Set theory category

## See also

[edit | edit source]

* Wikipedia:set theory

Link to any subpages this page might have