# Formal Logic/Preliminaries/Sets

← Start of Preliminaries |
↑ Preliminaries |
End of Preliminaries → |

## Contents

# Sets[edit]

Presentations of logic vary in how much **set theory** they use. Some are heavily laden with set theory. Though most are not, it is nearly impossible to avoid it completely. It will not be a very important focal point for this book, but we will use a little set theory vocabulary here and there. This section introduces the vocabulary and notation used.

## Sets and elements[edit]

Mathematicians use 'set' as an undefined primitive term. Some authors resort to quasi-synonyms such as 'collection'.

A *set* has *elements*. 'Element' is also undefined in set theory. We say that an element *is a member of* a set, also an undefined expression. The following are all used synonymously:

*x*is a member of*y**x*is contained in*y**x*is included in*y**y*contains*x**y*includes*x*

### Notation[edit]

A set can be specified by enclosing its members within curly braces.

is the set containing 1, 2, and 3 as members. The curly brace notation can be extended to specify a set using a rule for membership.

- (The set of all
*x*such that*x*= 1 or*x*= 2 or*x*= 3)

is again the set containing 1, 2, and 3 as members.

- , and

both specify the set containing 1, 2, 3, and onwards.

A modified epsilon is used to denote set membership. Thus

indicates that "*x* is a member of *y*". We can also say that "*x* is not a member of *y*" in this way:

### Characteristics of sets[edit]

A set is uniquely identified by its members. The expressions

all specify the same set even though the concept of an even prime is different from the concept of a positive square root. Repetition of members is inconsequential in specifying a set. The expressions

all specify the same set.

Sets are unordered. The expressions

all specify the same set.

Sets can have other sets as members. There is, for example, the set

### Some special sets[edit]

As stated above, sets are defined by their members. Some sets, however, are given names to ease referencing them.

The set with no members is the *empty set*. The expressions

all specify the empty set. Empty sets can also express oxymora ("four-sided triangles" or "birds with radial symmetry") and factual non-existence ("the King of Czechoslovakia in 1994").

A set with exactly one member is called a *singleton*. A set with exactly two members is called a *pair*. Thus {1} is a singleton and {1, 2} is a pair.

ω is the set of natural numbers, {0, 1, 2, ...}.

## Subsets, power sets, set operations[edit]

### Subsets[edit]

A set *s* is a *subset* of set *a* if every member of *s* is a member of *a*. We use the horseshoe notation to indicate subsets. The expression

says that {1, 2} is a subset of {1, 2, 3}. The empty set is a subset of every set. Every set is a subset of itself. A *proper subset* of *a* is a subset of *a* that is not identical to *a*. The expression

says that {1, 2} is a proper subset of {1, 2, 3}.

### Power sets[edit]

A *power set* of a set is the set of all its subsets. A script 'P' is used for the power set.

### Union[edit]

The *union* of two sets *a* and *b*, written *a* ∪ *b*, is the set that contains all the members of *a* and all the members of *b* (and nothing else). That is,

As an example,

### Intersection[edit]

The *intersection* of two sets *a* and *b*, written *a* ∩ *b*, is the set that contains everything that is a member of both *a* and *b* (and nothing else). That is,

As an example,

### Relative complement[edit]

The *relative complement* of *a* in *b*, written *b* \ *a* (or *b* − *a*) is the set containing all the members of *b* that are not members of *a*. That is,

As an example,

## Ordered sets, relations, and functions[edit]

The intuitive notions of *ordered set*, *relation*, and *function* will be used from time to time. For our purposes, the intuitive mathematical notion is the most important. However, these intuitive notions can be defined in terms of sets.

### Ordered sets[edit]

First, we look at ordered sets. We said that sets are unordered:

But we can define ordered sets, starting with ordered pairs. The angle bracket notation is used for this:

Indeed,

Any set theoretic definition giving 〈*a*, *b*〉 this last property will work. The standard definition of the *ordered pair* 〈*a*, *b*〉 runs:

This means that we can use the latter notation when doing operations on an ordered pair.

There are also bigger ordered sets. The *ordered triple* 〈*a*, *b*, *c*〉 is the ordered pair 〈〈*a*, *b*〉, *c*〉. The *ordered quadruple* 〈*a*, *b*, *c*, *d*〉 is the ordered pair 〈〈*a*, *b*, *c*〉, *d*〉. This, in turn, is the ordered triple 〈〈〈*a*, *b*〉, *c*〉, *d*〉. In general, an *ordered n-tuple* 〈*a*_{1}, *a*_{2}, ..., *a _{n}*〉 where

*n*greater than 1 is the ordered pair 〈〈

*a*

_{1},

*a*

_{2}, ...,

*a*

_{n-1}〉,

*a*〉.

_{n}It can be useful to define an *ordered 1-tuple* as well: 〈*a*〉 = *a*.

These definitions are somewhat arbitrary, but it is nonetheless convenient for an *n*-tuple, *n* 〉 2, to be an *n*-1 tuple and indeed an ordered pair. The important property that makes them serve as ordered sets is:

### Relations[edit]

We now turn to relations. Intuitively, the following are relations:

*x*<*y**x*is a square root of*y**x*is a brother of*y**x*is between*y*and*z*

The first three are binary or 2-place relations; the fourth is a ternary or 3-place relation. In general, we talk about *n*-ary relations or *n*-place relations.

First consider binary relations. A *binary relation* is a set of ordered pairs. The *less than* relation would have among its members 〈1, 2〉, 〈1, 3〉, 〈16, 127〉, etc. Indeed, the *less than* relation defined on the natural numbers ω is:

Intuitively, 〈*x*, *y*〉 is a member of the *less than* relation if *x* < *y*. In set theory, we do not worry about whether a relation matches an intuitive concept such as *less than*. Rather, *any* set of ordered pairs is a binary relation.

We can also define a 3-place relation as a set of 3-tuples, a 4-place relation as a set of 4-tuples, etc. We only define *n*-place relations for *n* ≥ 2. An *n*-place relation is said to have an *arity* of *n*. The following example is a 3-place relation.

Because all *n*-tuples where *n* > 1 are also ordered pairs, all n-place relations are also binary relations.

### Functions[edit]

Finally, we turn to functions. Intuitively, a function is an assignment of values to arguments such that each argument is assigned at most one value. Thus the *+ 2* function assigns a numerical argument *x* the value *x* + 2. Calling this function *f*, we say *f*(*x*) = *x* + 2. The following define specific functions.

Note that *f*_{3} is undefined when *x* = 0. According to biblical tradition, *f*_{4} is undefined when *x* = Adam or *x* = Eve. The following do not define functions.

Neither of these assigns unique values to arguments. For every positive *x*, there are two square roots, one positive and one negative, so *f*_{5} is not a function. For many *x*, *x* will have multiple sons, so *f*_{6} is not a function.
If *f*_{6} is assigned the value *the son of x* then a unique value is implied by the rules of language, therefore *f*_{6} will be a function.

A *function f* is a binary relation where, if 〈*x*, *y*〉 and 〈*x*, *z*〉 are both members of *f*, then *y* = *z*.

We can define many place functions. Intuitively, the following are definitions of specific many place functions.

Thus 〈4, 7, 11〉 is a member of the 2-place function *f*_{7}. 〈3, 4, 5, 35〉 is a member of the 3 place function *f*_{8}

The fact that all *n*-tuples, *n* ≥ 2, are ordered pairs (and hence that all *n*-ary relations are binary relations) becomes convenient here. For *n* ≥ 1, an *n*-place function is an *n*+1 place relation that is a 1-place function. Thus, for a 2-place function *f*,

← Start of Preliminaries |
↑ Preliminaries |
End of Preliminaries → |