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)

9
votes
2answers
630 views

Is there a mistake in the SEP article about Godel's Incompleteness theorems?

Update: The mistake referred to in this question has now been corrected. The below refers to a previous version of the article: The second supplement to the Stanford Encyclopaedia of Philosophy ...
6
votes
1answer
148 views

When was contemporary logical notation established

When contemporary fundamental logical notation was established? I mean basic symbols as used nowadays $\iff\implies\land\lor\lnot\forall\exists\vdash\models$.
1
vote
1answer
54 views

Logic expression simplification

I want to simplify this logic expression: Y = (A ∧ B ∧ ¬C ∧ D ) ∨ (C ∧ ¬D) ∨ (A ∧ B ∧ C) ∨ (¬A ∧ C) I know it must become Y = (A ∧ B ∧ D) ∨ (C ∧ ¬D) ∨ (¬A ∧ C) and I found it with Karnaugh, but I ...
6
votes
1answer
177 views

Turing invariance on large sets

Definition: A function $f: 2^{\omega} \rightarrow 2^{\omega}$ is Turing invariant if $x \equiv_T y \rightarrow f(x)\equiv_T f(y)$. Question I (under $ZFC$): Let $f: 2^{\omega} \rightarrow 2^{\omega}$ ...
1
vote
1answer
58 views

Problems with validity in type theory

I'm twisting my brains over some simple formulas in intensional type theory. First: If $\exists x \Box (x=^{\vee}j)$, s.t. $x$ is of type $<e>$ and refers to an entity $e$ and $j$ is of ...
1
vote
1answer
360 views

Equivalence vs equisatisfiability

Wikipedia page states that first order formula after skolemization is equisatisfiable but not equivalent to original one. I do not understand what the difference is. I know definition of ...
2
votes
1answer
77 views

Prove formula's tautology

Prove that a formula that only consists of variables, logical negation and logical equality, and in which all variables and negation appear for an even number of times, must be tautological.
0
votes
1answer
204 views

Solution of a symbolic logic problem with Separation of Cases inference rule

$$(( S \land \lnot P ) \lor ( Q \land R )) ∴ ( \lnot P \lor Q )$$ I am trying to solve this symbolic logic problem ^^ with the separation of cases inferences rule but I am having trouble.
0
votes
2answers
56 views

Formal negation of $((p\rightarrow q) \vee (q \leftrightarrow r)) \rightarrow q$

Can someone give me an outline for how I can negate the following? $((p\rightarrow q) \vee (q \leftrightarrow r)) \rightarrow q$
1
vote
1answer
33 views

Existential Quantifiers translated into categorical statements?

I've been recently trying to translate the categorical statements into the quantifiers ($\forall$ and $\exists$). Attempts I believe I can make the E statement as $$\nexists s:p,$$the A statement ...
2
votes
1answer
111 views

How is quantifier elimination accomplished in second and higher order logic?

In first order logic we can eliminate existential quantifiers using a second order equivalence relation: $\forall$x$\exists$y P(x, y) $\iff$ $\exists$f$\forall$x P(x, f(x)) Dropping the existential ...
0
votes
1answer
18 views

Simplification of expressions?

The expression below fd < S && ld > e || fs > s && ld > e || fd > s && ld < e || fd < s && ld < e Is the ...
1
vote
1answer
70 views

Jayne's Equation 1.13 Derivation

Dear Stack Exchange Members, I'm reading 'Probability Theory - The Logic of of Science" by ET Jaynes, and I'm on pg. 11. Jayne's says: *"...For example, we shall presently have use for a rather ...
0
votes
1answer
123 views

Church's first postulate for the foundation of logic

In his paper, A Set of Postulates for the Foundations of logic, Church enumerates a set of postulates that he calls formal postulates. They are all said to be true and free from intuitive logic. ...
19
votes
5answers
7k views

In plain language, what's the difference between two things that are 'equivalent', 'equal', and 'identical'?

In plain language, what's the difference between two things that are 'equivalent', 'equal', 'identical', and isomorphic? If the answer depends on the area of mathematics, then please take the ...
0
votes
1answer
50 views

Find some complete theory $U \supseteq T$

I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are: $\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$, $\psi \equiv ...
2
votes
1answer
246 views

How to transform expressions in polish-notation

Here is an example of a De Morgan transformation of a logic expression: $ \neg ({a} \wedge {b}) $ becomes $ (\neg {a} \vee \neg {b}) $ My intuitive view of this operation is that I'm "moving the ...
2
votes
1answer
56 views

Easy little triangle configuration

One of the four shapes is not needed to make the shape in the first pic. Which one? Once again, is it just noticing some properties? Or are there any other logical ways of figuring it out? I ...
1
vote
2answers
31 views

What does this proposition mean?

$∀x ∈ P(\Bbb{N}), x \notin \{\} \Rightarrow ∃y ∈ x, ∀z ∈ x \ | \ y < z$ Where $P(x)$ is the power set. I'm interpreting it as "in all subsets of the natural numbers, there exists a value smaller ...
0
votes
1answer
91 views

Exactly one in Predicate Logic

Could anyone tell me how to translate the following sentence into predicate logic. E : the set of elephants A : the set of animals G(x) : x is green E(x) : x is an elephant N(x; y) : name of x is ...
3
votes
3answers
191 views

Can a Turing Machine process an infinite string?

I read in a text book once that a finite state acceptor machine cannot be an acceptor for an infinite language. My question is does this apply to Turing Machines? The implication, it seems to me, ...
1
vote
1answer
33 views

Prove, that predicate is inexpressible in the given signature

I have a predicate $y=x+1$. I want to prove, that this predicate is inexpressible in $(\mathbb{Z}, {=}, f)$, where $f = x\mapsto(x+2)$. I understand, that I need to come up some automorphism, in ...
5
votes
2answers
124 views

A question about infinities and pots of paint

This question is inspired by http://math.stackexchange.com/a/1052384/66307 and quotes from it heavily. Take a countably infinite paint box; this means that it has one color of paint for each positive ...
1
vote
1answer
31 views

Quantifying over all random variables

I often encounter statements in the literature in probability theory of the form: "Let $(\Omega, \mathscr{A}, P)$ be a probability space, $S$ a state space and $X : \Omega \to S$ a random variable ...
1
vote
2answers
85 views

Proving logical equivalence of two statements

So for extra credit, our teacher told us to prove the following 2 statements are logically equivalent: The square is the quadrilateral that maximizes the area given a fixed perimeter $P$. The square ...
0
votes
1answer
89 views

Strong Kleene interpretation

Consider: $\\$ $\Box(\phi \wedge \psi) \rightarrow \Box(\phi) \wedge \Box(\psi)$ I guess this yields by the reflexivity axiom for intensional predicate logic? But I was wondering whether it is also ...
1
vote
0answers
74 views

Importance of Gödel Numbering System

How important is Gödel numbering to his incompleteness proofs, set theory, logic theory in general and proofs employing ZFC? Can we use some other numbering or 'meta' programming? How about if one ...
1
vote
2answers
184 views

Express a Proposition In Formal Logic

I am doing a question where I have to express: There is no largest prime number, in formal logic. This is the solution given: Of course this is a true statement, so it could be expressed by the ...
3
votes
2answers
77 views

Questions regarding well formed expressions in the Theory of types

I'm dealing with a question in type theory: Is it possible to assign types to $\alpha$, $\beta$, and $\gamma$ in such a way that both $(\alpha (\beta))(\gamma)$ and $\alpha (\beta (\gamma))$ are ...
0
votes
1answer
29 views

$A$ is c.e. $ \Leftrightarrow$ $A \le_{1}K_{0}$

$A$ is c.e. $ \Leftrightarrow$ $A \le_{1}K_{0}$ let $A\subseteq N$ show that if $A$ is c.e. $ \Leftrightarrow$ $A \le_{1}K_{0}$ proof:$\Leftarrow$ $A \le_{1}K_{0}$ via$f $ then we have $ x\in A ...
1
vote
1answer
73 views

Solve this tautology

Hypotheses: not $q$, $p$ or not $s$, $p \rightarrow$ ($d$ and $q$), $e \rightarrow s$ Conclusion: not $e$ I have thus far, but unsure how to proceed. I am looking forward to solve it using ...
1
vote
1answer
50 views

Does an interpretation of a structure by itself induce a bijection on the automorphism group of the structure?

Let $\Gamma$ be a model-theoretic interpretation of a structure $B$ in a structure $A$. Then $\Gamma$ induces a group homomorphism $\alpha_\Gamma:\mathrm{Aut}(A) \rightarrow \mathrm{Aut}(B)$. (See, ...
0
votes
0answers
36 views

express constraint violation

A very simple question, what's the mathematical symbol (expression) that represents constraint violation. Specifically, we have a set of constraints R each of which taking three variables, two sets of ...
2
votes
3answers
385 views

Can we prove that axioms do not contradict?

We construct many structures by chosing a set of axioms and deriving everything else from them. As far as I remember we never proved in our lectures that those axioms do not contradict. So: Is it ...
4
votes
6answers
142 views

the purpose of induction

After getting an answer (in a comment) from peter for this question I have a follow up question. If, in all horses are the same color problem for example, we need to use reason, reason which is ...
3
votes
4answers
252 views

how to point out errors in proof by induction

I have searched for an answer to my question but no one seems to be talking about this particular matter.. I will use the all horses are the same color paradox as an example. Everyone points out ...
1
vote
3answers
75 views

How to determine if this is true or false?

$$\exists x \in X, (P(x) \to Q(x))\hspace{0.2cm} \iff (\exists x \in X, P(x))\to (\exists x \in X, Q(x))$$ $$\forall x \in X, (P(x) \to Q(x))\hspace{0.2cm} \iff (\forall x \in X, P(x))\to (\forall x ...
0
votes
2answers
93 views

Proving that universal quantification distribute over conjunction

show $$\vdash [\forall x(P(x))\wedge \forall x(Q(x))]\to \forall x[P(x)\wedge Q(x)]$$ answer: by Q_{1}:$\forall x \phi\to\phi_{t}^{x}$ so we have $\forall x P(x)\to P(t)$ $\forall x Q(x)\to Q(t)$ ...
0
votes
2answers
120 views

Stroeker Problem: Sum of consecutive cubes being a perfect square

I encountered to following textbook problem in the book 'Introduction to probability' (p.34) by Blitzstein and Nwang. NO homework, but self-study ! Part a) is no problem, but b) struck me down. ...
1
vote
2answers
73 views

Pre-nex normal form. Correct way to distribute negations among quantifiers

Start point: $$(¬∀x P(x) ∨ ¬∀y Q(y)) → ¬∃x G(x)$$ Implication to Disjunction (DeMorgans Laws): $$¬(¬∀x P(x) ∨ ¬∀y Q(y)) ∨ ¬∃x G(x)$$ Now I am at the point where I need to move in the negations to ...
2
votes
2answers
141 views

Prove the Robinson arithmetic has infinite non-isomorphic models

I found this question: Can finite theory have only infinite models?, where is proved that Robinson's Arithmetic can have infinite models, but I've been unable to prove or find a proof of the existence ...
0
votes
0answers
64 views

show that if $x$ is not free in $\Psi$ then $\phi \rightarrow\Psi\vDash [(\exists x \phi)\rightarrow\Psi]$

show that if $x$ is not free in $\Psi$ then $$\phi \rightarrow\Psi\vDash [(\exists x \phi)\rightarrow\Psi]$$ answer: by QR $$\phi \rightarrow\Psi\vdash [(\exists x \phi)\rightarrow\Psi]$$ so ...
2
votes
2answers
200 views

How is the Liar Paradox a paradox?

In the Liar Paradox, someone says "I am a liar.", which we assume means "Everything I say is false." (although even that's not correct, a liar is defined as someone who says lies, not someone who only ...
55
votes
12answers
7k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
0
votes
2answers
42 views

Laws of Logic Negation Simple

I cant quite remember, when you are using the laws of logic to simplify an argument or an argument about sets. Do you start on the outside of the brackets with the outer most negation? Or the inner ...
5
votes
2answers
1k views

What are some examples of third, fourth, or fifth order logic sentences?

I know this seems like an obvious question, but I haven't been able to find any examples of sentences in logic higher than second order, so my intuition on how it's supposed to behave is failing me. ...
0
votes
0answers
43 views

proving $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$

I looking for proof of $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$ in the foloowing logic (SJ logic in paper of Greg Restall , Subintuitionistic logic) $$⊢A→A$$ ...
2
votes
3answers
51 views

Is the order of four quantifiers in a predicate formula relevant?

Is the formula: $$\forall x \exists y \forall z \exists u (F(x) \lor G(y) \to F(z) \lor G(u))$$ Equivalent to formula: $$\forall z \exists u \forall x \exists y (F(x) \lor G(y) \to F(z) \lor ...
2
votes
1answer
116 views

Show that given a partial order there exists a total order [duplicate]

STATEMENT: Suppose that $≺$ is a partial ordering of $\mathbb{N}$. Use the Compactness Theorem for first order logic to show that there is a total ordering $≺_∗$ of $\mathbb{N}$ such that for all n ...
4
votes
3answers
348 views

Need help to prove (A∪B) - (C - A) = A ∪ (B - C)

Having trouble with a discrete math question involving sets. Have been asked to prove: (A∪B) - (C - A) = A ∪ (B - C) This is what I have so far: x ϵ A or x ∈ (B - C) x ∈ A or (x ∈ B and x ∉ C ) ...