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
votes
0answers
13 views

Universum, interpretation few question.

i have few questin about predicate logic and interpretation : I have formula like this: 1) $(\forall x: \neg p(x) \vee q(x)) \Leftrightarrow \neg (p(x) \wedge q(x))$ No i must choose is either of ...
0
votes
3answers
57 views

Implies in a truth table, unclear. [duplicate]

In my textbook, we have the following truth table: $P$ true and $Q$ true means that "$P \implies Q$" is true. $P$ true and $Q$ false means that "$P \implies Q$" is false. $P$ false and $Q$ true ...
0
votes
0answers
27 views

define the “optimal” automatic theorem prover

my question is : is it possible to define in some way what should do an "optimal automatic mathematician" ? There are two points of view of an automatic theorem prover / automatic mathematician : ...
0
votes
1answer
23 views

Satisfiable formula only over even structares

In First order Logics, what formula can I cook up, that's satisfiable over all even structures, and only even structures. (even structure means it has an even number of elements in its domain).
0
votes
2answers
28 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
0
votes
0answers
23 views

Why aren't all NP-complete problems strongly NP-complete, if any NP problem can be reduced to an NP-complete problem

So we know that : (1). A problem is NP-complete if every other problem in NP can be reduced to it in polynomial time (2). A problem is said to be strongly NP-complete if a strongly NP-complete problem ...
1
vote
1answer
31 views

Setting Unknowns to 1

Suppose a square formation of troops 50 meters deep is marching with a dog in the middle of its back rank. The dog runs to the front of the formation, turns around instantaneously and runs back to ...
1
vote
2answers
61 views

How to prove that a statement is a theorem using Hilbert's system?

I'm looking for an actual step-by-step way of proving that a statement is a theorem using Hilbert's system. For instance: As can be seen from the above picture, the solution consists in a series of ...
2
votes
1answer
28 views

Derive a formula for the number of small square base pyramids required to create a bigger pyramid?

To quote from the problem statement: "Pyramids are built using smallest pyramids of "level 1", that are used as building blocks for higher levels. Stacking pyramids of "level 1" to create ...
0
votes
0answers
18 views

Formally define replacement operation for rules of replacement

I'm having some trouble formally defining non-uniform substitution the replacement operation for a rule of replacement in propositional logic. Based on the idea of "Non-Uniform Substitution" from here ...
0
votes
0answers
25 views

What is the relationship of the Liar Paradox and Gödel's sentence?

In both cases we get a negative result in a certain sense due to self-reference. Could Gödel's sentence be thought of as a representation of the Liar Paradox in the language of arithmetic? If that is ...
-2
votes
2answers
43 views

Universal instantiation another question why couldn't?

something like this: $ \exists x: p(x) \Rightarrow \forall x: p(x) $ $ \neg \exists x: p(x) \vee \forall x: p(x) $ $ \forall x: \neg p(x) \vee \forall x: p(x)$ So if i use here rule : universal ...
0
votes
0answers
28 views

Skolem normal form - difference form different thinking?

i found two tutorials which transfer this formula to Skolem form: $\forall x \exists y: \neg p(x,y) \vee \forall w \exists z: p(w,z)$ First case 1: $\forall x \exists y: \neg p(x,y) \vee \forall w ...
3
votes
1answer
233 views

Why does the Deduction Theorem use Union?

We have an initial set of premises $S$. We are given or observe or assume sentence(s) $A$ is/are true. We can then prove $B$. Formally, $S \cup \left\{A\right\} \vdash B$. Shouldn't it be an ...
2
votes
5answers
137 views

Rigorous proof of '${\{A \Rightarrow B}\} \iff {\{\neg B \Rightarrow \neg A}\}$' for a high school student

One method to prove the statement 'If A, then B' is to prove that 'If not B, then not A'. First time that I saw this method it was not (and still isn't) obvious. So I used a more obvious example to ...
1
vote
3answers
79 views

Prove that there are infinity many tautologies.

For this question I think I am suppose to use proof by contradiction, but I need some hints on how to proceed with the proof. Always if someone can give me a brief explanation on how proof by ...
2
votes
1answer
41 views

Basic First Order Logic Question

Which one of the following well formed formulae is a tautology? (A) $\forall x\exists yR(x,y)\iff\exists y\forall xR(x,y)$ (B) $[(\forall x\exists y(p(x,y)\Rightarrow R(x,y))]\Rightarrow ...
1
vote
0answers
43 views

How to translate set propositions involving power sets and cartesian products, into first-order logic statements?

As seen from an earlier question of mine one can translate between set algebra and logic, as long as they speak about elements (a named set A is the same as {x ∣ x ∈ A}). However I've stumbled upon ...
0
votes
1answer
58 views

Universal introduction - how exactly does it work?

How does universal introduction work? I have tried something like this : 1) $\exists x: p(x) \Rightarrow p(x) $ I'm using this rule and I'm getting something like this: 2) $\exists x: p(x) ...
1
vote
2answers
28 views

Confused on negation?

My textbook has the following (see Page 8 of Eccles's An Introduction to Mathematical Reasoning): Consider the following statement about a polynomial $f(x)$ with real coefficients, such as $x^2 + ...
3
votes
0answers
24 views

Question about Regularly Algebraizable Logics

I haven't found any posts related to Algebraic Logic, but I'll try anyway; here it is: Some notions: A logic is algebraizable when there is a class $K$ of algebras an there are structural ...
0
votes
1answer
40 views

Predicates spimple tautology or not. [on hold]

i'm not sure if am i doing it right. 1) $\exists x: p(x) \Rightarrow \forall x: p(x)$ <<--Tautology 2) $\forall x: p(x) \Rightarrow p(x) $ <<--- Here i can use instruduction universal ...
-1
votes
1answer
39 views

Prove that: $[\neg p \wedge (p \vee q)] \rightarrow q$ is a tautology by using laws of logic [on hold]

Please help me prove that $[\neg p \wedge (p \vee q)] \rightarrow q$ is a tautology by using the laws of logic.
0
votes
4answers
69 views

Proof to be tautology

$\forall x : (p(x) \wedge \neg q(x)) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x)$ The problem is: i know this is tautology but i don;t know how to proof it. Is anybody can help me?
0
votes
1answer
35 views

Proof of formulas in sequent calculus

Is there an algorithm for proof of formulas in sequent calculus, like resolution method? I'm especially interested in natural deduction. UPDATE Well, we have one scheme of axioms $$\Phi\vdash\Phi$$ ...
1
vote
3answers
23 views

Determine whether the following argument is valid

Premises: $p → r, q → r$, and $q ∨ ¬r$ Argument: $¬p$ I understand the answer but am having problems understanding how to construct this statement ie $(p → r)∧(q → r)∧(q∨ ¬r)$ where does the argument ...
1
vote
1answer
34 views

Propositional Logic Question

I have to convert an english sentence into a symbolic notation. I think I have this correct but I want to know if it is correct...I think it's right because I did it so that $P$ = "Brad went to the ...
0
votes
1answer
24 views

Task to prove consequence

I have two simple math logic tasks, which i try to solve using this rules http://integral-table.com/downloads/logic.pdf but i must be missing something. ⊢ (AvB) -> AB What i ve tried: AvB ⊢ AB ...
2
votes
1answer
44 views

What makes a logical expression false?

Assume that we are given a logical expression like $A$ and ($B$ or $C$) and $D$. The total evaluation of the expression is false and we know the value of each operand $(A,B,C,D)$. I need to develop an ...
3
votes
0answers
72 views

Is this a way to construct mathematics?(logic vs. set theory)

I recently asked a question about the fact that logic and set theory seems circular. link I got a lot of good and thoughtful answers, that probably explains everything, but I must admit I did not ...
2
votes
1answer
40 views

Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
0
votes
2answers
53 views

Prove $(p \rightarrow q) \land (r \rightarrow s) \implies ( \neg p \lor \neg r \lor q \lor s)$

$$((p \rightarrow q) \land (r \rightarrow s))\rightarrow ((p\land r)\rightarrow (q\lor s))$$ I have some problem with formula: $$(p \rightarrow q) \land (r \rightarrow s) $$ $$\equiv(\neg p \lor q) ...
0
votes
2answers
45 views

proof that power set A union B doesnt equal powerset A union powerset union B

Why is this equation: \begin{equation} \mathbb{P}(A \cup B) = \mathbb{P}(A) \cup \mathbb{P}(B) \end{equation} false with: $A = \{0\}$ and $B = \{1\}$? Are they not both $\{ \emptyset,0,1\}$?
0
votes
0answers
23 views

cnf: proving logical implication of satisfiability

I tried solving the below problem, but in the textbook there wasn't even an example how to solve a similar problem. All my ad-hoc attempts at solving it turned null. Can someone show me how to solve ...
0
votes
1answer
25 views

Hardness of index sets for computable structures

Suppose we have a computable structure $M$ and we want to show that its index set $I(M)$ is (many-one) $\Gamma$-hard for some complexity class $\Gamma$ (like $\Sigma^0_2$). To do this, we need to show ...
5
votes
2answers
87 views

Difference between 'true' and 'provable'

For a long time now I've been confused about the difference between truth and provability. I've also read questions like this but I still don't understand it. A typical example of my confusion is the ...
1
vote
2answers
26 views

Nested Quantifiers Doubt: “If $xy$ is equal to $x$ for all $y$, then $x=0$”

If $P(x,y,z)$ represents $xy=z$. Then represent the following statement using quantifiers,connectives etc. "If $xy$ is equal to $x$ for all $y$, then $x=0$". The answer given is $\forall x[ \forall ...
1
vote
1answer
51 views

Cohen forcing factoring

I start from $M$ a transitive countable model of $ZFC + \mathbb V= \mathbb L$ and I add a single Cohen generic $G$. Now if $A \in M[G]$ is also Cohen generic over $\mathbb L$ and $M[A] \ne M[G]$, can ...
3
votes
0answers
87 views

What does “Turing-complete” really mean?

People talk about various programming languages or computational models being "Turing-complete." But what does that technically mean? The technical definition is buried under tons of informal ...
2
votes
0answers
21 views

Determine if the members of a set can be made to equal a given number

Is there an easy way to determine if some combination of addition, subtraction, multiplication, and division will enable the numbers in a set to equal a given number? For example, if I have the ...
2
votes
1answer
31 views

If $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable?

In propositional logic, if $\Sigma$ is finitely satisfiable, can both $\Sigma \cup \{ \phi\}$ and $\Sigma \cup \{ \neg \phi\}$ be finitely satisfiable? I proved that at least one of $\Sigma \cup \{ ...
2
votes
3answers
46 views

Logical Equivalence

Prove that p $\rightarrow$(q$\rightarrow$p) is logically equivalent to $\neg p$ $\rightarrow$(p$\rightarrow$q) without using truth table. It is easy to show that both the statements are tautologies. ...
-2
votes
1answer
36 views

Methods of Proof and Disproof [closed]

If $2b^2 – 3ab + 1$ is even, then $2a-b$ is odd, where $a,b \in \mathbb{Z}$. If $5x-y$ is divisible by $4$ and $2x+3y$ is odd, then $7x + 2y$ is odd, $7x+2 \in \mathbb{Z}$.
0
votes
2answers
34 views

Another basic Logic Question

Translate this statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and the domain consists of all people. a) ∀x(C(x) → F(x)) The answer given in the book is:"Every ...
0
votes
1answer
53 views

Very Basic Logic Question

Given a set $S=\{-1,0,-5,-4\}$.Then is the following proposition true? $\forall x, (x>0 \implies x^2>0)$.
2
votes
0answers
30 views

On Levy's formal definition of class terms

I've been reading Levy's Basic Set Theory and it has recently been drawn to my attention a certain problem with Levy's definition of formulas and terms in his extended language (section I.4.1) (well, ...
0
votes
1answer
56 views

Using Sequent Calculus to prove $\exists x_1 x_2 [ B ( x_1 , x_2 ) \rightarrow \forall y_1 y_2 B ( y_1 , y_2 ) ]$

I need to prove the validity of the following formula using the sequent calculus LK: $$ \exists x_1 x_2 [ B ( x_1 , x_2 ) \rightarrow \forall y_1 y_2 B ( y_1 , y_2 ) ] \text{.} $$ I already had a look ...
0
votes
1answer
18 views

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive?

Is $ R = \{ (A,B) \in \Omega² \quad| \quad A \land B \} \quad$ with $\Omega = \{ A\quad| $ A is a proposition $ \}$ reflexive? I assume that you have to consider untrue propositions, too. $A \land ...
6
votes
1answer
28 views

Proving consistency by constructing models? How and why?

A theory T1 can be shown to be consistent by describing a model for it. But usually the model is also described in words, using terms from some other theory T2. So unless T2 is also consistent this ...
3
votes
1answer
66 views

Are there weak versions of the axiom of choice equivalent to weak versions of Zorn's lemma and similar principles?

I recalled reading about other weaker forms of $AC$, for example countable choice, where we could make choices from a sequence $(S_{k})_{k \in \mathbb{N}}$ of non-empty sets. I also recalled mention ...