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)

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
26 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
51 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
68 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
35 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, ...
0
votes
1answer
68 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
20 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
31 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
71 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 ...
0
votes
1answer
54 views

Proving “If $P$ and $Q$ then $R$”.

I want to prove the statement: If $P$ and $Q$ then $R$. I have proved the statement: If $P$ then $R$. I am done. Right? I want to prove the statement: If $P$ or $Q$ then $R$. I have proved the ...
2
votes
2answers
53 views

Predicate logic by resolution

I've been trying to study logic lately, as part of my AI course, and I've been going through some old, simple exam questions from my school. There is one question about resolution in particular that I ...
0
votes
1answer
38 views

When representable functions are recursive

I'm trying to show the following statement: A representable function in a true, effectively axiomatizable theory is recursive. I'm missing one step in my proof: I need to show that the relation: $ ...
0
votes
2answers
35 views

Isomorphism of a theory

So, I'm preparing for an exam and there are various examples regarding isomorphism, what I don't get at all. I don't seem to be able to grasp the idea of isomorphism. Could you explain please how does ...
1
vote
1answer
30 views

Finite extension of decidable theory is decidable

Exactly what it says on the tin. I'm trying to prove that if T2 is a finite extension of decidable theory T1, then T2 is decidable.
0
votes
0answers
25 views

Logic - “Small model property” for a signature with only binary predicates

The Lemma - Small Model Property says that if a monadic formula phi (i.e. over a monadic signature - contains only constants and (monadic) unary predicates) with k unary predicates is satisfiable, ...
3
votes
3answers
49 views

Is $\Diamond (p \rightarrow q) \rightarrow (\Diamond p \rightarrow \Diamond q)$ valid in K?

The modal logic K is the weakest normal modal system, comprised by classic logic augmented by (K), the necessity distribution axiom schema: $$\Box (\alpha \rightarrow \beta) \rightarrow (\Box \alpha ...
39
votes
9answers
3k views

Does mathematics become circular at the bottom? What is at the bottom of mathematics? [duplicate]

I am trying to understand what mathematics is really built up of. I thought mathematical logic was the foundation of everything. But from reading a book in mathematical logic, they use ...
2
votes
2answers
61 views

Explanation on the symmetry between identity axiom and cut rule

In Proofs And Types at the beginning of 5.1.4 Girard says that the identity axiom is somewhat complementary to the cut rule, more specifically 'The identity axiom says that $C$ (on the left) is ...
3
votes
1answer
61 views

Are all models of Peano arithmetic elementary equivalent?

By Löwenheim-Skolem we know there are models of (first order) PA that are not isomorphic to the standard model, but are elementary equivalent to it, i.e. they satisfy the same set of first-order ...
1
vote
2answers
28 views

Axiom of separation for $n$ tuples or $n$ place predicates

The axiom of separation seems to only work when you are using an arity 1 type predicate, how then can we form relations? I know the power axiom allows for you to work with a set of subsets and in turn ...
2
votes
2answers
42 views

Need help with checking whether a predicate logic formula is a tautology.

I have an example like this, and I don't know how to solve it (check if is tautology): $\left(\exists_{x} \forall_{y}: q(x,y) \Rightarrow \forall_{y} \exists_{x}:q(x,y)\right)$ So the question is how ...
5
votes
1answer
167 views

Since arithmetic has a model (thus it is consistent) why care if consistency can't be proved?

Since arithmetic has a model, the numbers as we know them, it is consistent. Why do we care if consistency can't be proved within arithmetic? Do I miss something, ie in what we can consider a model?
1
vote
1answer
61 views

Introduction to Symbolic Logic: 'Understanding Symbolic Logic, 2nd Edition,' by Virginia Klenk, Page 294

I read this passage in my textbook: ...if there is a counterexample in a domain with $m$ individuals, then there is also a counterexample in all larger domains. It follows by contraposition (and ...
6
votes
0answers
56 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
0
votes
2answers
26 views

How do you find the minterm list of a boolean expression containing XOR?

Let's say I have a boolean expression, such as F1 = x'y' ⊕ z . How do I go about finding the minterm list for that expression? The method I've tried is to take each term, such as x'y' and z, ...
5
votes
2answers
136 views

A Knight and Knave Problem

There are $69$ people in a room, of which $42$ are truth-tellers (they always tell the truth) and the rest are liars (they can lie or tell the truth). You are allowed to ask any person $A$ whether ...
3
votes
0answers
79 views

How can temporal and epistemic logic be combined?

Recently I read all kinds of work from logic scientist in which epistemic logic was the main topic. Where epistmic change refers to change in knowledge of some agent in a multi-agent system (in a ...
2
votes
1answer
62 views

Does semantic inconsistency guarantee syntactic inconsistency?

I'm wondering about the possibility of circumventing the problem of incompleteness posed by Roger Penrose in his book "Shadows of the Mind". It occurred to me (and, Googling has revealed to me, ...
1
vote
1answer
16 views

Constructing a tautology given a set $\Sigma \subset $Prop(A) with special properties.

I am trying to follow Logic Notes of Lou Van Dries and I am stuck at a particular question in propositional logic. Assuming $A$ is any set and Prop$(A)$ is the set of propositions on $A$. The ...
2
votes
2answers
66 views

Logic vs. type system

What's the difference between logic (in a narrow sense, i.e. a logical system such as ZOL, FOL, etc.) and type system? I will sketch my understanding of this -- please correct if I err. Under ...
0
votes
1answer
36 views

Proof that given an empty vocabulary, P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not definable.

Hi there i would like to prove this: Given an empty vocabulary L ( by empty I mean L = $\emptyset$), the property P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not ...
-3
votes
4answers
78 views

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$ [closed]

Prove that $(\neg p \wedge \neg q) \vee (p \wedge q) \equiv (\neg p \vee q) \wedge (\neg q \vee p)$. I need to prove it by using equivalent sentences.
2
votes
1answer
29 views

Modal Logic: ◊-Distribution

It's a theorem of K that $\diamond$ distributes to disjuncts and vice versa: $$\diamond(p \lor q) ≡ \diamond p \lor \diamond q$$ Does it distribute to negated disjuncts? Is the following a licit ...
0
votes
1answer
77 views

What is the arithmetic flaw/contradiction in The Paradox of the Knower?

I have linked and quoted from an article below, he states that there is some elementary contradiction based upon simple logic/arithmetic; I am failing to see the contradiction. Where/what is the ...