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 \map 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 call such a construction as a set former.

Some sources refer to it as (set) 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.


A common variant for presenting a conjunction of propositional functions:

$\set {x: \map P x \wedge \map Q x}$

is:

$\set {x: \map P x, \map Q x}$


Some sources use the notation:

$\boldsymbol [x: \map P x \boldsymbol ]$

for $\set {x: \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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Set/Definition_by_Predicate&oldid=728598"