Formal logic language

WARNING: this is a bad page - it is little more than "my notes", it could be wrong and should not be relied upon.

Introduction

Formal logic plays an important role, especially so in set theory, but overall an important role. It is important to have a concrete understanding of this.

Definitions

Functions

These take some arguments (the number of which is called "Arity") and return something.

Examples

• [math]\text{Plus}(\text{Natural }a,\text{Natural }b)\rightarrow\text{Natural}[/math]

Predicate

Predicates are basically relations - they are either true or false, they are similar to functions in the sense they are either true or false, but they are not functions as such (arguably they are functions, [math]P:X\times Y\rightarrow\{\text{true},\text{false}\}[/math])

Examples

• [math]\text{Mortal}(\text{Person }x)[/math]

Quantifiers

We cannot express things like "all men have a mother" in this language, we require quantifiers:

• [math]\forall[/math] - forall
• [math]\exists[/math] - exists
• [math]\exists_1[/math] - exists only one thing, a unique thing

Examples

• [math]\forall x:\text{Man}\exists_1 y:\text{Woman}\ \text{MotherOf}(x,y)[/math]

Example 1

[math]\forall x\forall y\forall z((P(x,y)\wedge P(y,z))\rightarrow P(x,z))[/math]	[math]\forall x\forall y\forall z(P(x,y)\wedge P(y,z)\rightarrow P(x,z))[/math]
for all [ilmath]x[/ilmath] for all [ilmath]y[/ilmath] for all [ilmath]z[/ilmath] if we have both [ilmath]P(x,y)[/ilmath] [ilmath]P(y,z)[/ilmath] then [ilmath]P(x,z)[/ilmath]	for all [ilmath]x[/ilmath] for all [ilmath]y[/ilmath] for all [ilmath]z[/ilmath] we have both [ilmath]P(x,y)[/ilmath] if we have [ilmath]P(y,z)[/ilmath] then [ilmath]P(x,z)[/ilmath]
Whenever we have ([ilmath]P(x,y)[/ilmath] and [ilmath]P(y,z)[/ilmath]) we also have [ilmath]P(x,z)[/ilmath]	[ilmath]P(x,y)[/ilmath] is true and whenever [ilmath]P(y,z)[/ilmath] is true then [ilmath]P(x,z)[/ilmath] is true
It is always true that if ([ilmath]P(x,y)[/ilmath] and [ilmath]P(y,z)[/ilmath]) then [ilmath]P(x,z)[/ilmath]	It is always true that [ilmath]P(x,y))[/ilmath] and (if [ilmath]P(y,z)[/ilmath] then [ilmath]P(x,z)[/ilmath])
[ilmath]P(x,y)[/ilmath] [ilmath]P(y,z)[/ilmath] [ilmath]P(x,z)[/ilmath] Uncertain True Uncertain True Uncertain True True True	[ilmath]P(x,y)[/ilmath] [ilmath]P(y,z)[/ilmath] [ilmath]P(x,z)[/ilmath] True (definition) Uncertain True (definition) True True