PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] example of universe of finite sets (Example)

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$




"example of universe of finite sets" is owned by rspuzio.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: levels, power set, cardinality, union, implies, number, subset, defining properties, satisfies, finite set, finite, universes, class
There is 1 reference to this entry.

This is version 5 of example of universe of finite sets, born on 2005-02-15, modified 2006-10-21.
Object id is 6747, canonical name is ExampleOfUniverseOfFiniteSets.
Accessed 1953 times total.

Classification:
AMS MSC03E30 (Mathematical logic and foundations :: Set theory :: Axiomatics of classical set theory and its fragments)
 18A15 (Category theory; homological algebra :: General theory of categories and functors :: Foundations, relations to logic and deductive systems)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)