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)

0
votes
1answer
14 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
40 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
17 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$ ...
-1
votes
0answers
22 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.
0
votes
0answers
16 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
1answer
46 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
votes
2answers
37 views

Is there a way to simplify… [on hold]

Is there a logical equivalence to ¬p∨q?
-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.
1
vote
3answers
30 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?
0
votes
0answers
14 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
25 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)$ ?
3
votes
1answer
30 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
1answer
22 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
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?
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" ...
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) ...
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 ...
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 ...
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 ...
4
votes
1answer
37 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$ ...
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?
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 ...
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'=\{\ ...
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.
0
votes
1answer
15 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 ...
0
votes
1answer
42 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 ...
-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 ...
1
vote
0answers
21 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
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 ...
0
votes
1answer
39 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?
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 ...
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 ...
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 ...
0
votes
1answer
34 views

Boolean Algebra, stuck

I'm having trouble simplifying this Boolean Algebra equation. Can anyone help? XY'Z + X'Y'Z + XYZ + XY'Z
5
votes
1answer
121 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 ...
0
votes
1answer
54 views

How to prove $A \rightarrow B \vdash (\exists x)A → (\exists x)B$? [closed]

Metatheorem(Distributivity or Monotonicity of $\exists$). For any $x,A,B,$ $A \rightarrow B \vdash (\exists x)A \rightarrow (\exists x)B$.
0
votes
1answer
28 views

Is the theory of real closed fields expanded by restricted analytic functions decidable?

Is the theory of real closed fields expanded by restricted analytic functions decidable? I have been doing a lot of reading on the subject, but I can't quite find a straight answer on this one. 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 ...
1
vote
1answer
30 views

If $\alpha$ is a tautology and $\beta$ a contingency then $(\alpha $ and $\beta) $ is equivalent to $\beta$.

If $\alpha$ is a tautology and $\beta$ a contingency then $(\alpha $ and $\beta) $ is equivalent to $\beta$. This is a pretty basic statement in logic, but I don't know how to prove it, could you ...
2
votes
1answer
20 views

For a finite character set $\Sigma$, what would be a formal proof that $\Sigma^{+} = \Sigma^{*}\Sigma$?

Let there be a finite character set $\Sigma$, as in computer science convention. $\Sigma^{*}$ is defined as in Kleene star notation (https://en.wikipedia.org/wiki/Kleene_star) with $\Sigma^{+}$ ...
-1
votes
0answers
14 views

Is total substring well-ordering of a set containing $\omega_0$-length string possible? [duplicate]

I originally asked the quesiton here: http://math.stackexchange.com/questions/1411731/can-a-set-containing-a-string-of-infinite-length-be-well-ordered-by-substring-to and Can a set containing a ...
0
votes
1answer
35 views

Can a set containing a string of length $\omega_0$ be well-ordered by substring total order?

I originally asked the quesiton here: http://math.stackexchange.com/questions/1411731/can-a-set-containing-a-string-of-infinite-length-be-well-ordered-by-substring-to But right after posting the ...
0
votes
3answers
35 views

Clarification regarding function

I have been reading Velleman's How to prove book and this is one of the paragraphs written in the Functions chapter: For every $a \in A$ and $b \in B$, $b = ...
1
vote
3answers
72 views

Can we express a $\forall x\in S \exists y\in T ~P(x,y)$ statement solely through $\land, \lor, \Rightarrow$?

I'm currently trying to prove that $\exists n\forall m~P(m,n)\Rightarrow \forall m\exists n P(m,n)$ formally. This is important to me because my professor and various only sources have hinted that in ...
3
votes
4answers
65 views

Intuitive explanation for p ∨ q → r ≡ ( p → r) ∧ (q → r)

Although, it is possible to prove the above equivalence using truth tables, I don't know how to prove it without using truth tables.Can someone explain it in plain english?
0
votes
1answer
9 views

Proving $F . G$ is the greatest lower bound

This is one of the problem I have been solving from Velleman's How to Prove book: Suppose $A$ is a set. If $F$ and $G$ are partitions of $A$, then we'll say ...
4
votes
4answers
144 views

Is it true that $A \in A$?

I defined the set $A$ as follow: \begin{align} A_0 & =\varnothing \\ A_1 & =\{A_0\}=\{\varnothing\} \\ A_2 & =\{A_1\}=\{\{\varnothing\}\} \\ A_3 & =\{A_2\}=\{\{\{\varnothing\}\}\} \\ ...
1
vote
2answers
189 views

Works of Kurt Gödel

I'd like to know how to get started with Gödel's work and theorems. I have a decent knowledge of tensors, Einstein field equations. When it comes to logic and set theory, I'm a beginner. Can anyone ...