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)

0
votes
0answers
13 views

Unary relation in a logical sentence

I'd appreciate help with this sentence: Let there be a language L and a structure M, and I need to prove the following sentence is logically false: $$\varphi :\exists xR(x)\rightarrow \forall yR(y)$$ ...
0
votes
1answer
25 views

True or falsehood of open formula under a fixed interpretation

Given the open formula: $\alpha =(\exists{{x}_{2}})({P}^{1}({x}_{1},{x}_{2}))$ And consider the interpretation $I$ where the domain is the natural numbers, and ${P}^{1}$ means equality. Is $\alpha$ ...
2
votes
0answers
31 views

Show that the law of the excluded middle does not hold in a BCCC

I want to show that the law of the excluded middle do not hold in a bicartesian closed category (BCCC), interpreted as follows: In general, there need not be a morphism $1 \to A + 0^A$ for $A \in \...
-1
votes
0answers
43 views
0
votes
1answer
26 views

Using separators as functional symbols in first order logic

Suppose we have the following definition of a term: A $term$ is: $x$, where "$x$" is a variable $c$, where "$c$" is a constant symbol $f(\tau_1,...,\tau_n)$, where "$f$" is a ...
1
vote
2answers
29 views

Predicate logic: $(\forall x\varphi \rightarrow \forall x\psi ) \nRightarrow (\forall x(\varphi \rightarrow \psi))$

Given $L$ language and $\varphi$ and $\psi$ are formulas. Needs to show that is happening in general: $$(\forall x\varphi \rightarrow \forall x\psi ) \nRightarrow (\forall x(\varphi \rightarrow \psi)...
0
votes
0answers
12 views

Logic-Calculating Cd Failures

I am working on homework and have the problem At a company every 4th CD is tested, the testing consists of 4 testing programs and the probability that they fail are as follow Program 1 : .01 Program ...
0
votes
3answers
31 views

Find the number of all possible valuations that will satisfy given expression.

This part concerns the 256 possible truth valuations of the following eight propositional letters A, B, C, D, E, F, G, H. For each of the following expressions, say how many of the 256 valuations ...
-1
votes
0answers
33 views

i dont understand how theorem calculation proofs work please help [closed]

I do not understand hilbert style proofs and how they work. Can someone please explain them to me? some things i need to know are: • Write theorem-calculations from Γ (equivalently, Γ−...
3
votes
4answers
93 views

$a^n$ even implies $a$ even

I've tried to prove that $(\forall a,n>0 \in \mathbb{N}),(a^n \text{ even} \implies a \text{ even})$, can someone tell me whether my proof is sound? Lemma 1: $a \text{ even} \implies a^2 \text{ ...
0
votes
1answer
48 views

The positive introspection axiom

I am studying modal logic with the textbook 'Reasoning about Knowledge' Fagin et al. 1995 The positive introspection axiom is taken as something that can be proved with the possible worlds model of ...
0
votes
2answers
47 views

Natural Deducion: assumptions can be used more than once?

Im trying to prove: $ \forall{x}\forall{y}(P(x,y)\rightarrow{}\sim P(y,x)) \vdash \forall{x} \sim P(x,x)$ What i have: $\forall{x}\forall{y}(P(x,y)\rightarrow{}\sim P(y,x))\;$ Premise $ \forall{y}...
2
votes
1answer
70 views

Why is the proof of Gödel's first incompleteness theorem no contradiction?

I consider the following version of Gödel's first incompleteness theorem: Assume $F$ is a formalized system which contains Robinson arithmetic $ Q$. Then a sentence $G_F$ of the language of $F$ can ...
2
votes
0answers
32 views

What's a good introduction to Second Order Logic

I'm looking for a good introduction to second order logic. Any recommendations?
0
votes
2answers
45 views

If empty set is a subset of empty set is always true , then is empty set not a subset of empty set always false? [closed]

If $\varnothing \subseteq \varnothing$ is always true , is $\varnothing \subsetneq \varnothing$ always false ? Any proofs ?
1
vote
1answer
47 views

What are the different ways to get a first-order formula that express the statement“$P$ is the $n$-th prime”

I know that such a $2$-predicate formula exists since Enderton's have already constructed such a formula in his text on mathematical logic but it was not easy to remember so I wonder if there is other ...
1
vote
0answers
23 views

Predicate calculus -help [duplicate]

I need to prove that the ∃x(R(x)→∀yR(y)) is logically valid. I'm trying to understand why this statement is true but I can't figure it out.
2
votes
1answer
49 views

What is the intutition behind the negative exponential ? in linear logic?

The positive exponential ! has a very satisfying interpretation in terms of the standard resource interpretation of linear logic. Given a resource $a$, we know that $!a$ means an infinite supply of $a$...
0
votes
1answer
35 views

How can I show that every $\Pi_1$ sentence consistent with Robinson Arithmetic is true in the standard model?

Let $\mathcal{N}=(\mathbb{N}, ...)$ be the standard model of Q (Robinson Arithmetic), and let $\mathcal{N}^{\ast}=(N, ...)$ be an arbitrary model. Let $\varphi$ be a $\Sigma_1$-theorem, and let $\...
-2
votes
1answer
51 views

How to show that Peano axioms prove that if $\varphi$ defines a non-empty set, then it has a least element? [closed]

Show the following statement in PA $\forall v_1\dotso\forall v_k\,(\exists v_0\,\varphi\to\exists v_0(\varphi\wedge\forall v_{k+1}<v_0\,\neg\varphi^{v_0}_{v_{k+1}}))$ With $v_0, v_1, \...
0
votes
3answers
67 views

Is this symbolic statement impossible?

Is this statement logically impossible if x is a single real number (i.e. not a set)? $$(x<5) \land(x>7)$$ it seems to me that x cannot both be greater than 7 and less than 5 if ...
1
vote
2answers
26 views

Should multiple premises of a natural deduction inference rule always have the same context?

Consider the conjunction introduction and implication elimination rules of natural deduction: $$\frac{\Gamma\vdash\alpha \quad \Gamma\vdash\beta}{ \Gamma\vdash \alpha \land \beta} (\land I) \qquad ...
0
votes
1answer
28 views

How can I express each of these quantifications in English?

Let T(x) be the statement "x has visited Tashkent" where the domain consists of all students of my school. How can I express each of these quantifications in English? ...
1
vote
3answers
41 views

Propositional calculus - I can't get why the answer for this test question is what it is

Consider the following premises. If A = B then B = C. B != C. If C > D then D < E. F != G and A = B. A = B or C > D. Alternatives: a) F != G b) F != G and D < E c) A = B d) B = C or D &...
-2
votes
2answers
29 views

Simplifying Logical formulas [closed]

Simplify the logical operators below a. ¬[ ¬Q ∨ (¬P ∧ Q) ] b. ((P ∧ Q) ∧ ¬R) ∨ [P ∧ ¬(Q ∨ R)] Am not able to start this of. I know what all the symbols mean but not able to simplify
5
votes
1answer
52 views

If $a\geq 0$ and $a<\epsilon$ for all $\epsilon>0$ can we show $a=0$ without the law of excluded middle?

I am a PhD student currently studying for an upcoming analysis test. I was working through some problems with a study group and one problem was to show that functions with a certain property send sets ...
3
votes
3answers
99 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
83 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
39 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
31 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
56 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
108 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
80 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
54 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
66 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
47 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
67 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
47 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
46 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\...
-1
votes
0answers
29 views

The 'Apply' algorithm

I have been trying to get a decent example of the Apply algorithm in vain. Can someone pliz help with this. Use the Apply algorithm to determine an OBDD for the formula: (p -> r) ^ (r -> q), ...
2
votes
0answers
84 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
69 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
84 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
58 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
47 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 ...