Questions about logic and 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
3answers
43 views

Find an equivalent to $(p\lor q) \to (p \lor r)$

I need some help regarding solving a logic. The question is to find an equivalent to the following logic. $(p\lor q) \to (p \lor r)$ Thanks in advance for help.
0
votes
2answers
50 views

How to find the equivalent formulas of $\neg ((p\land q) \to (p \land r))$ [closed]

I have following formula: $\neg ((p\land q) \to (p \land r))$ I need to find equivalent formulas of above expression. Thanks in advance for the help.
2
votes
1answer
36 views

What does this negation on both sides of K mean: A = ¬ K ¬

What does this negation on both sides of K mean: (A = ¬K¬) ? I'm not sure if it's a typo, as there are some errors in this paper (Hong et al.). Hong, Zhi Ling, and Mei Hong Wu. "Constrained ...
5
votes
4answers
297 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
6
votes
1answer
76 views

Who first discovered that some R.E. sets are not recursive?

Who first discovered that some recursively enumerable sets are not recursive, or equivalently that some semidecidable sets are undecidable? And in what context? Was the earliest formulation of this ...
0
votes
3answers
40 views

How to write $a|b \wedge ((a=0 \wedge b=0) \vee (a\ne0 \wedge b\ne0))$

How can I write the expression $$a|b \wedge ((a=0 \wedge b=0) \vee (a\ne0 \wedge b\ne0))$$ concisely and clearly in English? A direct translation yields $a$ divides $b$ and either {$a$ and $b$ ...
1
vote
1answer
101 views

Where do the topics covered in Lewis Carroll's 1896 book “Symbolic logic” fit in the modern mathematical curriculum?

Where do the topics covered in Lewis Carroll's 1896 book "Symbolic logic" fit in the modern mathematical curriculum? And what is the modern substitute or notation? It appears to me that all it covers ...
0
votes
0answers
25 views

When is the higher-order theory of a model categorical?

I'm interested in (classical) type theories $L$ with the following property. For $M$ any model of $L$ (in Set), let $T(M)$ be the type theory of $M$, i.e., the strongest extension of $L$ satisfied by ...
3
votes
1answer
58 views

Is there a way to tell how many different ways you can prove a theorem?

Consider the question. Given the nature of a sentence $S$, it there any way to tell how many different ways you can prove this sentence? Proofs are not distinct if we have a situation such as: $P ...
2
votes
2answers
46 views

What is the position of “exclusive or” in order of precedence for logical connectives?

In propositional logic the order of precedence I have found for the logical connectives is $\neg$ $\land$ $\lor$ $\Rightarrow$ $\Leftrightarrow$ Where do I have to put the exclusive or $\dot\lor$ ...
3
votes
0answers
25 views

Let $h: A \to B$ be a weak homomorphism. Is h$[A]$ a substructure of $B$?

A little bit more precise: let $\mathfrak{A}$ and $\mathfrak{B}$ be two structures. Define a weak homomorphism as a function $h: \mathfrak{A} \to \mathfrak{B}$ such that the folowing conditions are ...
-2
votes
1answer
73 views

D={ $ deg_T (A) | A \subseteq N$} Problem [closed]

Dear friends I wanted to ask the question that already asked 2 times but it's on-hold and after few days deleted, but I didn't get any answer. I try to solve it but confused. I don't know anything and ...
0
votes
0answers
23 views

Logical implication which is also known as rules of inference.

What is logical implication?? This is not a conditional connective -> . This is also known as rules of inference. Please explain it properly.
1
vote
1answer
61 views

set theory, Incompleteness and axiomatic systems

Is the number of theorems that can be proved (decidable) within a certain set of axioms (for instance ZFC) is finite or infinite ? in other words, are we going to fully exhaust that set of axioms ...
3
votes
1answer
34 views

Why is the assumption needed in this conditional introduction?

In the first derivation detailed here, why must we include a subderivation with $P$ as an assumption? We can derive $Q$ (4) from $S \land Q$ (2) without the help of $P$ (3); and then since we have ...
6
votes
1answer
63 views

Unique decomposition of wffs when left and right parentheses are indistinguishable

I'm working through Enderton's book A Mathematical Introduction to Logic 2nd Edition for self study. Section 1.3 Exercise 7 Suppose that left and right parentheses are indistinguishable. Thus, ...
-1
votes
3answers
92 views

Natural deduction from premise ¬(¬p∨¬q) to conclusion p∧q [closed]

What's the natural deduction of this exercise? Premise: ¬(¬p∨¬q) Conclusion: p∧q I think we should start with a Conjunction Introduction of p∧q like this: ¬(¬p∨¬q) ...
1
vote
1answer
45 views

Consistent Set of Sentences is Consistent in Expanded Language

Suppose that we have a set $\Phi$ of sentences over a first-order language $\mathcal{L}$ and that $\Phi$ is consistent. Suppose we have another first-order language $\mathcal{L}'$ such that ...
1
vote
3answers
53 views

The negation of an implication statement

$$\neg(A \longmapsto B)\lor \neg B$$ Does this this expression simplify to:? $$\neg A\longmapsto\neg B\lor \neg B$$ Which further simplifies to: $$\neg A\longrightarrow\neg B$$
2
votes
0answers
42 views

Propositions as sets of witnesses

Under the propositions-as-types paradigms, a proposition is identified with the type of all its proofs. From a more classical perspective (and assuming the full-blown axiom of choice), it sometimes ...
6
votes
4answers
262 views

A question regarding ❋166.44 in Whitehead & Russell's Principia Mathematica

In the first step of Dem, I wonder how $\Sigma ‘\times P^{;}Q$ is transformed into $\Sigma‘ \Sigma^;(P \overset{\downarrow}{.,})\dagger^; Q$. Thanks,
2
votes
0answers
45 views

Path-independent contour integrals and how to define them

If a contour $C$ is parameterized by $z(t): [a, b] \to \mathbb{C}$, then we define $$ \int_C f(z) \, dz= \int_a^b f(z(t)) \, z'(t) \, dt.$$ If the contour integral on the left side is equal to some ...
1
vote
2answers
46 views

2 formulas that are satisfied by the same finite structures

Let $A$ and $B$ be closed formulas in first order logic language. Assume that for any finite structure $M$: $$ M\models A \iff M\models B $$Prove or disprove: $A$ and $B$ are logically equivalent. I ...
1
vote
3answers
92 views

In Godel's first incompleteness theorem the Godel sentence G is true otherwise it contradicts itself, however its truth implies it is not provable .

How can this be? I understand there are two basic definitions of truth in mathematics, one being the formalist definition which includes excluded middle and the second form being the intuitionist in ...
2
votes
1answer
52 views

Simplifying ambiguous statements

I have been working on the following question from Velleman's How to prove book: Let S stand for the statement “Steve is happy” and G for “George is happy.” What English sentences are ...
3
votes
2answers
37 views

Forming up Complex logical forms from simple one

This is another problem I have been working from Velleman's How to prove book. Let P stand for the statement “I will buy the pants” and S for the statement “I will buy the shirt.” What English ...
1
vote
2answers
92 views

Is it possible to prove that the encoding of existentials in System F is valid?

In Girard's Proofs and Types, under item 11.3.5, second-order existential quantification is encoded in System F using universal quantification as follows: $$ \Sigma X.V \equiv \Pi Y. (\Pi X.(V \to ...
2
votes
1answer
35 views

Compactness and Arithmetic Confusion

Let $T$ be some theory capable of arithmetic and construct a provability predicate (which we will call $Prb_T$). Let $\mathbb{N} \models T$. Expand our language to include a new constant symbol $c$. ...
0
votes
3answers
49 views

Logical form of Either and Neither: Alice in room

This is one of the problem I have been working: ...
3
votes
2answers
133 views

Gödel's incompleteness theorems

In the last paragraph of Stephan Hawking's speech "Godel and the End of the Universe", he mentioned "... I'm now glad that our search for understanding will never come to an end, and that we will ...
1
vote
2answers
38 views

Method of verifying answers

I have been reading Velleman's How to prove it book and solving problems of the exercise in it. What concerns me is that I cannot verify if actually my solutions are correct. The book has only ...
2
votes
1answer
54 views

Use a proposition to prove another proposition

I'd like to ask for help with an exercise from Solow - How to Read and Do Proofs(3.16). I've tried to get through it but I can't make the proper connection between the two properties. I figured that ...
8
votes
2answers
499 views

Godel Incompleteness Theorem

Is there any mechanism or algorithm where one can generate mathematical statements/problems that are undecidable, i.e their proof is independent, from a certain set of axioms ?
-1
votes
1answer
59 views

How to rewrite and simplify sequence of negative words? [closed]

What's the general method or algorithm or procedure? I bold them below. I ask here because I venture that these sentences replete with confusing negative words, can be pruned and streamlined, with ...
0
votes
3answers
53 views

Logically proving that the smallest factor of an integer is prime

I argued it as follows, let $p, q, r$ and $s$ be predicates $p$: "$m$ is divisible by $k$" $q$: "$k$ is divisible by $n$ ($n < k$ and $m$ is divisible by $n$) " $r$: " $k$ is the smallest factor ...
4
votes
1answer
75 views

The “converse” of $P\rightarrow(Q\rightarrow R)$

As everyone know, even when reading mathematics books, a paragraph written in natural language contains much more information than just its purely logical translation. For my next tutor session, I am ...
5
votes
2answers
67 views

What is a finitary proof?

I started reading "mathematical logic", by J.R.Shoenfield, but I cannot quite understand a sentence in the very first chapter: Proofs which deal with concrete objects in a constructive manner are ...
0
votes
1answer
98 views

Natural deduction, from premise: $\,\lnot p \lor \lnot q,\,$ to conclusion : $\,\lnot(p \land q)$

What's the natural deduction of this exercise? Premise: $\lnot p \lor \lnot q$ Conclusion: $\lnot(p\land q)$ I must have something like the following, but I do not know how to start.
-2
votes
2answers
72 views

Creating Truth tables [closed]

What is the truth table for the logical expression? $$ (p \land (p \to q) \land r) \to ((p \lor q) \to r) $$ Frankly, I'm lost.
2
votes
1answer
77 views

Many to one Reducible & Polynomial time

we know that If $A \le_p B$, then $A$ can be reduced to $B$ in polynomial time. we know that If $A \le_m B$, then $A$ is many to one reduction to $B$ . can we deduce that: if $A \le_m B$ then $A ...
0
votes
1answer
75 views

Why is $x\mapsto x$-th prime number a partial recursive function?

I think that partial recursive functions correspond to all computable functions. Thus, if we can write a computer program to represent a function, the function is partial recursive. In computability ...
0
votes
2answers
98 views

Is the formula $ \forall x (A(x) \to B(x)) \to ( \exists x A(X) \vee \exists x B(X)) $ logically valid [closed]

Recently I studing on logic. I try to solve some first order formula that not valid. Why the following first order formula is not logically valid? every expert would please help me? 1- $ \forall x ...
4
votes
3answers
108 views

Deriving $A \rightarrow ( B \rightarrow C ) \rightarrow ( ( A \rightarrow B ) \rightarrow ( A \rightarrow C ) )$ in the sequent calculus

I need to prove the following theorem: $A\to (B\to C) \to ((A\to B) \to (A\to C))$ using the sequent calculus method. Using the rules: $$ G, A \Rightarrow B,D \over G \Rightarrow A \to B , D ...
-1
votes
1answer
64 views

Undecidability of First Order Logic [closed]

friends! I read in Ebraham's Outline of Logic that first order logic is undecidable because it lacks an algorithmic procedure which reliably detects invalidity in every case. It is undecidable ...
0
votes
1answer
34 views

What does it mean for a model to have 'the less cardinal possible'?.

I've encountered this question, and I'm not sure if my interpretation is right because if it is, seems like there would be very trivial models (and there would no problem at all). Ex 1: $\{\forall x ...
4
votes
1answer
75 views

How can I imagine a model of $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$?

Gödel's second incompleteness theorem states that if $\mathsf{ZF-Inf}$ is consistent, then $\mathsf{ZF-Inf} \nvdash \mathsf{Con(ZF-Inf)}$. Moreover, if $\mathsf{(ZF-Inf)} + \neg \mathsf{Con(ZF-Inf)}$ ...
0
votes
0answers
23 views

What is difference between logical implication and conditional statements? [duplicate]

I want to know that what is Logical implication? Hey i m a new user on this site. Please help me...May be this question may be repeated one but please answer me again... This is not conditional ...
-1
votes
1answer
69 views

The range of an increasing computable function relation is recursive [closed]

I read this post: A is recursive iff A is the range of an increasing function which is recursive, and also this tutorial on recursion theory. In the latter, I saw the following sentence: $A$ is ...
2
votes
1answer
38 views

Incompleteness theorem and regarding consistency of theory $T$

By Godel's incompleteness theorems, a formula expressing consistency of a theory that can contain Peano arithmetic cannot be derived or contained from/in the theory. Godel's completeness theorem ...
0
votes
1answer
66 views

Godel's completeness theorem and formula that states consistency of ZF

Godel's completeness theorem, in original formulation, says that every logically valid statement/formula has finite deduction of a formula. Now then there is Godel's incompleteness theorem. Would this ...