Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

2
votes
0answers
111 views

Lectures of many valued logic

I am looking for a good introduction to this topic... something with lots of examples and models would be nice. I am specially interested by the case where the truth values are open sets in a ...
2
votes
0answers
81 views

Making a Family of Problems into a Category and defining the Morphisms

This question relates to my previous question found here: Defining Category of Problems Let $\left\{\Pi_i \right\}_{i \in I}$ be a family of problems. Let the solution $u_i$ of $\Pi_i$ lie in some ...
2
votes
0answers
90 views

Introductory text about different stratification methods in higher-order logic and set theory

Could someone recommend me a good overview text about stratification of predicates, comprehension axioms, and other methods of avoiding the paradoxes in untyped or only loosely/relatively typed ...
2
votes
0answers
129 views

Can you express a logic system like S5 using only a Gödel number?

Since logic systems are just statements and/or axioms, can we formulate a logic system gödel numbering the system itself so that the system becomes nothing but a gödel number? For instance the modal ...
2
votes
0answers
127 views

Cut-elimination (transfinite induction base step)

I am having problems with the base step in a proof by transfinite induction. Consider a certain language $Z_{\infty}$, a language similar to PA but with an $\omega$-rule and a cut rule among its ...
2
votes
0answers
235 views

Same same but different: Coextensive relations in model and set theory

The definition of a structure in model theory can be summed up like this (for simplicity's sake without individual constants and functions): Def. 1 A structure is a triple of sets $\langle A, ...
1
vote
0answers
35 views
+250

Injury-free proof of Cof being $\Sigma^0_3$-complete

How can I prove, without using priority argument, that Cof, the set of indices of cofinite c.e. sets, is $\Sigma^0_3$-complete? I know an injury-free proof of Rec being $\Sigma^0_3$-complete, where ...
1
vote
0answers
62 views

Why is $\mathsf{Type} : \mathsf{Type}$ a contradiction?

In reading this cstheory.se question and this stackoverflow question, they mention that $\mathsf{Type}: \mathsf{Type}$ is inconsistent. I also understand that Coq has an infinite hierarchy of Types. ...
1
vote
0answers
30 views

Does Temporal Logic have undecidable propositions?

In order to avoid being too broad or ill defined let me preface by stating that by a proposition in temporal logic I mean a proposition which uses modal operators (until,next,...). In atemporal logic ...
1
vote
0answers
33 views

Prove Ordering of Mixed Quantifiers

I'm trying to familiarize myself with some of the formal logic behind mathematical proofs, and I'm having trouble proving some things explicitly even though I have no trouble with them intuitively. ...
1
vote
0answers
13 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
1
vote
0answers
19 views

Logical form of the statements

I have two statements taken from the book: How to prove it. S1 : We’ll have either a reading assignment or homework problems,but we won’t have both homework problems and a test. S2: You won’t go ...
1
vote
0answers
31 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
1
vote
0answers
81 views

Looking for this theorem by Devlin and Shelah

This is a theorem of Devlin and Shelah which I am looking for more details and also proof: $2^{\aleph_0}=2^{\aleph_1}$ is equivalent to the following statement: There is an $F:H(\aleph_1) ...
1
vote
0answers
26 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
1
vote
0answers
36 views

How to formally express a negative statement (in the wording or formulation of a theorem, for instance)

This is a doubt about English mathematical formal language. I would like to know the best way to express a negative hypothesis, in the formulation or statement of a theorem, proposition, etc., using ...
1
vote
0answers
51 views

Proofs that relied on paradoxical sentences

Graham Priest's Logic of Paradox is a modification of classical logic where the principle of explosion does not hold, so that there are inconsistent theories which are not automatically trivial. ...
1
vote
0answers
59 views

Recommendations for a thorough logic textbook

I'm looking for a (possibly introductory) textbook on logic that covers the motivation behind conventions in logic, like the definition of the implication. Prof. J. Lau has an excellent webpage, ...
1
vote
0answers
34 views

trace calculation of an operator valued matrix

just delete it ${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$${}$
1
vote
0answers
30 views

Proving strong completeness of propositional logic by assuming weak completeness via algebraic methods.

In logic via algebra (page $93$), Halmos tries to prove strong completeness ( if $S\models q$ then $S\vdash q$) assuming weak completeness ( if $q$ is a valid in the Boolean logic $(A,F)$ then $q\in ...
1
vote
0answers
45 views

What is the connection between game theory and (modal) logic?

I'm interested in dynamic epistemic logic lately (reasoning about information and change in multi-agent systems). I also like game theory. I'm looking for some good resources about the connection ...
1
vote
0answers
18 views

Prove that class of models isomorphic to some infinite model $M$ is not countably axiomatizable

In a related question the author posted similar problem for finite models, and stated that in case of an infinite model the class of models isomorphic to the given one is not with FO-axiomatizable, ...
1
vote
0answers
34 views

Construct theory with a condition

I would need some help here. I'm preparing for finals from mathematical logic and as I am browsing through some exercises, I often found these types: Let's say we have 2 propositions $\phi$ and ...
1
vote
0answers
45 views

Term models in group theory

Let $S_{Gr}$ be the language of groups, $Z$ an arbitrary set that does not contain elements of $\mathcal A_{S_{Gr}}$ (the corresponding alphabet). For each $z \in Z$ take a new constant symbol $c_z$ ...
1
vote
0answers
36 views

show that the theory of fields cannot be axiomatized by horn sentences

show that the theory of fields cannot be axiomatized by horn sentences im not sure how to show it, nearly everything is quantified so easily no free variables, maybe something to do with $\neg0 ...
1
vote
0answers
50 views

MTL algebra 'prelinearity' condition etymology

According to wikipedia the prelinearity condition of a monoidal t-norm logic is expressed as $(x\implies y) \vee (y\implies x) = 1$. As far as I know, the 'pre' prefixed version of a rule or ...
1
vote
0answers
55 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
1
vote
0answers
76 views

Why does a definition of multiplication in Presburger Arithmetic result in an undecidable theory?

Presburger Arithmetic is a decidable theory but if multiplication is added to it would that theory remain decidable? UPDATE: I began to write out the axioms that would distinguish Presburger ...
1
vote
0answers
35 views

Proof verification for structure construction

This question is from Enderton's mathematical logic. Question 8 sec 2.5 pg 146. It says assume the language that has $\forall$ and P, where P is a two place predicate symbol. Let A be the structure ...
1
vote
0answers
24 views

Lebesgue Measurable Sets & Axiom of Determinacy

While reading some logic theory I bumped against the theorem which states that every set of reals is Lebesgue measurable, assuming the axiom of determinacy. To prove this theorem it apparently ...
1
vote
0answers
39 views

Truth value of a mathematical statement about circles?

Let $A$ be the set of circles in the plane with center $(0,0)$ and let $B$ be the set of circles in the plane with center $(-2,3)$. Furthermore, let $P(C_1,C_2)\colon C_1$ and $C_2$ have exactly one ...
1
vote
0answers
55 views

First order logic and Second order logic: a question regarding domains

(1) I understood that in the language of first order logic quantification cannot be over sets (there are no predicate variables that can be bound by quantifiers), whereas the language of second-order ...
1
vote
0answers
75 views

First order logic and first order set theory

(1) I understood that in the language of first order logic quantification cannot be over sets (there are no predicate variables that can be bound by quantifiers), whereas the language of second-order ...
1
vote
0answers
109 views

How can nontrivial elementary embeddings of the universe to some inner model be surjective?

Consider $\kappa$ to the least measurable cardinal, or equivalently $\kappa$ is the critical point for an elementary embedding $j:V \rightarrow M$ from the universe $V$ to an inner model $M$ (critical ...
1
vote
0answers
41 views

Show that $\Phi$ is negation complete.

Im working on a FOL exercise but i'm a little stuck here. Let $S$ be a symbol set and $\mathcal{J} = (\mathcal{U}, \beta)$ an $S$-interpretation. Further let $\Phi:=\{\varphi\in ...
1
vote
0answers
47 views

Proof that $\cal K$ is an elementary class iff $\cal K$ is closed under elementary substructures.

Assume $\cal K$ is a pseudo elementary class. I need to prove that $\cal K$ is an elementary class iff $\cal K$ is closed under elementary substructures. Pseudo elementary class is a class of reducts ...
1
vote
0answers
71 views

Is this inference valid?

Is the following inference valid provided that the variable $z$ does not occur free in $\Gamma$ (Note: No restriction regarding whether or not $z$ occurs free in $\phi$ is assumed) ? $${ \Gamma \vdash ...
1
vote
0answers
58 views

How to convert conjunction inside disjunction into CNF?

How do I convert something like $$\bigvee_{a\in A} \bigwedge_{i\in L} (x_{i,a} \wedge y_{i,a})$$ into CNF? The $x_{i,a}$ and $y_{i,a}$ are variables.
1
vote
0answers
41 views

What does the statement “x is a diagram of classical logics” mean?

From the Wikipedia entry on quantum logic A more modern approach to the structure of quantum logic is to assume that it is a diagram – in the sense of category theory – of classical logics (see ...
1
vote
0answers
52 views

prove Lindenbaum’s lemma for a countable language

Been reading through some model theory and got to a section on constructing models from syntax and i have been presented with the following problem, sorry for the lack of solution i just have no idea ...
1
vote
0answers
147 views

Validity of a few FOL formulas

How we can obtain that the following examples (in my book wrote) is logically valid, I) $ \exists y \forall x p(x,y) \to \forall x \exists y p(x,y) $ II) $ \exists x \exists y p(x,y) \to \neg ...
1
vote
0answers
31 views

Statements in prenex normal form.

Put these statements in prenex normal form. a) $\exists x \ P(x) \vee \exists x \ Q(x) \vee A$, $\textit{where A is a proposition not involving any quantifiers.}$ b) $\neg (\forall x \ P(x) \vee ...
1
vote
0answers
27 views

Is the full strength of first-order logic needed for dealing with equational theories?

More specifically, if we have an equational theory $T$ (a set of equations understood as being implicitly universally quantified), are the (equational) consequences of $T$ that can be proved with ...
1
vote
0answers
59 views

Open interpretation of logical theories

This may be more appropriate for MO but I thought I'd ask here first as it's just a question about logic (not my strong point at all but not research-level in itself). I'm going through Razborov's ...
1
vote
0answers
204 views

How to solve a “logic grid/table puzzle” as well as a “logic game” from the LSAT

Dear fellow members of the prestigious brotherhood of philosophical and mathematical logicians, I am familiar with symbolic logic on a level such as is covered in Patrick Hurley's textbook A Concise ...
1
vote
0answers
60 views

Disproving $\neg Q$ proves Q in all cases?

Does disproving the negation of a claim prove the claim in all scenarios and sufficient enough to say Q is true? Even if Q is an implication, or an equality, or etc? What about vacuous truths? Can ...
1
vote
0answers
39 views

preservation in unions of chains

Let $K=\{A_i:i\in\omega\}$ be a countable chain of infinite (not necessarily countable) N−substructures, where N is a binary relation and let A be the limit (union) of K. Let Ax be a $\Pi_2$ ...
1
vote
0answers
81 views

Can someone verify my work for finding the following closures?

This is the problem I am currently working on Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the a.reflexive closure of ...
1
vote
0answers
65 views

A universally valid second-order sentence only if CH holds.

I'm looking for a second-order sentence that is universally valid only if CH holds. I'm thinking a surjection between all not enumerable sets onto $\mathbb{R}$ but I don't know how to write it. Thank ...
1
vote
0answers
25 views

Closed term conditions in PA

The situation I have to transfer statements from the "recursive world" into the "$\color{red}{\text{syntactical world}}$", in the context of binumerability of primitive recursive predicates into the ...