User:Randall Holmes/Sandbox/semi-formal naive set theory

Here we present a modest proposal for semi-formal naive set theory. This is set theory adequate for all practical purposes outside of set theory itself with no fear of nasty paradoxes sneaking in.

membership and equality

Some things in the mathematical universe are sets. Some things in your favorite universe may not be sets.

We use the notation $x\in S$ to say that the object x is an element or member of the set S. We may also say that x belongs to S, or, very briefly x is in S. We will try not to say that x is contained in S because that invites confusion. We are tempted by the nonstandard idiom S owns x, which goes well with the use of "belongs" and avoids the common "S contains x", which is deceptive.

If every element of a set S is also an element of a set T, we say that S is a subset of T, written $S\subseteq T$. We may also say that S is contained in T or that T contains S.

Sets can be given using finite lists. For example $\{1,2,3\}$ is a set whose elements are 1,2,3. Its subsets are (among others) $\{1\}$, $\{1,3\}$, $\{1,2,3\}$ itself, and even the infamous $\{\}$ or $\emptyset$, the empty set. $\{1,2,3\}$ is the same set as $\{3,2,1\}$, or even $\{3,2,2,1,1,1\}$ (these are lists in which order of elements or repetition of elements has no meaning).

Two sets are equal iff they have the same elements. This does not mean that non-sets (which have no elements, of course) are all identical to the empty set. But it does mean (among other things) that there is only one empty set.

Please notice that if there is a relation of part to whole among sets, it is not the membership relation. If A is part of B and B is part of C, then A is part of C. Notice, though, that $2\in \{2,3\}$, $\{2,3\}\in \{\{2,3\}\}$ but $2\not \in \{\{2,3\}\}$. $\{2,3\}$ has two elements, 2 and 3, while $\{\{2,3\}\}$ has just one element, $\{2,3\}$. So we see that x is not always the same as the set whose only element is x (if indeed this is ever true!), though we have a tendency to talk this way when talking about points in geometry. On the other hand the subset relation does have the property that if $A\subseteq B$ and $B\subseteq C$ hold, then $A\subseteq C$ follows: the subset relation is formally suitable (and metaphorically suitable) to be the relation of part to whole on sets.

The universe

We start by introducing a major player, the universe of discourse, informally known as U.

• U is a set.
• Every finite set of elements of U is also an element of U.
• Every element of U which is a set has every element and every subset also in U. (Notice that this does not mean that all subsets of U belong to U; we can show that this is not true).
• For each element A of U, the set of all finite subsets of A belongs to U.

The idea is that U contains all the material we start out wanting to talk about. If a set is part of our universe of discourse, we may reasonably expect all of its elements and all of its subsets to also be in our universe of discourse, and it is convenient to be able to make finite (unordered) lists of things in our universe of discourse and still be in our universe of discourse.

We need to be more explicit about how we arrange for all finite sets to be in U: we stipulate that $\emptyset$ is in U, that the set $\{x\}$ is in U for each x in U, and that for each pair of sets A and B, their boolean union $A\cup B$, defined as the set of all x such that either $x\in A$ or $x\in B$ belongs to U as well. This is more than enough to ensure that any $\{x_{1},\ldots ,x_{n}\}$ = $\{x_{1}\}\cup \ldots \cup \{x_{n}\}$ belongs to U if all its elements belong to U.

Our reasons for including "the set of all finite subsets of A" for A in U may be allowed to remain mysterious for the moment. We must, though, say what we mean. An element of U is said to be finite if it belongs to each subset of U which contains the empty set, contains all singletons, and is closed under boolean unions (U itself is stipulated to be such a subset): finiteness for elements of U is sufficient to make it clear what is meant by finite in each of the conditions above.

Numerals

We can use the properties of U cited above to show that there is a sequence of objects usable as numerals in U: define 0 as $\emptyset$, 1 as $\{0\}$, 2 as $\{0,1\}$, and so forth. Each natural number n is thus defined as the finite set $\{0,\ldots ,n-1\}$.

Properties and universes

We might naively suppose that any property $Q$ determines a set $\{x\mid Q(x)\}$ whose elements are all the x for which the sentence Q(x) (x has the property Q) is true. This we do not suppose here.

We do suppose that for any property Q, there is a set $\{x\in U\mid Q(x)\}$ of all x which have the property Q and belong to our universe U. We suppose further that there is a set U₂ which has all subsets of U as elements. Moreover, we allow this process to be repeated: we suppose that there is a set U₃ which has all subsets of U₂ as elements , and that every property Q determines a set $\{x\in U_{2}\mid Q(x)\}$ which belongs to U₃, and further that U_n+1 exists for each natural number n, having among its elements all the subsets of U_n, and having elements $\{x\in U_{n}\mid Q(x)\}$ for each property Q. We suppose (but do not restrict ourself to supposing) that any open sentence R(x) in mathematical language (including the language of our set theory) expresses a property of x.

We usually suppose that every set A belongs to U_n for some n (depending on A).

We have not defined U₂ as the power set P(U) of U (we can define P(U) as the set of all elements of U_2 which are subsets of U): we have left open the possibility that there are more elements of U₂. In fact, we stipulate that each U_n has the same closure properties as U: each finite subset of U_n belongs to U_n, each element or subset of an element of U_n belongs to U_n, and for any A in U_n, the set of all finite subsets of A also belongs to U_n.

Some facts about subsets

For any set $A\in U$, and property Q, we can define $\{x\in A\mid Q(x)\}$ as $\{x\in U\mid x\in A\wedge Q(x)\}$. All elements of A are in U, so this has the intended members, and it belongs to $P(U)$ by the discussion above. But it is also a subset of A, and any subset of an element of U belongs to U, so we actually have $\{x\in A\mid Q(x)\}\in U$ for any set A belonging to U and any property Q.

Subsets of elements of U are elements of U, but subsets of U itself are not so reliable.

Consider $R=\{x\in U\mid x\not \in x\}$. This set might or might not contain all of U (nothing we have said prevents some sets from being elements of themselves, though it is hard to see how to show that there is (or is not) such a set). One thing that is certain is that it is not an element of U (though it is an element of P(U)). R is an element of R iff R is an element of U and R is not an element of R. If "R is an element of U" were true, this would simplify to the impossible "R is an element of R iff R is not an element of R". We can use the same technique to build sets in each Pⁿ⁺¹(U) which are not in Pⁿ(U). This is the positive content of Russell's paradox for our semi-formal theory.

Notice that U itself cannot belong to U, because it has a subset R which does not belong to U.

The set of natural numbers

For any set x, define $x^{+}$ as $x\cup \{x\}$. Notice that for each natural number n as we have defined them individually above, n+1 = n⁺, and also that for any set x in U, $x^{+}$ is also in U.

We call a subset I of U $inductive$ just in case $\emptyset$ is in I and for each x in I, we also have $x^{+}$ in I.

Notice that U itself is inductive, and that each inductive set contains 0 (as we have defined it) and contains n+1 if it contains n. We define the set N of all natural numbers as the set of all elements of U which belong to every inductive set.

The form of this definition enforces the principle of mathematical induction, and with some cunning enables the definition of relations and operations of arithmetic as well.

It would be entirely natural to stipulate that N, which clearly belongs to P(U), belongs to U as well, and to make similar decisions as further kinds of numbers and basic sets of numbers are constructed.

Ordered pairs, cartesian products, and relations

The ordered pair (a,b) is defined as $\{\{a\},\{a,b\}\}$ The crucial point about this (and any) definition of an ordered pair is that (a,b)=(c,d) implies both a=c and b=d.

Notice that for any a and b in U, we have (a,b) in U as well.

This means that for any relation (two place predicate) R(x,y) we will find the set $\{(x,y)\mid R(x,y)\}$ in P(U), which will code the restriction of the relation R to U. Similar constructions work higher up in the hierarchy.

For any sets A and B, we define the cartesian product $A\times B$ as $\{(a,b)\mid a\in A\wedge b\in B\}$. Any relation with domain a subset of A and range a subset of B is coded by a subset of $A\times B$. Though it is a bit late in the game to fiddle with our basic rules, we notice that it would be very nice if U were closed under cartesian products, as then relations between sets from U would be in U for the same reason that subsets of sets belonging to U are in U.

As it turns out, this has already been arranged. Certainly a one- or two-element set is finite. The cartesian product of A and B inhabits the set of all finite subsets of the set of all finite subsets of $A\cup B$, which inhabits U if A and B do.