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
1answer
44 views

Complexity & Computation & Logic Problem [closed]

As i study for prepare to CS Final exam, i have some challenges. can i say all of following statements are true? 1) each infinite recursive set, is union of two disjoint infinite recursive set? 2) ...
1
vote
1answer
92 views

Prove that the disjunctions of all conjucts is a disjunctive normal form

Question: I am attempting the following exercise from An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof by Peter B. Andrews: X1408. Prove that if $\mathbf{A}$ is a wff ...
2
votes
2answers
112 views

Proving the roots of a polynomial are irrational

This is a homework question so I'm just looking for some guidance. Basically we are asked to write a step by step proof in the form of assume/then statements for: $\forall x \in \mathbb{R}, ax^2 + ...
2
votes
2answers
106 views

Gödel incompleteness theorem [closed]

Gödel incompleteness theorem states that any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.So what are some Gödel sentences about ...
2
votes
2answers
111 views

Proof of Sylow's theorem.

I read this proof of Sylow's theorem in Rotman's "An introduction to the Theory of Groups" and I don't understand what is the argument in the second paragraph (the one in the green box) for. Isn't ...
3
votes
2answers
51 views

Confused about the use of variables w/ logical quantifiers

Sorry if this is a really dumb question, but... After reading How to Prove it, I've become a little confused. On page 70, an example stating something similar to this is provided: $[\exists x P(x) ...
1
vote
1answer
41 views

law of implication

I'm trying to follow the solution of an exercise that asks to use rules of inference to show that something is true but I don't know how to go from step 2 to step 3: Step 1 $\quad \forall x((\lnot ...
2
votes
2answers
72 views

Is there a modal operator which distributes over the implication?

Is there any notable modal operator $\Box$, so that if $P,Q$ are proposition $$\left(\Box(P\implies Q)\right)\Leftrightarrow\left(\Box P\implies \Box Q\right)$$
0
votes
1answer
31 views

Does intuitionist logic deny diagonal argument?

Let us for example give an example of diagonal proof of uncountability of the set of real numbers $\mathbb{R}$. Would intuitionists accept this, or deny this? If they deny this argument, why would ...
0
votes
0answers
37 views

Undecidable sentence in Godel's incompleteness theorem? [duplicate]

At first I want to apologize to you for repeating my question, since I didnt get satisfying answer. And because answering to this question is very important to me, I have to repost this question. ...
3
votes
2answers
40 views

Contraposition in intuitionistic logic?

I read that contraposition $\neg Q \rightarrow \neg P$ in intuitionistic logic is not generally equivalent to $P \rightarrow Q$. If this is right, in what case can this contraposition ...
0
votes
1answer
33 views

$[\exists x \in U, P(x)] \implies [\forall x \in U, P(x)]$

I know this statement is not always true, but I'm having a hard time proving it. I'm also wondering what the difference between: $[\exists x \in U, P(x)] \implies [\forall x \in U, P(x)]$ and ...
2
votes
3answers
111 views

If $A$ is false, is $\neg A$ true without invoking law of excluded middle?

Let's say that we know that $A$ is false. We disallow the use of law of excluded middle. Then is it true that $\neg A$ is true? Add: How would "false" be (usually) defined in intuitionisitc logic and ...
5
votes
3answers
60 views

Contraposition and law of excluded middle

Does truth-equivalence of an $A \rightarrow B$ and contrapositive $\neg B \rightarrow \neg A$ rely on the law of excluded middle?
5
votes
1answer
66 views

Partial order on cardinalities without the axiom of choice

Cardinality can still be defined without choice, e.g. as equivalence class of equipotent sets, see Defining cardinality in the absence of choice. Injections define partial order on cardinalities by ...
4
votes
5answers
95 views

Book about different kind of logic

I'm searching for a book that talks about different kind of logic ( esoteric and particular one too ) and their uses and differences. Does such a book exist?
1
vote
0answers
36 views

What follows from Incompleteness about provability of partial correctness?

A colleague and I can't figure out what our professor is getting at with this question: What follows from the incompleteness theorems about the provability of partial correctness assertions? What ...
0
votes
1answer
40 views

Examples of non-trivial determiner formulas of trnsitive models of ZFC

Notation: For each $\{\in\}$-formula $\varphi(x_1,\cdots,x_n)$ and each $\in$-model $M$, define: $$\varphi (M)=\{(a_{1},\cdots,a_{n})\in M^{n}~|~\langle M,\in\rangle\models \varphi ...
0
votes
0answers
39 views

The Major Weaknesses in Ramified Type Theory

I am reviewing a paper on the major weaknesses of Ramified Type Theory in predicative second-order arithmetic. These four are listed as "weaknesses." But, I have my doubts. It seems at least that 3) ...
0
votes
2answers
121 views

Undecidable sentence in Godel's incompleteness theorem

In Godel's incompleteness theorem, the undecidable sentence is g: I am not provable. Ok. I accepted it and realized that in satandard interpretation it is true. So we found a true sentence which ...
2
votes
2answers
147 views

Is it Theoretically Impossible to Demonstrate that Set Theories Are Consistent?

I have to present on the main realist and non-realist arguments for/against set theory. According to one of my sources, it remains a matter of debate as to whether any of the set theories' (ZF, NF, ...
0
votes
1answer
35 views

conclusions/rules of inference

I need to find the relevant conclusion/conclusions from the following premises and explain the rules of inference used to obtain each conclusion from the promises: Problem: "All foods are healthy to ...
6
votes
2answers
247 views

Set theoretic realism

What are the main contemporary arguments for and against realism about set theory?
0
votes
1answer
72 views

Mathematical notation for expressing the top n elements

I would like to know what is the mathematical notation to express the top n elements. Look at the equation below. Here $x_w$ is a feature vector representing the contribution of a particular word $w$. ...
1
vote
1answer
39 views

Ramified Type Theory: Determining Orders/Levels

I understand how to determine order in unramified type theory. But, how do you determine order and level in ramified type theory (per Church's interpretation of Russell)? The example given in the ...
1
vote
1answer
71 views

How to define multiplication in addition terms in monadic second order logic?

How to define multiplication in addition terms in monadic second order logic? meaning, having natural numbers variables, N sub-groups variables, successor function, negations, "for every", "there ...
1
vote
2answers
94 views

Can we make recursion into an axiom schema?

The language of second-order arithmetic is (by definition) generated by a constant symbol $0$ and a unary function $S$. However, first-order arithmetic (hereafter $\mathrm{PA}$) famously requires a ...
2
votes
1answer
66 views

An extension of PA which is not true theory?

K is said to be a true theory if all proper of K are true in the standard model. Please show that there is an ω-consistent extension K of PA such that K is not a true theory. I think this is a ...
3
votes
2answers
89 views

Can a non-classical logic be used as a meta-logic to develop classical logic?

I have read much about non-classical logics such that paraconsistent logics , relevance logics , substructural logics , non-monotonic logic and so on. I think that the meta-logic logicians use to ...
1
vote
4answers
85 views

Why is “$P \Rightarrow Q$” equivalent to “$\neg Q \Rightarrow \neg P$”?

Why is "$P \Rightarrow Q$" equivalent to "$\neg Q \Rightarrow \neg P$"? I am trying to understand why this does always apply, in terms of pure logic. Can you please explain it to me?
0
votes
0answers
59 views

alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...
1
vote
2answers
149 views

Predicate calculus is not scapegoat theory ?!

A theory T is scapegoat if for every formula A with only one free variable there exist a closed term s such that T proves: (∃x(¬A(x)))⇒¬A(s) Why any predicate calculus is not scapegoat theory ? Please ...
3
votes
3answers
70 views

Is there any false case for that: $\exists x \in D, \forall y \in D, P(x, y) \implies P(y, x)$?

Is there any false case for that: $\exists x \in D, \forall y \in D, P(x, y) \implies P(y, x)$?\ I just can get the true case.\ How can we define D and P in a false case?\ Thx guys.
1
vote
2answers
59 views

why$(\forall x \in U, P(x)) \implies (\exists x \in U, P(x))$ is false?

may I have a complete proof of that "$(\forall x \in U, P(x)) \implies (\exists x \in U, P(x))$ " is false? thx guys
1
vote
1answer
41 views

Why this is true?$\exists x \in U, [P(x) \land Q(x)] \Leftrightarrow [(\exists x \in U, P(x)) \land (\exists x \in U, Q(x))]$ [duplicate]

$$ [\exists x \in U, P(x) \land Q(x)] \Leftrightarrow [(\exists x \in U, P(x)) \land (\exists x \in U, Q(x))] $$
0
votes
0answers
44 views

Proof: All recursive functions are arithmetic (logic)

So I'm trying to understand the proof of the following statement: > All recursive functions are arithmetic The proof begins with: "It is sufficient to show that all arithmetic functions satisfy ...
1
vote
3answers
76 views

$\neg(A\Rightarrow B) \iff A\land \neg B$

When considering the question: Rewrite the following using only the symbols $A, B, \lor, \land, \neg$ : $$\neg(A\Rightarrow B)$$ I do not understand how to interpret this and what method to ...
4
votes
1answer
34 views

Discrete 101: Validity of proof: Finding that p→q ∨ ¬r, q→p∧r, therefore p→r is invalid.

I'm sorry to bother with what apparently is a very easy Basic Logic question, but in my class'es notes there's an example that the professor probably explained in class: ...
1
vote
3answers
77 views

A problem in Logic

If A,B and C are statements such that C is true only if exactly one of A and B is true.If C is false then which of the following statement is true? $1$.If A is false then B is false. $2$.If A is ...
2
votes
2answers
96 views

How to prove that the law of the excluded middle is necessary?

This is a follow up question to this answer by Carl Mummert to the question whether every proof with contradiction can also be proved without contradiction. As Carl Mummert pointed out, there are ...
2
votes
1answer
26 views

Translation question from english to symbolic sentence?

Universe the real numbers. between any integer and any larger integer there is a real number. $\forall x \forall y$ $(x \in Z \wedge y \in Z \wedge y>x \rightarrow \exists k (x<k<y)$ ...
0
votes
1answer
37 views

Interchange quantifiers using the generalization theorem

On p. 111 (section 2.4) of Enderton's A Mathematical Introduction to Logic, immediately after the proof of the Generalization Theorem the following example is given $$\forall x \forall y \alpha ...
0
votes
3answers
40 views

Why does one modulus disappear when modded by another modulus?

I have the following equation: ( ((X + Y) mod 29) - Y) mod 29 = Z However, This can also be written as: ...
1
vote
1answer
25 views

Definition in satisfiability problem

While I was reading the PhD thesis of Balder ten Cate (2005). Model theory for extended modal languages. I found a theorem that says: 2.6.4Theorem. The frame satisfiability problem for modal ...
2
votes
2answers
42 views

Translating from english to a symbolic sentence?

How would I translate the following from english to a symbolic sentence with quantifiers. The universe of discussion is all real numbers. Every integer is greater than some integer. I did the ...
1
vote
1answer
75 views

Definition of a group written in formal logic

Is the formal logic in these axioms correct? A group is a nonempty set $G$ with a binary operation $*$ that satisfies the following axioms: $(a * b) \in G \; \forall \;a,b \in G$ $a * (b * c) = (a ...
1
vote
1answer
70 views

Fitch-Style Proof Help

I'm having some trouble solving a Fitch Proof, Here's how far I've gotten. Any Help is appreciated. Thank You
2
votes
1answer
56 views

Fitch-Style First Order Logic

I have been stuck on this proof for a while. Here's where I'm at: Goal $(\neg B \to \neg A) \leftrightarrow (A \to B)$ l 1. $A \to B$ ll 2. $\neg B$ lll 3. $A$ lll 4. $B$ Elim 1,3 ...
3
votes
3answers
103 views

Fitch-Style Proof

Hi I'm having trouble solving a Fitch Style Proof and I was hoping someone would be able to help me. Premises: $A \land (B \lor C)$ $B \to D$ $C \to E$ Goal: $\neg E \to D$ Thank You
0
votes
0answers
25 views

What are all of the computable or semidecidable properties of a first order sentence?

I'm interested in features of first order theories that can be used to differentiate first order sentences from each other in hopes there might be some way of measuring what makes one sentence more ...