next up previous
Next: Naive Set Theory Is Up: Set Theory Handout Previous: Additions to First Order

Defining Additional Set-Theoretic Notation

It is a striking fact that these minimal additions to first-order logic allow us to define the rest of the notation of set theory, so that we need not add any more primitives to the language itself.

For example, we can define some familiar set-theoretic ideas as follows.

Definition 1 (List Notation)   { $x_1, x_2, \ldots, x_n$} denotes a set s if and only if $\forall y (y \in s \leftrightarrow (y=x_1 \vee y=x_2 \vee \ldots \vee y=x_n))$

We could add a clause specifying that this set must be unique (i.e. that for any set $s'$, if $y \in s'$ if and only if it is $x_1$ or $x_2$ or ...or $x_n$, then $s' = s$. However, the Axiom of Extensionality guarantees that this will be true whenever the definition above is satisfied, so we do not need to add this explicitly.

Definition 2 (Brace Notation)   {$x\vert P(x)$} denotes a set s if and only if

$\forall z (z \in s \leftrightarrow P(z)) \wedge \forall b (\forall z (z \in b \leftrightarrow P(z)) \to b=s) $

This time we have listed both the existence and uniqueness requirements. Notice that the first conjunct says that there is a set consisting of all the items $x$ of which $P(x)$ is true. The Axiom of Comprehension guarantees that there will be such a set for every property $P(x)$ expressible in first order logic, so it guarantees that there will be a set that satisfies the first conjunct. The second conjunct says that there is no more than one set that satisfies the property $P(x)$. The Axiom of Extensionality guarantees that this conjunct will be satisfied whenever the first conjunct is. So, taken together, the two axioms guarantee that there will always be a set that satisfies the conditions for being denoted by {$x\vert P(x)$}, thus guaranteeing that brace notation always succeeds in identifying a unique set.

We can give similar definitions for the intersection and union functions:

Definition 3 (Intersection)   $ \forall a \forall b \forall z(z \in a \cap b \leftrightarrow (z \in a \wedge z \in b))$

Definition 4 (Union)   $ \forall a \forall b \forall z(z \in a \cap b \leftrightarrow (z \in a \vee z \in b))$

(We have simply written these definitions as biconditionals. We could regard these biconditionals as additional axioms of our formal system, but to keep the system simple we will instead regard the right-hand side of the biconditional as defining the left-hand side. The definitions of list and brace notion could be written in this way as well.)

We can also define the relations of subset and proper subset.

Definition 5 (Subset)   $ \forall a \forall b (a \subseteq b \leftrightarrow \forall x (x \in a \to x \in b))$

Definition 6 (Proper Subset)   $ \forall a \forall b (a \subset b \leftrightarrow (\forall x (x \in a \to x \in b) \wedge \exists y (y \in b \wedge y \notin a)))$

Here '$y \notin a$' is simply a helpful abbreviation of the negation '$\neg(y \in a)$'.


next up previous
Next: Naive Set Theory Is Up: Set Theory Handout Previous: Additions to First Order
cbrown 2002-01-27