Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

0
votes
1answer
8 views

Logical question with a balance and flour

The problem is: I have a balance of $9$ kgs of flour and two weights; $250$g and $50$g. In the matter of $3$ steps I have to divide them into $2$ bags of $7$ and $2$ kg, respectively. I know that ...
0
votes
2answers
31 views

How to demonstrate this tautology using equivalences?

I have this tautology $(P \wedge (P \rightarrow Q) \wedge (Q \rightarrow R)) \rightarrow R$ I couldnt prove it by using equivalences. Using Definition of implication and then using negative ...
0
votes
1answer
38 views

Natural deduction proof / Formal proof : Complicated conclusion with no premise

Find a formal proof for the following: $\vdash [(\neg p \land r)\rightarrow (q \lor s )]\longrightarrow[(r\rightarrow p)\lor(\neg s \rightarrow q)]$ As you can see. No premise to use. We have to use ...
1
vote
1answer
28 views

consistency strength

I am just beginning to read about consistency strength, and wondered if someone could clarify the relation between a two kinds of claims that I'm encountering. (1) A theory, T, proves the consistency ...
1
vote
2answers
36 views

What is exactly the difference between $\forall x \neg P(x)$ and $\neg \forall xP(x)$?

What is the difference between $\forall x \neg P(x)$ and $\neg \forall xP(x)$ or $\exists x\neg P(x)$ and $\neg \exists x P(x)$ ?
2
votes
1answer
46 views

Deductive logic counter-intuitive result

I am working on a small proof in deductive logic. Here is what must be proved: $(\exists x \in T \mid A \implies P(x)) \implies A \implies (\forall x \in T \mid P(x))$ To me that looks unprovable ...
1
vote
1answer
34 views

Proof that every non-empty subset of a woset (X, $\leq$) has a unique minimal element.

I want to prove that every nonempty subset of a woset (X, $\leq$) has a unique minimal element. What I’m looking for: clarification and/or hints. I want to solve it on my own, but this is all the ...
1
vote
2answers
935 views

Deriving Universal Modus Tollens

I'm asked to derive the validity of Universal Modus Tollens from the validity of Universal Instantiation and Modus Tollens. I'm new to this deriving/proving stuff, so I'm not sure if I'm doing it ...
-1
votes
1answer
43 views

prove using natural deduction $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$

so I ran into some trouble proving the following: $(R \rightarrow (P \rightarrow Q))\vdash (Q\rightarrow P) \lor (P \rightarrow Q)$ My approach thus far: Honestly I'm really stuck. So basically my ...
0
votes
1answer
13 views

Propositional variables in semantic equivalence

I'm learning the semantic equivalence rules/laws in propositional logic, but I'm confused by what the propositional variables in the rules are supposed to represent. For example, the associative ...
0
votes
2answers
59 views

Is it possible to have logic without syntax (with only semantic proof methods)?

In one paper I have read a note "Thus, unlike approaches which make use of full first order logic, unprovability of a formulae with respect to a agent specification can be shown by each of two ...
1
vote
1answer
22 views

Is solvability of diophantine equations over a p-adic field decidable?

As far as I understand, the decidability of solvability of diophantine equations over the rationals is an open problem. What about the decidability of solvability over a given p-adic field?
0
votes
0answers
24 views

Resolution calculus converting into set of clauses

Here is $T$: $a \lor \neg b$ $\neg a \lor (c \land d)$ $b$ I am suppose to use resolution calculus to prove that $T \models d \land b$ holds. As in the first step, we translate $T$ ...
45
votes
6answers
2k views

Proving the existence of a proof without actually giving a proof

In some areas of mathematics it is everyday practice to prove the existence of things by entirely non-constructive arguments that say nothing about the object in question other than it exists, e.g. ...
0
votes
2answers
433 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 ...
9
votes
1answer
105 views

What's an Isomorphism?

I'm familiar with the definition (inverses and bijections, preserving operations) in the context of groups and vector spaces, the hoeomorphism of topological spaces, and have some feeling for the ...
0
votes
0answers
16 views

Is (A v C) v B in conjunctive normal form?

I need T to be a set of clauses in conjunctive normal form. T = { (¬A ^ ¬C) → B } T = { ¬(¬A ^ ¬C) v B } T = { (A v C) v B } I 'simplified' it to T = { (A v C) v B }, is it in CNF? ...
0
votes
2answers
37 views

Algebraically transform logic expression

Algebraically transform: $\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$ to $\exists x\forall z(P(x) \wedge Q(y) \wedge \neg R(z))$ Justify each step with one or more ...
4
votes
1answer
30 views

No simplifying identities for any single nonzero number under addition.

Consider the structure $(\mathbb{R}, +, r)$, where r is a nonzero real number. Are the commutative and associative identities already sufficient to derive all universally valid equations in that ...
0
votes
1answer
559 views

Translate English sentences in statement logic

The task is: Give agood translationof the following puzzle into formal statement logic. ...
1
vote
2answers
2k views

Proving De Morgan's Law with Natural Deduction

Here is my attempt, but I'm really not sure if I've done it right; as I'm just about getting the hang of Natural Deduction technique. Have I done it correctly? If not, where did I make errors and ...
0
votes
1answer
39 views

sets with quantifiers

My professor wrote the following theorems and definitions on the blackboard. ...
0
votes
3answers
28 views

Prove that the following statements are all logically equivalent.

Prove that the following statements are logically equivalent: $A \subseteq B$ $A \cap B = A$ $A \cup B = B$ $B^c \subseteq A^c$ Here is what I have so far. I am not sure how ...
0
votes
2answers
20 views

Express each of the following statements as expression using quantified predicates and the domain“People.”

Here are two questions confused me. Express each of the following statements as expression using quantified predicates and the domain "People." 1) Some high school students are not enrolled in class ...
0
votes
0answers
34 views

Does Gödel sentence depend on numbering?

If we change Gödel's numbering definition of the $Prov$ predicate will change as well, but the meaning won't. How is that going to affect $G$? It seems to me like it will change as it is actually ...
2
votes
3answers
60 views

$a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent.

Suppose a,b,c and d are statements such that $a \Rightarrow b$, $b \Rightarrow c$, $c \Rightarrow d$, $d \Rightarrow a$. Argue that any two of these statements are logically equivalent. Hey, Im ...
1
vote
0answers
30 views

Is there a consistent arithmetically definable extension of PA that proves its own consistency?

Gödel's second incompleteness applies, for instance, to r.e. extensions of PA. I am wondering if it applies more generally to arithmetically definable extensions of PA. I see that there is a complete ...
2
votes
2answers
53 views

Write expressions w/out quantifiers (convert to AND/OR expressions)

A universe contains the three individuals $a,b$, and $c$. For these individuals, a predicate $Q(x,y)$ is defined, and its truth values are given by the following table: \begin{array}{c|ccc} ...
2
votes
2answers
45 views

Can you represent other logical operations using only $\neg$ and $\Leftrightarrow$ (not and equivalence)? [duplicate]

I can check on WolframAlpha for how to represent some logical operations using others, but I don't see anything for $\Leftrightarrow$. Is it because it is impossible? ...
0
votes
1answer
17 views

One place predicates and expressing them as strings of propositions

How do you express a quantified one-place predicate with a variable, such as ∃x[SING(x)] as a string of connected propositions?
3
votes
1answer
37 views

How many possible ways are there to make $\exists x \exists y \,\mathrm{Loves}(x,y)$ true, with five elements in the domain?

I'm a professional philosopher, not a mathematician, so I got myself stumped and hope somebody here will be kind enough to help me. When I'm explaining the universal and existential quantifiers to ...
2
votes
1answer
43 views

Definition of “substitutable” in Mathematical Logic

I'm reading Leary's Mathematical Logic text where it defines the phrase "substitutable" and most of it is sensible: $t$ is substitutable for $x$ in $\phi$ if $\phi$ is atomic. $\phi := ...
-1
votes
2answers
44 views

LOGICALLY EQUIVALENT: NAND and NOR [on hold]

Is there a way to represent "p NOR q" using "NAND" with logical equivalence?
0
votes
1answer
21 views

On the functional-completeness of the sheffer stroke

I have seen functional-completeness (in regards to boolean functions) defined as: A set X of truth-functions (of 2-valued logic) is functionally complete if and only if for each of the five ...
0
votes
2answers
364 views

Prove using a proof sequence and justify each step

Prove using a proof sequence that the argument is valid [ A --> (B ∨ C) ] ∧ B' ∧ C' --> A' I'm having some trouble figuring the proof out here. Here is what I have so far. Is this on the right ...
3
votes
1answer
58 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
3
votes
0answers
34 views

N body computer

Which mathematical questions can be answered with an n-body computer? An n-body computer is an arrangement of n-bodies moving under mutual gravitation that is prepared in an initial state to answer a ...
118
votes
11answers
13k views

Do we know if there exist true mathematical statements that can not be proven?

Given the set of standard axioms (I'm not asking for proof of those), do we know for sure that a proof exists for all unproven theorems? For example, I believe the Goldbach Conjecture is not proven ...
1
vote
3answers
61 views

Gödel's Incompleteness Theorem and Numerical Analysis

I am no expert in Mathematical Logic so I can't really express my question formally but I do hope that it will make sense. As far as I know the implication of Gödel's incompleteness theorem for ...
2
votes
1answer
26 views

Show that a sequence of elements each realizing an isolated type over the previous realizes an isolated type

I'm trying to prove the following result which seems correct to me, but I'm not sure how to proceed. The proposition is: Let $M$ be a structure, $A\subseteq M$, $(a_1,\dots,a_n)$ be a sequence ...
1
vote
1answer
34 views

Logical form of a set-theoretic statement.

From Velleman's 'How to Prove it' book, there is one statement - written below - of which I don't know how to write the logical form of, and I'm wondering if somebody could write it out. The ...
0
votes
1answer
39 views

Translate the following into predicate calculus. State assumed universe of discourse

This is my first assignment on these, so I would greatly appreciate your help. Translate the following into predicate calculus. For each answer, also state the assumed universe of discourse. ...
3
votes
0answers
45 views

Structural induction proof

I am trying to solve the following problem, please help me to complete the proof: I need to find the relation between the number of comas in a term $p_c$ of language L = {f,g} and the number $p_f$ of ...
4
votes
0answers
38 views

Group orderable iff all its finitely-generated subgroups are orderable

I want to proof this specifically using the Compactness Theorem from propositional logic (this is an exercise from Model Theory, Hodges). $G$ orderable means there is a total ordering s. t. $g\leq h$ ...
-2
votes
1answer
39 views

Propositional-Calculus/ Set Theory Proof using Identities [on hold]

$$(\sim P\,\lor \sim Q)\equiv (Q\to (\sim P\,\lor\sim Q))\land ((\sim P\,\lor \sim Q)\to Q) $$ Can someone demonstrate the identity proof here? I've been trying to figure this out, but with no ...
0
votes
1answer
52 views

prove using natural deduction $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$

how do I prove the following using Natural Deduction ? $((P \land Q) \rightarrow R) \vdash (P \rightarrow R) \lor (Q\rightarrow R)$ My current approach: So instead of proving $(P \rightarrow R) ...
2
votes
1answer
64 views

Different axiomatizations of set equality

I've seen two definitions (or axioms?) of set equality: $a=b \Leftrightarrow (\forall x : x \in a \Leftrightarrow x \in b)$ $a=b \Leftrightarrow (\forall x : a \in x \Leftrightarrow b \in x)$ That ...
0
votes
1answer
43 views

Can someone explain and help me with propositional logic in discrete math?

Can someone explain to me in detail how to complete these two problems without using truth tables? I'm having a hard time understanding what to do. I know that I'm supposed to use the laws, etc. But ...
0
votes
1answer
13 views

Minimal Model, from formula

{p2 ^ p3 -> p1, p3 ^ p4 -> p2, .... p9 ^ p10 -> p8} Find the minimal model. My professor told me the answer is the empty set, but aren't these minimal models too?: {p1}, {p2}, {p3}, {p4}, {p5}, ...
2
votes
1answer
36 views

Proof using formal deduction, how to introduce a conclusion?

Prove that $(E \land G) \lor ( G \rightarrow F )$ is formally deducible from $(E \lor F)$ where: "$\land$" means AND "$\lor$" means OR "$\rightarrow$" denotes an implication This is what I have ...