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

Show For any language L two L-structures M and N are elementarily equivalent iff they are elementarily equivalent for every finite sublanguage.

Setting For any language \mathcal L, two \mathcal L-structures \mathcal M and \mathcal N are elementarily equivalent iff they are elementarily equivalent for every finite sublanguage. Attempt (\Rightarrow) Given \mathcal M\equiv \mathcal N, so \mathcal M\models \phi \iff \mathcal N \models \phi for every \mathcal L-sentence \phi. Now suppose there is finite sublanguage of \mathcal … 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