Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

4
votes
1answer
223 views

Some questions about Gödel's theorems of completeness and incompleteness

I am taking a course where we are covering a bit of logic, and I am trying to understand a some nuances of Gödel's theorems of completeness and incompleteness. Q1) Is it correct to say that Gödel's ...
1
vote
1answer
102 views

What is dual representation in plain English?

Can someone please explain what is Dual representation in plain English. I read its definition on wikipedia and at many other places but could not develop an intution for it. Please explain in plain ...
0
votes
2answers
50 views

Contrapositive Inquiry

Suppose you want to show that $A \implies B$. This is equivalent to showing $\neg B \implies \neg A$. But now suppose you show that assuming $\neg B$ it is POSSIBLE that $\neg A$, but not ...
1
vote
1answer
290 views

Tracing a most-general unifier algorithm

I'm trying to trace the algorithm for getting the most general unifier, and I'm a bit confused. Can there be more than one solution? (although the adjective 'most' suggests otherwise) found online: ...
2
votes
1answer
55 views

Comparing models through partial isomorphisms

Let $T$ be a theory of a language $\mathcal{L}$ with no function symbols. Let $\mathfrak{A}, \mathfrak{B} \models T$. For all finite sets $X \subseteq A$ and $Y \subseteq B$, there exists a function ...
0
votes
2answers
131 views

Why is this proof wrong?

I am taking a course on logical equations and I found this exercise while reading about proofs and how to prove a given sentence and what kind of mistakes usually occur when you are trying to prove ...
2
votes
3answers
67 views

Logic: If and only if (iff) statement

I'm reading D'Angelo and West, first edition for recreation. In example 20, it states "If integers x and y are odd, then x+y is even." (I took this to mean, P(x,y both odd) -> Q (x+y is even.) Easy ...
2
votes
1answer
68 views

A representation of well-orderings?

Is there a well-ordering $P$ of the set of real numbers $\mathbb{R}$ such that there is NO function $f: \mathbb{R}->\mathbb{R}$ satisfying the property: for all $x,y \in \mathbb{R}$, $xPy$ iff ...
0
votes
1answer
42 views

Finding the truth value

How to find the truth value of: $\lim_{n \to \infty}\left[1 + \frac{\ln\left(10\right)}{n}\right]^{n} = 10$ is necessary for $ \lim_{n\to \infty}\left[1 + \frac{\ln\left(10\right)}{n}\right]^{n} = ...
0
votes
2answers
154 views

Is $ \forall x(P(x) \lor Q(x)) \vdash \forall x P(x) \lor \exists xQ(x) $ provable?

I know I should be able to determine whether the following holds, but I am not able to either find a model to show that this is false nor can I prove its correctness by using natural deduction. $ ...
1
vote
1answer
77 views

In predicate logic, can existential variables be used interchangeably?

When doing a derivation in predicate logic, am I allowed to use two different existential variables interchangeably? For instance, is $\forall xPx$ (or $∃xPx$) equal to $\forall yPy(∃yPy)$? If I ...
3
votes
1answer
84 views

DPLL Algorithm $ \rightarrow $ Resolution proof $ \rightarrow $ Craig Interpolation

I really need help here for an exam that I got tomorrow .. Let's say I got a bunch of constraints: $ c1 = { \lnot a \lor \lnot b } \\ c2 = { a \lor c } \\ c3 = { b \lor \lnot c } \\ c4 = { \lnot b ...
1
vote
2answers
96 views

A correct logical representation for an iff expression

For every integer n, $n^{3}$ is even if and only if n is even This is clearly an implication, the problem is the order of the statement confuses me. $n^{3}$ is even $\Longrightarrow$ n is even vs ...
3
votes
2answers
640 views

Is it true that all of the euclidean geometry problem in the IMO(international mathematical olympiad) could all be solve by the analytical geometry?

Is it true that all of the euclidean geometry problem in the IMO(international mathematical olympiad) or even generalize to say that all the plane geometry problem and 3d-geometry could be solve by ...
3
votes
2answers
100 views

Equivalence between two definitions of infinitary logic

The common definition of $ \omega $-logic (a.k.a $\mathcal{L}_{\omega_1,\omega}$ logic) is the usual first order logic allowing infinite conjunctions and infinite proof. Chang and Keisler, in section ...
0
votes
1answer
81 views

Models of the full theory of a structure

I'm reading Model theory: an introduction, by David Marker. I'm at page 14, where it says: ...one way to get a theory is to take $\operatorname{Th}(\mathcal{M})$, the full theory of an ...
3
votes
2answers
102 views

Is entailment biconditional or conditional?

When we say a KB entails Q it means that it is never the case that KB is true and Q is false. Does this mean entailment is similar to the conditional statement KB -> Q? I'm confused because our ...
3
votes
1answer
115 views

$L-$rank (Kunen exercise)

I'm stuck with exercise 5 at page 180, where it asks me to compute explicitly the $L-$rank $\rho(\bigcup x)$ of $\bigcup x$ in terms of $\rho(x)$. You can obviously define $\bigcup x$ from the ...
0
votes
2answers
70 views

Question Regarding Logical Contradiction

Let's say I attempted to solve a logical statement in the form using contradiction: $\forall x \in \Bbb R, (P \implies Q)$ Negated: $\exists x \in \Bbb R, (P \land \lnot$ Q). Initially I did not ...
1
vote
1answer
121 views

Logic/Quantifiers and Proofs/counterexample

How do I negate the following statement? Also please help me with this exercise:
0
votes
2answers
69 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
136 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
123 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
118 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
72 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
58 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
214 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
267 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
233 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
136 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
162 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 ...
10
votes
2answers
395 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
462 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
181 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
195 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
76 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
53 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
159 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
3k 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
97 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
41 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
547 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
106 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
58 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
158 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 ...
2
votes
1answer
156 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, ...