## What is to define truth in Mathematical Logic?

Tarski’s Undefinability Theorem says that arithmetical truth cannot be defined in arithmetic. What is the meaning of “definition”? Is it formal? Answer Yes, it is. According to : TARSKI UNDEFINABILITY THEOREM (1933) : The set #ThN [i.e. the set of Gödel-numbers of sentences true in N] is not definable in N. Here the concept of … Read more

## What is the negation of the statement “Every odd nmber is divisible by 2”.

Intuitively,I think it is “no odd number is divisible by 2” or it could be “every odd number is not divisible by 2”. Is this a trivial question or is there more to it? What is the correct answer? BTW it is from a text i am reading. Answer Suppose that you wanted to prove … Read more

## Complete $n$-types for the theories of $( \mathbb Z , s )$ and $( \mathbb Z , s , < )$

This is exercise 4.5.2 from Marker’s Model Theory: An Introduction (p.163), quoted verbatim: Let $T$ be the theory of $(\mathbb Z,s)$ where $s(x) = x+1$. Determine the types in $S_n(T)$ for each $n$. Which types are isolated? Do the same for $(\mathbb Z, <, s)$. Here $S_n (T)$ denotes the set of all complete $n$-types … Read more

## What sequent does this derivation prove?

Trying to learn sequent calculus and so I am trying to work thru some examples to get a better grip/understanding but the following question is not answered at the back of the book. I wrote my guess in the blue writing in the attached picture, however I am unsure of my answer because phi appears … Read more

## How to understand this informal description of the levels of the arithmetical hierarchy?

In my class notes I do not understand why the following statement is true, nor what it means: Informally, the lowest level in the Arithmetical Hierarchy in which n-ary relation R is definable determines how often we have to go through the natural numbers in their totality in order that we are guaranteed to have … Read more

## Negating an equals sign?

If, when negating a statement, and part of that statement is 3y=x, can you just say 3y does not =x by putting a line through the = sign or is there another way to negate the statement? The statement was “For all x there exists a y, such that [(y>x)∧(x=3y)].” Which I turned into “For … Read more

## Prove ∅⊢(α→(¬α→¬β))\emptyset \vdash(\alpha\rightarrow (\neg\alpha\rightarrow \neg \beta)).

Prove ∅⊢(α→(¬α→¬β)). Using the axioms: (ϕ→(ψ→ϕ)) ((ϕ→(ψ→γ))→((ϕ→ψ)→(ϕ→γ))) ((¬ϕ→¬ψ)→((¬ϕ→ψ)→ϕ))) And the inference rule modus ponens. A proof in this manner means a sequence of lines where each line is an axiom, or a formula from your “base” set ({α,¬α} below), or an inference (using modus ponens), with the last line being the formula being proved. I … Read more

## Is there a way to decide whether a differential equation is solvable or not?

Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson had negatively settled Hilbert 10th problem, I wonder if there is an analog result to the differential equations ? Answer There is newer stuff, but you can find a partial answer in an old short paper Some Recursively Unsolvable Problems in Analysis (Adler, AMS Proceedings, 1969). … Read more

## How to proofs work in three-valued Kleene logic?

In three-valued logics such as Kleene logic, there is a third truth value U, which represents “undefined”, or “who knows?”. It behaves like “either true or false”, and truth tables for not, and and or can be filled out appropriately: What does a proof look like in this logic? When does B (semantically) follow from … Read more

## BAN logic notation: what does horizontal line mean?

I’m learning BAN logic and trying to understand the notation. The bellow picture is an example form Security Engineering by Ross J Anderson. My question is what does the horizontal line mean? I’m guessing it can be read like and if/then statement where the top is the if condition and bottom is the then part? … Read more