Definition:Language of Set Theory

From ProofWiki
Jump to: navigation, search

Definition


The language of set theory consists of the language of predicate logic with the binary predicate symbol $\in$, denoting membership.


Predicate Symbols

The language of set theory uses only one predicate symbol, $\in$, the membership sign.

It is a binary predicate symbol.

Using $\in$, other symbols such as $=$ can be defined (see Definition:Set Equality).


Connectives

The language of set theory borrows the connectives from the language of predicate logic. However, some of the connectives can be considered definitional abbreviations.

$\land$ and $\neg$ can be taken as primitive connectives with the following definitional abbreviations:

\(\displaystyle P \implies Q\) \(\operatorname{for}\) \(\displaystyle \neg ( P \land \neg Q )\)
\(\displaystyle P \lor Q\) \(\operatorname{for}\) \(\displaystyle \neg ( \neg P \land \neg Q )\)
\(\displaystyle P \iff Q\) \(\operatorname{for}\) \(\displaystyle ( ( P \implies Q ) \land ( Q \implies P ) )\) justified because $\implies$ is already a definitional abbreviation

$\implies$ and $\neg$ can be taken as primitive connectives with the following definitional abbreviations:

\(\displaystyle ( P \land Q )\) \(\operatorname{for}\) \(\displaystyle \neg ( P \implies \neg Q )\)
\(\displaystyle ( P \lor Q )\) \(\operatorname{for}\) \(\displaystyle ( \neg P \implies Q )\)
\(\displaystyle ( P \iff Q )\) \(\operatorname{for}\) \(\displaystyle \neg ( ( P \implies Q ) \implies \neg ( Q \implies P ) )\)

The sheffer stroke $|$ can be taken as a sole primitive connective with the following definitional abbreviations:

\(\displaystyle \neg P\) \(\operatorname{for}\) \(\displaystyle ( P \vert P )\)
\(\displaystyle ( P \implies Q )\) \(\operatorname{for}\) \(\displaystyle ( P \vert ( Q \vert Q ) )\)

The other connectives can be defined using $\neg P$ and $( P \implies Q )$ as the "new" primitive connectives.


Quantifiers

The language of set theory adopts the same quantifiers as those in the language of predicate logic.

However, only $\forall$ is necessary to adopt as a primitive symbol, and $\exists$ can be defined:

$\exists x: P(x) \operatorname{for} \neg \forall x: \neg P(x)$


Rules of Formation

The language of set theory is endowed with the following rules of formation:

  1. If $x$ and $y$ are variables, then $x \in y$ is a well-formed formula.
  2. If $P$ and $Q$ are well-formed formulae, then $\neg P$, $( P \implies Q )$, $( P \land Q )$, $( P \lor Q )$, and $( P \iff Q )$ are also well-formed formulae.
  3. If $P$ is a well-formed formula and $x$ is a variable, then $\forall x: ( P )$ and $\exists x: ( P )$ are well-formed formulae.

It is seen that these rules constitute a bottom-up grammar.


Sources