# Formal Logic/Preliminaries/Sets

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

# Sets[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

### Subsets[edit | edit source]

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 | edit source]

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

### Union[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 → |