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

Semi-formal naive set theory is a foundational system for mathematics and higher logic that should prove adequate for most, perhaps even all, purposes outside of set theory itself, and also be free from the well-known paradoxes.

Membership and equality

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

The notation $x\in S$ asserts 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. The nonstandard idiom S owns x tempts and goes well with the use of "belongs," and moreover avoids the common but deceptive "S contains x."

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.

The elements of a finite set can be listed. 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\}.$ (In these lists, the 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.

If there is a relation of part to whole among sets, it is not the membership relation. Parthood is commonly taken to be transitive: 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\}$. Hence x is not always the same as the set whose only element is x (if indeed this were ever true!), though we tend to talk in this manner 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. Hence the subset relation is formally (and metaphorically) suited to be the relation of part to whole on sets.

The universe

We begin by introducing the universe of discourse, denoted U, having the following properties:

• 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 (Note that it can be proved that not all subsets of U belong to U.);
• 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 wish to talk about from the outset. 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₂ 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. We adopt no restrictions on how much additional stuff each U_n+1 can contain. The U_n's are a hierarchy of universes of discourse each fit for the same purposes as U; we expect that anything we do will fit in some fixed universe in this hierarchy.

To ask whether all the U_n form a sequence or set is to transcend naivete.

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 U₂ (and $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 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 U_n+1 which are not in U_n. 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 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 (or any other) definition of an ordered pair is that (a,b)=(c,d) implies both a=c and b=d.

Note that if $a\in U$ and $b\in U$, then $(a,b)\in U$ as well. Hence for any relation (two place predicate) R(x,y), $\{(x,y)\mid R(x,y)\}\in P(U),$ which codes the restriction of the relation R to U. Similar constructions work higher up in the hierarchy.

If A and B are sets, the Cartesian product $A\times B$ is defined as $\{(a,b)\mid a\in A\wedge b\in B\}$. Any relation whose domain is a subset of A and whose range is a subset of B is coded by a subset of $A\times B$. Although it is a bit late in the game to fiddle with the basic rules, note 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. A one- or two-element set is certainly 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.