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
2answers
22 views

Convert form form CNF to DNF

i have few question about converting forms to DNF, CNF and from CNF to DNF. 1) How can i convert this to DNF $(p \vee q) \wedge (q \vee \neg r) $ 2) How can i convert this to CNF $(p \wedge q) \vee ...
-1
votes
1answer
59 views

Does $\mathcal{P}(\mathbb{N})$ contain infinite sets?

I know that $\mathcal{P}(\mathbb{N})$ is infinite and uncountable. However, is the power set of the natural numbers considered to contain only finite sets of natural numbers, or infinite ones as well? ...
0
votes
2answers
79 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
8
votes
2answers
168 views

Why do we know that Gödel sentences are true in the standard model of set theory, but do not know if the continuum hypothesis is?

By what methods can we identify sentences that are true in the standard model of set theory, but not in other models? In particular, how do we prove that Gödel sentences are true in the standard ...
2
votes
1answer
90 views

A math puzzle about slow clock

You have the misfortune to own an unreliable clock. This one loses exactly 20 minutes every hour. It is now showing 4:00am and you know that is was correct at midnight, when you set it. The clock ...
0
votes
2answers
46 views

If $P$ is true then not $Q$

I'm trying to solve the following problem: "If this sentence is true then tomorrow will not rain". tomorrow will rain tomorrow will not rain the sentence is a paradox What I thought is: $P ...
-2
votes
2answers
44 views

Problem on elementary logic and set theory

Let A and B be sets with B is a subset of A. Prove that A \ (A\B)=B. I start by saying that suppose x is in A \ (A\B). By definition, x is in A and X is not in (A\B) . However, x is not in A\B ...
0
votes
3answers
38 views

complete the proof for this statement

$$\forall x \in \mathbb{R}, x \neq 0 \implies \frac{1}{x^2\:+3}\:<\:\frac{4}{5}\: $$ I thought of doing the contrapositive but not sure what to do next. $$ \frac{1}{x^{2\:}+3}\:\ge ...
1
vote
3answers
67 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 ...
2
votes
1answer
47 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
30 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
38 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
35 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
33 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
1answer
77 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
33 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
22 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
31 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
44 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 ...
-1
votes
0answers
32 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
276 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
146 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
165 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
47 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 ...
2
votes
2answers
72 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
62 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
29 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
27 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
4answers
74 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
42 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
27 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
38 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
45 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
97 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
53 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
58 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
48 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
1answer
31 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
31 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
95 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
30 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
69 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
98 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
23 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
36 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
54 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. ...
0
votes
2answers
36 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
55 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
34 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, ...