Questions about 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
votes
0answers
44 views

Term rewriting; Compute critical pairs

I have tried to solve the following exercise but I got stuck while trying to find all the critical pairs. Any help is appreciated. Let $$ \sum = \left \{ \circ, i, e \right \} $$ where $\circ$ is ...
6
votes
0answers
71 views

Imaginary Number in Logic

The equation $x^2 = -1$ was once said to have no solution. Then the number $i$ was discovered (or invented?) and our number system got richer. In particular, in this new wonderful world of complex ...
0
votes
1answer
25 views

combine 4* 4 bytes values into 4 bytes and extract each value separately using one byte keys.

Here's my problem , I have 4 * 4 bytes i.e a,b,c,d and each one is 4 bytes length I want to generate x = function(a,b,c,d) , where x is 4 bytes and generate aKey,bKey,cKey,dKey where each key is 1 ...
0
votes
1answer
15 views

First order logic expression of “Each finite state automaton has an equivalent push-down automaton”?

Problem is Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such ...
2
votes
2answers
78 views

Is this a tautology: $\forall xP(x) \implies Q(x)$ if there's no $x$ such that $P(x)$?

Is this a tautology: $\forall xP(x) \implies Q(x)$ if there's no $x$ such that $P(x)$? I know that if there was an exists there instead of a for all, the antecedent would be false and thus the ...
0
votes
1answer
18 views

Demonstration with fitch notation and quantifiers

I'm tryng to demonstrate with fitch notation this: {∀x (A(x) ↔ B(x)), ∀x (A(x))} |= ∀x (B(x)) Here what I tried: http://i.stack.imgur.com/7S5Zy.png Someone can explain me how i can obtain ∀x (B(x)? ...
0
votes
1answer
18 views

Can the “$\forall x\in X $” be moved in this statement? “$\Gamma$ satisfiable $\implies \exists v:v(\alpha)=1 \forall \alpha \in \Gamma$”.

Can the "$\forall x\in X $" be moved in this statement? "$\Gamma$ satisfiable $\implies \exists v:v(\alpha)=1 \forall \alpha \in \Gamma$". I mean, is this the same than to write "$\Gamma$ ...
0
votes
5answers
78 views

Equivalence of $P\rightarrow Q$ and $\lnot P\lor Q$

How do we explain the logical equivalence $$(P\rightarrow Q ) \equiv [(\neg P)\; \vee \; Q]$$ and if possible could you please give an example illustrating this equivalence. Thanks alot !!
0
votes
0answers
26 views

Assistance in proving a tautology using a series of logical equivalences.

I am trying to prove, using a series of logical equivalence rules, that the following formula is a tautology: $$[a∧(a→b)∧(b→c)]→c$$ Yet despite numerous successes on other tautologies and logical ...
3
votes
0answers
87 views
+150

Reference request: equivalence between formulas in fixed point and first-order logic

I'm looking for materials on the relationship between first-order and fixed-point logics, specifically on the condition for a formula in some sort of fixed-point logic to have an equivalent ...
1
vote
2answers
47 views

Playing with propositional truth-tables

The following is the truth-table describing the definitions which allow us to establish truth values to composite formulae or molecules, which is nothing new: I had an idea about playing with the ...
1
vote
3answers
32 views

Discrete Math logically equivalent?

Show that $$(p \land q) \lor (\lnot p \land \lnot q) \equiv p\leftrightarrow q$$ How would I go about doing this? Do I use a truth table or a more "algebraic" process?
3
votes
1answer
56 views

The $<$-relation on $\mathbb{Z}$ is not definable in $(\mathbb{Z}, 0, +)$

I am a complete newcomer to logic and I'm having trouble proving the following: The $<$-relation on $\mathbb{Z}$ is not definable in $(\mathbb{Z}, 0, +)$. Now, I know that the $<$-relation on ...
0
votes
2answers
18 views

How do you transform the following in an implication?

So, I have : If the moon is made of green cheese, then cows jump over it. The moon is made of green cheese. Therefore, cows jump over the moon. How would I transform this as a logical implication ...
1
vote
1answer
78 views

Why is $\mathsf{Type} : \mathsf{Type}$ a contradiction?

In reading this cstheory.se question and this stackoverflow question, they mention that $\mathsf{Type}: \mathsf{Type}$ is inconsistent. I also understand that Coq has an infinite hierarchy of Types. ...
-1
votes
2answers
37 views
-5
votes
1answer
23 views

Help!!! I dont know where to start [on hold]

~P → Q, P →R ~R → Q I have to have this is in a formal proof and I dont know where to begin.
8
votes
2answers
406 views

Are the Gödel's incompleteness theorems valid for both classical and intuitionistic logic?

I am studying an undergraduate text about math logic. The proofs of the two Gödel's incompleteness theorems are not completely formal: they are admittedly simpler that the real proofs. For what I ...
0
votes
0answers
17 views

The DNF complexity of a function and its complement

If $f:\{0,1\}^n \to \{0,1\}$ is a $DNF$ formula with $t$ terms of width $w$, what can we say about the $DNF$ complexity of $\neg f$ (i.e., what is the number of terms and width needed to represent ...
0
votes
1answer
26 views

Is p|(q|r) is it equivalent to (q and r)

Using De Morgan's laws can I turn $p|(q|r)$ into: $(q \ and \ r)$ or does the and become an or, such as $(q \ or \ r)$ ?
0
votes
4answers
67 views

Why is this expression false?

I have thought thoroughly over this expression $(\:∀x∃y\:(Q(x, y) ⇒ P(x))\:) ≡ (\:∀x\:(∃y\:Q(x, y) ⇒ P(x))\:) $ however I do not understand why they are not equivalent? I thought the "there exists" ...
1
vote
2answers
34 views

Statements with multiple quantifiers

Suppose $P(x,y)$ is a predicate whose truth depends on $x$ ($x\in D$) and $y$ ($y\in E$). In the following statement,does the order of assigning values to $x$ and $y$ matter? For example, assign some ...
3
votes
1answer
32 views

Exercise from mathematical Logic about length of sentences in SL

Problem is that : Let $\phi%$ be a sentence of length $n$. Show that for $1\leqslant k<n$, $r(\phi,k)<l(\phi,k) $, where each of them represents the number of left(or right) parenthesis among ...
0
votes
2answers
17 views

how to convert this into cnf $(P\vee Q) \leftrightarrow (P\wedge Q)$?

Given the statement $(P\vee Q) \leftrightarrow (P\wedge Q)$ How can we simplify the double implication to obtain a CNF ? Is there any logical equivalence which I can use?
3
votes
2answers
26 views

Logic formula translation

I'm translating logic formulas into English and I've come across the following logic L-formula: $ \forall i \forall j \forall k: (\mathrm{in}(i,xs) \land \mathrm{in}(j,xs) \land \mathrm{in}(k,xs) ...
0
votes
1answer
310 views

Translate English sentences in statement logic

The task is: Give agood translationof the following puzzle into formal statement logic. ...
1
vote
1answer
56 views

$X = \{x\ :\ P(x)\}$ is it true that $a\in X⟺P(a)$

$X = \{x\ :\ P(x)\}$ is it true that $a\in X⟺P(a)$ I think it is true that $a\in X ⟹ P(a)$ but I'm not sure whether the converse is correct.
2
votes
1answer
51 views

Examples of theories with enough constants

A theory $\Gamma$ of $L$-sentences has enough constants if for every $L$-formula $\phi(x)$ with one free variable $x$, there is a constant $c$ such that $$\Gamma \vdash \exists x \phi(x) \rightarrow ...
4
votes
2answers
56 views

The indeterminacy of 0/0 and vacuous truth?

Today, my roommate and I picked up our friend from the airport. We were supposed to pick him up yesterday, but he missed his flight. We joked that he misses flights a lot, and that only catches 70% of ...
7
votes
1answer
293 views
+400

$F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$). Theorem 1. Assume that the characteristic of $F$ is zero. Then the existential theory ...
2
votes
1answer
70 views

Is this a statement (logic)?

$\frac{x^2-25}{x-5}=x+5$ represents a statement, which can be true or false (if $x\neq5$). But if $x=5$ is it still a statement? E.g. Is "undefined expression equals 10" a statement? And why?
3
votes
1answer
148 views

Prove a set of connectives is functionally complete

What is the right way of proving that a set of logical connectives is or not functionally complete? For example, if I have {→,∨} how can I show it is or not functionally complete? Any ideas?
4
votes
1answer
38 views

How to formulate the requirements that a counterexample must satisfy?

Let $p_1, p_2$ and $p_3$ be three statements. Suppose now we know that if $p_1$ is true, then $p_2$ and $p_3$ are equivalent. That is, if $p_1$ and $p_2$ are true, then $p_3$ is true, and if $p_1$ ...
1
vote
1answer
28 views

interpreting words as if-then statements

In my book it is stated the $P \rightarrow Q$ is used to interpret $P$ only if $Q$. So, in the statement "$x$ divides 4 only if $x$ divides 8" should the symbolic form not be $P: x \text{ divides ...
3
votes
1answer
40 views

How can you prove the equivalance relation for the following model?

Given two Kripke-frames $M=(W,R)$ and $U=(E,S)$ where $W,E$ are 'possible worlds' and $R,S$ are equivalence relations on $W,E$ respectively. we define $M\otimes U = (W',R')$ as follows: $W'=\{\ ...
5
votes
1answer
122 views
+50

Facts on elementary submodels

In the paper of "Aspero, Larson, Moore - Forcing Axioms and the CH" three facts are stated as well-known. As i have not read them before, they are not that obvious to me. Maybe good references to ...
1
vote
1answer
23 views

Logic formula translation

I'm studying for a logic exam I've come across the following L-formula $$ \forall i (\operatorname{in}(i,xs) \Rightarrow \exists j (i = 2 \cdot j)) $$ Where the $\operatorname{in}(x,xs)$ predicate ...
0
votes
1answer
43 views

Sentence $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements

I'm trying to prove this result: For any natural number $n \geq 1$ there is a sentence $\phi_n$ such that $\phi_n$ is true in $S$ iff $S$ has at most $n$ elements. My attempt: By induction ...
0
votes
1answer
16 views

Bounding probability based on binary values

I've been reading this paper on probabilistic logic: http://ai.stanford.edu/~nilsson/OnlinePubs-Nils/PublishedPapers/problogic.pdf On page 76 theres a 3d diagram and Nilsson mentions the bounds on ...
-2
votes
1answer
29 views

$f^{-1}(S)$ of a recursively enumerable set [on hold]

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a computable function and let $S \subseteq \mathbb{N}$ be recursively enumerable. How does one show that the inverse image $f^{-1}(S)$ is also recursively ...
0
votes
1answer
28 views

In which way are these logical statements similar to each other?

If x is even, then x is not divisible by 5. Every even integer is not divisible by 5. Alright so the original problem is for me to determine a counterexample if these are false. I already found a ...
1
vote
0answers
22 views

Does this method show that the projections $K$ and $L$ of an enumeration are primitive recursive?

In the fifth edition of Boolos et al's Computability and Logic, Exercise 6.5 asks the following (modified to provide background definitions): Define $K(n)$ and $L(n)$ to be the first and second ...
0
votes
1answer
41 views

If x is even, then x is not divisible by 5.

I have to provide a counterexample otherwise. So if one counterexample is enough, can I say x=10, because 10/5 = 2, thus x is not divisible by 5. Is this a justifiable answer?
4
votes
2answers
98 views

Can we find a formula defining a recursively enumerable set?

By Post's Theorem we know that a set $A\subseteq\mathbf{N}$ is recursively enumerable iff it is definable by a $\Sigma_1$-formula, i.e. there exists a $\Sigma_1$-formula $\varphi(x)$ with $x$ free ...
5
votes
1answer
57 views

Does the foundations of Arithmetic need to be effective?

I was reading about Godel's incompleteness theorem which is true for any formal theory that satisfies certain properties. One of these properties is the following: "The theory is assumed to be ...
4
votes
0answers
120 views

Infinite Chain of Implication Statements - Can it have a Conclusion?

First, does an infinite string of implication statements have a conclusion? If so, is there a such thing as a "closure" of such a beast, giving a conclusion? I am also trying to determine if the ...
1
vote
1answer
36 views

$\gamma=(\psi \implies \phi)$ is a tautology $\equiv \psi$ is a contradiction or $\phi$ is a tautology.

Prove that: If $\psi,\phi$ are formulas such that $\text{VAR$(\psi)$} \cap\text{VAR$(\phi)$}=\emptyset$. Then $\gamma=(\psi \implies \phi)$ is a tautology $\equiv \psi$ is a ...
2
votes
2answers
71 views

How does the Soundness Theorem follow from this lemma?

The soundness theorem is a famous theorem in logic that goes like this: If $\Gamma \vdash \phi$, then $\Gamma \vDash \phi$. It's supposed to follow readily from Lemma 3.2.3 from Moerdijk/Van ...
41
votes
5answers
37k views

What's the difference between predicate and propositional logic?

I'd heard of propositional logic for years, but until I came across this question, I'd never heard of predicate logic. Moreover, the fact that Introduction to Logic: Predicate Logic and Introduction ...
2
votes
1answer
42 views

Is it true that $A\cong B$ implies $A = B$ when $A$ and $B$ are ordered structures

In Immerman's book "Descriptive complexity" he says that $A \cong B$ implies $A = B$ when $A$ and $B$ are totally ordered structures. See: http://i.stack.imgur.com/BjXKE.png (Descriptive ...