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

Application of the resolution method

The text of logic that I am following give an example of the resolution method to prove the theorem$$\models \forall x((\varphi(x)\rightarrow\psi)\rightarrow(\exists x\varphi(x)\rightarrow\psi)).$$ In ...
4
votes
2answers
209 views

Is $\Delta_0=\Delta_1$ in arithmetical hierarchy?

I have seen a definition (e.g. http://www.math.ubc.ca/~bwallace/ArithmeticalHierarchy.pdf) of an arithmetical hierarchy in computability starting with: "let $\Delta_0=\Sigma_0=\Pi_0$ be the set of all ...
2
votes
1answer
476 views

Puzzle : Truant List of Statements

I was working my way through some puzzles in Discrete Maths by Rosen, when I came across the following question: The $n^{th}$ statement in a list of 100 statements is : "Exactly $n$ of the ...
2
votes
1answer
71 views

On Decidability of first order logic

why we need the beta-function to show that arithmetic (the theory of the standard model) is undecidable, but that no beta-function is needed for shown that universal validity in first-order logic is ...
1
vote
0answers
57 views

A computable set of sentences neither probable nor disprovable from $PA$

I need to prove that, given a computable binary tree $T$ whose paths are exactly the complete extensions of $PA$ (via some Gödel coding), there is a computable $X\subseteq\mathbb{N}$ such that for all ...
1
vote
1answer
65 views

Is it valid to make an assumption that directly contradicts a given premise?

Is it valid to make an assumption that directly contradicts a given premise? For example, if I want to deduct the proposition $$¬(p→q) ⊢ p∧¬q$$ I'd like to assume $p→q$, so I can falsify things ...
2
votes
3answers
96 views

Predicate Logic Family Cousins

Consider the set of predicates $M(x)$, $F(x)$, $S(x, y)$, and $P(x, y, z)$ with meanings “is male”, “is female”, “are siblings”, and “are parents of”, respectively. Write a formula for predicate $C(x,...
4
votes
3answers
1k views

How to express the statement “not all rainy days are cold” using predicate logic?

I am trying to figure out how to express the sentence “not all rainy days are cold” using predicate logic. This is actually a multiple-choice exercise where the choices are as follows: (A) $\forall d(...
0
votes
2answers
91 views

There is relation that is symmetric and transitive but not reflexive? [duplicate]

Let $L=\left\{R\right\}$ be a language with only one relation symbol. Consider these formulas: $\Psi _1\:=\:\forall x\left(R\left(x,x\right)\right)$ $\Psi _2\:=\:\forall x\forall y\left(R\left(x,y\...
1
vote
2answers
140 views

A first order sentence such that the finite spectrum of that sentence is the following subsets of $\mathbb{N}^+$.

I would like to find a language $\mathcal{L}$ and first order sentence $\phi$ of $\mathcal{L}$ so that its finite spectrum is $\{p^n ~:~ n > 0, \text{ p is prime}\}$ $\{ p ~:~ p \text{ is prime}\}...
0
votes
1answer
67 views

Show some $\mathbb{X} \subseteq \mathbb{N}^+$ occurs as the finite spectrum of a sentence for this language.

Setting Define the finite spectrum of an $\mathcal{L}$-sentence $\phi$ as $$\{ n \in \mathbb{N}^+ ~:~ there ~ is~ \mathcal{M} \models \phi ~with~ |\mathbb{M}| = n\}$$ And let $$\mathbb{X} = \{ 2^n ...
1
vote
2answers
53 views

Translation logic to English

Given these conditions... $P(x) = x$ is a cow, $Q(x) = x$ makes milk, $R(x,y) =$ both $x$ and $y$ are the same object. This expression says the following.. $$(\exists x)[P(x) \wedge Q(x)]$$ and ...
0
votes
2answers
183 views

Proving equivalency using boolean algebra laws of logic

I have a question on my exam papers relating to proving equivalences using the laws of logic, but I'm not sure how to work it out as I don't have the solution paper. Can someone explain to me the ...
0
votes
1answer
192 views

Simplifying Simple Boolean XOR Expression (!AB + A!B)

I am trying to simplify the 5 gate XOR from a A!B + !AB expression to a (A + B)!(A + B) implementation. How can I convert ...
0
votes
1answer
49 views

Logical Predicates

Say you have the following predicates and you're using variables: P(x) = "x is a cow", Q(x) = "x makes milk", and lastly R(x,y) "x and y are the same object". From there you have the following ...
0
votes
2answers
46 views

Principle of propositional congruence

Let $\varphi$ be a propositional formula, defined as a formula containing propositional symbols and connectives only, and let $\psi,\chi$ be propositions. I read the following principle of ...
1
vote
2answers
53 views

How to work with a statement: “for all $x$, if $p(x)$ then $q(x)$” (contradiction and contraposition)

Proving by contradiction and contrapositive a statement of the sort "for all $x$, if $p(x)$ then $q(x)$" Question about the notation: is it equivalent to $\forall x (p(x)\to q(x))$ or $(\forall x (p(...
2
votes
3answers
231 views

Propositional Logic Tautology Proof

I have question about a proposition that I need to prove is a tautology: $((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ I have tried negating the first large bracket, ...
2
votes
1answer
130 views

Is $\lor$ definable in intuitionistic logic?

The Wikipedia page mentions that $\{\lor,\leftrightarrow,\bot\}$ and $\{\lor,\leftrightarrow,\neg\}$ are complete sets of operators for intuitionistic logic, and also gives a few equivalences for ...
0
votes
2answers
126 views

How to prove that $\Gamma\vdash\forall x\psi$ if $x$ occurs free in $\Gamma$, via generalization theorem?

In Enderton's logic [page $120$], he says: Assume we wish to prove $\Gamma\vdash\phi.$ where $\phi$ is $\forall x\psi$. If $x$ does not occur free in $\Gamma$, then it will suffice to show $\Gamma\...
0
votes
1answer
231 views

Distinguish between substructure, submodel, elementary substructure, and elementary submodel.

I can see (although I must not really understand) the definition of these terms, but could someone please explain the difference between these concepts, and whether any one of them imply the other? ...
2
votes
1answer
376 views

How do I prove these biconditional statements?

I keep getting stuck when I get to (not p or q) and (p or not q) for number 3 and for number 4 I get stuck in relatively the same place. Edit: I want to prove them with using equivalence laws, not ...
5
votes
1answer
100 views

Proving that ∼(∃x) P (x), is false is equivalent to proving that (∀x )∼P (x) is true.

I found this phrase in the page 60 of the book "A Transition to Advanced Mathematics, 8th Edition, written by Smith/Eggen/St. Andre." "Proving that ∼(∃x) P (x), is false is equivalent to proving that ...
0
votes
1answer
84 views

How to calculate the cardinality of a model

I know, thanks to some clarifications received from a user of this site, the definition of a model. When evaluating the cardinality of a model by taking the interpretations of all the constants, ...
2
votes
2answers
80 views

How to show validity in classical logic?

Firstly, I would like to know what does it mean to be a valid expression in classical logic. Secondly, How do we show validity of a formula (in sequent calculus) such as: (∀x A → ∃xB) → ∃x(A → B) As ...
2
votes
1answer
103 views

What is finite in a finite model

I am studying some theorems of model theory in an introductory text of mathematical logic. I know that a model is a way of associating the relationary symbols of a signature $\Sigma$ to $k$-ary ...
2
votes
1answer
214 views

Difference between Hilbert program and Russel & Whitehead's Principia Mathematica

May some one explain me what is difference between Hilbert program and Russel & Whitehead's Principia Mathematica? I know both of them wanted to reduce the mathematics into a set of axioms and ...
6
votes
2answers
109 views

No proposition $\chi$ such that $\mathscr{M}\models\chi\iff\mathscr{M}$ is infinite

Let notation "$\models$" be used for the two following case: let $\mathscr{M}\models\varphi$, where $\mathscr{M}$ is an interpretation model and $\varphi$ is a proposition, mean that $\varphi$ holds ...
1
vote
0answers
150 views

Henkin Construction: Goedel completeness Theorem

I am trying to understand better the Henkin construction, which consist first in an extension of the signature and then of the theory. Here are my question about this topic: we extend the ...
1
vote
2answers
39 views

Showing that $\neg[ Px\rightarrow \forall xPx]\vdash \forall xPx$ via generalization theorem

Let $P$ be a unary relation, we want to show that: If $\neg[ Px\rightarrow \forall xPx]\vdash Px$ then $\neg[ Px\rightarrow \forall xPx]\vdash \forall xPx$. I want to do that via generalization ...
5
votes
2answers
99 views

Propositional Logic Help

I need to prove that $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology using Laws of Logic (not truth tables). This is what I tried: $\equiv (( \neg p \wedge p) \vee (\neg p \wedge q)) \...
1
vote
1answer
22 views

Boolean operation initiation in a Matrix application

Given a function taking input matrix $A$ and $B$. The function only returns True if $A$ and $B$ are both vectors (either coulomb or row vector.) Is the following right? if (numRow(A)!=1 and ...
1
vote
2answers
101 views

Is this theorem equivalent to “existential instantiation” rule?

In Enderton's, There is a theorem called "existential instantiation", it says: Assume that the constant symbol $c$ does not occur in $\alpha ,\beta , \Gamma$ and that: $$ \Gamma\cup\{\alpha^x_c\...
4
votes
1answer
61 views

If $\phi$ is a $\Sigma_2$ sentence and $H_{\kappa} \models \phi$, then $V \models \phi$?

In the title question, $\kappa$ is any infinite cardinal. It's easy to see that the result is true if $\phi$ is $\Delta_0$ or $\Sigma_1$. I first tried proving the result for $\Pi_1$, but I don't see ...
0
votes
1answer
251 views

proof detail concerning bijection between a set and its power set

Theorem: If $X$ is a set, then $X$ is not equivalent to its power set. Proof: suppose for a contradiction that $f:X\to P(X)$ is a bijection. Define $B:=\{x \in X, x\not\in f(x)\}$. Because $f$ is ...
0
votes
1answer
41 views

Do these claims imply each other?

$T$: A set of natural numbers. $C_1: 2$ is the only prime number that divides elements of $T$. $C_2 :$ If $i, j \in T$, and $i < j$, then $i$ divides $j$. For $C_1 \rightarrow C_2$, I think it'...
1
vote
1answer
114 views

Prove true in natural numbers (Peano Arithmetic)

While reviewing old exercise sheets, I have found this question and am having difficulties understanding some of the logic: Let $\mathbb{N}$(natural numbers) be a model for Peano Arithmetic, that ...
2
votes
1answer
21 views

Difference between these two statements

$\forall x\in S, \forall z\in S,\exists y\in C, (x\neq z) \Rightarrow ...$ $\forall x\in S, \forall z\in S, \exists y\in C,...$ Why is there a need for $x \ne z$ in 1. Isn't it already implied that ...
0
votes
2answers
37 views

Logical equivalence: Which side is better to start to obtain the other?

How to resolve this with steps please: $$p \to (q \lor r) \equiv (p \to q) \lor (p \to r)$$ I just don't get how with less variable we can have more after or with more we can have less?
1
vote
2answers
47 views

Trouble with a theorem in Hunter's Metalogic

I'm a logician studian and I'm reading Hunter's Metalogic. I'm having trouble understanding and exemplifing part of a theorem in the book. It's the theorem 40.14, pp. 156-7. 40.14. Let t and u be ...
2
votes
2answers
122 views

Find logic expression for given truth table

So I was given this truth table and I need to find a logical expression for the formula to give such a result (where there can be two or three 2-place connective expressions (e.g. $A \lor B$ counts as ...
3
votes
2answers
55 views

When is $\neg(x\le 21\iff x>15)$ true?

Let $x\in\mathbb{R}$. I want to find for which $x$ the statement $$ \neg(x\le 21\iff x>15) $$ holds. I believe it is true when $x\in(-\infty,15)\cup[21,\infty)$, but I don't know how to write ...
2
votes
1answer
90 views

Simplifying Circuits

I have a question regarding simplifying a circuit of a function below that has 5 logic gates in original. $f = (A + B) \cdot (C + D) + (A + B) \cdot (C + D)' + C$ $= (A + B) \cdot ((C + D) + (C + D)'...
3
votes
1answer
63 views

Problems in formalizing these sentences

This is the first sentence that I have to formalize: "Every student likes at least one type of cake" Let: $S(x)$ stands for 'x is a student' $C(x)$ stands for 'x is a type of cake' $L(x,y)$ ...
0
votes
2answers
57 views

Weird logic question I need help with!

The professor tells Jim: "It is necessary that you get at least a B on the final in order to pass the course". Jim gets a B. What can she conclude? a) He passed b) He can conclude nothing... I ...
2
votes
1answer
79 views

Prove $ \vdash \alpha \to \alpha $ in minimal logic of Hilbert

$ \vdash \alpha \to \alpha $ I'm trying to find a way solving this statement using minimal logic of Hilbert which have only two axiom's K & S and one only rule the modus pones (MP) : what ...
2
votes
1answer
44 views

Proving a variable true through rules of inference

Question: Use rules of inference to show that if $(p → q) ∧ (q → p),\; t ∨ q,\; t ∨ p,\; (p ∧ q) → t$, then $t$ is true. Work So Far: $$\text{1. }(p \implies q) \land (q \implies p)\text{ | Premise}$...
3
votes
1answer
42 views

Boolean Algebra: Converting $xy'z + wxy'z' + wxy + w'x'y'z' + w'x'yz' = w'x'z' + xy'z + wx$

Notation w,x,y,z are all just primary statements "+" is the OR logical operator what looks like two or more statements being multiplied is actually the AND operator The complement or prime ...
0
votes
1answer
50 views

Predicate Logic Question: Implications/Operations on the Empty Set

Suppose T is a set of Natural numbers. C1: $2$ is the only prime number that divides elements of $T$ C2: $T$ is the set of all natural numbers that satisfy the quadratic equation $x^2+x+1=0$. I'm ...
3
votes
2answers
149 views

What is the modus ponens of a tautology?

In the statement $P$ and $Q$, please show that $\; (P \land (P \Rightarrow Q))\Rightarrow Q \;$ is a tauntology. The state the $\;(P \land (P \Rightarrow Q))\Rightarrow Q\;$ in words. I know I need ...