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
52 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
62 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
95 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
33 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
41 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
55 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
38 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
39 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
50 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
143 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
26 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
72 views

Proving $\vdash (p\to q)\lor (q\to r)$ using natural deduction

I'm trying to prove the following: $\vdash (p\to q)\lor(q\to r)$ using only intuitionistically valid rules. I've tried a few different ways, and I think my problem is that I'm not sure what ...
1
vote
0answers
90 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
47 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
63 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
45 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
42 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
32 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
39 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
52 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
56 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
60 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
27 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
66 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
30 views

How do I notate this statement about a state of affairs (similar to a possible world)?

I'd like to notate this statement formally: If any given agent desires that a certain state of affairs obtains, then there is no state of affairs in which she enjoys greater security than that one. ...
1
vote
0answers
21 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
51 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
68 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
75 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
40 views

Confusion between categoricity and indiscernability

From wikipedia: Indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula. Usually only first-order formulas are considered. Is this because ...
1
vote
0answers
57 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
45 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
42 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
70 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 ...
1
vote
0answers
54 views

Logic and Generalizations

As as logic student, I often encounter the following: a situation where a formal system can't see a generalization is true, but I can. The usual case is that of $\omega$-incompleteness. It is often ...
1
vote
0answers
32 views

Contrapositive verifications

The contrapositive of: The product of an irrational number and a non-zero rational number is irrational. is: If the product of two numbers is rational, then it cannot be the case that one ...
1
vote
0answers
34 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
1
vote
0answers
14 views

Expressing an equal sized partition in second order logic

I would like to characterize the class of (finite) structures that can be partitioned into two disjoint sets $X,Y$ having the same cardinality, using second order logic (with usual logical connectives ...
1
vote
0answers
30 views

Algorithm to force decidability of statements using an intuitionistic series of new axioms

Consider pairs $(\Phi,n)$ where $\Phi$ is a finite set of statements in Peano arithmetic and $n$ is an integer. Say that $p'=(\Phi',n')$ is an elementary intuitionistic extension of $p=(\Phi,n)$ iff ...
1
vote
0answers
44 views

question in math logic: find the d.n.f. and c.n.f.

The question is as follows: Find the disjunctive and conjunctive normal forms of the following: $$ (A \to (B \to C)) \to ((A \to \neg C) \to (A \to \neg B)) $$ My solution is as follows, but I ...
1
vote
0answers
39 views

Relations between equations in a theory, and the number of independent equations

I have a question on equational reasoning in theories, which is made quite often in mathmeatics, and I am trying to make this more formal. So for my attempt to make this more rigouros, I choosed ...