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
17 views

How to derive a truth value from the following formula, one where the formula is T and one where it is F

Hi Guys I am trying to derive a structure from the formula where truth value for one structure is F and for another is T. I haven't seen a formula like this before so I am slightly confused. this is ...
0
votes
2answers
21 views

Is ( ¬p AND (p OR q) ) AND ¬q a contradiction?

As We Know That p AND (q OR r) = (p AND q)OR(p AND r) we have ...
0
votes
2answers
55 views

What is the perimeter of the rectangle formed by 7 separate squares with different sides? Explain how you arrived at your conclusion? [on hold]

Here is the the question: you have 7 squares with sides 1, 2, 2, 2, 3, 4, 5. These squares form a rectangle with no gaps or overlaps. What is the perimeter of the rectangle formed A) 34 ...
2
votes
2answers
27 views

how to prove the following propositional formula using semantic equivalence

Hi Guys I am trying to prove the following formula using the rule below ...
1
vote
1answer
60 views

Why do we call “comprehension” and “regularity” to the axiom schemas in Set Theory?

I have several Set Theory books in my "shelve" but I have found the justification for the names in none. Usually all of them just state something like: "The axiom schema of ...
5
votes
1answer
97 views

The Reals are not interpretable in the complex numbers

Let $L=\{+,\dot{},0,1\}$ be the language of fields. I wish to show that the reals ($N=(\mathbb{R},+,\dot{},0,1)$) are not interpretable in the structure $M = (\mathbb{C},+,\dot{},0,1)$. I have the ...
1
vote
0answers
23 views

Show that $\Sigma_n^0 \not= \Pi_n^0$ holds for every $n \in \mathbb{N}$ (arithmetical hierarchy)

I want to know, how I can prove $\Sigma_n^0 \not= \Pi_n^0$ in the arithmetic hierarchy. For $\Sigma_1^0$ it is easy, since the diagonal halteproblem would be one example. But how to prove it for all ...
1
vote
1answer
44 views

Show that multiplication is not definable on set of Natural Numbers with successor function

I've shown that the theoty in the question admits quantifier elimination. If the $F(x,y)=xy$ (multiplication) was definable on $\mathbb{N}$ with successor function and $0$ then the statement ...
0
votes
1answer
26 views

Defining Material Conditional

Defining the conditional statement "$\phi \implies \psi$" so as to capture what is meant by implication requires that we ignore the issue of causation. From Keith Devlin's Introduction to ...
0
votes
1answer
19 views

Distinguishing pure, closed lambda terms

Let $M$ be a full model of the simply typed lambda calculus, over some collection of base types, with the constraint that $|D_\sigma|\geq 2$ for each base type $\sigma$. Let $a$ and $b$ be two closed ...
0
votes
2answers
27 views

Vacuous statements and explosion

So my understanding of vacuous statements is as follows: For any statement $P$, the statement $(\forall x \in \emptyset)(P(x))$. This can be argued as follows: Assume for contradiction $\neg [(\forall ...
3
votes
0answers
85 views

Why is recursion theory suffering from terminological bloat?

Several questions on MSE in recent months and most recently this one have made me feel that recursion theory is suffering from terminology bloat. Why have so many synonyms for "recursive" and ...
0
votes
1answer
27 views

Trouble with step 2 resolution calculus

I need to prove T ⊨ A v B with the resolution calculus from a set T. Step 1 Transform T into a set of clauses (CNF). Clause 1 = A v ¬C Clause 2 = C v A v B Step 2 Try to find a resolution ...
1
vote
1answer
17 views

How to convert sentence into logic formula

Hi I wanted to know if I have converted this sentence into propositional logic correctly. This is the sentence At least two of the propositions $p$, $q$ and $r$ are true. and this is my answer ...
1
vote
3answers
32 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
47 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 ...
1
vote
1answer
52 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 ...
0
votes
2answers
47 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)$ ?
1
vote
1answer
37 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 ...
0
votes
2answers
53 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 ...
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 ...
1
vote
1answer
23 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
1answer
36 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$ ...
0
votes
0answers
18 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? ...
11
votes
1answer
141 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
3answers
30 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
0answers
37 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 ...
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 ...
2
votes
1answer
51 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 ...
2
votes
3answers
67 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 ...
3
votes
1answer
43 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 ...
0
votes
1answer
41 views

sets with quantifiers

My professor wrote the following theorems and definitions on the blackboard. ...
2
votes
2answers
46 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
19 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
40 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 ...
4
votes
1answer
31 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
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 ...
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 ...
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 ...
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
1answer
40 views

Propositional-Calculus/ Set Theory Proof using Identities [closed]

$$(\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
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. ...
4
votes
0answers
39 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$ ...
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 ...