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
2answers
72 views

Model and countermodel to $\exists x.\forall y. x<y$ (with $<$ an arbitrary relation)

Can someone please help me with this question. I have been struggling with it for ages and can't quite seem to work it out: Let $<$ be a binary relation symbol that we will write infix. Let ...
1
vote
1answer
69 views

The rule $\phi \leadsto \phi\land\psi$ is not sound

I have been asked to show that this rule is not sound: $$\frac{\varphi}{\varphi\wedge\psi}\wedge I'$$ Any help with this would be greatly appreciated.
7
votes
2answers
141 views

For two theories $T,T'$, what does $T\vdash Con(T')$ really tell us about the models of $T$?

Inspired by this question, which I realized I couldn't answer (because model theory and me don't get along). I've made a few edits to (hopefully constructively) tighten the question a bit. If for ...
5
votes
1answer
129 views

Impossibility of theories proving consistency of each other?

By Godel's second incompleteness theorem, a consistent theory (to which the theorem applies) cannot prove itself consistent. I learned that it's also impossible to have a pair of consistent theories ...
3
votes
3answers
134 views

When is first order induction valid?

Assume we know $\forall x(P(x))$ is true in a model of Peano arithmetic (PA). Does this mean we can prove $\forall x(P(x))$ using induction? If not, why not? If $P(x)$ is true for all $x$ then $P(0) ...
1
vote
1answer
75 views

Given a theorem can it always be reduced logically to the axioms?

It's probably a silly question but I’ve been carrying this one since infancy so i might as well ask it already. let ($p \implies q$) be a theorem where $p$ is the hypotheses and $q$ is the ...
0
votes
3answers
59 views

Proving a theorem or statement correct using numbers

Why is it that you CAN'T use numbers to prove a theorem or statement is correct in mathematics but you CAN use numbers to prove a theorem or statement is wrong? e.g: the triangle inequality |a+b| < ...
0
votes
2answers
218 views

A (too?) simple argument for the undefinability of definable sets

Preliminaries (see e.g. Jech, Set Theory, p. 5): To every formula $\varphi(x)$ of ZF set theory corresponds a class $C = \lbrace x : \varphi(x)\rbrace$, but only to some formulas corresponds a set. ...
4
votes
2answers
409 views

Is the empty function always a bijection?

Let $f_A:\emptyset\to A$ be the empty function with range $A$. The definition of a bijection as applied to this function is: $$\forall x,y \in \emptyset (x=y \implies f_A(x)=f_A(y))$$ negating you ...
0
votes
1answer
351 views

Natural Deduction please help!

I am sorry for posting this here, but this is my last resort. I have been fighting with these natural deduction problems for the last two weeks. I take an online college logic course and it makes it ...
1
vote
1answer
184 views

How to prove “basic” identities in first order logic?

On the Wikipedia page for First-order logic, there is a list of Provable Identities. Although they seem very basic, I can't find anyone giving a formal proof of them. In particular, consider one ...
1
vote
1answer
44 views

Complete recursively Set

The set $\Sigma=\{ p_1\rightarrow p_2, p_2\rightarrow p_3, ... \}$ Is it complete? why? Is it recursively axiomatizable? Why? Is the consequences of this set recursive? Why? Thanks so much.
2
votes
0answers
172 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 ...
1
vote
0answers
63 views

Formulas in a Field and in a Field Extension.

Let $\mathbb F$ be a field and let $a, b, c, d$ be fixed elements in the field $\mathbb F$. Consider the formulas 1) $\exists\;x\;\;:\;\;x^2=-1.$ 2) $\exists\;x\;\;:\;\;(xa=c\land xb=d).$ Formula ...
11
votes
2answers
491 views

Minimal difference between classical and intuitionistic sequent calculus

Consider propositional logic with primitive connectives $\{{\to},{\land},{\lor},{\bot}\}$. We view $\neg \varphi$ as an abbreviation of $\varphi\to\bot$ and $\varphi\leftrightarrow\psi$ as an ...
2
votes
2answers
635 views

Tautological and logical consequence

In Herbert Enderton's book A Mathematical Introduction to Logic, it is mentioned [see page 115] that $Pc$ is not a tautological consequence of $\forall xPx$ (when both are taken as sentence variables ...
0
votes
2answers
352 views

What is a Sub Formula and What is a Maximal Sub Formula in Propositional Logic

What is a Sub formula of a Propositional Formula? Suppose I have a formula C or -C Then what are the sub formulas of this and what is the maximal sub formula of this Propositional Formula. I am a bit ...
5
votes
1answer
246 views

where to start reading theory of logics?

I am a student who is working Lie Theory. I want to start read theory of logics. I just need some reference and I have few questions regarding this, i) will studying theory of logics will improve my ...
0
votes
1answer
82 views

Transform OR clause to algebraic equations (linear programming)

So basically my question is: does it exist a way to transform the clausure (a or b or c) into one or more algebraic equations giving as a result 0 or 1 AND that can be included in a linear programming ...
2
votes
1answer
56 views

Showing that $|\phi(\mathcal{N})| = \kappa$ s.t. $\mathcal{M} \equiv \mathcal{N}$ with $|\mathcal{N}| = \kappa$

Problem: Suppose $\mathcal{M}$ is an $L$-structure and $\phi \in L_n$ ($n > 0$) is such that $\phi(\mathcal{M})$ is infinite. Then show that for every cardinal $\kappa$ with $\kappa \ge |L|$ there ...
3
votes
1answer
173 views

Axioms based on $\leftrightarrow, \lor, \bot$ for propositional intuitionistic logic?

Propositional intuitionistic logic can be axiomatized based on $\;\to, \land, \lor, \bot\;$, with modus ponens $$ \text{from }\; \phi \;\text{ and }\; \phi \to \psi \;\text{ infer }\; \psi $$ as the ...
0
votes
1answer
37 views

Contrapositive clarification

Let's say I have this statement: ∀ real numbers x, if −x is not irrational, then x is not irrational. Which one of the following statements is equivalent to this? [because −(−x) = x], 1.∀ real ...
0
votes
3answers
6k views

Prove « If P(A) is a subset of P(B) => A is a subset of B » [duplicate]

I need to prove «If P(A) is a subset of P(B) => A is a subset of B», generally, I understand the main way I should prove it, but the problem is in the formal, pedantic language I have to use to ...
5
votes
2answers
100 views

Axiomatisation of propositional logic using $\land$ and $\neg$

I am looking for a simple axiomatisation of a particular version of propositional logic that is defined in terms of $\land$ and $\neg$ only. I am guessing that it only needs one rule of inference: ...
2
votes
1answer
43 views

Question about Lemma D1.4.4(iii) in the Elephant - possible typo?

Given a morphism $[\theta] \colon \lbrace \bar{x}.\phi \rbrace \rightarrow \lbrace \bar{y}. \psi \rbrace$ in the syntactic category $\mathcal{C}_{\mathbb{T}}$ of a (cartesian) theory, we are told, in ...
1
vote
3answers
1k views

Show that $ \{\lnot,\leftrightarrow\} $ is not functional complete

I have to prove that this set of logical operators is not functional complete - $$ \{\lnot,\leftrightarrow\} $$ i've tried implement this set by $ \{\rightarrow,\lor\} $ which is not functional ...
0
votes
1answer
118 views

Showing that $\mathcal{M} \preccurlyeq \mathcal{N} \implies \mathcal{M} \equiv \mathcal{N}$.

Suppose that $\mathcal{M} \preccurlyeq \mathcal{N}$. Then by definition we have that $\mathcal{M}$ is a substructure of $\mathcal{N}$ s.t. for any (possibly empty) tuple $\overline{a}$ from $M^n$ and ...
0
votes
2answers
60 views

Using the following key, symbolize the following

Using the following key, symbolize the following a = André C _ = _ is a cook P _ = _ is a philosopher W _ = _ is wise (a) If all philosophers are cooks, then all cooks are philosophers. ...
2
votes
3answers
177 views

Give a proof of $\forall x Fx \lor \forall x Gx \vdash \forall x (Fx \lor Gx)$

Give a proof of: $$\forall x Fx \lor \forall x Gx \vdash \forall x (Fx \lor Gx)$$ I don't know how to proof, but here is my attempt. 1 1) $\forall x Fx \lor \forall xGx \quad$ P 2 ...
3
votes
1answer
193 views

tautologies and contradictions with $r$

I'm really struggling to understand tautologies and contradictions. I've been able to do $(p \rightarrow q) \leftrightarrow (\lnot q \rightarrow \lnot p)$ and I understand why it is a tautology, ...
2
votes
1answer
120 views

Deduction Theorem Subtlety and Predicate Proof

In standard, first-order predicate logic suppose that with a set of assumptions $\Gamma$ I can deduce $$\Gamma\cup\{A(a),B(m),\forall x\forall y\exists z[A(x)\land B(y)\rightarrow C(x,y,z)]\}\vdash ...
0
votes
1answer
41 views

help with nand circuit

I tried to make a circuit from this expression but it's not working right. Here's the expression and circuit: Expression ...
0
votes
1answer
20 views

equality of two objects depending on conditions.

I want to state that two objects $t_i, t_j$ are equal if some conditions hold. Can this be done by writing: $t_i = t_j \rightarrow$ some conditions?
2
votes
2answers
242 views

Is there a proper term and/or symbol for an “agnostic” conclusion?

My question stems from the material conditional: $p \rightarrow q\\p\\\therefore\space q$ However, if $\bar p$ then the conditional is silent. I would like a way to represent this fact using, if ...
2
votes
1answer
81 views

Can a sentence in a model-theoretic conservative extension be translated in the language of its reduct?

Let $L1$ and $L2$ two languages with $L1 \subset L2$ and $T1$ and $T2$ respectively a theory in $L1$ and $L2$. We say that $T2$ is a model-theoretic conservative extension of $T2$ iff every model $M1$ ...
5
votes
10answers
10k views

How do I prove this statement is tautology without using truth tables?

How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$ I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left ...
1
vote
1answer
58 views

Showing that $|\phi(\mathcal{M})| = |\phi(\mathcal{N})|$ if $\phi(\mathcal{M}) \Subset M^n$ and $\mathcal{M} \equiv \mathcal{N}$

Let $\phi \in L$ define a finite set $X$ in the $L$-structure $\mathcal{M}$. Show that in every $\mathcal{N}$ elementarily equivalent to $\mathcal{M}$, the set defined by $\phi$ has the same power as ...
0
votes
2answers
48 views

Is my transitivity proof correct for the relation over $\mathbb{Z} \times \mathbb{Z}$ where $(a,b)R(c,d) \iff (a \le c \lor b \le d)$?

I'm having a hard time developing abstract thinking to solve problems regarding a relation's properties. I've spend quite an absurd amount of time on this one, but I think I finally grasped a bit of ...
0
votes
1answer
632 views

How Would You Translate This Sentence To Predicate Logic?

"There exists an Apple such that for every person, he loves that apple." I believe the translation is: $$\exists x(\forall y((\text{Apple}(x) \wedge \text{Person}(y)) \to \text{Loves}(y,x)))$$ ...
2
votes
4answers
1k views

What is the correct notation for equations and sets

If i want to continue this equation, which logic connective is the most correct or most people use in tests: $$ 2x = 4 \rightarrow x= 2 $$ or $$2x =4\Rightarrow x=2 $$ or $$2x=4 ...
0
votes
1answer
330 views

Logical representation of a prime number

Is it correct to represent a prime number like this? $$\exists k \in \mathbb N,\, \exists n\in \mathbb N\, \Big((n\mid k) \land (n=k \lor n=1)\Big)$$
1
vote
1answer
48 views

Proving a relation's inverse's properties by knowing the original's.

I'm getting fairly confused with two exercises related to proving a relation's inverse's properties by knowing the original's. I couldn't do either. Any hint is appreciated. If $R$ is a ...
1
vote
1answer
72 views

Substitution identities: $\mu(x/ \sigma)(y/\tau) = \mu(x/ \sigma, y/\tau) = \mu(y/\tau)(x/\sigma)$

If $x$ and $y$ are distinct variables, $\sigma$ and $\tau$ closed $M$-terms, and $\mu$ is any $M$-term, how can I show that $\mu(x/ \sigma)(y/\tau) = \mu(x/ \sigma, y/\tau) = \mu(y/\tau)(x/\sigma)$ ? ...
3
votes
1answer
111 views

deducibility from peano axioms

I have to solve the following problem: Using $\exists$ Introduction prove that PA$\vdash x\leq y \wedge y\leq z \longrightarrow x\leq z$: I used that if $x\leq y$ then $\ \exists \ r\ x+r=y$ and in ...
1
vote
1answer
158 views

On deductively closed theories

Definition A theory $T$ is a set of sentences. A structure $\mathcal{A}$ is a model of $T$ if $\mathcal{A}\vDash T$. To better understand the situation, let us recall the classical Galois connection ...
4
votes
1answer
886 views

Convert a WFF to Clausal Form

I'm given the following question: Convert the following WFF into clausal form: \begin{equation*} \forall(X)(q(X)\to(\exists(Y)(\neg(p(X,Y)\vee r(X,Y))\to h(X,Y))\wedge f(X))) \end{equation*} ...
0
votes
1answer
154 views

Propositional Logic questions about tableau method

Hello i am learning for my exam from logic, I came across the question which i don't know how to solve it. Can tableau for a propositional formula containing an infinite path exist? Can be tableau ...
2
votes
1answer
59 views

Proof via equivalence laws; $(a \lor b) \equiv (b \lor a)$?

Is this a correct progression to prove that $p \rightarrow (q \rightarrow r) \equiv q \rightarrow (p \rightarrow r)$? $$\begin{align} p \rightarrow (q \rightarrow r) & \equiv p \rightarrow (q ...
2
votes
2answers
74 views

How can I further simplify $(a \le b) \lor (b \le a)$ to prove that it is a tautology?

Over $\mathbb{Z}$, $aRb \iff a \le b \lor a = 3b$. Determine if it is total. I think it is: Have arbitrary elements $a,b \in \mathbb{Z}$. We have to prove that $aRb \lor bRa$, which can be ...
2
votes
1answer
371 views

How would you show if a formula is valid in first order logic?

I'm trying to understand how I can solve two particular tasks. I need to show if the following formulas are valid: $Pa \lor Pb \rightarrow \exists xPx$ and this one $\forall xPx ...