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)

0
votes
2answers
19 views

Let $P(x)$ be an open sentence. Is "$P(x)$ and not $P(x)$ proposition?

Let P(x) be an open sentence. Is "P(x) and not P(x)" a proposition ? And another question. Is " if n=2, then n is even" a proposition ? P.S. I don't know where link of teaching for writing symbol of ...
3
votes
0answers
46 views

The Hyperreal number system

Currently reading Infinitesimal Calculus by Henle and Kleinberg. In this text, page 25, they note that they define a hyperreal number system, not the hyperreal number system. This is because "there ...
0
votes
1answer
25 views

if skolem($\alpha$) is valid then $\alpha$ is valid

I am trying to prove the following claim: let $sk(\alpha)$ be the sentence received from the skolemization of a given sentence $\alpha$. Prove : $\vDash sk(\alpha) \implies \vDash \alpha$ I tried ...
3
votes
1answer
30 views

Simplifying propositional logic

Hi I asked a question a few hours ago which has been solved but I got stuck on another exercise so I thought I'd reach out for some help. I have the premise: $((A \to B) \land (\lnot A \to C))$ ...
5
votes
0answers
40 views

Elementary submodels in stationary logic.

In the paper "Stationary Logic" by Barwise, Kaufmann and Makkai the authors prove that stationary Logic L(aa) has Löwenheim number $\aleph_1$, i.e. every satisfiable set of sentences has a model of ...
8
votes
5answers
875 views

“All true theorems are logically equivalent”

I've seen the phrase "all true theorems are logically equivalent" thrown around here, when people ask if a theorem X and a theorem Y are logically equivalent. What is meant by this? Are they just ...
1
vote
1answer
49 views

Prove or disprove wether the sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true

I got stuck at this problem for some hours: Determine whether the first-order sentence $\exists x\forall y Q(x,y)\to \forall y\exists x Q(x,y)$ is logically true, where $Q$ is a 2-ary predicate ...
2
votes
2answers
48 views

Help with natural deduction (Propositional logic)

I'm trying to get to $(\neg A \to C)$ from the following formula: $$(A \wedge B) \vee (\neg A \wedge C)$$ I have attempted the following: $$((A \wedge B) \vee \neg A) \wedge ((A \wedge B) \vee C ...
0
votes
3answers
46 views

Verifying logic without drawing truth tables

Want to know is there a way to solve these sort of problems without drawing truth tables? I found that it's kinda time consuming drawing truth table for each question. Help pls. Check the images ...
1
vote
1answer
47 views

Using the notion of provability only, how to show that $\Gamma \nvdash \varphi$?

For a practical example, suppose I want to show that $\{ P\} \nvdash Q$. From completeness, this is trivial: just find a model where $P$ is true and $Q$ false. But suppose I am stubborn and I don't ...
3
votes
2answers
28 views

Rule of inference and truth table issue

Let P – Light is on Q – The switch is down R – The door is open ...
2
votes
2answers
31 views

Prove using Hilbert calculus $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$, formal proof.

Prove: $\forall x(Px\rightarrow x\equiv a)\vdash Pb\rightarrow Pa$ Using Hilbert Calculus Format of solution: Step (my understanding) Solution: (1) $\forall x(Px\rightarrow x\equiv a)\vdash ...
1
vote
1answer
27 views

Problems with basic proof in modal logic (event based)

I am having trouble deriving the following basic result: $\ast$) For every $\omega \in \Omega, \omega \in P (\omega),$ from the following axioms: A1) $K (\Omega) = \Omega$, A2) $K (A) \cap K (B) ...
1
vote
1answer
31 views

Prove that iff a formula $\phi (v_1, v_2,…v_n)$ is satisfied in the substructure $\mathcal M$, then it is satisfied in structure $\mathcal N$

Assume $\mathcal M \subseteq N$ structures for signature $S$. $\mathcal M$ is a substructure of $\mathcal N$. Let $\phi(v_1, \cdots v_n)$ be a formula without quantifiers. Prove by induction on ...
0
votes
1answer
67 views

Hanf Numbers and Decidability

Currently reading J.L. Bell's Models and Ultraproducts and at the end of Chapter 4 section 4 the authors comment that "In spite of the fact that most languages can easily be shown to possess Hanf ...
2
votes
1answer
66 views

Determine under which conditions the formula $\phi[t/x]\leftrightarrow \forall x ((x=t)\rightarrow \phi)$ is logically true

I am stucked at this problem for a long time: Determine under which conditions the following first-order formula is logically true $$\phi[t/x]\leftrightarrow \forall x ((x=t)\rightarrow ...
4
votes
4answers
75 views

If $T$ a consistent set of sentences and $a,b$ sentences such that $T\vdash (a\rightarrow b)$and $T\vdash (\lnot a\rightarrow b)$ Then $T\vdash b$ [on hold]

I am stucked at this problem for a long time: Let $T$ be a consistent set of first-order sentences and let $\alpha,\beta$ be sentences. Prove that if $T\vdash( \alpha\rightarrow \beta)$ and ...
2
votes
0answers
28 views

A fundamental question on relation between logic, formal system and mathematics.

I was reading this book titled "Godel - A Life of Logic, by J.L Casti and W.DePauli " In pages 30-32 he mentions how a formal system is developed by using a set of symbols as 'axioms' and a set of ...
3
votes
1answer
37 views

Generalizations of pregeometries

Combinatorial geometries and pregeometries are important in classifying strongly minimal (as well as O-minimal) theories. More formally, a model of a strongly minimal (or an O-minimal) theory with the ...
2
votes
1answer
43 views

Determine whether the given pair of statements are contrary, contradictory, or neither.

Consider the following pair of statements: All multiples of three are odd / Some multiples of three are odd. No triangle has an interior angle sum of zero degrees / Some triangle has an ...
3
votes
3answers
31 views

Proof Using Natural Deduction (including '=' rules)

I have a natural deduction proof that I'm stuck on. Obviously I'm not asking someone to just tell me the answer, but if anyone could help me with the next step/point out any mistakes I've made it ...
0
votes
0answers
51 views

Negating a conditional statement

Statement:If Fido barks, then Fido is a tree. Let p = Fido barks Let q = Fido is a tree. symbolic form $p \to q$ My attempt $p \to q $ is logically equivalent to $\lnot\ p \lor q$ ...
3
votes
1answer
55 views

Show that the set of all points $x \in \mathbb R$ where $f$ is differentiable is definable in $\mathcal M=(\mathbb R; +,-(), \cdot, \lt, 0,1,f)$

For the structure $\mathcal M=(\mathbb R; +,-(), \cdot, \lt, 0,1,f), n_f=1 $ show that the set of all points $x \in \mathbb R$ where $f$ is differentiable is a definable set. My issue here is how to ...
-2
votes
1answer
62 views

What is 0^0 ?? 0, 1 or not defined [duplicate]

What is the value of $0^0$ ?? I have read many discussions regarding it but the result was only confusion. Is it 0, 1 or not defined??
0
votes
1answer
15 views

Placement of quantifiers in a symbolic statement

I have the statement: Let $A_n$ be an indexed set of numbers defined by $A_n = n\mathbb{Z}_{\geq m}$ for $n,m \in \mathbb{Z}$. Consider the claim C: For all $n$, if $x,y$ is in $A_n$, then ...
-2
votes
0answers
32 views

Translate the following english sentences into predicate logic language [on hold]

a) A computer system is intelligent if it can perform a task which, if performed by a human, requires intelligence b) A program cannot be told a fact, then it cannot learn the fact
1
vote
1answer
50 views

Prove by Natural deduction that $\lnot\exists xP(x)\rightarrow\forall x\lnot P(x)$

I got this problem: Prove by Natural deduction in First Order Logic that $\lnot\exists xP(x)\rightarrow\forall x \lnot P(x)$ I tried to prove it using the Contradiction Theorem but I got ...
2
votes
0answers
29 views

Example of language $\mathcal{L}_1$ and set $\Gamma_1$ s.t. $\Gamma_1$ is Henkin but not consistent

Question: Give an example of language $\mathcal{L}_1$ and set $\Gamma_1$ of $\mathcal{L}_1$-formulae such that $\Gamma_1$ is Henkin but not consistent Answer: Let $\mathcal{L}_1$ be arbitrary and ...
2
votes
2answers
57 views

Vacuously true? Prove or disprove that for every theory $T$, if $T$ is not satisfiable then for every $\phi$, $T \vdash \phi$

Is it vacuously true? Prove or disprove that for every theory $T$, if $T$ is not satisfiable then for every $\phi$, $T \vdash \phi$. If $T$ is not satisfiable, then there is no structure ...
1
vote
2answers
37 views

Prove or disprove that for theory $T$, $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$.

Prove or disprove that for theory $T$, $T \vdash (\phi \rightarrow \psi) \iff T \cup \{\phi\} \vdash \psi$. This seems quite right, but I don't know how to prove it. So lets start with ...
1
vote
1answer
34 views

Can a sum of a nonprincipal ultrafilter and a principal ultrafilter be equal to the nonprincipal ultrafilter?

If $ \mathcal U$ is a nonprincipal ultrafilter and $\mathcal V$ is a principal ultrafilter, can $ \mathcal U \oplus \mathcal V$ be equal to $\mathcal U$ ?
-2
votes
1answer
21 views

FOL formula and check valididty of this? [on hold]

I think the following is logically valid, but my TA says it's not logically valid. $ \forall x (A(x) \to B(x)) \to ( \exists x A(x) \vee \exists x B(x)) $ Who Can Clarify me about this Formula ?
-4
votes
0answers
35 views

R.E set and Recursive Set, A Confusing Axioms !?!? [on hold]

I want to check true or false of the following two axioms. who can help me or add some hint: I) $ A=\{x \mid \Phi_x\text{ is not one-to-one function} \}$ is an r.e set. II) if $A$ is an r.e ...
3
votes
1answer
25 views

Functional completeness for a ternary operator

If I define a ternary logical connective $\clubsuit(a,b,c)$ by the following truth table: \begin{array}{ccc|c}a&b&c&\clubsuit(a,b,c)\\\hline ...
2
votes
1answer
28 views

Models of Linear Logic

I am looking for an introduction to the model theory of Linear Logic. Can you recommend any clear introductions? I am particularly interested in those models that regard coherence spaces.
0
votes
1answer
19 views

Give an L-formula ϕ4(x) that defines the interval [1,√2) ⊂ R in M.

Let L = {+, · P} where + and · are binary function symbols and P is a unary predicate symbol, and let M be an L-structure where its domain |M| is the set R of real numbers, + and · are the usual ...
-3
votes
0answers
65 views

logic. Decide whether the following sequent is valid. [on hold]

Decide whether the following sequent is valid. Justify any claims. You may freely quote results from the Propositional Calculus. ((∃x) G(x)) ⇒ ((∃y) H(y)) ⊢ (∃x)(G(x) ⇒ H(x))
0
votes
2answers
23 views

Give an L-formula ϕ(x, y) that defines the less-than relation < over R in M.?

Let L = {+, ·, P} where + and · are binary function symbols and P is a unary predicate symbol, and let M be an L-structure where its domain |M| is the set R of real numbers, + and · are the usual ...
2
votes
2answers
54 views

What is a theory and what is its extension

As I understand, a theory is a set of sentences which are closed under some notion of deduction (i.e., applying deduction rules to the sentences of a theorem does not produce any new sentences) ...
2
votes
0answers
31 views

is 2nd criterion of inference satisfied for the restrictions on rules governing quantifiers

these two criteria are mentioned in patrick suppes book- intro to logic. then to account for criterion 1 , some rules of restrictions on quantifiers are given. But about criterion 2, how do we know ...
0
votes
1answer
23 views

is criterion of eliminability and criterion of non creativity independent

In introduction to logic by Patrick suppes, in Theory of definition 2 criteria are given, criterion of eliminability and criterion of non creativity. So if any formula is eliminable it should also be ...
1
vote
1answer
43 views

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable

Show $(\mathbb{Z}, +, \cdot, 1, 0 )$ is not R-decidable It gives the hint to use $x \in \mathbb{N} \leftrightarrow \exists x_0 \exists x_1 \exists x_2 \exists x_3(x \equiv x_0 \cdot x_0 \wedge x_1 ...
1
vote
2answers
37 views

show the set of valid second-order $\emptyset$-sentences is not R-enumerable

show the set of valid second-order $\emptyset$-sentences is not R-enumerable this would have the empty symbol set i.e. $S = \emptyset$ so it would be sentences that are universally or existentially ...
1
vote
2answers
42 views

where to begin with mathematical logic- text suggestions

My name is battlefrisk and I intend to pursue a career in either operations research or artificial intelligence. I have only taken a single class on logic, and I am considering buying a text on the ...
3
votes
1answer
64 views

Relationship between $S$ and $S^{-1}$

This is one of the problem I have been solving in Velleman's How to Prove book: Suppose $R$ is a relation on $A$, and let $S$ be the transitive closure of $R$. Prove that if $R$ is symmetric, ...
3
votes
2answers
72 views

Why is the implication “If pigs could fly, I'd be king” a true implication? [duplicate]

Let $P$ = "Pigs can fly" and $Q$ = "I'm king". Apparently, there's a rule stating that $P \implies Q$ is true, if $P$ is false. In this example, $P$ is indeed false, because pigs cannot fly. But how ...
2
votes
0answers
36 views

Probabilistic Logic

I was wondering if there is any system of logic that has been worked out that explicitly uses probabilistic notions at its foundation. It would include ideas like as a first principle, all statements ...
2
votes
0answers
28 views

Expressing quantifier free $\mathcal{L}_{PA}$-formulae $\varphi(y,\vec{x})$ with polynomials

I'm stuck at the following exercise: I want to show that for every quantifier-free formula in the language of $\mathsf{PA}$ there are polynomials $P(y,\vec{x}),Q(y,\vec{x})$ such that for all ...
2
votes
1answer
76 views

for all $x$, $P(x)$ implies there exists $x$, $P(x)$?

$$\begin{align*} \big[\forall x\,P(x)\to\exists x\,P(x)\big]&\iff\left[\big(\neg\forall x\,P(x)\big)\lor\exists x\,P(x)\right]\\ &\iff\exists x\,\neg P(x)\lor\exists x\,P(x)\;, \end{align*}$$ ...
8
votes
0answers
136 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need ...