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)

1
vote
0answers
43 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
40 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
50 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
68 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
32 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
20 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
37 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
54 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
69 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
103 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
34 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
44 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
57 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
51 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
40 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
51 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
144 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
29 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
58 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
143 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
57 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
38 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
57 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
23 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 ...
1
vote
0answers
50 views

Is there a difference between induction in Peano Arithmetic and Presburger Arithmetic

Following this question I still do not get clearly the difference between defining exponentiation in PA but impossiblity of recursively define multiplication in Presburger Arithmetics I was thinking ...
1
vote
0answers
47 views

Is my answer for the composite relation correct and not the textbook's?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 5 pg 593] Here is how my textbook's way of representing a relation with a matrix And the definition of a ...
1
vote
0answers
33 views

Löwenheim-Skolem for Lindström's Theorems

In Mathematical Logic by Ebbinghaus/Flum/Thomas the Löwenheim-Skolem Theorem worded like this: Every satisfiable and at most countable set of formulas is satisfiable over a domain which is at most ...
1
vote
0answers
40 views

Need clarification on recursive functions.

Given any function $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ and a recursive $h:\mathbb{N}_0 \rightarrow \mathbb{N}_0$ , I know that to prove $h\circ f$ is recursive I only need to prove that $f$ is ...
1
vote
0answers
56 views

Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
1
vote
0answers
70 views

Determine whether this statement is true or false

I have a statement A: "$\forall x, \exists y$ such that $\forall z, x + y = z$." I can find a $y$ for all $x$ and $z$ such that $y = z -x$. But this $y$ is not fixed for all $x$ and $z$. Hence A ...
1
vote
0answers
35 views

Learning of causal structure

I was wondering if someone could help me understand a few things on this wikipeida page on causality http://en.wikipedia.org/wiki/Causality#Structure_learning related to the following possible ...
1
vote
0answers
71 views

Show if theory T is ∀∃-axiomatizable, then T has an existentially closed model.

Setting Definition $\mathcal{M} \models T$ is existentially closed if whenever $\mathcal{N} \models T$, $\mathcal{N} \supseteq \mathcal{M}$, and $\mathcal{N}\models \exists \bar{v} ...
1
vote
0answers
28 views

Examples and exercises about the interpretation method in logic

I am a beginner student of logic and I am experiencing some trouble at finding interpretations that help me prove dependence/independence of axioms, consistency, as well as the independence of ...
1
vote
0answers
72 views

Definitions of isomorphism and elementary substructures

Let us define -all the definitions are from V. Manca, Logica matematica, 2001, 'mathematical logic'- a $\Sigma$-morphism as a function $f:D_1\to D_2$ between models $\mathscr{M}_1$ and ...
1
vote
0answers
22 views

House allocation with existing tenants

In a house allocation with existing tenants model using the TTC mechanism, consider the incentive of an agent to misreport his/her preferences. Can it ever be that misreporting the true preferences by ...
1
vote
0answers
52 views

A computable set of sentences neither probable nor disprovable from $PA$

I need to prove that, given a computable binary tree $T$ whose paths are exactly the complete extensions of $PA$ (via some Gödel coding), there is a computable $X\subseteq\mathbb{N}$ such that for all ...
1
vote
0answers
74 views

Henkin Construction: Goedel completeness Theorem

I am trying to understand better the Henkin construction, which consist first in an extension of the signature and then of the theory. Here are my question about this topic: we extend the ...
1
vote
0answers
34 views

Does the class of all periodic subsets of $\mathbb{Z}$ of peroid greater than $k$ form a field of sets?

We say that a subset $X\subseteq \mathbb{Z}$ is a periodic subset of $\mathbb{Z}$ of period $k$ if the set obtained from $X$ by adding $k$ to each element of $X$ is $X$ itself. Does the class of all ...
1
vote
0answers
76 views

what does “a wff f(x, y)” mean exactly? (context: transfinite recursion)

I'm currently working through Herbert B. Enderton's book "Elements of set theory". I have a question concerning notation in logic, of which I know the basics but in which I'm not that firmly grounded. ...
1
vote
0answers
49 views

Would a “Prenex Sum of Products” be canonical?

I know that prenex normal form (PNF) is not canonical, and there is an example in Wikipedia showing two equivalent formulae in PNF that differ in their prefixes, but have equal matrices: $\forall x ...
1
vote
0answers
59 views

Importance of Gödel Numbering System

How important is Gödel numbering to his incompleteness proofs, set theory, logic theory in general and proofs employing ZFC? Can we use some other numbering or 'meta' programming? How about if one ...
1
vote
0answers
46 views

Logic in Science

I am in the process of writing an essay about how disciplines interlink. In one of my paragraphs I am talking about logic, where is say how logic is a subset of mathemtics (logicism) and therefore any ...
1
vote
0answers
43 views

Proof of Correctness: Recursion inside loop

I am trying to prove the correctness of the algorithm in the research paper. It is at page 17 in the pdf. ...
1
vote
0answers
30 views

$\exists G \in L'. G \iff \mathtt{True}(gn(\neg G))$ in the language $L'$ with Godel numbering $gn$ and $\mathtt{True}$ predicate?

I am reading a paper Definability of Truth in Probabilistic Logic . Given a language $L$ with the Godel numbering $gn:L \to \mathbb{N}$ the authors extend it with a predicate $\mathtt{True}$ to a ...
1
vote
0answers
35 views

Some doubts regarding decidable sets

I've been working at one of the problems, related to the decidability. Let's denote $ f: \mathbb{N} \rightarrow \mathbb{N}$ as a computable increasing function, $A \subset \mathbb{N}$ is a ...
1
vote
0answers
22 views

Richardson's Theorem - Simple example

Does anyone know an actual expression $E$ built according to the conditions of Richardson's Theorem that makes the predicate $E=0$ recursively undecidable?
1
vote
0answers
76 views

Mathematical Logic Puzzles

The following are some puzzles from a Mathematical Logic course. I sat in on the first lecture but unfortunately, it didn't work with my schedule. However, I did take an problem sheet and I'm curious ...