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
28 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
23 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
15 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
25 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
35 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
55 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
68 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
32 views

Boolean Algebra, stuck

I'm having trouble simplifying this Boolean Algebra equation. Can anyone help? XY'Z + X'Y'Z + XYZ + XY'Z
3
votes
0answers
71 views

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
52 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
26 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
35 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
70 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
61 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
143 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
185 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
33 views

Tautology vs Contradiction vs Workable formula [on hold]

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
728 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
108 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
64 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
64 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, ...
0
votes
1answer
41 views

If $\models \neg \phi$, then $\models \phi^\circ$, where $\phi^\circ$ is the “semi-dual” of $\phi$

This is exercise 1.3.22 from Hinman's Fundamentals of Mathematical Logic. Let $\mathrm{Sent}_{\neg, \vee, \wedge}$ be the set of all sentences from propositional logic closed under negation, ...
0
votes
0answers
21 views

Problem regarding type inhabitation

Perhaps it is a trivial question but I'm very new to Lambda Calculus and Proof Theory. Before we go to the core problem let's take account of the following Definition: For arbitrary type $\tau \in ...
1
vote
2answers
46 views

Can I do instantiation like this?

Suppose, if I have been given this: $\forall x \in A(P(x))$ and $\exists y \in A(Q(y))$. Now from $\forall x \in A(P(x))$ using universal instantiation, I get $P(c)$ where $c$ is an arbitrary element ...
1
vote
0answers
36 views
+250

Injury-free proof of Cof being $\Sigma^0_3$-complete

How can I prove, without using priority argument, that Cof, the set of indices of cofinite c.e. sets, is $\Sigma^0_3$-complete? I know an injury-free proof of Rec being $\Sigma^0_3$-complete, where ...
-2
votes
1answer
51 views

Proof validity of following FOL/statement given by Natural deduction

The fastest running person is a Jamaican. Therefore, anyone who is not a Jamaican can be overrun by someone. User predicate P (x) : x is a person, F (x, y) : x can run faster than y and J(x) : x ...
0
votes
1answer
27 views

Order of quantifiers in prenex normal form

I was wondering while doing some transformation into prenex form whether there is a situation when it does matter in what order you pull out the quantifiers to the front. If you know a good example, ...
2
votes
1answer
45 views

Proof of derivability

I'm a beginner at mathematical logic and I've come across the following problem: Let $X, Y \subset \mathcal{F}$, where $\mathcal{F}$ is the set of all formulas, and assume that $X \cup \{ \lnot ...
0
votes
4answers
67 views

Having hard time understanding implies

$P \Rightarrow Q$ I am having hard time understanding the second and third rows in the truth table. Implies means use if than, but the third statement is confusing. $P$ : Tesla Model S is a fast ...
0
votes
2answers
39 views

Diagonalization Principle

Diagonalization principle has been used to prove stuff like set of all real numbers in the interval [0,1] is uncountable. How is this principle used in different areas of maths and computer science ...
0
votes
1answer
37 views

Winning strategy for graphs (Ehrenfeucht-Fraïssé games)

I'm stuck with a question: Proof that you can't express if a graph is cyclic in first-order logic. The definition of cyclic is that for every node there is a ...
1
vote
2answers
42 views

Build a 3 bit full adder using only XOR gate?

I don't know if this is the right place to ask this, but I'm trying to design the logic for a simple calculator and I was wondering how can you build/design a 3 bit full adder using only XOR (one or ...
-3
votes
0answers
32 views

Neither symmetric nor asymmetric [closed]

I have a set X={s,t,u,v}. I have shown an example where X is symmetric, antisymmetric but not asymmetric, asymmetric but how would I get an example of a binary relation that is neither symmetric nor ...