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

Find weights and threshold of function

I have been tasked with finding if a a function can be represented through threshold logic, and if that is the case to find the associated weights and threshold. The function is: $$ f = x_7 + x_6 \...
3
votes
1answer
91 views

Formalizing splitting into cases

Let $x$ denote a fixed but arbitrary real, and suppose we're trying to solve an equation like $$(x^2-1)^2 = 1.$$ The 'high school' approach is to just shuffle the functions on one side onto the other ...
2
votes
3answers
124 views

Is “all swans are white” equivalent to “if it is not white, then it is not a swan”?

More formally, is "All As are Bs" equivalent to "if it is not a B, then it is not an A"?
0
votes
4answers
88 views

why is $\forall x (p(x) \implies q(x)) \not\equiv (\forall x p(x)) \implies (\forall x q(x))$

I'm having a hard time wrapping my head around why $\forall x (p(x) \implies q(x)) \not\equiv (\forall x p(x)) \implies (\forall x q(x))$
0
votes
0answers
10 views

scotts theorem and other representation theorems for order aggreeing qualitative quantitative probability measures

Scotts theorem and other theorems give conditions under which a qualitative ordering (>= for at least as probable than) which satisfies certain constraints (total pre-order, finite cancellation axioms ...
0
votes
1answer
95 views

Translations with more than one quantifier

I've been having trouble translating statements with multiple quantifiers, and I would like some feedback and advice on my answers for the following translations. Let $Kxy$ mean '$x\operatorname{knows}...
6
votes
2answers
331 views

Precisely, what is a primitive recursive definition?

If I understand correctly, the language of primitive recursive arithmetic has a distinguished function symbol $S$, together with a function symbol for each primitive recursive definition (hereafter ...
2
votes
1answer
27 views

Logical consequence problem

$P=(\forall x)(\exists y) GTOE(x,y)$ $Q=(\exists y)(\forall x) GTOE(x,y)$ And I want to know whether Q is an logical consequence of P. I know P is a logical consequence of Q. But I cannot identify ...
1
vote
1answer
29 views

What does it mean to say that an automaton construction is “effective”?

Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{...
0
votes
0answers
22 views

Composition of substitutions of SLD tree

I found a question on my university past paper and it asked to get the SLD tree from a computation rule using some rules and facts. However I obtained the answer and to complete the question I have to ...
1
vote
1answer
43 views

Different definitions on closure under logical consequence

I am confronted with two (at first glance) different definitions on closure under logical consequence and would like to know whether they are equivalent and, if not, which is the one that would match ...
0
votes
1answer
38 views

What do these propositions show?

I am going through some lecture slides and have come to something that I do not understand. I get the general idea of what he is trying to do but I am not sure how the propositions show this. The ...
0
votes
0answers
8 views

Complexity class for subsumption for $\mathcal{AL}(\circ, ^{-})$

According to Baader et al's Description Logic Handbook, subsumption for $\mathcal{AL}(\circ)$ and $\mathcal{AL}(^{-})$ is in $\mathrm{P}$. However, I am not sure what complexity class subsumption for $...
1
vote
0answers
51 views

Prove there's no such algorithm

Prove there's no algorithm which gets $\varphi$, a formula without free-variables as in input and returns a formula of the form $\varphi ' =\exists x_1,\ldots,\exists x_n \psi$ where $\psi$ is a ...
0
votes
1answer
47 views

Are there any examples of consistent proper axiomatic extensions of classical logic?

By a proper axiomatic extension, I mean a logic with the same set of well formed formulas as classical logic, but with the set of theorems of the logic a proper superset of the theorems of classical ...
1
vote
2answers
24 views

Construct a truth table for $\left[\left(p\Rightarrow q \right) \land \sim q\right]\Rightarrow \sim p$

$\left[\left(p\Rightarrow q \right) \land \sim q\right]\Rightarrow \sim p$ I just wanted to check if I did this correctly: $$\begin{array}{c|c|c|c} \text{p} & \text{q} & \text{$p \...
8
votes
1answer
735 views

What is an example of a non standard model of Peano Arithmetic?

According to here, there is the "standard" model of Peano Arithmetic. This is defined as $0,1,2,...$ in the usual sense. What would be an example of a nonstandard model of Peano Arithmetic? What would ...
1
vote
1answer
34 views

Notation matter concerning 'or'-elimination

I have to show that $\{(\phi\lor\psi),(\lnot\phi)\}\vdash\psi$ using the following natural deduction rule: I don't know which of these is correct in term of notation: Could you please tell me? ...
2
votes
3answers
86 views

What does a period in between quantifiers mean?

I'm currently reading the notes (rather a book) of an MIT preliminary math course for discrete mathematics. In section on page 39, some ZFC axioms are written and roughly explained. For example, the "...
1
vote
1answer
42 views

Overspill in computable nonstandard models

Tennenbaums' theorem does not apply to Robinson Arithmetic ($Q$). There is a computable, nonstandard model of $Q$ "consisting of integer-coefficient polynomials with positive leading coefficient, plus ...
4
votes
1answer
86 views

what mathematical theorem is this

Reading Gödel, Escher, Bach by Douglas R. Hofstadter, at p. 552, Achilles asks the Crab to play this piece: ∀a:∃b:∃c:<~∃d:∃e:<(SSd * SSe) = b ν (SSd * SSe) = c> ^ (a+a)=(b+c)> And it seems ...
16
votes
4answers
2k views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
1
vote
0answers
113 views

Green eyes/Common Knowledge problem proof verification

I was trying to solve the common knowledge problem, but am not sure if my proof is accurate. Here is a rough statement of the problem : 'An island consists of $k$ people with green eyes, all ...
0
votes
1answer
26 views

Prove tautology using truth trees

Hi there I have to prove some tautologies using truth trees. I am doing this by negating the expresion and then trying to find contradictions on every branch. But I can't achieve this. I can't find ...
0
votes
1answer
79 views

Is there any System that's not logicist?

I have this assignment about different types of formal logic systems, like Lewis S5, Fuzzy Logic and some others, but now they ask me to search for any non logicist system, but I've search a lot and ...
1
vote
2answers
56 views

A question regarding contrapositive for implications

I am slightly confused about the negation for an implication after encountering two questions as follows: "Let P be the statement: If 3 is even, then 6 is even or divisible by 5. Write the negation ...
0
votes
1answer
27 views

what is the difference between symbolic and formal logic

I have just started learning logic, and was wondering is there any difference between symbolic and formal logic, or are they the same thing? And I would also like to know what the relationship of ...
0
votes
1answer
43 views

Dominating function easier to understand

Is there a pair of function $f$ and $g$ (both $\mathbb{N}\rightarrow\mathbb{N}$ and definable in the language of first-order Peano arithmetic) such that asymptotically $f$ dominates $g$, and $f$ has ...
1
vote
2answers
38 views

Is there a finite set of sentences, $\Gamma$ which is satisfiable?

Prove/ Disprove: There's a finite satisfiable set of sentences above $\Sigma$ a monadic-language, $\Gamma$ such that $\Gamma $ is satisfiable only for structures with size larger than $5$. ...
1
vote
2answers
38 views

Every finite subset of $\Gamma$ is consistent implies $\Gamma$ is consistent

Thm: If every finite subset of $\Gamma$ is consistent then $\Gamma$ is consistent. My notes claims that it can be implied from compactness of $\vdash$. Meaning: If $\Gamma \vdash A$ then there's a ...
-2
votes
2answers
74 views

How we can proove that propositions “the customer is always right”. [closed]

Yes it's seems like , doesn't make a sense ,but just think a second,can we do this?
0
votes
1answer
27 views

Determine the contrapositive of this statement:

For all real numbers $x$ and $y$, if the sum $x + y$ is rational, then $x$ is rational and $y$ is rational. My attempt at answer this: $p$ = "if the sum $x+y$ is rational" $q$ = "then $x$ is ...
0
votes
1answer
21 views

How to write the formula in Disjunctive Normal Form (DNF)?

Formula is: $$\emptyset=((p \lor r)\to q)\land (q\to r)$$ This is what I've already done: $$(p \lor r) \lor \lnot q)\land (q \lor \lnot r)$$ $$(p \lor r \lor \lnot q)\land (q \lor \lnot r)$$ and ...
0
votes
1answer
15 views

Monotonicity property of logical systems

Suppose we have a logical system $s$. Now, the monotonicity property tells us that: $\Gamma \vdash A$ and $\Gamma \subseteq \Delta$ implies that $\Delta \vdash A$. I see this definition somewhat ...
4
votes
1answer
1k views

Convert a WFF to Clausal Form

I'm given the following question: Convert the following WFF into clausal form: \begin{equation*} \forall(X)(q(X)\to(\exists(Y)(\neg(p(X,Y)\vee r(X,Y))\to h(X,Y))\wedge f(X))) \end{equation*} ...
0
votes
1answer
62 views

Difference of these two First Order Logic statements

1) $(\forall x)(\exists y)x{\le}y$ 2) $(\exists y)(\forall x)x{\le}y$ Assume that the domain of the variable is $D={0,1,2,...,99}$ These two statements says two things in natural language. I just ...
1
vote
1answer
63 views

Can we logically analyze mathematical theorems as if-then statements?

Many theorems in math have an if-then form. For example: "If a polynomial is of $n^{th}$ degree, then it has $n$ roots. In my other question, I learned that in order to analyze statements using truth ...
0
votes
1answer
30 views

A question concerning discharging assumptions

In page 19 of Mathematical Logic by Chiswell and Hodges, they provided a derivation of the sequent $\vdash (\phi\to(\phi\to\phi))$: where $(\to I)$ is: I understand that if we discharge $\phi$ ...
3
votes
1answer
87 views

Classical logic without negation and falsehood

It seems to me that Gerhard Gentzen's sequent calculus could just omit negation and falsehood, and still prove any classical tautology in a suitable form. (One approach might be to translate $\lnot A$ ...
0
votes
0answers
27 views

Translate common language to formally

I am learning sentence logic( again) and I have an exercise which I'm not sure If I did it wrong or right: Let $(A,\leq)$ be an totally ordered set. Translate to formal language: "Any totally ordered ...
0
votes
1answer
22 views

Determining values of the statements

I have a hard time, solving some logical statement exercises. Given two statements $v(x): |x| = 2$ and $u(x): x > 1$, where $x \in A = \{-1, 0, 1, 2, 3, 4\}$, I have to determine all values of ...
4
votes
4answers
151 views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
2
votes
0answers
54 views

Undecidable problems involving elementary functions

I am reading the article "Some undecidable problems involving elementary functions of a real variable" by Daniel Richardson and have some problems with understanding Lemma Three : Let $h(w)=w\sin w, ...
0
votes
0answers
26 views

How to determine value of statement

Given statement $v(x): |x| = 2 \text{ where } x \in A = \{-1, 0, 1, 2, 3, 4\}$. What will value of $\lnot v(x)$ look like?
1
vote
1answer
42 views

Is this translation correct?

If I say some real numbers are rational it can be denoted in first order logic, $(\exists x)$ $(real(x) \land rational(x))$ Where $real(x)$ - x is a real number. $rational(x)$ - x is a rational ...
0
votes
1answer
23 views

Formula to calculate Price of Service

I would like some help in elaborating a formula for a service I will be providing, to a retailer's clients. In simple terms I would be payed a 5% percentage over the price of the clients purchase, ...
0
votes
1answer
25 views

$A,B$ satisfies on the same finite structures implies $A,B$ are logically equivalent?

$A,B$ are two sentences in Predicate Logic, such that for every finite structure $A$ is satisified iff $B$ is satisfied. Prove/ Disprove: $A$, $B$ are logically equivalent. I assume this ...
3
votes
1answer
66 views

Dual statements involving functors

I know how to construct the dual of a statement concerning objects and morphisms of a category, and understand the duality principle associated, but I am having trouble when various categories and ...
3
votes
1answer
45 views

“One cannot hope to find any further essentially new lattice properties…”

I found the following passages in “A Course in Universal Algebra” by Burris and Sankappanavar. One cannot hope to find any further essentially new lattice properties which hold for the class of ...
2
votes
2answers
79 views

Changing Hilbert-style axioms

Consider the following system for Hilbert-style deduction: Axioms: $A \rightarrow (B \rightarrow A)$ $(A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))$ ...