Decidability of a predicate.

Question

I have the following problem:

Let the following predicates be: $P1, P2, Q1, Q1 : R \to \{0,1\} $ .

It is given that $P1 \lor P2$ and $Q1 \lor Q2$ are semidecidable and $P2 = \lnot Q2$

What can it be said about $P1 \lor Q1$?

I have searched all over the internet and I simply cannot understand the concept of decidability of a predicate, let alone a logic operation with predicates.

Answer 1

See Herbert Enderton, Computability Theory An Introduction to Recursion Theory (2011) [pag.4] :

The concept of decidability can [...] be described in terms of functions: For a subset $S$ of $\mathbb{N}$ , we can say that $S$ is decidable iff its characteristic function

$C^S(x)$ = Yes if $x \in S$

$C^S(x)$ = No if $x \lnot \in S$

is effectively calculable. Here “Yes” and “No” are some fixed members of $\mathbb{N}$, such as $1$ and $0$.

So, a predicate $P$ is decidable when you have an effective way (an algorithm) to check, for each $x$ in the domain of $P$, if $x$ is in $P$ (i.e. if $P(x)$ is true).

The class of effectively calculable functions (and predicates) is closed under standard logical operators (like $\land$ , $\lnot$, $\lor$) ; so, the conjunction of two decidable predicates $P$ and $Q$ (i.e. $P \land Q$) is again decidable.

From algorithms checking for membership into sets $P$ and $Q$ you can find an algorithm checking for membership into the intersection of $P$ and $Q$ (i.e.$P \cap Q$).

Take as an example the set of natural numbers $\mathbb{N}$ and let $P$ the predicate "_ is even", so that $P(x)$ is true for $x \in \mathbb{N}$ iff "$x$ is even".

Let $Q$ the predicate "_ is multiple of $5$"; now $P \land Q$ is the predicate "_ is even and multiple of $5$".

By usual arithmetical methods, you can check, for each number $x \in \mathbb{N}$, if $(P \land Q)(x)$ is true (e.g.it is true for $10$, $20$ ..., i.e.by all numbers divisible by $2$ and $5$).

Answer 2

About semi-decidability, we have that (again form Enderton's book, pag.5) :

It is very natural to extend these concepts to the situation where we have half of decidability: Say that S is semidecidable if its “semicharacteristic function”

$c^S(x)$ = Yes if $x \in S$

$c^S(x)$ = undefined if $x \lnot \in S$

is an effectively calculable partial function. Thus, a set S of numbers is semidecidable if there is an effective procedure for recognizing members of S. We can think of S as the set that the procedure accepts. And the effective procedure, while it may not be a decision procedure, is at least an acceptance procedure. Any decidable set is also semidecidable. If we have an effective procedure that calculates the characteristic function $C^S$, then we can convert it to an effective procedure that calculates the semicharacteristic function $c^S$. We simply replace each “output No” command by some endless loop.

The fundamental theorem regarding these two concepts is (pag.9) :

Kleene’s theorem: A set (or a relation) is decidable if and only if both it and its complement are semidecidable.