# Tagged Questions

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

57 views

### Extensionality in Second Order Arithmetic?

I'm wondering how (or if) sets can be proven to be unique within certain subsystems of second order arithmetic (such as $\mathbf{ACA}_0$). I was thinking that we would have a kind of extensionality ...
37 views

### how to prove by inference

Can I apply modus ponens for 1 and 2 to get numbers 3's argument? The end output should be $s$ and this seems too simple. $(p ∨ r) → (q ∧ s)$ Premise $p$ Premise $(q ∧ s)$ modus ponens 1,2 $s$ ...
106 views

### “Well-defined” ordering on the set of equivalence classes

I'm trying to work my way through Herbert Enderton's A Mathematical Introduction to Logic, and I'm currently stuck on the following exercise (3.2.3, to be precise): Let $\mathfrak{A}$ be a model ...
441 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 ...
40 views

### Proving arguments logically by inference

I think I am on the right track but got stuck on 6. $p ∨ (r ∧ t)$ premise $¬p ∨ ¬(q ∧ u)$ premise $(q ∧ u) ∨ s$ premise $¬s$ premise $(r ∧ t) ∨ ¬(q ∧ u)$ 1,2, Resolution $(q ∧ u)$ 3,4, ...
423 views

45 views

28 views

### Meaning of $∃y∃z : \text{times}(y,z) = x \land (\neg (y=1) \land \neg (z=1))$

I have the following question: $P(x) \iff ∃y∃z : \text{times}(y,z) = x \land (\neg (y=1) \land \neg (z=1))$ $\text{times}$ is the multiplication function The world is a world of natural numbers ...
At first English is not my native language if something is not perfectly formulated or described I'm sorry. Could somebody please tell me what the generally valid statement of this is? $$\forall x(\... 1answer 71 views ### How do we prove that an interpretation A is isomorphic to itself? Prove that an A is isomorphic to A, where A is an interpretation. So far I know that there is a correspondence from A to A via the identity function because id(x) = x for every x. This proves ... 2answers 74 views ### p \leftrightarrow \sim q \equiv (\sim p \wedge q)\vee (p\wedge\sim q) I've been trying to solve this for about an hour now, but I keep getting stuck after a few steps. Here's what I have so far: (p \rightarrow \sim q)\wedge(\sim q \rightarrow p).......................... 2answers 49 views ### Are the following contradictions? I have the following: p\to (q\land p) p\to \neg (q\land p) I am asked if they are contradictions, can someone explain what that means exactly. I did a truth table for both, and if ... 1answer 57 views ### Logic - Simplifying a propositional logic expression So my teacher was showing us an example in class and then blasted through it during the last minutes of the class. He does not respond to his emails outside of his office hours, so I was wondering if ... 1answer 69 views ### Conjunctive Normal Form Conversion The question is to turn the following formula into Conjunctive Normal Form: \rm \neg [(p \vee q) \wedge (r \to s)] \to p \wedge \neg q \wedge \neg s I have come up to here: \rm \neg [(p \... 1answer 158 views ### Tautology - First Order Logic I have a question in my exam practice, to determine if the following statement is a tautology, in First Order Logic: I think it is a tautology, but am I correct? In my course the proffesor told us ... 2answers 60 views ### Translating a sentence to predicate logic I have the following sentence: "Everyone who has a tail is a dog" and its translation to predicate logic is:$$\neg\exists x \, ( \neg\text{dog}(x) \land \text{hasTail}(x))$$I don't ... 1answer 93 views ### Formal Proof - Propositional Logic I missed this class on formal proofs and apparently the professor is not going over it any longer. I'm stuck on this current question in the textbook and I'm unsure on what the procedures are to solve ... 1answer 59 views ### Show that any model of \Delta is a Nonstandard Model of Arithmetic I was hoping that someone could help check my proof. I originally thought I was spot of with my proof, but my professor suggested that my method was wrong. So, I went to check the hint in the back of ... 1answer 365 views ### Well-formed formula, Inductive Definition So I have to inductively define: The number of propositional variables of a "Well-formed formula" The set of propositional variables of a "Well-formed formula" The set of parenthesis in a "Well-... 1answer 57 views ### Two Place Position and Model Question ! i get trouble in one multiple choice question in logic course: any one could help me with some description ? if we have Two-place position predicate, like : 1) all models of \varphi is ... 3answers 221 views ### Universal quantifier distributes over implication Is \forall x \forall y: P(x) \to Q(y) the same thing as (\forall x P(x)) \to (\forall y:Q(y)) ? If not can someone give an example as to why it isn't? I'm not getting the whole ... 1answer 136 views ### Identities of the Hyperoperation heirarchy The hyperoperation heirarchy in the naturals starts with addition, then multiplication, then exponentiation, then tetration, and so on. Each operation is defined as repeated application of the ... 2answers 959 views ### How to show Universal Quantifier distributes over implication? How to show Universal Quantifier distributes over implication? I've tried to no avail to show \forall x(P(x) \implies Q(x)) is equivalent to \forall x(P(x)) \implies \forall (Q(x)) but it seems no ... 1answer 50 views ### Inversion lemma for G3ip I'm following the book Structural Proof Theory by Negri and others. In it, they claim on page 32 about G3ip that if ⊢ _ n A \& B, Γ ⇒ C, then ⊢ _ n A, B, Γ ⇒ C. But, given that the only ... 1answer 48 views ### How do I notate this statement about a state of affairs (similar to a possible world)? I'd like to notate this statement formally: If any given agent desires that a certain state of affairs obtains, then there is no state of affairs in which she enjoys greater security than that one. ... 1answer 112 views ### Proving a set adequate Show that the set of connectives \{\wedge, \leftrightarrow, \oplus\} is adequate, where \oplus is defined by the truth table: \begin{array}{|c | c | c |} \hline p & q & p \oplus q \\ \... 1answer 55 views ### First Order Logic and Some Validity Checking I'm sorry for put an image insted of typing it... infact this is an 2012-exam on Logic. i found the solution of this quiz that wrote by one TA. he wrote just the second line is not valid logically in ... 1answer 114 views ### If \Gamma\cup\{\sim(A\land B)\} is consistent, what can be said about \Gamma\cup\{\sim(A\lor B)\},\Gamma\cup\{\sim A\},\Gamma\cup\{\sim B\}? The following question arose in the NOI of India Section taken a few days back: Let \Gamma be a set of predicate formulas, and let A, B be two predicate formulas; if the theory \Gamma \cup \{ ... 1answer 78 views ### Predicate logic sentence translation help? I have an assignment on predicate logic and while I understand my notes when I'm reading them, applying those notes to the questions I'm being asked isn't working so well. I've got a couple different ... 3answers 223 views ### A confusion about proof by contradiction… This may be a duplicate question but I am curious as to the answer regarding the statement "some theorems can only be proved by contradiction". In Can every proof by contradiction also be shown ... 3answers 80 views ### Is “X, but Y” logically equivalent to “X and Y”? While reading about Mathematical Logic in a book, I found the following, Conjunction. If X is a statement and Y is a statement, the statement "X and Y" is true if X and Y are both ... 3answers 59 views ### p\land\neg q\to r, \neg r, p ⊢ q -natural deduction I have the following:$$p\land\neg q\to r, \neg r, p ⊢ q$$I know that my attempt is incorrect, but I will show it anyways: Step 1) p\land\neg q\to r ----premise Step 2) \neg r -----premise ... 1answer 73 views ### ⊢p \land q \to (p\to q) - Natural deduction proof confusion I have the following:$$⊢p \land q \to (p\to q)$$I'm having a difficult time trying to figure out where to begin. I believe that I am supposed to assume p and <... 6answers 4k views ### Why is mathematical induction a valid proof technique? [duplicate] Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows. Problem: The main form for normal induction over ... 1answer 35 views ### f \in \Sigma_n^1 \iff f \in \Pi_n^1 in an analytical hierarchy The proposition 1.7 in Higher Recursion Theory by Sacks states f \in \Sigma_n^1 \iff f \in \Pi_n^1 with the proof: Since f is a function, then, f(x)=y \iff \forall z. [y \neq z \implies f(x) \... 1answer 49 views ### Proving the order relation in \mathrm{PA} is total. Let \mathrm{PA} be the first order logic axioms of Peano Arithmetic. Define an order relation by:$$ x\leq y\; \text{ if }\; (\exists z)(x+z=y).  Can it be proved that this relation is total?
I have language $L = \{ < \}$. I have the following structures: $|M| = \{ 1-\frac{1}{m} |m\in Z, m >1\}$ $|N| = \{ 1-\frac{1}{m} - \frac{1}{n} |m,n\in Z, m,n >1\}$ I need to find a ...