## You are here

Homeexample of universe of finite sets

## Primary tabs

# example of universe of finite sets

This is an example of a class of universes in which all sets are finite. Not only are they good for illustrating the notion of universe, but they are appropriate for formalizing finite math.

To construct our universe, we begin with a finite set $\mathbf{U}_{0}$ and apply an inductive process. We shall illustate the construction more explicitly for a particular choice of $\mathbf{U}_{0}$ later.

We define the sets $\mathbf{U}_{i}$ for $i>0$ as follows: $\mathbf{U}_{i}$ is the set of all finite sets each of whose elements lie in some $\mathbf{U}_{j}$ with $j<i$. Then we define $\mathbf{U}$ as

$\mathbf{U}=\bigcup_{{i=0}}^{\infty}\mathbf{U}_{i}.$ |

To show that $\mathbf{U}$ is a universe, we need to check that it satisfies the four defining properties. This is easily done as follows:

1. If $x\in\mathbf{U}$, then $x\in\mathbf{U}_{i}$ for some $i$. By definition, if $y\in x$, then $y\in\mathbf{U}_{j}$ for some $j$ such that $j<i$. Since $\mathbf{U}_{j}\subset\mathbf{U}$, we conclude that $y\in\mathbf{U}$.

2. If $x,y\in\mathbf{U}$, then $x\in\mathbf{U}_{i}$ and $y\in\mathbf{U}_{j}$ for some $i,j$. Pick $k$ such that $k>i$ and $k>j$. Then, by definition, $\{x,y\}\in\mathbf{U}_{k}$. Since $\mathbf{U}_{k}\subset\mathbf{U}$, we conclude that $\{x,y\}\in\mathbf{U}$.

3. If $x\in\mathbf{U}$, then $x\in\mathbf{U}_{i}$ for some $i$. Hence, every element of $x$ belongs to some $\mathbf{U}_{j}$ with $j<i$. Also, by definition, $x$ is finite. Hence, every subset of $x$ is a finite set every element of which lies belongs to some $\mathbf{U}_{j}$ with $j<i$. This means that every subset of $x$ belongs to $\mathbf{U}_{i}$. Since there are only a finite number of subsets of $x$ and each of these is an element of $\mathbf{U}_{i}$, it follows that $\mathcal{P}(x)\in\mathbf{U}_{{i+1}}\subset\mathbf{U}$.

4. Let us first show that, if $x,y\in\mathbf{U}$, then $x\cup y\in\mathbf{U}$. By definition, there exist $i,j$ such that $x\in\mathbf{U}_{i}$ and $y\in\mathbf{U}_{j}$ for some $i,j$. Pick $k$ such that $k>i$ and $k>j$. Since every element of $x$ lies in $\mathbf{U}_{m}$ for some $m<i$ and every element of $y$ lies in $\mathbf{U}_{n}$ for some $n<j$ and $n,m<j$, it follows that every element of $x\cup y$ belongs to $\mathbf{U}_{l}$ for some $l<k$. Hence, $x\cup y\in\mathbf{U}_{k}\subset\mathbf{U}$. More generally, this implies that any finite union of elements of $\mathbf{U}$ must lie in $\mathbf{U}$. Since every element of $\mathbf{U}$ is finite, every family $\{x_{i}|i\in I\in\mathbf{U}\}$ is finite, hence $\cup_{{i\in I}}x_{i}\in\mathbf{U}$.

To illustrate how this works, let us take $\mathbf{U}_{0}=\{a,b\}$. Then we have:

$\mathbf{U}_{0}=\{a,b\}$ |

$\mathbf{U}_{1}=\{\>\{\},\{a\},\{b\},\{a,b\}\>\}$ |

$\mathbf{U}_{2}=\{\>\{\},\{a\},\{b\},\{a,b\},\{\{\}\},\{\{a\}\},\{\{b\}\},\{\{a% ,b\}\},\{\{\},a\},\{\{\},b\},\{\{\},a,b\}$ |

$\{\{a\},a\},\{\{a\},b\},\{\{a\},a,b\},\{\{b\},a\},\{\{b\},b\},\{\{b\},a,b\},\{% \{a,b\},a\},\{\{a,b\},b\},\{\{a,b\},a,b\},$ |

$\{\{\},\{a\}\},\{\{\},\{a\},a\},\{\{\},\{a\},b\},\{\{\},\{a\},a,b\},$ |

$\{\{\},\{b\}\},\{\{\},\{b\},a\},\{\{\},\{b\},b\},\{\{\},\{b\},a,b\},$ |

$\{\{\},\{a,b\}\},\{\{\},\{a,b\},a\},\{\{\},\{a,b\},b\},\{\{\},\{a,b\},a,b\},$ |

$\{\{a\},\{b\}\},\{\{a\},\{b\},a\},\{\{a\},\{b\},b\},\{\{a\},\{b\},a,b\},$ |

$\{\{a\},\{a,b\}\},\{\{a\},\{a,b\},a\},\{\{a\},\{a,b\},b\},\{\{a\},\{a,b\},a,b\},$ |

$\{\{b\},\{a,b\}\},\{\{b\},\{a,b\},a\},\{\{b\},\{a,b\},b\},\{\{b\},\{a,b\},a,b\},$ |

$\{\>\{\},\{a\},\{b\}\>\},\{\>\{\},\{a\},\{b\},a\>\},\{\>\{\},\{a\},\{b\},b\>\}% ,\{\>\{\},\{a\},\{b\},a,b\>\},$ |

$\{\>\{\},\{a\},\{a,b\}\>\},\{\>\{\},\{a\},\{b\},a\>\},\{\>\{\},\{a\},\{b\},b\>% \},\{\>\{\},\{a\},\{b\},a,b\>\},$ |

$\{\>\{\},\{b\},\{a,b\}\>\},\{\>\{\},\{b\},\{a,b\},a\>\},\{\>\{\},\{b\},\{a,b\}% ,b\>\},\{\>\{\},\{b\},\{a,b\},a,b\>\},$ |

$\{\>\{a\},\{b\},\{a,b\}\>\},\{\>\{a\},\{b\},\{a,b\},a\>\},\{\>\{a\},\{b\},\{a,% b\},b\>\},\{\>\{a\},\{b\},\{a,b\},a,b\>\},$ |

$\{\>\{\},\{a\},\{b\},\{a,b\}\>\},\{\>\{\},\{a\},\{b\},\{a,b\},a\>\},$ |

$\{\>\{\},\{a\},\{b\},\{a,b\},b\>\},\{\>\{\},\{a\},\{b\},\{a,b\},a,b\>\}\>\}$ |

As the reader can see, the cardinality of these sets increases rather quickly! Also, note that $\mathbf{U}_{1}$ is the power set of $\mathbf{U}_{0}$. Loosely speaking, $\mathbf{U}_{n}$ consists of all sets such that one must dig at most $n$ levels deep to arrive at the individuals $a$ and $b$.

## Mathematics Subject Classification

18A15*no label found*03E30

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections