Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

1
vote
2answers
15 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 ...
1
vote
2answers
97 views

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

Which is the correct formula for the sentence? “not all rainy days are cold” Can anyone tell me how to read the 4 options correctly?
0
votes
2answers
29 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 ...
0
votes
1answer
15 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 ...
0
votes
1answer
21 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
30 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 ...
1
vote
2answers
28 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 ...
-2
votes
1answer
44 views

Cardinality of set $\mathbb{N}^{\mathbb{N}}$ and $\{0,1\}^{\mathbb{N}}$

How to show that these two sets have the same cardinality? I know that to show that two sets have the same cardinality I need to show that there is an bijection from one set to another.
0
votes
1answer
14 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
20 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
28 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
18 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 ...
1
vote
2answers
31 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
51 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
1answer
19 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 ...
0
votes
1answer
36 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
29 views

Proof of ⊢ (∀xA → ∃xB) → ∃x(A → B) [on hold]

Can somebody give me the proof of ⊢ (∀xA → ∃xB) → ∃x(A → B) using sequent calculus in classical logic.
2
votes
1answer
58 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
51 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
30 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
44 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
53 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 ...
1
vote
0answers
33 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 ...
4
votes
2answers
56 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
33 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
28 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 ...
4
votes
2answers
39 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
18 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
34 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: $$ ...
2
votes
1answer
31 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
23 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
0answers
19 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 ...
1
vote
1answer
50 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
14 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
32 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
0answers
21 views

predicate-logic - I think these claims are equivalent, can you verify please?

T is a set of natural numbers. c1: if 2 is the only prime number that divides elements of T. c2: all elements of T are equal to 2^n, where n is a natural number. I'm pretty sure c1 implies c2, ...
0
votes
2answers
27 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 ...
1
vote
2answers
30 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
51 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 ...
1
vote
1answer
41 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) * (C + D) + (A + B) * (C + D)' + C = (A + B) * ((C + D) + (C + D)') + C = (A ...
3
votes
1answer
27 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
46 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
29 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) : ...
2
votes
1answer
19 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{ | ...
3
votes
1answer
16 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
32 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
46 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 ...
1
vote
2answers
94 views

Prove $x' \neq x$ using Peano axioms

I am looking at Edmund Landau, Foundation of analysis and do not agree with is proof of Theorem 2 part 2. I put the pages here for easy reference (http://pbrd.co/1y89p7b and http://pbrd.co/1y89A2s). ...
0
votes
1answer
21 views

Satisfiability of the resolvent

What would be a way to prove the following statement: S = {$C_1$, $C_2$} and C is the resolvent of $C_1$, $C_2$. By resolvent I mean the result of the resolution operation. The theorem: if S is ...
0
votes
1answer
24 views

Please help with understanding a logic definition: Subformula

Alright, so I am reading "Computability and Logic" by Boolos and Jeffrey, specifically I'm on chapter 9 "A Precis of First-Order Logic: Syntax. There has been more than a handful of definitions in ...