Questions tagged [logic]

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 following tags as well, if they fit the question: (model-theory), (set-theory), (computability), and (proof-theory). This tag is not for logical puzzles, use (puzzle).

Filter by
Sorted by
Tagged with
9 votes
2 answers
449 views
+50

How would the constructible hierarchy change if you remove parameters?

The constructible hierarchy is defined as follows. $L_0=\varnothing$. For any ordinal $\beta$, $L_{\beta+1}(X)=Def(L_{\beta})$, where $Def(X)$ is the set of all subsets of $X$ which are first-order ...
-2 votes
2 answers
52 views

When can we discuss the 'truth value' of a statement?

Let's take an expression like $x+x$ and $2x$ and form a statement which is always true in my domain D. For example, $x+x=2x$ this statement is true for all $x$, so for any value of changing $x$, why ...
3 votes
0 answers
61 views

How to prove that permutations of x-y can go infinite

I am a novice when it comes to mathematics, but I have been give a problem that is causing quite the headache. Basically, I need to know if two values are able to infinitely go against one another ...
0 votes
0 answers
31 views

Proof of Lemma 1 in Shoenfield's Mathematical Logic

I'm having a little trouble with the proof of Lemma 1 (link to screenshot below) in Shoenfield's Mathematical Logic. The overall scheme is easy enough--it's just induction on n. What I don't get is ...
2 votes
0 answers
17 views

Proving chain order from Peirce's Law

I am trying to prove any one of the following statements $((p \to r) \lor (q \to s)) \to ((p \to s) \lor (q \to r))$ $(p \to q) \lor (q \to r)$ $((p \to q) \to q) \to (p \lor q)$ $(p \to q) \lor (q \...
0 votes
1 answer
24 views

Showing a set is computable

Let $V = \{\ulcorner\phi\urcorner \mid A \vdash \phi\}$, where $A$ is $\{(\forall{x})(\forall{y})x=y\}$. I'm having trouble understanding why my book* states (in the solution to problem $1$, Section $...
0 votes
0 answers
22 views

Logical constraint: If $X>0$ then $Y=1.$ Else $Y=0.$

I have been struggling a lot with coming with two big-M constraint to represent this. I can only seem to restrict one part of the logical condition, but not the other. So, first case: If $X_1>0$ ...
1 vote
1 answer
33 views

A true but unprovable sentence $\theta$ that is not a $\Pi$-sentence

Question $4$ from Section $7.7.3$ in "A Friendly Introduction to Mathematical Logic" (Christopher C. Leary and Lars Kristiansen; $2$nd edition): Let $A = \{\phi \mid \phi \text{ is a } \Pi\...
4 votes
1 answer
493 views

Is 'London is the capital of UK' mathematically acceptable statement?

A statement is called 'acceptable' if it's either true or false. In particular, an acceptable statement can't be paradoxical, ambiguous or subjective. (Here is a similar question asking about ...
3 votes
3 answers
83 views

Understanding non-truths and writing them as contradictions

A contradiction is defined as a logical proposition that is always false, such as $(p \land \neg p) \iff False $ According to my Professor, examples of non-truth are (1) Assuming that $(p\rightarrow q)...
1 vote
2 answers
429 views

about counter-example for Quantifier based statement (logic)

I have a logic based statement of this form: $$ (\forall x\ ,p(x))\to (\exists y\ , q(x,y))) $$ I am trying to find out if this statement is TRUE or False. I have 2 methods of proof, and one leads ...
1 vote
0 answers
28 views

Proof of cut-elimination for a propositional calculus?

Consider the classical propositional calculus over the alphabet $\{\bot,\top,\neg,\land,\lor,\rightarrow\}$ with the following inference rules (together with the initial sequent): Is cut-elimination ...
0 votes
0 answers
15 views

Proving that the given sets are not semi-computable

We are given the sets $A = \{e \mid \{e\}(x) = x \text{ for all } x \in \mathbb{N} \}$ and $C = \{e \mid \{e\} \text{ is a total function} \}$ (this is from problem $5$, Section $7.8.1$, in "A ...
0 votes
0 answers
24 views

Are ZFC and Formal Number theory already built upon the intuitive notion of set and natural number?

These two theories are known to be first-order theories. And the definition of the first-order logic typically involves something like "set of symbols $a_1, a_2, a_3...$", which already ...
2 votes
1 answer
38 views

Semi-computable set of non-logical axioms implies semi-computable set of deductions

Question $1$ from Section $7.7.3$ in "A Friendly Introduction to Mathematical Logic" (Christopher C. Leary and Lars Kristiansen; $2$nd edition): Let $A$ be a consistent set of $\mathcal{L}...
1 vote
1 answer
53 views

An explanation for a supposedly simple proof

I'm struggling to understand this reasoning. I've simplified it, but you can find it in full in the text Computability and Unsolvability (1985) by Martin Davis, chapter 3, page 48. Let $P(z)$ be a ...
1 vote
1 answer
90 views

Do logical connectives in type theory not form well-formed formulas like they do in classical logic?

I have been doing exercises in Lean theorem prover where I was introduced to type theory. There is a variety of type theories, this question applies to those that behave similarly to Lean's dependent ...
3 votes
1 answer
157 views

Equations and truth tables

Let's say I work on the inequality |x-1|>x-2 in the following way: |x-1|>x-2 ⇔ x-1≥0 ∧ |x-1|>x-2 ∨ x-1<0 ∧ |x-1|>x-2 ⇔x-1≥0 ∧ x-1>x-2 ∨ x-1<0 ∧ -(x-1)>x-2 ⇔x-1≥0 ∧ -1>-2 ∨ x-...
3 votes
3 answers
96 views

Do Hindley-Milner theories have a Deduction Theorem?

Deduction Theorem: Given $\Gamma \cup \{A\} \vdash B$, we can deduce $\Gamma \vdash A \to B$ HM Counter-Example (?): Take $A$ to be $\forall f : \alpha \to \alpha, \forall x : \alpha, f(x) = f(f(f(x)))...
3 votes
1 answer
60 views

left-adjoint to join in a Heyting algebra

Define a Heyting algebra to be a bounded lattice $L$ with an operation $\to : L^{op}\times L \to L$ such that for any $x, a, b \in L$ we have $x\wedge a \leqslant b$ iff $x \leqslant a \to b$. ...
0 votes
0 answers
40 views

Determining whether a given set of sentences is satisfiable [closed]

I recently ran into this seemingly simple, yet tricky problem, and I would like your help solving it. Determine whether the following set of sentences is satisfiable or not. If not, use natural ...
1 vote
1 answer
71 views

If theory (in some logic) has 2 different models, are these models related in some other way?

Let us assume, that we work in sound and complete logic. Let us assume that we have theory Th and 2 different models Mod1 and Mod2 that are interpretations of this theory Th. My question is - what we ...
0 votes
2 answers
90 views

How are $∀y∃x\:P(x,y)$ and $∃x∀y\:P(x,y)$ different? [duplicate]

MIT Opencourseware Notes 6.042J says that $$\exists x \forall y \:P(x, y) \implies \forall y \exists x \: P(x, y)$$ is a valid assertion. I am confused because of a counter model that I thought of: if ...
0 votes
2 answers
1k views

Help in understanding a logic puzzle

Discrete Mathematics and Its Applications, 8e, by Rosen solves the following logic puzzle: As a reward for saving his daughter from pirates, the King has given you the opportunity to win a treasure ...
1 vote
2 answers
49 views

How to most quickly check whether a given sentence is logically equivalent to $p↔q$?

This is from a Discrete Mathematics term test: Q4. Which of the following statements is/are logically equivalent to $p ↔ q$? (I) $(¬p \lor q) \land (p \lor ¬q)$ (II) $(¬p \land ¬ q) \lor (p \land q)$ ...
1 vote
1 answer
87 views

Induction as a theorem within the metatheory?

That induction works seems obvious and yet it typically needs to be included as an axiom (as I understand it). Would it be possible instead to start with a theory which doesn't include induction and ...
1 vote
3 answers
113 views

A confusion on baisc conditional statement. Logical falsehood entails everything as long as antecedent is not universally true?

In the logic, we could assign T\F to antecedent and consequent to evaluate the conditional statement. It's easy to evaluate because it's either universally true or false. example 1. If $4$ is an even ...
-4 votes
0 answers
26 views

Are (p → q) ∨ (q → r) and p → r equivalent statements? [closed]

Could anyone pls help me with this question, please? thank you :>
3 votes
4 answers
67 views

Why is this true? $(\exists x, Px \to r) \iff (\forall x, Px) \to r$

I can totally understand the forward direction: if there is an $x$ such that $Px$ implies $r$, then clearly having $Px$ true for all $x$ will imply $r$. But the other direction doesn't make any sense ...
1 vote
1 answer
39 views

A sound and complete proof system for $\forall$-first-order logic

There is, as is well-known, a sound and complete proof system for first-order logic. It is also known that equational logic, which is the fragment of first-order logic that concerns only universally ...
4 votes
1 answer
81 views

Is there a formal definition of "Proving theorem X without using theorem Y"?

In math textbooks and math classes, the author or professor sometimes says to prove a certain theorem without using another theorem. I understand what that means intuitively. But is there a formal ...
8 votes
1 answer
759 views

What exactly is Levy hierarchy?

Wikipedia lacks information on Levy hierarchy, so what exactly is Levy hierarchy? This will tell me what $\Delta_0$ means in KP set theory.
3 votes
0 answers
53 views

Axioms for multiplicative number theory?

Multiplicative number theory is concerned with divisibility, modular arithmetic and the primes. Of course all of the relevant multiplicative properties are theorems of Peano arithmetic and this is ...
1 vote
3 answers
386 views

Prove double negation of LEM in intuitionistic logic

I understand that in intuitionistic logic, the law of excluded middle $P \lor \lnot P$ and double negation elimination $\lnot \lnot P \to P$ are not true in general (for every proposition $P$). ...
1 vote
0 answers
18 views

Semi-computable sets are not closed under set subtraction

Showing that $A \setminus B$ is not semi-computable for semi-computable sets $A$, $B$ is not too difficult: $\mathbb{N} \setminus C$ is not a semi-computable set for a semi-computable, but not ...
1 vote
3 answers
94 views

is $(\phi^2 > 2) \Rightarrow (\phi > 1.4)$ true or false?

First, I need to evaluate left and right hand sides of '$\Rightarrow$' to use definition of implication (its truth table). And, I'm simply lost in a question: "how should I evaluate truth or ...
1 vote
2 answers
85 views

Why is $\exists x \forall y \exists z \left(\left( y = x + z \right) \lor (z \leq x) \right)$ false?

I am trying to wrap my head around the proposition $$\exists x \forall y \exists z \left(\left( y = x + z \right) \lor (z \leq x) \right),$$ where $x, y, z \in \Bbb N^+$. The proposition is false, but ...
0 votes
3 answers
92 views

How to prove that ∼p → (q ∧ r) is false? [closed]

I am a beginner in logic. With the premise that (q ∧ r) is false, how can I prove that ∼p → (q ∧ r) is invalid? This is the last part of a logic problem. I have built this truth table: ...
2 votes
1 answer
58 views

Puzzle: Rotors intro to logic Stanford Course

I need help with this puzzle, I tried to solve it but could find what's wrong with my solution, forgive me if I have any silly mistakes. it has been quite some time since I have done any mathematics. ...
0 votes
6 answers
647 views

Understanding the p implies q statement

The p implies q statement is often described in various ways including: (1) if p then q (i.e. whenever p is true, q is true) (2) ...
1 vote
1 answer
131 views

Differences between conditional in truth-functional logic and the conditional in natural language?

How can we account for the differences between the conditional in truth-functional logic and the conditional in natural language?
5 votes
8 answers
1k views

How does one know if $A \implies B$ (an implication) is true without knowing if $B$ (the consequent) is true?

This might be a weird question but I was trying to distinguish the difference between an implication and modus ponens. I think the distinction is clear in my head (but I have something missing), modus ...
2 votes
2 answers
689 views

Using "implies" to refer to material conditional

Is it acceptable to translate the binary connective "$\let\ f\rightarrow$" into English with "implies"? I'm unsure because "implies" for me immediately brings to mind logical implication, but I've ...
1 vote
2 answers
206 views

A logical implication in which both sides are unrelated

Is this proposition true or not: $$ \forall x(x=x) \rightarrow \forall x( x^2 -a^2 = (x+a)(x-a))$$ The left side $x=x$ does not have to do anything with the right side $x^2 - a^2 = (x+a)(x-a),$ but ...
1 vote
2 answers
69 views

Need help with proof by induction, that $6n + 6 < 2^n$ for all $n > 5$ [duplicate]

Not sure how to even wrap my head around this, and want more practice in proofs by induction. So I let P(n) be "$6n + 6 < 2^n$" and prove by induction that it holds true for all $n > 5$...
8 votes
1 answer
132 views

How hard is it to show $\mathsf{ZF-Pow}\not\vdash\mathsf{AC}$?

This is motivated by comments on this question. Let $T_0=\mathsf{ZF-Pow}$ and $T_1=\mathsf{ZF-Pow+\neg AC}$. (Note that there is some subtlety about what precisely $\mathsf{ZF-Pow}$ is; here, I adopt ...
2 votes
3 answers
2k views

Which should I study first: Logic or set theory?

I'm an undergraduate student in a college of sciences and technics studying maths, physics, computing and some chimestry so we studied elementary materials in logic and set theory. As I am interested ...
2 votes
2 answers
133 views

FST and SND operations in language of elementary arithmetic.

I'm trying to figure out this problem, without any luck now. Maybe you can help me. Suppose we have a first order logic with functions and predicates. We pick a signature, that consists of operation ...
3 votes
2 answers
63 views

Taxonomy of proofs of compactness in propositional logic

I know of two proofs of compactness in propositional logic, one which is a very fast use of Tychonoff's theorem. The other takes a very long tour through several lemmas, but sticks to strictly ...
2 votes
2 answers
76 views

Rationalising and simplifying nested square roots

So I have reached a point where I have got the answer as $\frac{\sqrt{2+\sqrt{3}} - \sqrt{2-\sqrt{3}}}{2}$ But I need to prove that it is $\frac{\sqrt{2}}2$ How can I do so? I know they're numerically ...

1
2 3 4 5
512