Questions about logic and 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
2answers
42 views

Questions regarding well formed expressions in the Theory of types

I'm dealing with a question in type theory: Is it possible to assign types to $\alpha$, $\beta$, and $\gamma$ in such a way that both $(\alpha (\beta))(\gamma)$ and $\alpha (\beta (\gamma))$ are ...
0
votes
1answer
25 views

$A$ is c.e. $ \Leftrightarrow$ $A \le_{1}K_{0}$

$A$ is c.e. $ \Leftrightarrow$ $A \le_{1}K_{0}$ let $A\subseteq N$ show that if $A$ is c.e. $ \Leftrightarrow$ $A \le_{1}K_{0}$ proof:$\Leftarrow$ $A \le_{1}K_{0}$ via$f $ then we have $ x\in A ...
1
vote
1answer
55 views

Solve this tautology

Hypotheses: not $q$, $p$ or not $s$, $p \rightarrow$ ($d$ and $q$), $e \rightarrow s$ Conclusion: not $e$ I have thus far, but unsure how to proceed. I am looking forward to solve it using ...
1
vote
1answer
36 views

Does an interpretation of a structure by itself induce a bijection on the automorphism group of the structure?

Let $\Gamma$ be a model-theoretic interpretation of a structure $B$ in a structure $A$. Then $\Gamma$ induces a group homomorphism $\alpha_\Gamma:\mathrm{Aut}(A) \rightarrow \mathrm{Aut}(B)$. (See, ...
0
votes
0answers
22 views

express constraint violation

A very simple question, what's the mathematical symbol (expression) that represents constraint violation. Specifically, we have a set of constraints R each of which taking three variables, two sets of ...
1
vote
3answers
212 views

Can we prove that axioms do not contradict?

We construct many structures by chosing a set of axioms and deriving everything else from them. As far as I remember we never proved in our lectures that those axioms do not contradict. So: Is it ...
4
votes
6answers
108 views

the purpose of induction

After getting an answer (in a comment) from peter for this question I have a follow up question. If, in all horses are the same color problem for example, we need to use reason, reason which is ...
3
votes
4answers
96 views

how to point out errors in proof by induction

I have searched for an answer to my question but no one seems to be talking about this particular matter.. I will use the all horses are the same color paradox as an example. Everyone points out ...
0
votes
0answers
20 views

show $A$ is c.e. $ \Leftrightarrow$ $A \le_{m}K_{0}$

let $A\subseteq N$ show that if $A$ is c.e. $ \Leftrightarrow$ $A \le_{m}K_{0}$ proof:$\Leftarrow$ $A \le_{m}K_{0}$ via$f $ then we have $ x\in A \Leftrightarrow \ f(x) \in K_{0}=\{<x,e>: ...
1
vote
3answers
48 views

How to determine if this is true or false?

$$\exists x \in X, (P(x) \to Q(x))\hspace{0.2cm} \iff (\exists x \in X, P(x))\to (\exists x \in X, Q(x))$$ $$\forall x \in X, (P(x) \to Q(x))\hspace{0.2cm} \iff (\forall x \in X, P(x))\to (\forall x ...
0
votes
2answers
32 views

Proving that universal quantification distribute over conjunction

show $$\vdash [\forall x(P(x))\wedge \forall x(Q(x))]\to \forall x[P(x)\wedge Q(x)]$$ answer: by Q_{1}:$\forall x \phi\to\phi_{t}^{x}$ so we have $\forall x P(x)\to P(t)$ $\forall x Q(x)\to Q(t)$ ...
0
votes
2answers
59 views

Stroeker Problem: Sum of consecutive cubes being a perfect square

I encountered to following textbook problem in the book 'Introduction to probability' (p.34) by Blitzstein and Nwang. NO homework, but self-study ! Part a) is no problem, but b) struck me down. ...
1
vote
2answers
23 views

Pre-nex normal form. Correct way to distribute negations among quantifiers

Start point: $$(¬∀x P(x) ∨ ¬∀y Q(y)) → ¬∃x G(x)$$ Implication to Disjunction (DeMorgans Laws): $$¬(¬∀x P(x) ∨ ¬∀y Q(y)) ∨ ¬∃x G(x)$$ Now I am at the point where I need to move in the negations to ...
2
votes
2answers
67 views

Prove the Robinson arithmetic has infinite non-isomorphic models

I found this question: Can finite theory have only infinite models?, where is proved that Robinson's Arithmetic can have infinite models, but I've been unable to prove or find a proof of the existence ...
0
votes
0answers
33 views

show that if $x$ is not free in $\Psi$ then $\phi \rightarrow\Psi\vDash [(\exists x \phi)\rightarrow\Psi]$

show that if $x$ is not free in $\Psi$ then $$\phi \rightarrow\Psi\vDash [(\exists x \phi)\rightarrow\Psi]$$ answer: by QR $$\phi \rightarrow\Psi\vdash [(\exists x \phi)\rightarrow\Psi]$$ so ...
2
votes
2answers
50 views

How is the Liar Paradox a paradox?

In the Liar Paradox, someone says "I am a liar.", which we assume means "Everything I say is false." (although even that's not correct, a liar is defined as someone who says lies, not someone who only ...
43
votes
11answers
5k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Godel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
0
votes
2answers
23 views

Laws of Logic Negation Simple

I cant quite remember, when you are using the laws of logic to simplify an argument or an argument about sets. Do you start on the outside of the brackets with the outer most negation? Or the inner ...
2
votes
2answers
116 views

What are some examples of third, fourth, or fifth order logic sentences?

I know this seems like an obvious question, but I haven't been able to find any examples of sentences in logic higher than second order, so my intuition on how it's supposed to behave is failing me. ...
0
votes
0answers
35 views

proving $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$

I looking for proof of $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$ in the foloowing logic (SJ logic in paper of Greg Restall , Subintuitionistic logic) $$⊢A→A$$ ...
2
votes
3answers
43 views

Is the order of four quantifiers in a predicate formula relevant?

Is the formula: $$\forall x \exists y \forall z \exists u (F(x) \lor G(y) \to F(z) \lor G(u))$$ Equivalent to formula: $$\forall z \exists u \forall x \exists y (F(x) \lor G(y) \to F(z) \lor ...
1
vote
1answer
29 views

Show that given a partial order there exists a total order [duplicate]

STATEMENT: Suppose that $≺$ is a partial ordering of $\mathbb{N}$. Use the Compactness Theorem for first order logic to show that there is a total ordering $≺_∗$ of $\mathbb{N}$ such that for all n ...
4
votes
3answers
315 views

Need help to prove (A∪B) - (C - A) = A ∪ (B - C)

Having trouble with a discrete math question involving sets. Have been asked to prove: (A∪B) - (C - A) = A ∪ (B - C) This is what I have so far: x ϵ A or x ∈ (B - C) x ∈ A or (x ∈ B and x ∉ C ) ...
0
votes
0answers
23 views

show $(\forall x) (\forall y)P(x,y) \vdash(\forall y) (\forall z)P(z,y)$

$$(\forall x) (\forall y)P(x,y) \vdash(\forall y) (\forall z)P(z,y)$$ answer: $$(\forall x) (\forall y)P(x,y) \equiv(\forall y) (\forall x)P(x,y)$$ $Q_{1}:$$(\forall x \phi)\rightarrow\phi_{t}^{x} $ ...
1
vote
0answers
38 views

Logic in Science

I am in the process of writing an essay about how disciplines interlink. In one of my paragraphs I am talking about logic, where is say how logic is a subset of mathemtics (logicism) and therefore any ...
0
votes
1answer
32 views

How much choice is needed for the transfer principle?

To construct the hyperreals via ultrapower the Boolean prime ideal theorem apparently suffices. However, to prove the transfer principle for the extension $\mathbb{R}\subset{}^\ast\mathbb{R}$ ...
2
votes
1answer
23 views

Craig's Interpolation Theorem in Propositional logic.

This is an exercise in Mendelson's Mathematical Logic. If $\mathscr{B} \implies \mathscr{D}$ is a tautology, and $\mathscr{B}$ and $\mathscr{D}$ have the statement letters $B_1, \dots, B_n$ in ...
0
votes
2answers
34 views

Boolean Algebra: Simplifying product of sums

I'm trying to simplify (A+B+C)(A+notB+C)(notA+B+notC) The K-map gives me (A+C)(notA+B+notC) but when I use boolean ...
2
votes
2answers
36 views

How to efficiently determine if any two propositional formulas are equivalent

Given any two arbitrary propositional formulas (but only using $\land, \lor, \lnot$), like $\lnot(A \land (B \lor \lnot B) \land C)$ and $\lnot C \lor \lnot A$, how can I (or a computer) efficiently ...
0
votes
2answers
40 views

Expressing boolean operators using logical operators

From my limited understanding of logical operators, it is possible to express the more complex logical operators such as $\operatorname{xnor}$ and $\operatorname{iff}$ as a combination of just a few ...
2
votes
1answer
56 views

How can a proof by formula induction in a formal language be formalized?

From a set of not-so-rigorous lecture notes on Metalogic: Formulas of $L$: (i) Each sentence letter is a formula. (ii) If $A$ is a formula, then so is $\neg A$. (iii) If $A$ and $B$ ...
1
vote
3answers
22 views

Discrete Structures : predicate logic (negations)

Could someone please explain why the negation makes "nobody" into "someone" and not "everyone" Which of the following is the correct negation for “Nobody is perfect.” 1. Everyone is imperfect. ...
0
votes
2answers
25 views

Trouble understanding surjective function proof

I'm studying for my discrete math exam and I'm having some trouble understanding this practice problem and solution. I know what surjective functions are, but I can't really understand the way this ...
0
votes
2answers
34 views

To prove $A\rightarrow B, C\rightarrow D \vdash (A\vee C)\rightarrow (B\vee D)$ with natural deduction [closed]

How to prove this statement? $ A\rightarrow B, C\rightarrow D \vdash (A\vee C)\rightarrow (B\vee D)?$ in inference rule? tnx!
3
votes
0answers
59 views

Consequence in $\mathcal{L}_{\infty\lambda}$

Consider the infinitary first-order language $\mathcal{L}_{\infty\lambda^+}$ whose non-logical vocabulary consists of $\lambda \geq \omega$ individual constants and countably many predicate constants ...
1
vote
2answers
48 views

$\vdash[(\forall x)P(x)]\rightarrow[(\exists x)P(x)]$

$$\vdash[(\forall x)P(x)]\rightarrow[(\exists x)P(x)]$$ answer:$$\neg P(x)\to\neg P(x)$$$$by QR$$ $$ \neg P(x)\to(\forall x)\neg P(x)$$$$by QR$$ $$(\exists x) \neg P(x)\to(\forall x)\neg P(x)$$ ...
2
votes
1answer
43 views

Are there non-trival logics that exibit soundness and completeness that are not first order?

In our logic class, we just we just completed the proofs of soundness and completeness. To me, these proofs hinge on models being filtered through first order logic. For instance, I could set up a ...
0
votes
0answers
23 views

show that $K_{1}$is not computable?

show that $K_{1}=\{x|W_{x}\ne \emptyset\}$is not computable? answer: i let $K_{1}$is computable. so $K_{1}$is computable enumerable. then $K_{1}$ is $\sum_{1}^0 $ and $z\in K_{1}\iff z\in ...
0
votes
1answer
28 views

Theorems of GL in modal logic

So I've been reading George Boolos' "The Logic of Provability" and he's explaining different systems of modal logic. He's taken as his basic symbols → (implication), □ (necessity), ⊥ (falsehood), a ...
0
votes
0answers
14 views

Proving that a predicate calc wff with a bi conditional [duplicate]

Prove: ∀x(C → D(x)) ↔ (C →∀xD(x)) resources: axiom 1:∀XA →Axt axiom 2:∀X(A→B) → (∀XA→∀XB) axiom 3:A→∀XA; Hilbert Generalization rule my attempt: ...
1
vote
1answer
20 views

Recurrence Relations: Understanding Homogeneous Reccurences

In an effort to better educate myself on the practices of Discrete Math. I have been attempting several practice problem sets. While most of the concepts up to this point have made sense, I find ...
1
vote
1answer
34 views

Proving a bi-conditional predicate calculus formulae

Prove the following: ∀x(C → D(x)) ↔ (C →∀xD(x)) I am looking at the axioms I can use under hilberts deductive system as well as the Generalization rule but I ...
6
votes
5answers
194 views

Is a proposition about something which doesn't exist true or false?

Let S = {x | x is not an element of x } The set S doesn't exist. Then, would a proposition such as "The cardinality of S is 1," be true or false? Equivalently, I could have made a proposition, "the ...
0
votes
1answer
18 views

How to negate $(a=1 \text{ and } b=n) \text{ or } (a=n \text{ and } b=1)$ to get $1<a<n \text { and } 1<b<n$?

n>1 is composite if and only if it can be written as a product $n=ab$ of integers $a$ and $b$ such that $1<a<n$ and $1<b<n$. If a prime number $n$ is the product of two positive ...
1
vote
1answer
29 views

How would one prove that satisfaction of closed formulas is valuation-independent? (In FOL)

Consider this proposition in first-order logic: For any interpretation $I$, any closed formula $\phi$ and any two valuations $\rho$, $\sigma$. $I\rho \models \phi \iff I\sigma \models \phi$ This is ...
0
votes
1answer
97 views

Trouble with by-contradiction proof

I'm studying for an exam and I'm having trouble with one of these problems. ...
1
vote
0answers
39 views

Knights and Knaves island [duplicate]

You appear on the Island of Knights and Knaves. Knights always tell truth, knaves always lie. You meat three inhabitants, Carl, Peggy and Zippy, and hear the following conversation: Carl says, "I ...
2
votes
1answer
35 views

Countable transitive model of ZFC and $\mathcal{P}(\omega)$

Let $\mathbb{M}$ be a countable transitive model of ZFC. I understand that $\omega^\mathbb{M} = \omega$ but $\mathcal{P}(\omega)^\mathbb{M} \neq \mathcal{P}(\omega)$, for ...
1
vote
1answer
21 views

I'm trying to find the latex symbol for a logical notation… Analogy: the symbol is to “logical and” as $\Sigma$ is to summation [closed]

I'm trying to find the latex symbol for a logical notation... Analogy: the symbol is to "logical and" as $\Sigma$ is to summation. For example if I want to "logical and" over sentences with varying ...
-2
votes
1answer
52 views

Model Theory - Equivalence of formulas using automorphisms

Let $\mathbf Q$ denote the additive group of rational numbers, i.e. the structure $\mathbf Q = (\mathbb Q;+,0)$. Let $L$ be the language of $\mathbf Q$ and let $T$ be the complete theory of $\mathbf ...