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)

5
votes
1answer
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 ...
2
votes
1answer
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$ ...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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, ...
0
votes
2answers
423 views

Conditional statements explanation

I'm really confused with conditional statements. For example, given $P(x) \to Q(x)$. Actually it's equivalent to $\lnot P(x) \lor Q(x)$, right? It's easy to understand its true value - only when $P(x)...
1
vote
0answers
119 views

Definitions of isomorphism and elementary substructures

Let us define -all the definitions are from V. Manca, Logica matematica, 2001, 'mathematical logic'- a $\Sigma$-morphism as a function $f:D_1\to D_2$ between models $\mathscr{M}_1$ and $\mathscr{M}_2$,...
1
vote
1answer
43 views

Why is it necessary for a theory to not have any finite models to apply Los-Vaught test?

In Los-Vaught test as stated in Enderton's, it's said that the theory should not have any finite models as a condition. As I was reading the proof, I didn't figure out where exactly this condition is ...
1
vote
1answer
57 views

Is there only one negation of the statement?

I am very much confused with the negation of the following statement. A sequence of real numbers is divergent $\implies$ either it is unbounded or there must exist at least one pair subsequences ...
0
votes
1answer
87 views

Using contrapositive to Prove that if an average of a thousand numbers is less than 7, then at least one of the numbers being averaged is less than 7 [duplicate]

so I know that the contrapositive will be something like; If all the numbers are greater than or equal to 7, then the average cannot be less than 7. How do i go about proving it from there? or is ...
1
vote
1answer
34 views

Simpson's Definition of Parameters and Definability

Simpson makes his definition of parameters and definability in Definition I.2.3 of his book Subsystems of Second Order Arithmetic (can be found here). On page 5 he says that: "Note that an $L_2$-...
2
votes
2answers
150 views

Prove that if an average of a thousand numbers is less than 7, then at least one of the numbers being averaged is less than 7 [closed]

I tried proving this by contraposition, by saying, "If every number that is being averaged is greater than 7, then the average of a thousand numbers is less than 7." This seems easier to prove, but I ...
2
votes
1answer
94 views

Intuitively speaking, why was there a need to “eliminate” quantified variables in mathematical logic?

I'm trying to wrap my head around the understanding of lambda-calculus, from a math/computing/logic standpoint and am reading more about its very genesis. This has taken me to 1924 - Schonfinkel's ...
0
votes
2answers
76 views

Is the Formula Logically Valid?

I have a question for my exam and I find it hard to understand. I have to prove that the following formula is logically valid: The professor told me to "push" all the symbols inside the brackets, ...
3
votes
1answer
59 views

Temporal Logic Tautology

I have the following question: if it is necessary that p -> p = tautology? I think it's not, and I am showing my example for the contradiction, below: ...
2
votes
0answers
64 views

How can i solved this using fitch notation?

I have a little problem that is proof this following statement using fitch notation, can anyone help me out? :) |= (t → s) ∧ ¬((s → q) → (t → q)) Thanks in advance.
2
votes
1answer
72 views

Show that the subset of a real ordered field defined by a ring formula has a least upper bound.

So currently trying to get well practiced in model theory, and i have come across the following question which i need some help with. Esentially let $S \subseteq \mathbb{R}$ be a non empty set, ...
1
vote
1answer
119 views

Are these a Tautology?

Are the following two well-formed formulae a tautology ? $ \forall x\forall y P(x,y)\rightarrow \forall x\forall y P(y,x) $ $[ \forall x\exists y (P(x,y) \rightarrow R(x,y) ) ] \leftrightarrow [ \...
1
vote
1answer
45 views

Is universal instantiation correctly applied here?

The question asks me to determine if the following arguments are valid. $\begin{array}{rcr} A) & \forall x \forall y K(x, y) \, \vDash \forall x K(x,x) \\ 1. & \forall x \forall y K(x,y) \\ 2....
3
votes
1answer
126 views

Axioms defining a Turing machine

I have found the following characterisation in axiomatical terms of a Turing machine: $Q_0(q)\rightarrow T(q)$ $S_0(x)\rightarrow S(x)$ $C(x)\rightarrow S(x)$ $Q_0(q)\land T(qx)\land S(y)\...
0
votes
2answers
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 ...
3
votes
3answers
2k views

What is the meaning of ∀x(∃y(A(x)))

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(\...
1
vote
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 ...
4
votes
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)$..........................
1
vote
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 ...
1
vote
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 ...
0
votes
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 \...
3
votes
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 ...
1
vote
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 ...
-2
votes
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 ...
1
vote
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 ...
0
votes
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-...
0
votes
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 ...
0
votes
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 ...
3
votes
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 ...
2
votes
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 ...
0
votes
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 ...
3
votes
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. $...
0
votes
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 \\ \...
1
vote
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 ...
0
votes
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 \{ ...
1
vote
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 ...
3
votes
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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 <...
21
votes
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 ...
1
vote
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) \...
1
vote
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?
2
votes
1answer
44 views

Find a formula that separate between structure

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