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)

5
votes
4answers
596 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
4
votes
1answer
114 views

Notation in Sacks' 'Higher Recursion Theory'

I'm having trouble with the notation in Sacks' Higher Recursion Theory. I've asked specific questions from page 4. Instead of reading my question in detail and trying to understand my confusion (which ...
3
votes
1answer
76 views

How to show that $\mathrm{Cn}(\mathrm{Cn}(A)) = \mathrm{Cn}(A)$?

How to show in propositional logic, that $\mathrm{Cn}(\mathrm{Cn}(A)) = \mathrm{Cn}(A)$? I thought of first showing $\mathrm{Cn}(\mathrm{Cn}(A)) \subseteq \mathrm{Cn}(A)$ and then ...
4
votes
2answers
2k views

How to convert an English sentence that contains “Exactly two” or “Atleast two” into predicate calculus sentence?

For example: There are two people with income less than 4K/year.
2
votes
1answer
108 views

Proving that if $x$ is not free in $A$, then $(\exists x)(A\to B)\leftrightarrow(A\to(\exists x)(B))$

Assuming $x$ does not occur free in $A$, prove that $$(\exists x (A \to B)) \leftrightarrow (A \to ( \exists x B))$$ using any of the following axioms; MP, HS, or the Deduction Theorem. 1) $A \to ...
-5
votes
1answer
178 views

Apply the compactness theorem to show that there are nonstandard models [closed]

Apply the compactness theorem to show that there are nonstandard models of complete arithmetic (the set of all arithmetic truths). Apply it likewise to show there are nonstandard models of analysis, ...
2
votes
1answer
333 views

Translating FOL from English?

I have searched for answers/help, but I am not able to find specifics. I am on a "FOL for Dummies" level, I really have no clue what I'm doing. Edit: I understand most of the symbols (∀x, the ...
0
votes
2answers
2k views

I want a clear explanation for the Principle of Strong Mathematical Induction

I understood the Principle of Mathematical Induction. I know how to make a recursive definition. But I am stuck with how the "Principle of Strong Mathematical Induction (- the Alternative Form)" ...
6
votes
3answers
148 views

If $T$ proves $\operatorname{Con}(ZFC)$, is $T$ at least as strong as set theory?

I am looking for either a proof of counterexample of this: Lemma: Let $\pi$ be a faithful interpretation of $PA$ into $ZFC$, and let $PA'$ be the image of $PA$ under $\pi$. If there is a $T$ with ...
3
votes
1answer
311 views

Probability and Axiom of Choice

I'm not a logician, so I apologize if what follows translates to nonsense. I would like to try to define a different theory of random choice. I hesitate to call it probability theory because I do not ...
8
votes
2answers
128 views

A homogeneous set of some kind

Let $f : \mathbb{N}^k \to \mathbb{N}$ be a computable total function such that $f (\vec{x}) > \max \vec{x}$ for all $\vec{x}$. Question. Why is there a decidable set $A$ such that ...
1
vote
1answer
128 views

Can the ongoing need for a meta language be stopped by a loop?

As an afterthought to this question on sets in set theory, and more specifically to the observation that a (first-order) logic requires a meta-language to explain itself (i.e. there is already an ...
3
votes
1answer
94 views

Formal second-order statements of Archimedean and completeness properties

I am trying to translate the following statements from English to second-order logic, and I want to know if I got them right. I have a language for an ordered field $(F,+,\cdot,0,1,\leq)$, i.e., I ...
4
votes
0answers
82 views

An “internal” condition on $T$ so that for the standard provability predicate, $T$ proves $\text{Pf}(\underline S)$ implies $T$ proves $S$?

This is probably quite basic, but I'd like to make sure I got this right. Regarding the proof of Goedel's first incompleteness theorem, say that we have $T$ containing $PA$ effectively axiomatizable ...
0
votes
1answer
107 views

Explicit Big-$\mathcal{O}$ proof with predicate logic

For my newest homework I have given two functions $h,h^+:\mathbb{N}\to\mathbb{R}$ with $h(n)=n^{(-1)^n}$ and $h^+(n)=h(n+1)$. I have to proove that $h^+(n) \not\in\mathcal{O}(h(n))$ with an explicit ...
1
vote
1answer
445 views

Deriving Universal Modus Tollens

I'm asked to derive the validity of Universal Modus Tollens from the validity of Universal Instantiation and Modus Tollens. I'm new to this deriving/proving stuff, so I'm not sure if I'm doing it ...
3
votes
1answer
104 views

What does this logic evaluate to in plain English?

I am trying to teach myself logic and feel a bit fuzzy about this statement. $$\forall x \exists y P(x, y)$$ where the universe is the students in a class and P(x, y) means student x copies off of ...
3
votes
1answer
280 views

Can one use DeMorgan's Laws to expand a long trail of ANDs and ORs?

For instance, Is $\neg (((p \land q) \lor r) \land s)$ equivalent to $((\neg p \lor \neg q) \land \neg r) \lor \neg s$?
7
votes
1answer
345 views

Why is it sensical for a proposition with a false antecedent to validate to true?

In propositional logic, the statement "If pigs can fly, then elephants can lay eggs." validates to true because the antecedent validates to false. In other words, given $a \rightarrow b$, if a is ...
0
votes
1answer
154 views

rank of subformulae

How to show that the rank of a strict subformulae is strictly less than the rank of the formula in propositional logic? I can "see" that it is true, but how to strictly show it? I don't now how to ...
2
votes
3answers
512 views

Predicate Logic expressions - are the equivalent?

Are the following expressions equivalent? ¬∃x(student(x) ∧ learn(x)) ∀x(student(x) ∧ learn(x)) ¬∀x(student(x) ∧ learn(x))
2
votes
3answers
388 views

Is there a decision procedure for intuitionistic propositional logic?

Is institutionistic propositional logic decidable? If so, what is a decision procedure for it, like tableaux for classical propositional logic? EDIT: In the first revision I mistook "predicate" for ...
1
vote
0answers
96 views

translation of a sentence in FOL using Skolem functions

Consider the first-order sentence (1) $\forall x\exists y(\forall z Dxz\to\exists z\neg Dyz)$ and interpret Dab as the two-place relation "a has doubts about b." On a recent exam, I translated the ...
0
votes
3answers
141 views

Logical Equivalance

Determine whether the following pairs of statements are logically equivalent or not. Give a reason. (i) $p \to (q \to r)$ and $(p \to q) \to r$ (ii) $p \to (q \to r)$ and $q \to (p \to ...
1
vote
2answers
307 views

Classical contradiction in logic

I am studying for my logic finals and I came across this question: Prove $((E\implies F)\implies E)\implies E$ I don't understand how there is a classical contradiction in this proof. Using ...
1
vote
3answers
166 views

Finding minimal form — Velleman exercise 1.5.7a

I am self-studying out of Velleman's "How to Prove It", and am trying to solve exercise 7, part a from section 1.5. The problem is to show that $$ (P \to Q) \land (Q \to R) = (P \to R) \land ((P ...
3
votes
1answer
209 views

Provability and truth

The following is quoted from Set Theory and the Continuum Problem by Raymond M. Smullyan and Melvin Fitting. So far, no attempts have been the slightest bit successful in determining whether the ...
2
votes
1answer
127 views

Terminology for implication of theorems

In Portuguese, the following is considered the accepted terminology for the implication of theorems: $$\text{Theorem:}\\ \text{Hypothesis } \Rightarrow \text{ Thesis}$$ Hypothesis is the antecedent ...
2
votes
3answers
488 views

First order logic.

In Artificial intelligence, I saw the following question and answer in website. Question: Politicians can fool some people all of the time, and they can fool all people some of the time, ...
0
votes
2answers
326 views

Relationship between XOR and “AND”

I want to XOR the password (0x3d), byte by byte, with 0x42, then 0x51, then 0xF7, then 0x6F. this would give me 0xb6..... But, Is there a shortcut to this operation?
3
votes
4answers
844 views

If p then q misunderstanding?

The statement $P\rightarrow Q$ means: if $P$ then $Q$. p | q | p->q _____________ T | F | F F | F | T T | T | T F | T | T Lets say: if I'm hungry $h$ - ...
0
votes
2answers
136 views

Clarification for the definition of “a term is free for a variable in some wf. of a first order language”

Definition 1 Let $A$ be any wf. of a first order language L and $x$ be any variable. We say $x$ occurs free in $A$ if there is at least one occurrence of $x$ in $A$ which is not the scope of ...
1
vote
1answer
243 views

Do the proofes in set theory rely on the semantics of the formulas used in the axioms?

Motivation: The Axiom of separation $$\forall w_1,\ldots,w_n \, \forall A \, \exists B \, \forall x \, ( x \in B \Leftrightarrow [ x \in A \wedge \phi(x, w_1, \ldots, w_n, A) ] )$$ is used to ...
1
vote
1answer
92 views

Proof through consistency

Take first-order Peano Arithmetic PA. We know that Gentzen proved PA consistent. Now, if one sets for example $\varphi$ to represent Fermat's theorem in FO, would proving PA+$\varphi$ consistent be ...
2
votes
2answers
2k views

Which law of logical equivalence says P ∨(~P ∧ Q) ≡ P ∨Q?

I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
3
votes
1answer
218 views

Why does $\{\phi,(\phi\Rightarrow\psi)\}$ not semantically entail $\psi$ if $\phi$ has a free variable and $\psi$ doesn't?

Right off the bat, I want to make clear that my logic lecturer has adopted a rather non-standard form of the predicate calculus in which structures can be empty. Normally, structures are required to ...
1
vote
1answer
159 views

Where is my mistake in this proof? $(A \lor B) \land (A \rightarrow C) \lor (B \rightarrow D) \rightarrow (C \lor D)$

Here is what I finished with, although the problem states that it is a tautology and not a contingency. $$For :(A \lor B) \land (A \rightarrow C) \lor (B \rightarrow D) \rightarrow (C \lor D)$$ ...
3
votes
3answers
181 views

Non-Archimedean non-standard models for R

Let $\langle R,0,1,+,\cdot,<\rangle$ be the standard model for R, and let S be a countable model of R (satisfying all true first-order statements in R). Is it true that the set 1,1+1,1+1+1,… is ...
1
vote
2answers
204 views

Is this incompleteness result easier to get than incompleteness of PA?

Gödel's theorem for Peano Arithmetic shows that (under consistency hypothesis on PA) there is a statement which cannot be proved or disproved within PA that is true under the standard model ...
2
votes
2answers
175 views

Lefschetz Principle: explicit embeddings into $\mathbb C$.

I am very confused about the Lefschetz Principle. I read the Tarski Principle, but I am not acquainted with logic. Is there a statement more close to the language of field theory? Most of all, I ...
4
votes
3answers
230 views

Theories and models

I apologize if my question is not well formed. The reason for it is that I don't understand the concepts enough to be able to ask a completely meaningful question. In the classes we said that a ...
1
vote
2answers
156 views

How can you add 'not G' to a formal system without introducing omega inconsistency?

In any formal system S that is susceptible to Godel's proof, we can make a formula G which is undecidable. That should mean that we can add either $G$ or $\neg G$ as an axiom to S and still end up ...
1
vote
1answer
99 views

Undecidability and algorithmic verification

The following question has been asked few hours ago : How can any statements be proven undecidable? I'd like to ask a similar but more precise question. Could we imagine that the Syracuse conjecture ...
4
votes
3answers
283 views

How can any statements be proven undecidable?

As I understand it, undecidability means that there exists no proofs or contradictions of a statement. So if you've proved $X$ is undecidable then there are no contradictions to $X$, so $X$ always ...
1
vote
1answer
729 views

Restrictions on universal generalization

Wikipedia's article on universal generalization doesn't seem to give a satisfactory explanation of the restrictions on when it can be used: Assume $\Gamma$ is a set of formulas, $\varphi$ a ...
3
votes
1answer
278 views

What does universal quantification mean?

In ZFC, for example, there is no universal set, so what does it mean to write $\forall x (\cdots)$, i.e., for all sets something is true? Does it avoid the problem by quantifying over all elements but ...
4
votes
2answers
303 views

What is the “common” definition of model in first order logic?

While reading the note "First-Order Logic in a Nutshell" from Lorenz Halbeisen (can't find it online, but it's also a section in his book Combinatorial Set Theory page 31-44.), I got confused by the ...
13
votes
6answers
1k views

What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
8
votes
3answers
2k views

Is Foundational Research a Dead Field?

I'm a second year mathematics major at a pretty good school. Ever since I became a math major I have been most interested in set theory and logic, which I guess can be lumped into the category of ...
2
votes
1answer
161 views

Differences between between concepts related to Gödel's Incompleteness theorems: self-referencing, diagonalization and fixed point theorem?

I am studying the proof of Gödel's first Incompleteness theorem at the moment and I don't understand the differences between self-referencing, diagonalization and fixed point related to Gödel's proof. ...