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)

2
votes
1answer
35 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
27 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
58 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
48 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
23 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
31 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
18 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
31 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
33 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
66 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
55 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?
-3
votes
1answer
60 views

Pigeonhole Principle proving [on hold]

Suppose that there are 30 people in the room. Assume that everyone in the room has at least one acquaintance. Show that there are two persons in the room who have equal numbers of acquaintances. Since ...
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
138 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
181 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
47 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
64 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
40 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
32 views

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

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
726 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
97 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
63 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
40 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
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 ...
-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
43 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
64 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
38 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
36 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
39 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 ...
2
votes
0answers
25 views

How - in a Kripke model - to define a world by modal formulas true only at them?

I'm currently using van Benthem's "Modal logic for open minds", ed. 2010. In page 16 (and later in exercises), he considers a model whose relations are shown by directed graphs (the so called process ...
2
votes
0answers
29 views

What the definition of validity of a formule in a possible Kripke-world in Modal Logic?

Basic question here but I cannot find the definition: Given a modal logic and a set of propositions $P$, a model $M=(W,R,V)$ where $W$ are possible worlds, $R$ an accesibility relation and $V$ a ...
4
votes
1answer
67 views

extending automorphisms in complete boolean algebras

Suppose $A$ is a complete subalgebra of a complete boolean algebra $B$. Suppose $f : A \to A$ is an automorphism. Then $f$ can be extended to an automorphism of $B$. I can see this using the fact ...
3
votes
1answer
18 views

Let $\Gamma$ be a $\kappa$-based monotone operator where $\kappa$ is regular. Then the closure ordinal of $\Gamma$ is $\kappa$.

A monotone operator $\Gamma: \mathcal{P}(A) \to \mathcal{P}(A)$ is an operator such that, if $X \subseteq Y \subseteq A$, then $\Gamma(X) \subseteq \Gamma(Y)$. A monotone operator is $\kappa$-based ...
0
votes
1answer
87 views

A few questions about a true but unprovable statement

Can someone explain to me what this comment means: If ZFC is not a sound theory, a true but unprovable statement may be refutable and therefore decidable. What is a sound theory? What is ...
1
vote
2answers
38 views

Is the replacement theorem true for conditionals?

I read about the replacement theorem in Kleene's intro to logic which is as follows: If $\vDash(A\sim B)$ then $\vDash(C_A\sim C_B)$ where $C_A$ is a formula containing formula $A$ and $C_B$ is ...