# Propositional Extension

## 31.01.2021

### Contents/Index

1. Introduction
@2. Propositional Extension
3. Syntax
4. Semantics
5. Natural Deduction
6. Equivalences

We want to extend our reasoning system of propositional logic. In here we can reason about declarative statements like "I have a cat". However we do not have any way to reason about sets of things, maybe we want to talk about some of or all of. Instead of developing a new system for these quantitative statements, we just extend what we have developed from proposition logic with predicates on sets. A predicate is that of assigning an attribute to for example a person. I want to reason about a "red haired person", that is reason about a person who is red haired. I can express this as $x$ is a person, and $x$ is red haired. Say we have that $P(x)$ is a predicate which is true if $x$ is a person. Say we have that $R$ is a predicate that is true if $x$ is red haired. So now I can formalize the above as $$P(x) \land R(x)$$ We still use the connectives from propositional logic, however we just add these predicates. Furthermore we add variables, like $x$, we can reason about. Say that $x$ is taken from the domain of mammals. We can add a quantifier to our system in order to tell if we are talking about all of the entities in our domain. We denote this quantifier $\forall$. Now we can state something like $$\forall x . P(x) \land R(x)$$ which is not true. That is it is not true that all mammals are red haired persons. We can add one more quantifier. We want to reason about the existence of some specific element in our domain. We denote this quantifier $\exists$. So now we can state something like $$\exists x . P(x) \land R(x)$$ which is true, we have at least one person somewhere who is red haired. Note the "at least", if we have some predicate, $P$, that is true for all $x$, then there also exists a $x$ for which $P$ is true. Note also that existence requires the domain to be non empty. If there exists a $x$ for which $P$ is true, then we have at least this $x$ in the domain. However if for all $x$ $P$ is true, then $P$ is true given an empty domain.

Predicates in this language can have any number of arguments. However in the grammar on next page we restrict the number of arguments to be greater that 0. A predicate of 0 arity is simply a proposition atom. A predicate with one argument is called unary - like $P$ and $R$ above. A predicate with two arguments is called binary. For example we could have $Y(x,y)$ interpreted as $x$ is younger than $y$. So now we can form expressions like $$\forall x . P(x) \lor P(x,x)$$ which states that every mammal is either a person or younger than itself. Which is not the case. We can add quantifiers, like $$\forall x \exists y . Y(x,y)$$ which states that for every mammal there exists some other mammal that is older. This is not strictly true since we have some mammal that are the oldest. However do we include dead mammals? Even if so, are there some oldest mammal of them all? Let $O(x)$ denote $x$ is oldest of all. And we have $$\forall x \exists y . O(x) \lor Y(x,y)$$ When chaining the two different quantifiers, the order is quite important. Chaining as $$\forall x \exists y$$ reads as for every $x$ there exists some $y$. For example let the domain be real numbers. Let $P(x,y) = x \lt y$. Now the following predicate is true $$\forall x \exists y . P(x,y)$$ That is no matter how big of a real number $x$ you come up with, I can always find some real number $y$ that is bigger. However of we reverse the order, that is $$\exists y \forall x . P(x,y)$$ we have a predicate that is not true. This expression states that I can come up with one single $y$ that is bigger than any $x$ you can come up with. I try with $10^{99999999999}!$, where $!$ is faculty, and you counter my proposal with $10^{99999999999}! + 1$.

We can use concrete values, that is constants, instead of variables. For example $andy$ is a dog. Now $$\exists x . Y(x,andy)$$ states that there exists some mammal that is younger than $andy$. We can extend these constants by letting them take arguments. Now they are functions. For example let $m(x)$ be the function that returns the mother of $x$. Now we can express something like $$\forall x . P(x) \rightarrow Y(x,m(x))$$ which states that if some mammal $x$ is a person, then this mammal is younger than its mother. Functions are so in a mathematical sense, hence they need be well defined. So if $b(x)$ returns the brother of $x$, then we have problems. Since one can have more than one brother. A solution is to restrict the function. Maybe let it return the oldest brother. If this not raises further problems.