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
2answers
26 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
20 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
1answer
26 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
45 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
53 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
27 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
36 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
66 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
22 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
36 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
2answers
54 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
27 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
0answers
20 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
27 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
38 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
56 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
70 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
118 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$? [on hold]

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
71 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
62 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 ...
0
votes
2answers
36 views

What's next step to prove this boolean expression?

I need to prove that the first member of this equivalence is true: $$(p\vee q)\wedge (\sim p \wedge (\sim p\wedge q))\equiv \sim p \wedge q$$ I have reached the following point, but I don't know how ...
5
votes
1answer
49 views

From Primitive Recursive to Recursive by Iterating over more than one Argument?

Is the only way a function can be recursive and not primitive recursive by growing faster than primitive recursion allows (as with Ackerman's function)? If so, then consider the following. Primitive ...
2
votes
1answer
66 views

Proving $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ using Fitch notation

I'm supposed to prove the validity of the following $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove ...
0
votes
0answers
40 views

Is the set containing just zero a mathematical field? [duplicate]

Consider the set $\left\lbrace0\right\rbrace$ together with the usual operations of addition and multiplication. Is this set together with these operations a field? I know that one of the ...
0
votes
2answers
35 views

Tautology vs Contradiction vs Workable formula [closed]

can someone draw a relationship between: The figure represents a set of propositional formulas plot the relationship between: Tautology, Contradiction, Workable formula. Thank you very much! ...
0
votes
1answer
42 views

What is this called in propositional logic?

What is the common name for something of the form $\Gamma \vdash B$ where $\Gamma$ is a set of formula and B is a single formula. I'm currently calling it a conditional assertion. I thought it ...
0
votes
1answer
33 views

convert to CNF and can anyone guide me with the steps?? [closed]

Convert to CNF: $$x_1 \land x_2 \land \big(\neg (x_3 \lor x_4)\big) \lor \big(x_5 \land (\neg x_4)\big).$$
7
votes
4answers
732 views

As of August 2015, is the “set” of all gold medalists in the 2016 Olympics a set?

As of August 2015, is the "set" of all gold medalists in the 2016 Olympics a set? I think it is since the defining property is very clear. However, given any $x$, we do not know if $x$ is in this ...
1
vote
2answers
109 views

How does Turing's thesis imply the existence of a universal Turing machine?

In the fifth edition of Boolos et al's Computability and Logic, Exercise 4.5 asks the following: A universal Turing machine is a Turing machine $U$ such that for any other Turing machine $M_n$ and ...
1
vote
0answers
16 views

$\forall a[P(a)\implies Q(a)]\wedge \forall a[Q(a)\implies P(a)]\stackrel{?}{\equiv} \forall a[[P(a)\implies Q(a)]\wedge [Q(a)\implies P(a)]]$ [duplicate]

I'm reading: Devlin's Joy of Sets. He gives the definition of the axiom of extensionality: The definition of subset: And then there is this exercise: Rewriting it, I'd have: ...
1
vote
1answer
22 views

Prove that $R$ is anti-symmetric

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 ...
3
votes
1answer
65 views

Independence of existence of inaccessible cardinals

Let $I$ be the formula which states that there exists strongly inaccessible cardinals. My question is regarding the proof of $ZFC\nvdash I$ appearing in Jech (part of theorem 12.12). He starts by ...
1
vote
1answer
65 views

On provability of Paris–Harrington theorem

It is said that the Paris–Harrington theorem is true, but not provable in Peano arithmetic. I want to ask: So how do they know that it is true if it has no proof? I cannot imagine someone knows ...
0
votes
1answer
32 views

What kind of proof system have Zalta used in “Basic Concepts in Modal Logic”?

I have read that text and I'm so interested in the proof theoretic style (as also claimed by Zalta that it is used in modern approaches to modal logic) in it: That is both more mathematically rigorous ...
0
votes
3answers
111 views

Proof that there are infinitely many prime numbers

I answered a question to prove that there are infinitely many prime numbers, but I'm not sure if my attempt is right. Can somebody help me to check if my attempt is right? I would like, if I am wrong, ...