Namespaces
Variants
Actions

Difference between revisions of "Identical truth"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
i0501001.png
 +
$#A+1 = 47 n = 0
 +
$#C+1 = 47 : ~/encyclopedia/old_files/data/I050/I.0500100 Identical truth,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''logical truth, tautology''
 
''logical truth, tautology''
  
A property of formulas in the language of predicate calculus, meaning that the formulas are true in all interpretations and for all admissible values of their free variables. For example, for a formula containing only one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501001.png" />-place predicate symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501002.png" /> and variables of one sort (that is, variables which are interpreted in the same domain of variation), any pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501003.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501004.png" /> is an arbitrary non-empty set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501005.png" /> is an arbitrary binary relation on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501006.png" />, is an [[Interpretation|interpretation]]. Arbitrary elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501007.png" /> are admissible values for the free variables. Truth of a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501008.png" /> at values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i0501009.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010010.png" />) of the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010011.png" />, respectively, is defined by induction on the structure of the formula, as follows. (Here the free variables run through the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010012.png" /> and the predicate symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010013.png" /> denotes the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010014.png" />.)
+
A property of formulas in the language of predicate calculus, meaning that the formulas are true in all interpretations and for all admissible values of their free variables. For example, for a formula containing only one $  2 $-
 +
place predicate symbol $  \rho $
 +
and variables of one sort (that is, variables which are interpreted in the same domain of variation), any pair $  ( M , R ) $,  
 +
where $  M $
 +
is an arbitrary non-empty set and $  R \subseteq M \times M $
 +
is an arbitrary binary relation on $  M $,  
 +
is an [[Interpretation|interpretation]]. Arbitrary elements of $  M $
 +
are admissible values for the free variables. Truth of a formula $  \phi ( x _ {1} \dots x _ {n} ) $
 +
at values $  a _ {1} \dots a _ {n} $(
 +
$  n \geq  0 $)  
 +
of the variables $  x _ {1} \dots x _ {n} $,  
 +
respectively, is defined by induction on the structure of the formula, as follows. (Here the free variables run through the set $  M $
 +
and the predicate symbol $  \rho $
 +
denotes the relation $  R $.)
  
Suppose that a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010015.png" /> is given, as well as a finite sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010016.png" /> of variables containing all the free variables of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010017.png" />; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010018.png" /> denote the set of all finite sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010019.png" /> of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010020.png" /> at which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010021.png" /> is true in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010022.png" />. A set of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010023.png" /> can be constructed inductively as follows (here it is assumed that the logical symbols in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010024.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010027.png" />):
+
Suppose that a formula $  \phi $
 +
is given, as well as a finite sequence $  \overline{x}\; = ( x _ {1} \dots x _ {n} ) $
 +
of variables containing all the free variables of $  \phi $;  
 +
let $  | \phi ;  \overline{x}\; | $
 +
denote the set of all finite sequences $  ( a _ {1} \dots a _ {n} ) $
 +
of elements of $  M $
 +
at which $  \phi $
 +
is true in $  ( M , R ) $.  
 +
A set of the form $  | \phi ;  \overline{x}\; | $
 +
can be constructed inductively as follows (here it is assumed that the logical symbols in $  \phi $
 +
are $  \wedge $,  
 +
$  \neg $,  
 +
$  \exists $):
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010028.png" /></td> </tr></table>
+
$$
 +
| \phi ; \overline{x}\; = \
 +
\{ {( a _ {1} \dots a _ {n} ) } : {
 +
( a _ {i} , a _ {j} ) \in R } \}
 +
$$
  
if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010029.png" /> has the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010030.png" />;
+
if $  \phi $
 +
has the form $  \rho ( x _ {i} , x _ {j} ) $;
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010031.png" /></td> </tr></table>
+
$$
 +
| \phi _ {1} \wedge \phi _ {2} ;  \overline{x}\; |  = \
 +
| \phi _ {1} ;  \overline{x}\; |  \cap \
 +
| \phi _ {2} ; \overline{x}\; | ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010032.png" /></td> </tr></table>
+
$$
 +
| \neg \phi ;  \overline{x}\; |  = M  ^ {n} \setminus  | \phi ; \overline{x}\; | ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010033.png" /></td> </tr></table>
+
$$
 +
| \exists y  \phi ;  \overline{x}\; =   \mathop{\rm pr} _ {n+} 1  | \phi ; \overline{x}\; y | ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010036.png" /> denote, respectively, intersection, difference and projection along the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010038.png" />-st coordinate (that is, the image with respect to the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010039.png" />) of sets.
+
where $  \cap $,  
 +
$  \setminus  $,  
 +
$  \mathop{\rm pr} _ {n+} 1 $
 +
denote, respectively, intersection, difference and projection along the $  ( n+ 1 ) $-
 +
st coordinate (that is, the image with respect to the mapping $  ( a _ {1} \dots a _ {n} , a _ {n+} 1 ) \mapsto ( a _ {1} \dots a _ {n} ) $)  
 +
of sets.
  
Identical truth for a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010040.png" /> with free variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010041.png" /> then means that for any interpretation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010042.png" />, every sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010043.png" /> of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010044.png" /> belongs to the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010045.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010046.png" /> the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010047.png" /> is either empty or a singleton. For example, the formula
+
Identical truth for a formula $  \phi $
 +
with free variables $  x _ {1} \dots x _ {n} $
 +
then means that for any interpretation $  ( M , R ) $,  
 +
every sequence $  ( a _ {1} \dots a _ {n} ) $
 +
of elements of $  M $
 +
belongs to the set $  | \phi ;  x _ {1} \dots x _ {n} | $.  
 +
For $  n = 0 $
 +
the set $  | \phi ;  \overline{x}\; | $
 +
is either empty or a singleton. For example, the formula
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050100/i05010048.png" /></td> </tr></table>
+
$$
 +
\exists y  \forall x  \rho ( x , y )  \supset \
 +
\forall x  \exists y  \rho ( x , y )
 +
$$
  
 
is an identical truth. The converse implication is not an identically-true formula.
 
is an identical truth. The converse implication is not an identically-true formula.

Latest revision as of 22:11, 5 June 2020


logical truth, tautology

A property of formulas in the language of predicate calculus, meaning that the formulas are true in all interpretations and for all admissible values of their free variables. For example, for a formula containing only one $ 2 $- place predicate symbol $ \rho $ and variables of one sort (that is, variables which are interpreted in the same domain of variation), any pair $ ( M , R ) $, where $ M $ is an arbitrary non-empty set and $ R \subseteq M \times M $ is an arbitrary binary relation on $ M $, is an interpretation. Arbitrary elements of $ M $ are admissible values for the free variables. Truth of a formula $ \phi ( x _ {1} \dots x _ {n} ) $ at values $ a _ {1} \dots a _ {n} $( $ n \geq 0 $) of the variables $ x _ {1} \dots x _ {n} $, respectively, is defined by induction on the structure of the formula, as follows. (Here the free variables run through the set $ M $ and the predicate symbol $ \rho $ denotes the relation $ R $.)

Suppose that a formula $ \phi $ is given, as well as a finite sequence $ \overline{x}\; = ( x _ {1} \dots x _ {n} ) $ of variables containing all the free variables of $ \phi $; let $ | \phi ; \overline{x}\; | $ denote the set of all finite sequences $ ( a _ {1} \dots a _ {n} ) $ of elements of $ M $ at which $ \phi $ is true in $ ( M , R ) $. A set of the form $ | \phi ; \overline{x}\; | $ can be constructed inductively as follows (here it is assumed that the logical symbols in $ \phi $ are $ \wedge $, $ \neg $, $ \exists $):

$$ | \phi ; \overline{x}\; | = \ \{ {( a _ {1} \dots a _ {n} ) } : { ( a _ {i} , a _ {j} ) \in R } \} $$

if $ \phi $ has the form $ \rho ( x _ {i} , x _ {j} ) $;

$$ | \phi _ {1} \wedge \phi _ {2} ; \overline{x}\; | = \ | \phi _ {1} ; \overline{x}\; | \cap \ | \phi _ {2} ; \overline{x}\; | ; $$

$$ | \neg \phi ; \overline{x}\; | = M ^ {n} \setminus | \phi ; \overline{x}\; | ; $$

$$ | \exists y \phi ; \overline{x}\; | = \mathop{\rm pr} _ {n+} 1 | \phi ; \overline{x}\; y | , $$

where $ \cap $, $ \setminus $, $ \mathop{\rm pr} _ {n+} 1 $ denote, respectively, intersection, difference and projection along the $ ( n+ 1 ) $- st coordinate (that is, the image with respect to the mapping $ ( a _ {1} \dots a _ {n} , a _ {n+} 1 ) \mapsto ( a _ {1} \dots a _ {n} ) $) of sets.

Identical truth for a formula $ \phi $ with free variables $ x _ {1} \dots x _ {n} $ then means that for any interpretation $ ( M , R ) $, every sequence $ ( a _ {1} \dots a _ {n} ) $ of elements of $ M $ belongs to the set $ | \phi ; x _ {1} \dots x _ {n} | $. For $ n = 0 $ the set $ | \phi ; \overline{x}\; | $ is either empty or a singleton. For example, the formula

$$ \exists y \forall x \rho ( x , y ) \supset \ \forall x \exists y \rho ( x , y ) $$

is an identical truth. The converse implication is not an identically-true formula.

In the case where an interpretation is fixed, a formula is sometimes called identically true if it is true in the given interpretation for any values of its free variables.

References

[1] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[2] J.R. Shoenfield, "Mathematical logic" , Addison-Wesley (1967)
How to Cite This Entry:
Identical truth. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Identical_truth&oldid=16212
This article was adapted from an original article by V.N. Grishin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article