# Tagged Questions

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 ...

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 ...
89 views

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 ...
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 ...
55 views

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 ...
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 ...
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$ ...
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: ...
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 ...
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 ...
48 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
79 views