Sets

Article Info

Last Updated: 3 November 2025 (5e1700b)
Tags: Logic

Under construction This section is incomplete and may contain errors.

Sets are:

unordered
contain no duplicates

Set Notation

Set are expressed by putting the items in curley bracket pairs, with each item being comma seperated.

The set of items A, B, C can be expressed using set notatation as: $\{A, B, C\}$. Sets can contain other sets,in which case they are just treated like any other member of the set. The nested values do not count as being in the set directly.

Nesting Sets

$X = \{A, B, \{ C \}\}$ is a set which contains:

A as a member
B as a member
The set {C}, which contains:
- C as a member

Note that the set X does NOT (directly) contain C, so C would not be considered a member of X, however the set {C} is considered a member of X

Empty Set

The set which contains no items is called the ’empty set’, and has it’s own symbol, $\emptyset$.

Set Operations

Union

The union of two sets is a set containing both their members:

$\{A, B, C\} \cup \{1, 2, 3\} = \{A, B, C, 1, 2, 3\}$

Remember, a set contains no duplicates, so if an item appears in both sets, it should only appear once in the resulting set.

Intersection

The intersection of two sets is the items they have in common:

$\{A, B, C\} \cap \{A, 2, 3\} = \{A\}$

Difference

The difference of two sets is all elements in the first set which are not in the second set.

$\{A, B, C\} \setminus \{A, 1, 2\} = $

Cartsiain Product

The cartsiain product of two sets is defined as the combination of all elements:

$\{A, B, C\} \times \{X, Y, Z\}$

$\{ (A, X), (A, Y), (A, Z), (B, X), (B, Y), (B, Z), (C, X), (C, Y), (C, Z) \}$

Set Predicates

There are some operations you can perform on sets which return either a ’true’ or ‘false’ answer:

Membership

The membership operator, $\in$, returns true of the element is contained with the set.

$A \in {A, B, C} = \mathrm{true}$, but $X \in {A, B, C} = \mathrm{false}$

$?? \in \{A, B\}$	Result	Reason
$A$	true	A is contained in the set
$B$	true	Same as above
$C$	false	C does not appear in the set
$\{A\}$	false	Although A appears in the set, this represents ’the set containing A’
$\emptyset$	true	The empty set is in every set

Subset

A subset is a set whos members are completely contained within the other set.

$ \{A, B\} \subset \{A, B, C\} = \mathrm{true}$ but $\{A, B\} \subset \{A, X\} = \mathrm{false}$

$?? \subset \{A, B\}$	Result	Reason
$\{B, A\}$	true	A set is a subset of itself (also see proper subset)
$\{A\}$	true	All elements of the left-hand set are contained in the right hand side
$\{B\}$	true	Same as above
$\{X, Y\}$	false	Neither X nor Y appear in the right hand set
$\{X\}$	false	X is not in the right hand set
$\{X, A, B\}$	false	Although A and B appear, X does not
$\emptyset$	true	The empty set has no elements, therefore ‘all elements appear in the right hand side’

Subset is true if the two sets are the same, namely, $\{A, B\} \subset \{A, B\} = \mathrm{true}$

Proper Subset

Proper subsets is the subset operator which does not consider a set to be a subset of itself.

Proper Subset is false if the two sets are the same, namely, $\{A, B\} \subsetneq \{A, B\} = \mathrm{false}$

Superset

TODO

Proper Superset

TODO

Well known sets

There are some sets which are used a great deal within computing. These often have their own symbols:

Name	Symbol	LaTeX	Meaning
Boolean	$\mathbb{B}$	`\mathbb{B}`	True or False, $\{\mathrm{true}, \mathrm{false}\}$
Natural Numbers	ℕ	`\mathbb{N}`	Positive Intergers, $\{1, 2, … \}$
Natural Numbers	$\mathbb{N}^+$	`\mathbb{N}^+`	Positive Intergers + zero, $\{0, 1, 2, … \}$
Integer	ℤ	`\mathbb{Z}`	Signed Integers, $\{…, -1, 0, 1, …\}$

Note ‘Natural Numbers’ can be used to mean either including or not including 0. Its important to know which is meant as the notation is not always used consistantly.