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)

3
votes
2answers
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
32 views

Negation of double universal quantifications

In logic, when I want to negate the formula $$\forall x \forall y( F(y) \land A(y) \to \neg G(x,y))$$ what is the correct equivalent? Intuitively, I think it gives $$\exists x \forall y (F(y) \land ...
1
vote
1answer
58 views

Adding witnesses to prove Gödel's completeness theorem

I am currently working with "The Foundations of Mathematics" by Kunen to understand the proof for Gödel's completeness theorem due to Henkin. When adding the witnessing terms, there is one thing I ...
0
votes
2answers
111 views

On the existence of sets in bijection

Given a set $X\not=\emptyset$ is it always true that there is a set $Y$ such as $X\not=Y$ but $X$ and $Y$ are in bijection? I think it is true, but which axioms of logic justify it? I mean, if $X=\{a,...
1
vote
1answer
57 views

Is my proof to show that $\mathcal{P}(A) \subseteq\mathcal{P}(B) \implies A \subseteq B$ correct? $\mathcal{P}$ refers to the power set.

Suppose $A$ and $B$ are sets, and that $x$ is an arbitrary element of $A$. The definition of the given $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ means $$\forall y[(y \in \mathcal{P}(A) \rightarrow y \...
3
votes
1answer
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-...
0
votes
2answers
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?
1
vote
5answers
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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" ...
1
vote
1answer
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 ...
1
vote
1answer
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: ...
1
vote
1answer
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 ...
1
vote
1answer
55 views

Veryfing a proof without a truth table

I have the following proof to verify without using truth tables but rather to use the laws or theorems of logical equivalence. I am suppose to prove $(p\wedge q)\vee p\equiv p$, but I am stuck at$(p\...
2
votes
0answers
87 views

Are these strengthenings of a rank-into-rank cardinal axiom known to be inconsistent with $ZFC$?

I am just getting acquainted with "very strong" large cardinal axioms, and it seems there is a consensus that among large cardinal axioms, the rank-into-rank cardinal axioms are at the threshold of ...
1
vote
1answer
70 views

Arithmetical hierarchy: Why is $\Delta_0^0\ne \Delta_1^0$?

The definitions are different from one textbook to the other, but if we take the following definitions: $\Delta_0^0$ = all the first-order arithmetic formulas with bounded quantifiers only. $\...
3
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
2answers
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 ...
2
votes
3answers
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 ...
2
votes
1answer
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 ...
27
votes
2answers
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?
4
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
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 ...
3
votes
2answers
61 views

How to prove that $(p\rightarrow q)\wedge(p\rightarrow r)$ and $p\rightarrow (q \wedge r)$ are logically equivalent?

I am trying to prove that $(p\rightarrow q)\wedge (p\rightarrow r) = p\rightarrow (q \wedge r)$. This is my approach: $(p\rightarrow q)\wedge(p\rightarrow r) = (-p \vee q) \wedge (-p \vee r)$ = ${[...
1
vote
1answer
53 views

Are equality and non-equality mutually dependent?

Is there any type of objects or ideas for which asking about their equality makes sense, but asking about non-equality doesn't? (or vice versa) Intuitively, "not equal" is a negation of "equal", so ...
5
votes
2answers
85 views

Formal systems in which $\forall x \in \mathbb{R}(x \neq 0 \rightarrow x^{-1} \neq 0)$ is true, but the contrapositive is disallowed.

Question. Are there any formal systems out there for which $$\forall x \in \mathbb{R}(x \neq 0 \rightarrow x^{-1} \neq 0)$$ is true, but the contrapositive $$\forall x \in \mathbb{R}(x^{-1} =...
0
votes
1answer
82 views

Can we take definability and existence as primitive notions of a theory?

One of my friend tries to develop an alternative viewpoint of Set Theory. For this he has taken the terms binary relation, set, existence and definability as primitive notions of his Set Theory. After ...
1
vote
2answers
52 views

How does the axiom schema of replacement work?

According to this website, the first partion of this axiom schema is Let $P(y,z)$ be a propositional function, which determines a function. That is, we have $∀y(∃x:(∀z:(P(y,z)⟺(x=z))))$. ...
-7
votes
1answer
272 views

Are Godel's incompleteness theorems proven non-trivial?

Godel's incompleteness theorem states there will be unprovable statements in some language. Can it be proven that the unprovable statements in some language $F$ are necessarily not just "trivially ...
1
vote
0answers
85 views

easy proof of the completeness theorem [closed]

The completeness theorem of first-order logic states: If $\Phi\models\phi$, then $\Phi\vdash\phi$. Assume that I have a calculus $\vdash$ in mind for which I want to prove this completeness theorem. ...
2
votes
1answer
50 views

Function $F(n)=n+n$ is not $\Delta_0$

Define $F(n)=n+n$, for $n<\omega$, and $F(n)=0$, for $n\not\in\omega$. I have to show that this is not a $\Delta_0$-function but it's the composition of two $\Delta_0$-functions. I have one hint; ...
2
votes
1answer
49 views

Is there a way to reduce a set of linear inequalities representing a set of vectors in $\{0,1\}^n$?

Given a fixed number $r$, such that a vector $v_i \in \{1,0\}^n$ has exactly $r$ ones and $n-r$ zeroes, and a number of inequalities, (say $I$ is this set of inequalities) representing a set $J$ of ...
0
votes
2answers
46 views

Why is this counter-example valid?

I don't understand why the counter example of the following argument is valid: $\forall x\exists y(Ax\iff By)$ $\exists xBx \land \exists x\sim Bx $ $\forall x(Ax \to \sim Cx) $ ...
1
vote
2answers
90 views

When does circular reasoning go wrong?

Consider the following erroneous usage of L'hopital's rule: $$\lim_{h \to 0} \frac{f(x+h) - f(x)}{h} = \lim_{h \to 0} \frac{D_h(f(x+h) - f(x))}{D_h(h)} = \lim_{h \to 0} \frac{f'(x+h)}{1} = f'(x) \...
1
vote
1answer
49 views

Second Order Arithmetic

Since second order arithmetic is finitely axiomatazible why do not work with it, and insted we prefer first order Peano Axioms that include induction scheme?
0
votes
1answer
44 views

Express statement with predicates and quantifiers.

Ex: A student must take at least $60$ course hours, or at least $45$ course hours and write a masters thesis, and receive a grade no lower than a B in all required courses, to receive a masters degree....
-1
votes
1answer
33 views

Express the statement using predicates and quantifiers.

Ex: A passenger on an airline qualifies as a frequent flier if the passenger flies more than $25,000$ miles in one year or takes more than $25$ flights during that year. I started and made up these ...
2
votes
1answer
20 views

Use truth tables to show logical equivilance

Q: Show using truth tables that $\lnot(p \to q)$ and $(p \land q)$ are logically equivalent. So I thought that the negation of $(p \to q)$ was $(p \land \lnot q)$ so not sure if "logically equivalent"...
0
votes
1answer
45 views

Herband model for a forumla

I need to find a Herband model for the formula $Pc \land \forall x (\exists y (Px \leftrightarrow \neg Py))$, where $c$ is a constant and $P$ is a unary relation. I've already read the theory but ...
0
votes
1answer
38 views

Prove a relation is primitive recursive, x is prime?

Is $\{x \in \mathbb{N}| \mbox{ x is prime}\}$ primitive recursive? Hello, $x \in \{x \in \mathbb{N}| \mbox{ x is prime}\} $ if and only if $ \forall y : y \le x \Rightarrow (y=1 \vee y=x \vee \neg (...
4
votes
4answers
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 ...
-3
votes
1answer
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....
1
vote
2answers
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 ...
0
votes
2answers
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 ...
1
vote
1answer
34 views

Every intersection of a finite number of open subsets is also open

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 \...
0
votes
0answers
44 views

What rules should I use to rewrite equations?

For a homework assignment I have to prove the following: Using: \begin{align} &[A_1]\quad \text{found} = (∃k : 0 \le k \lt i : b[k])\\ & [A2] \quad0 \le i \le N\\ &[A3]\quad i < N \\ &...