Definition:Set/Definition by Predicate

From ProofWiki
Jump to navigation Jump to search

Definition

An object can be specified by means of a predicate, that is, in terms of a property (or properties) that it possesses.

Whether an object $x$ possesses a particular (characteristic) property $P$ is either true or false (in Aristotelian logic) and so can be the subject of a propositional function $\map P x$.

Hence a set can be specified by means of such a propositional function:

$S = \set {x: \map P x}$

which means:

$S$ is the set of all objects which have the property $P$

or, more formally:

$S$ is the set of all $x$ such that $\map P x$ is true.

We can express this symbolically as:

$\forall x \paren {x \in S \iff P(x)}$

In this context, we see that the symbol $:$ is interpreted as such that.


Also known as

This construction is sometimes known as the set-builder notation or as set comprehension.

This is also sometimes rendered as set builder notation.

Some sources refer to it as definition by characteristic property.


An alternative notation for this is $S = \set {x \mid \map P x}$, but it can be argued that the use of $\mid$ for such that can cause ambiguity and confusion, as $\mid$ has several other meanings in mathematics.

On the other hand, if the expression defining the predicate is thick with $:$ characters, it may improve clarity to use $\mid$ for such that after all.

Some authors, mindful of such confusion, use the notation $S = \set {x; \map P x}$ as the semicolon is relatively rare in mathematical notation.


Sometimes it is convenient to abbreviate the notation by simply writing $S = \set {\map P x}$ or even just $S = \set P$.

For example, to describe the set $\set {x \in \R: \map f x \le \map g x}$ (for appropriate functions $f, g$), one could simply use $\set {f \le g}$.

Some sources simply identify $x$ as a variable, and then refer to $A = \set x$ as the set of all the values that $x$ can take.


Some sources use the notation $\boldsymbol [x: \map P x \boldsymbol ]$ for $\set {\map P x}$.


Axiomatic Set Theory

In the context of axiomatic set theory, a more strictly rigorous presentation of this concept is:

$S = \set {x \in A: \map P x}$

which means:

$S$ is the set of all objects in $A$ which have the property $P$

or, more formally:

$S$ is the set of all $x$ in $A$ such that $\map P x$ is true.

This presupposes that all the objects under consideration for inclusion in $S$ already belong to some previously-defined set $A$.


Thus any set $S$ can be expressed as:

$S = \set {s: s \in S}$


See the Axiom of Specification.


Examples

University Professors

An example in natural language of a set definition by predicate is:

$S := \text {the set of all university professors}$


Musical Mathematicians

Let $M$ denote the set of all the mathematicians in the world.

Let $I$ denote the set of all people who can play a musical instrument.

Let $S$ denote the set of all mathematicians who can play a musical instrument.


Then we can define $S$ as:

$S := \set {x: x \in M \text { and } x \in I}$

or as:

$S := \set {x \in M: x \in I}$


Set of Integers $x$ such that $2 \le x$

Let $S$ be the set defined as:

$S := \set {x \in \Z: 2 \le x}$

Then $S$ is the set of all integers greater than or equal to $2$:

$S = \set {2, 3, 4, \ldots}$


Set of Integers $x$ such that $x \le 5$

Let $S$ be the set defined as:

$S := \set {x \in \Z: x \le 5}$

Then $S$ is the set of all integers less than or equal to $5$:

$S = \set {\ldots, 2, 3, 4, 5}$


Set Indexed by Natural Numbers between $1$ and $100$

Let $V$ be the set defined as:

$V := \set {v_i: 1 \le i \le 100, i \in \N}$

Then $V$ is the set of the $100$ elements:

$V = \set {v_1, v_2, \ldots, v_{100} }$

and can also be written:

$V := \set {v_i: i = 1, 2, \ldots, 100}$

or even:

$V := \set {v_i: 1 \le i \le 100}$

as it is understood that the domain of $i$ is the set of natural numbers.


Set Indexed by Natural Numbers between $1$ and $10$

Let $U$ be the set defined as:

$U := \set {u_i: 1 < i < 10, i \in \N}$

Then $U$ has exactly $8$ elements:

$U = \set {u_2, u_3, u_4, u_5, u_6, u_7, u_8, u_9}$


Also see


Sources