# 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).

25,600 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
17 views

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

1 vote
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
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 ...
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 ...
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 ...
38 views

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$. ...
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
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 ...
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 ...
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
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
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
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 ...
26 views

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

Could anyone pls help me with this question, please? thank you :>
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
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 ...
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 ...
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.
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
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
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
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
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 ...
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: ...
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. ...
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
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?
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 ...
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
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
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$...
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 ...
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 ...
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 ...
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 ...