Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

2
votes
0answers
134 views

Can “tit for tat” strategy be defined in monadic second-order logic?

Prisoner's dilema game can be represented as a game tree, which could be infinite game with corresponding infinite game (binary) tree in common case. There is well-known tit for tat strategy, which ...
2
votes
0answers
89 views

Formula Complexity of $\models_n$

I want to show $\models_0$ is $\Sigma_1$, and $\forall n \geq 1, \models_n$ is $\Sigma_n$. So for the base case, $\models_0 \ulcorner \phi \urcorner$ is true iff $\ulcorner \phi \urcorner \in ...
2
votes
0answers
82 views

How to use a very complicated theorem for proving simpler statements without falling into a loop?

There are some too complicated theorems in mathematics which have very complicated proofs in hundreds of pages. There are few mathematicians who are aware of the entire proof of such theorems in full ...
2
votes
0answers
34 views

Are these two approaches to calculating return rate mathematically consistent?

I have coded two C# programs, which use two different approaches to evaluate the outcome of a certain casino-style game (casino-style in the sense that the user pays points to take a turn, and ...
2
votes
0answers
96 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on $...
2
votes
0answers
83 views

On the back and forth conditions for a set of partial isomorphisms

I've recently begun reading Poizat's A Course in Model Theory and already in the first pages I had some doubts. One odd (not necessarily bad) thing is that he defines notions such as isomorphism only ...
2
votes
0answers
125 views

Relation between existential and universal quantificator in category theory

Let $\mathscr C$ be a cartesian (i.e. with finite limits) category with subobject classifier $\Omega$ and generic subobject $\tau:I\to\Omega$ (here $I$ denote the terminal object). Let $f:X\to Y$ and ...
2
votes
0answers
55 views

When is the higher-order theory of a model categorical?

I'm interested in (classical) type theories $L$ with the following property. For $M$ any model of $L$ (in Set), let $T(M)$ be the type theory of $M$, i.e., the strongest extension of $L$ satisfied by $...
2
votes
0answers
53 views

Propositions as sets of witnesses

Under the propositions-as-types paradigms, a proposition is identified with the type of all its proofs. From a more classical perspective (and assuming the full-blown axiom of choice), it sometimes ...
2
votes
0answers
100 views

Path-independent contour integrals and how to define them

If a contour $C$ is parameterized by $z(t): [a, b] \to \mathbb{C}$, then we define $$ \int_C f(z) \, dz= \int_a^b f(z(t)) \, z'(t) \, dt.$$ If the contour integral on the left side is equal to some ...
2
votes
0answers
42 views

Showing non-independence of a statement with respect to an axiomatic system

Is it possible to show that either a statement or its negation is non-independent of say, ZFC, without actually proving or disproving said statements? The reason I ask is because I've read of proofs ...
2
votes
0answers
59 views

Two definitions of functions

In literature on logic and set theory, there seem to be two different definitions of functions, one more general than the other. First of all, a function $f\colon X\to Y$ consists of three element $(X,...
2
votes
0answers
49 views

Meaning of Biinterpretability.

I'm reading this paper: http://www.math.cornell.edu/~shore/papers/pdf/hyp9.pdf and I am struggling with the meaning of Biintereptability, to quote the paper A degree structure $D$ is ...
2
votes
0answers
181 views

How large or small can the gap in Shelah's main gap theorem be, up to consistency?

Shelah's main gap theorem in model theory says: For each first order complete theory $T$ in a countable language if $I(T,\kappa)$ denotes the number of its models of size $\kappa$ then one of ...
2
votes
0answers
26 views

Sub-Graph containing all predecessors

Let $\Gamma$ be a directed graph, and $\Gamma'$ a subgraph. Is there a terminology for the following property? $\Gamma' \subset \Gamma$ is called ------ if, for all $y \in \Gamma'$ and for all $x$ ...
2
votes
0answers
81 views

Does There Exist A Fourth Independent Axiom Here?

I use Polish notation. The implicational calculus of propositions under detachment and uniform substitution has the following axioms as a basis: ...
2
votes
0answers
122 views

Simplify Product of Sums

Similar question to: Boolean Algebra - Product of Sums I was given a truth table and asked to give the sums-of-products and the product-of-sums expressions. I reduced the sums-of-products ...
2
votes
0answers
49 views

Transfert principle of a conservative extension of ZFC

In the following paper, there is a theory called $^*ZFC$ in the language $(^*,\in)$. The *-map is (more or less) defined on the Von Neuman hierarchy $S$ and verifies the following axiom schemata true ...
2
votes
0answers
48 views

Selecting a unique pair satisfying a condition $\varphi$ with an ordering

Given a finite structure $\mathfrak{A}$ with Universe $|A| < \infty$ and signature $\tau$. We say a pair $(a,a') \in A$ satisfies a $\tau$-formular $\varphi$ iff $$ \mathfrak{A} \models \varphi(a,...
2
votes
0answers
60 views

Certain sequents as inference rules

Fix a signature $\sigma.$ Then a coherent formula is a first-order formula built using only $\{\wedge,\vee,\top,\bot,\exists\}.$ See the link for more information. Furthermore, by a "special" ...
2
votes
0answers
165 views

Semantic Proof of Tarski's Undefinability of Arithmetic Truth

A few years ago I took a logic course and I've since lost my notes. I seem to remember a very semantic proof of Tarski's theorem on the undefinability of arithmetic truth, one that didn't use the ...
2
votes
0answers
44 views

Books/papers on model theory in non-monotonic logic

I am working on a project whose object language is in non-monotonic logic. Since the project involves reasoning about the models, I am thinking of translating a non-monotonic problem into a first-...
2
votes
0answers
133 views

Isomorphism of finite models

Let $\mathfrak A$ and $\mathfrak B$ are models of finite signature $\sigma$. Prove that $\mathfrak A$ and $\mathfrak B$ are isomorphic, if $\mathfrak A \equiv \mathfrak B$ and $\mathfrak A$ is finite ...
2
votes
0answers
69 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
0answers
71 views

Help understanding Smullyan’s semantics definition for First-Order Logic

Ref.to Raymond Smullyan, First-Order Logic (1968 – Dover reprint). Some background : [pag.44] - individual variables (to be used bound) and individual parameters (to be used free) [pag.47] - ...
2
votes
0answers
147 views

Questions about semantics for First-Order Logic

The basic clause in the semantic definition of satisfaction for quantifiers in f-o logic cab be stated in two alternative forms (for simplicity I assume a formula $A(x)$ : A) take an assignment ...
2
votes
0answers
80 views

Check that constructed recursive function proves that set is recursive.

Let $\forall\exists$-formula be any formula that looks like $\forall x_1...\forall x_m$$\exists y_1...\exists y_n \phi$, where $x_1...x_m, y_1...y_n$ - variables, $m,n \ge 0$ , $\phi$ - unquantified. ...
2
votes
0answers
81 views

Lowering the power of infinite model

I need to prove that for every infinite model $\mathfrak A$ of signature $\sigma$ exists model $\mathfrak B$ with attributes: $\mathfrak A \equiv \mathfrak B$. $\parallel \mathfrak B \parallel = \...
2
votes
0answers
129 views

cut elimination for infinitary logic

Takeuti (1987, 223) derives a cut-elimination theorem for infinitary logic from the soundness-and-completeness theorems. However, is there a way to adapt the original Gentzen-style proof? The ...
2
votes
0answers
128 views

Cut-off Subtraction in Coq

I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
2
votes
0answers
134 views

An example of a proof in sequent calculus

I'm reading Gaisi Takeuti, Proof Theory (2nd ed - 1987), and I'm trying with some exercises. See pag.13 : Ex.2.5.2) Prove the following in LK : $(A \supset B) \supset \lnot A \lor B$. In order to ...
2
votes
0answers
90 views

How much arithmetic can Predicative Second-Order EFA do?

As discussed in this MathOverflow question, I'm trying to find what the result would be of applying a Feferman-Scutte-like analysis to the predicativism of Edward Nelson and Charles Parsons, who ...
2
votes
0answers
48 views

Prove that there are no theorems in which there are no occurrences of disjunction

Ref : Peter Andrews, An Introduction to Mathematical Logic and Type Theory To Truth Through Proof (1986). Exercise X1210 : Does $\mathscr{P}$ have any theorems in which there are no occurrences ...
2
votes
0answers
176 views

Non-Constructive Proofs

I have just started to read more about constructivism and its critique towards classical logic. As I was reading, I came across a passage about non-constructive results, that mentioned the following ...
2
votes
0answers
178 views

Information content of universal sentence

What is the information content of a sentence S like 'one has a successor'. To me, it looks like if we assume no a priori knowledge, both S and it's negation will have equal probablity 1/2. This is ...
2
votes
0answers
87 views

Countable Ultrahomogeneous Structures

I've been learning about countable ultrahomogeneous structures, where ultrahomogeneous means every isomorphism of finitely generated substructures extends to an automorphism of the whole structure. ...
2
votes
0answers
59 views

Difference between defining a constant and beginning with it in a structure

For example, let's suppose that I have my structure $\langle\mathbb{R},+\rangle$ and that $\exists!x\forall a\in \mathbb{R}(a+x=x+a=a)$ as an axiom. In this case $0:=x$. But what if I consider the ...
2
votes
0answers
92 views

How strong is ramified predicative second-order arithmetic?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
2
votes
0answers
75 views

Tricking the Second Incompleteness Theorem

On Wiki, the Second Incompleteness Theorem reads as For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, if T ...
2
votes
0answers
94 views

Minimal number of variables in a ZFC-undecidable sentence?

Let $\phi$ be a sentence of set theory. In Prenex form, $\phi$ can be written $$ {\bf Q}_1 x_1 {\bf Q}_2 x_2 \ldots {\bf Q}_n x_n \ \ \psi(x_1,x_2, \ldots ,x_n) $$ where each ${\mathbf Q}_i$ is ...
2
votes
0answers
54 views

Algebraization of attribute-value logic

Jürgen Wedekind ("Classical logics for attribute-value languages", can be googled up) has defined an attribute-value logic as a fragment of predicate logic. There are no predicates except for ...
2
votes
0answers
161 views

What kind of logics satisfy the coincidence lemma?

Lets formulate the incidence lemma as follows. We have a possibly infinite set of variables X and the domain of discourse U. Lets define an interpretation of the variables X in the domain U as a ...
2
votes
0answers
143 views

How to turn a topological space into a semi-decidable logic?

In two interesting posts(here and here),it is mentioned that "there is a close connection between semi-decidable logics and topological spaces" Michael O’Connor wrote: In fact, given a ...
2
votes
0answers
74 views

Functors that have a natural Isomorphism

Find different functors $T, S: Rng \rightarrow Rng$ both identity on objects IE: for each ring $R, T(R)=S(R)=R$, such that there is a natural isomorphism between T and S. I know that a natural ...
2
votes
0answers
79 views

Proof for a finite number of elements

if I want to proof something for a restricted finite number of elements, meaning the following: Imagine that I have a theorem that is somehow similar to the following: For each element in $\mathbb{A}...
2
votes
0answers
75 views

The Barcan schema in Modal logic

On page 11 of this article by Timothy Williamson http://link.springer.com/article/10.1007/s10670-013-9474-z#page-12 the Barcan schema in first-order modal logic is discussed. Williamson says, "...
2
votes
0answers
165 views

How to show Simp. and Creat. are $\Sigma^0_2$-Hard

Let Simp={$e:W_e$ is simple} and Creat={$e:W_e$ is creative} I'm having troubles showing these sets are $\Sigma^0_2$-Hard, ie that any $\Sigma^0_2$ set can be many-one reduced to them. I've already ...
2
votes
0answers
263 views

First Order logic with vertex covers

Let $G=(V,E)$ be a directed graph. Let $E$ be a binary relation such that $(x,y) \in E$ iff there is an edge from vertex $x$ to vertex $y$. Let the world of first order interpretation be the set of ...
2
votes
0answers
154 views

Confusion in first-order logic inference

I'm having some difficulty with understanding the following paragraphs taken from the Russell & Norvig’s Artificial Intelligence: A Modern Approach, regarding first-order logic inference: The ...
2
votes
0answers
81 views

Proving that an effective procedure is correct

I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it. Definitions: (1) The ...