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

101 views

### What is the correct negation of the Statement “For every rational number $x$, $x \lt x + 1$ ”

They statement is $:-$ For every rational number $x$, $x \lt x + 1$ At first glance my answer was $:-$ There exists a rational number $x$ such that $x \geq x + 1$ But then i saw this ...
90 views

### Categorical semantics explained – what is an interpretation?

I’ve been really having a hard time trying to understand categorical semantics. In fact, I am confused to the point I am afraid I don't know how to ask this question! I’ve been reading textbooks like ...
42 views

### Diophantine relations using an equation with polynomials of degree at most 4

I'm completely stuck at exercise 5.8.5 of Mathematical Logic, Chiswell & Hodges: Here are the mentioned definition and theorem: I'm stuck because I failed to use the hint given in the ...
32 views

84 views

### Precise definition of Σ00 in the arithmetical hierarchy

I encountered several different definitions for Σ00 = Π00 = Δ00 of the arithmetical hierarchy. Following are two definitions which seem to me different but I'm not sure: All first-...
60 views

### Mathematical induction: $4 + 5 + 6 + … + n = \dfrac{n(n+1)}{3}$ where $(n \ge 4)$

Prove using mathematical induction that 4 + 5 + 6 + … + n = [n(n+1)] / 3 (n is an integer >= 4) I just wanted to confirm because my Base case P(4) is false. So this statement can't be proven?
60 views

### Is Contra-positive and Converse statements just different way of saying a if then statement?

So i had this question :- Write, If a natural number is odd, then its square is odd in different ways. I had included these statements in my answer :- $(1): -$ If the square of a natural ...
69 views

### Is it possible to eliminate a contradiction without recourse to the principle of explosion?

I'd like to derive the following inference rule: $$\frac{p\lor(q\land\neg q)}{p}\quad\text{[ContradictionElimination]}$$ I assumed that I could do this minimally somehow, however it turns out I ...
50 views

### Necessary truth of mathematical proposition.

Take from Possible world- an introduction to logic and its philosophy. p-21 Following quote provide us with necessary definition of what "logically necessary" or as far as i think "necessary truth" ...
68 views

### Every transitive $\in$-linearly ordered set is $\in$-well ordered without axiom of foundation

I try to prove that every ordinal number $(\alpha,\in)$ is well-ordered, where an ordinal number is defined as a transitive $\in$-linearly ordered set. So all I have to show is, that every non-empty ...
37 views

### Is there a name for the propositional tautology (and it's associated rule) $Q\Rightarrow(P\Rightarrow Q)$?

I have the tautology $Q\Rightarrow(P\Rightarrow Q)$. I can prove this intuitionistically: ...
61 views

### Relation and Function in a language

At the very beginning of David Marker's book Model Theory, it defines a language to be given by a set of function symbols $F$ and a set of relation symbols R. I am just wondering isn't a relation a ...
55 views

85 views

### Existential axioms for category theory

There are some existential axioms in set theory, for example, axiom schema of specification. It's my understanding that category theory isn't based essentially on set theoretic foundation. If so, I ...
59 views

### Expressibility of Peano arithmetic and the Arithmetical Hierarchy

First-order Peano arithmetic has no non-logical symbols other than S, +, *, < and variables. One allows finite quantification over predicates such as: $\forall k<n: \phi(k)$ where $\phi(k)$ is a ...
51 views

### What exactly is the role of the material conditional in intuitionistic logic?

There seems precious little around about the use of the material conditional in intuitionistic logic aside from the Wikipedia page https://en.wikipedia.org/wiki/Material_conditional and I can't seem ...
69 views

### Did I pick the error? Mathematical Logic

Given these propositions: \begin{align} x&=y \\ x^2&=xy \\ x^2-y^2&=xy-y^2\\ x+y&=y\\ y+y&=y\\ 2y&=y\\ 2&=1 \end{align} I've found out that the error is "$x+y=y$". Am ...
49 views

### Is double negation introduction an axiom of intuitionistic logic or can it be derived?

If I have a rule for negation introduction... Rule (NegationIntroduction,ProofByNegation) Premises P=>Q, P=>⌐Q Conclusion ⌐P ...then it seems ...
1k views

### Is there a model of ZFC inside which ZFC does not have a model?

Assuming ZFC has a model, is there a model of ZFC such that in that model, ZFC has no model? Also, assuming ZFC has a model, is there a model of ZFC such that in that model, ZFC is inconsistent?
87 views

### The monadic second order theory with $<$ and Presburger arithmetic

Consider the monadic second order logic over the natural numbers with $<$ as a predicate, i.e. the second order logic over $(\mathbb N, 1, <)$, where we can quantify over sets and individual ...
42 views

### Proving existence of a wff that is logically equivalent to a wff given some conditions

For convenience, let us define a wff to be positive if there is no use of the negation symbol $\neg$ at all in the wff. Hence, for example, $W=P\iff Q$ is a positive wff. Now the question is to show ...
24 views

### What are some methods of proving undefinability results? (Reference)

I'm trying to prove some results regarding undefinability of functions from the natural numbers in certain structures, but besides texts on elemental logic and number theory, i haven't found anything ...
61 views

201 views

### Calculus of Natural Deduction That Works for Empty Structures

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\Gamma$ is a set of formulas and $\phi$ a ...
72 views

### A philosophical question on probability theory [closed]

This question is philosophical in nature. The example is taken from theology, but one may invent more examples, including these more scientific than mine. Nevertheless it is a valid mathematical issue....
27 views

### Is this conclusion via rules of inference correct?

Use rules of inference to show: ∀x(P(x) → Q(x)) premise ∀x(Q(x) → R(x)) premise ¬R(a) premise ¬P(a) conclusion I have a lot of trouble with these sort of questions and was wondering if I did this ...
38 views

### About a proof of the Adequacy of Natural Deduction for Propositional Logic

In Mathematical Logic by Chiswell and Hodges, section 3.10 page 89 proves the following theorem: Theorem 3.10.1 (Adequacy of Natural Deduction for Propositional Logic) Let $\Gamma$ be a set ...
Edit: former solution was deleted Assume $$\bigcap_i \Bbb C \setminus A_i \neq \emptyset, i = 1, ..., n.$$ Thus $$\exists x \in \bigcap_i \Bbb C \setminus A_i,$$ and therefore \exists x \in \...