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)

1
vote
1answer
37 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
30 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
25 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) ...
0
votes
0answers
7 views

VC-dimension for conjunctions with negations

I need any hint in the following problem. Let $\mathcal{F}_k$ be a set of all possible conjunctions of binary variables $x_1, \dots, x_k$ and their negations. How could I prove that ...
1
vote
1answer
27 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
61 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
53 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
67 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
24 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
31 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
38 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
29 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
43 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
53 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
61 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
48 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
28 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
56 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
36 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$ ?
-1
votes
1answer
20 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 ?
-3
votes
0answers
33 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
42 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
70 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
35 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 ...
1
vote
0answers
25 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
134 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 ...
1
vote
1answer
79 views

When two theorems are equivalent? [Formal definition]

I understand that two mathematical statements (theorems) are equivalent when one can prove any of the statements by using the other one. Is there a formalism for such a description?
1
vote
1answer
50 views

Identify the type of fallacy

"Mohan is a student and he is hardworking. Therefore, all students are hardworking." Is the fallacy committed here that of converse accident or of composition? From what I understand, it is the ...
0
votes
1answer
31 views

Non-empty intersection of specific sets

For any set Y (to begin with, it may be countable), given a collection of relations $$R = \{R_y \subseteq \{0,1\}^Y \mid y \in Y\},$$ having the finite intersection property and such that for ...
0
votes
1answer
39 views

What does “resolve away” exactly mean in propositional logic?

I have never had logic classes so I always struggle with the assignments that concern this interesting field. I was reading the slides about resolution theorem proving and there was a step-by-step ...
0
votes
0answers
43 views

Math, logic symbol for “instance of”

I saw a discussion of a possible symbol for "example," but I need "example/instance of." There is of course $a \in S$ which is a is a member of/in S, but is there a specific way of stating $a ...
1
vote
1answer
22 views

Prove $\vdash\forall x(\alpha\to\beta)\to(\exists x\alpha\to\exists x\beta)$

I want to show that: $\vdash\forall x(\alpha\to\beta)\to(\exists x\alpha\to\exists x\beta)$ I started my deduction as follows: $\vdash\forall x(\alpha\to\beta)\to(\forall ...
2
votes
1answer
30 views

Are the following logical statements equal? Solution verification

We were requested to rewrite the following statement: \begin{equation*} ((\phi \rightarrow(\psi \lor \lnot X)) \land (\phi \rightarrow (\psi \land X))) \end{equation*} using $\exists, \land, \lnot $ ...
1
vote
3answers
51 views

How is “p implies q” same as “q unless not p”?

I want to know how is "p implies q" same as "q unless not p"? ie how is "$p\Rightarrow q$" same as "$q$ unless $\neg p$" ?