# TU Wien:Logic and Computability VU (Ciabattoni)/Exam 2022-09-13

Zur Navigation springen Zur Suche springen

## Exam 2022-09-13

Formalize the following sentence:

"If every politician is a showman and no showman is sincere, then there exists a politician that is insincere."

If the sentence is true then prove it, otherwise state a counterexample.

Consider the following formula: ${\displaystyle \exists x_{1}\exists x_{2}.{\big (}B(x_{1},x_{2})\to \forall y_{1}\forall y_{2}.(B(f(y_{1}),y_{2})){\big )}}$

If the formula is valid present a proof using sequent calculus, otherwise state a counterexample.

Consider the following two sets

${\displaystyle I_{1}=\{j\mid \Phi _{j}(j)\downarrow {\text{ within }}k{\text{ steps }}\}}$

and

${\displaystyle I_{2}=\{j\mid \Phi _{j}(j)\downarrow {\text{ with }}j\in k\}}$

are the two sets recursive or r.e.? Can we use Rice Theorem? Motivate your answer and consider the two cases where

(a) ${\displaystyle k=1,\dots ,4}$

(b) ${\displaystyle k={\mathcal {N}}}$

Let G be the modal formula ${\displaystyle \Diamond \Diamond \neg A\to \neg \Box A}$. Prove or refute:
(1) G is valid in every transitive frame. (2) If ${\displaystyle F\models G}$ for a frame F, then F is transitive.
Use the proof of the ADRF theorem to show that the function ${\displaystyle f(g(x)\cdot g(y),x+y)+2}$ is arithmetically definable, if f and g are arithmetically definable. Hint: Specify the witnessing formula, following slide 23 of the last set of slides (on incompleteness).