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
0answers
11 views

Seemingly Simple Equation Question “Verify my solution please!”

"A container is 1/8 full of water. After 10 cups of water are added, the container is 3/4 full. What is the volume of the container, in cups?" Ok I wrote out an equation: (1/8)V + 10C = (3/4)V. I ...
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
22 views

$f^{-1}(S)$ of a recursively enumerable set

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
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
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
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?
2
votes
2answers
94 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
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 ...
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
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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
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
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 ...
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 ...
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^{+}$ ...
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 ...
-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 ...
6
votes
1answer
115 views

Construct an OR gate when missing input information

Is there a way to construct an OR gate when the input for one combination is unknown? For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = ...
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 = ...
9
votes
6answers
727 views

Countable axiom of choice: why you can't prove it from just ZF

This is a follow-up question to the discussion about the finite axiom of choice here. Suppose we have a countable collection of non-empty sets $\{A_1, A_2, A_3,\cdots\}$ Reasoning as indicated in ...
1
vote
0answers
35 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 ...
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 ...
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 ...
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 ...
9
votes
5answers
2k views

General McNugget problem

The classic McNugget problem states: Chicken McNuggets can be purchased in quantities of 6, 9, and 20 pieces. You can buy exactly 15 pieces by purchasing a 6 and a 9, but you can't buy exactly 10 ...
6
votes
1answer
769 views

Distinction between equality, logical equivalence and biconditionality.

This is my first post here so I'm not sure about the proper etiquette, but I have quite a few questions all pertaining to one underlying concept, and I hope it's okay that I've grouped them all into ...
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
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
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
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).$$
3
votes
2answers
59 views

Proving $Y$ such that $Y \cap B = \emptyset$

I have been solving this problem from Velleman's How to prove book: Suppose $B \subseteq A$ and define a relation $R$ on $\mathcal{P}(A)$ as follows: ...
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 ...
-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
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 ...
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 ...
6
votes
1answer
234 views

$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 ...
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 ...
4
votes
1answer
574 views

Convert a WFF to Clausal Form

I'm given the following question: Convert the following WFF into clausal form: \begin{equation*} \forall(X)(q(X)\to(\exists(Y)(\neg(p(X,Y)\vee r(X,Y))\to h(X,Y))\wedge f(X))) \end{equation*} ...