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)

6
votes
3answers
174 views

Equivalence relation using tableaux

How can I prove that two formulae are equivalent using analytic tableaux? For example, how can I prove the following theorem? $$ (p \rightarrow q) \equiv (\neg q \rightarrow \neg p)$$
6
votes
3answers
626 views

How to prove a set of sentential connectives is incomplete?

On Page 52, A Mathematical Introduction to Logic, Herbert B. Enderton(2ed), Show that $\{\lnot, \# \}$ is not complete. A set of connective symbols is complete, if every function $G : \{F, T\}^n ...
6
votes
1answer
198 views

Łoś's Theorem holds for positive sentences at reduced products in general?

Let $ \mathcal{L} $ be a language for first-order logic whose logical primitives are $ \neg$, $\vee$, $\wedge$, $\forall$, and $\exists$, with the usual formation rules. A sentence $ \sigma $ is ...
6
votes
1answer
146 views

Admissible ordinals…

a little question about admissible sets: Is every $\mathfrak{M}$-admissible ordinals an admissible ordinal ? where $\mathfrak{M}$ is a $L$-structure over $L=\{R_1,\dots,R_k \}$. Thanks.
6
votes
4answers
265 views

Which sentence among the three sentences is the lie?

The second statement is the lie or the third statement is the lie. This statement is a truth, or the last statement and the second statement cannot both be truths. The first statement is the lie and ...
6
votes
1answer
391 views

Compactness theorem equivalent

I've been reading Enderton's Mathematical Introduction to Logic. One of the exercises on Compactness theorem requires the proof that the following corollary [(Corollary 17A) Suppose $\Sigma \models ...
5
votes
1answer
142 views

Understanding the proof of “$\sqrt{2}$ is irrational” by contradiction.

I have some difficulties in understanding the proof of "$\sqrt{2}$is irrational" by contradiction. I am reading it in 10th class(in India) Mathematics book( available online, here ) This is the ...
5
votes
2answers
69 views

Contrapositive statement

We know that sometimes it is quite difficult to prove a mathematical statement; but it's contra-positive statement turns out to be easier. I am curious, why does it happen? Is there anything deep ...
5
votes
2answers
156 views

Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
5
votes
1answer
127 views

If $\Sigma \vdash \phi$ implies $\Sigma \vdash \varphi$ then $\Sigma \vdash \phi \to \varphi$ on propositional logic?

My main aim is to prove or disprove that if $\Sigma \vdash \phi$ implies $\Sigma \vdash \varphi$ then $\Sigma \vdash \phi \to \varphi$ where $\Sigma$ donotes a set of sentences in propositional logic. ...
5
votes
4answers
395 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
5
votes
3answers
150 views

Can Peirce's Law be proven without contradiction?

Good evening, I heard the proof by contradiction is required for Peirce's law. AFAIK, truth tables are not related directly to proofs by contradiction, and if of an operation $\text {op}$ we have a ...
5
votes
2answers
93 views

Discrete math logic question

I have the following two questions. For all real numbers x, there is a real number y such that $2x+y=7$ would this be true or false? I think true because if you put $2(7)+y=14$ $2(8)+y=14$ there ...
5
votes
3answers
683 views

Is “The present King of France is bald” studied by maths?

Intuitively, "The present King of France is bald." is false. But Bertrand Russell said it would mean that "The present King of France is not bald.", which seems to be false. This apparently leads to ...
5
votes
1answer
159 views

What is the proof-theoretic ordinal of the first-order theory of real closed fields?

I recently asked a question on MathOverflow, concerning a predicative second-order theory of real numbers. Now the standard way of developing predicativity in the case of second-order arithmetic is ...
5
votes
1answer
137 views

consistency strength of PA

Why does PA prove the syntactic consistency of its finite subtheories? Please try to give a self-contained explanation (or good outline), or point me to a reference with a good explanation. Thanks.
5
votes
3answers
235 views

What's the problem this logic

In Lewis Carroll's story "What the Tortoise Said to Achilles," the swiftfooted warrior has caught up with the plodding tortoise, defying Zeno's paradox in which any head start given to the tortoise ...
5
votes
1answer
299 views

What are a list of helpful boolean identities for solving boolean functions?

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful ...
5
votes
5answers
1k views

Side-stepping contradiction in the proof of ; ab = 0 then a or b is 0.

Suppose we need to show a field has no zero divisors - that is prove the title - then we head off exactly like the one common argument in the reals (unsurprisingly as they themselves are a field). ...
5
votes
1answer
177 views

Is weak forcing a semantic relation?

I'm vaguely recalling things from innumerable aeons ago: A condition $p$ forces the negation $\sim\varphi$ of a sentence $\varphi$ precisely if no condition that extends $p$ forces $\varphi$. From ...
5
votes
3answers
404 views

Undecidable conjectures

Suppose we work with a conjecture saying that something is true for any natural $n$. For each $n$ there exists an algorithm of finite length allowing one to decide whether it is true or false for this ...
5
votes
4answers
2k views

Implication and equivalence arrows, when to use them?

In my course book we have something called implication arrows $\Rightarrow$ and equivalence arrows $\Leftrightarrow$ and I have never managed to understand them. When do I know which to use and how ...
5
votes
2answers
269 views

$\omega$-saturation of $(\mathbb{R},<)$

Could anyone of you explain me why $(\mathbb{R},<)$ is $\omega$-saturated? EDIT: do you know also why the theory of Boole algebras without atoms is $\omega$-categoric? Added: The added question ...
4
votes
1answer
58 views

If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$

If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$ Here, a set of formulas is inconsistent means they syntactically imply some formula as well as its negation. ...
4
votes
1answer
95 views

What goes wrong when you try to reflect infinitely many formulas?

The reflection principle in ZFC shows that you can construct a set that reflects finitely many formulas. Suppose we wanted to reflect {$\phi_n$} and we construct a set $M_n$ to reflect $\phi_1, ... , ...
4
votes
3answers
63 views

Name for introducing negation with quantifiers

The rewriting of $\varphi\to \psi$ into the logically equivalent $\neg \psi\to\neg \varphi$ is called contraposition. Is there a similar word for rewriting $\forall x.\varphi$ into $\neg\exists ...
4
votes
2answers
59 views

When is de-Skolemizing statements appropriate?

In first order logic we often convert prenex normal form statements to Skolem normal form statements to eliminate the existential quantifier: $\exists$x$\forall$y$\exists$z$\phi$(x,y,z) becomes ...
4
votes
3answers
213 views

Concrete example for diagonal lemma

Diagonal lemma says that in a theory with enough assumption for any formula $A(x)$ there exist a sentence $B$ such that $B$ $\iff$ $A(\#(B))$ is a theorem in that theory, in which $\#(B)$ represents ...
4
votes
6answers
233 views

Logical issues with the weak law of large numbers and its interpretation

In several probability textbooks I have found what amounts to the following argument: Let A be an event in some probabilistic experiment. Let p=P(A) be the probability of this event occurring in ...
4
votes
2answers
180 views

Model-theory and Proof-theory in Propositional Logic

I'm trying to link results of model theory and proof-theory in propositional language. Here i will use $\models$ to denote logical consequence, in the model-theory sense. Being $x,y$ two formulas of ...
4
votes
1answer
152 views

How do we know that certain concrete nonstandard models of the natural numbers satisfy the Peano axioms?

It is easy to come up with objects that do not satisfy the Peano axioms. For example, let $\Bbb{S} = \Bbb N \cup \{Z\}$, and $SZ = S0$. Then this clearly violates the axiom that says that $Sa=Sb\to ...
4
votes
2answers
125 views

Can the material implication ever be used as the main connective within the scope of an existential quantifier?

Can the material implication ever be used as the main connective within the scope of an existential quantifier? Usually, a conjunction is the main connective in sentences bound by an existential ...
4
votes
4answers
304 views

The set of all things. A thing itself?

If the universe is the set of all things. Does it contain itself? In other words is it a thing itself? I know its a stupid question, but it really grinds my gears. Thanks! Edit 8.12 Okey, someone ...
4
votes
2answers
259 views

Natural deduction: $(\neg q \to\neg p)\vdash(p\to q)$ without Modus Tollens

Can anyone help me to obtain this result in natural deduction, without using modus tollens: $$(\neg q \to \neg p) \vdash ( p \to q)$$
4
votes
2answers
128 views

Is there a sentence in the language of $\mathrm{PA}$ asserting that $\mathrm{PA}$ is sound?

We often write $\mathrm{Con}(\mathrm{PA})$ for the sentence (in the language of $\mathrm{PA}$) asserting that $\mathrm{PA}$ is consistent. Is there a sentence $\mathrm{Sou}(\mathrm{PA})$ (in the ...
4
votes
1answer
218 views

Can second order logic express each (computable) infinitary logic sentence?

In chapter 9 of Ebbinghaus et. al, the logical systems $\mathcal{L}_\text{II}$ ("full" second order logic with standard semantics) and $\mathcal{L}_{\omega_1\omega}$ (countable infinitary logic with ...
4
votes
2answers
3k 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.
4
votes
3answers
317 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 ...
4
votes
2answers
258 views

$\wedge,\cap,\times$ and $\vee,\cup,+$ are always interchangeable?

Update : Should have left the Arithmetic out of this question, the new modified question is posted here : $\wedge,\cap$ and $\vee,\cup$ between Logic and Set Theory always interchangeable? ...
4
votes
3answers
654 views

Classifying Types of Paradoxes: Liar's Paradox, Et Alia

The well-known Liar's Paradox "This statement is false" leads to a recursive contradiction: If the statement is interpreted to be true then it is actually false, and if it is interpreted to be false ...
4
votes
4answers
484 views

Exists iff for all

I have a theorem of the following scheme: $Q \Leftrightarrow \exists x\in Z: P(x) \Leftrightarrow \forall x\in Z: P(x)$. How to simplify it (not to write $P(x)$ twice)?
4
votes
1answer
4k views

Logic Puzzle of the age of three sons

There is a puzzle, it goes something like this: Someone talks to a guy, and asks, Give me the age of my three sons, The other guy asks for some clues: The product of the age of the three sons (of ...
4
votes
2answers
381 views

Disjunction in Intuitionistic Logic, what about $((P \to U \lor V) \to Z)$

I wonder whether the following holds in intuitionistic logic: $$((P \to U \lor V) \to Z) \leftrightarrow ((P \to U) \to Z) \land ((P \to V) \to Z)$$ For disjunction I assume the following two rules: ...
3
votes
2answers
50 views

Super Simple question on Logic and Modus Ponens

I am totally mixed up with these: using ONLY this three axioms and Modus Ponens:$$1. \ F \implies (G\implies F) \\ 2. \ (F \implies (G\implies H))\implies ((F \implies G)\implies (F \implies H)) \\ ...
3
votes
1answer
38 views

Suppose a $\in \mathbb{Z}$. $a^{2}|a$ if and only if $a \in \{-1,0,1\}$

Suppose a $\in \mathbb{Z}$. Then $a^{2}|a$ if and only if $a \in \{-1,0,1\}$ So, I have started and this is what I have so far: Case 1: If $a^{2}|a$, then $a \in \{-1,0,1\}$. For the sake of ...
3
votes
3answers
105 views

Formal notion of computational content

In constructive mathematics we often hear expressions such as "extracting computational content from proofs", "the constructivity of mathematics lies in its computational content", "realizability ...
3
votes
2answers
64 views

Confused about the use of variables w/ logical quantifiers

Sorry if this is a really dumb question, but... After reading How to Prove it, I've become a little confused. On page 70, an example stating something similar to this is provided: $[\exists x P(x) ...
3
votes
2answers
120 views

Contraposition in intuitionistic logic?

I read that contraposition $\neg Q \rightarrow \neg P$ in intuitionistic logic is not generally equivalent to $P \rightarrow Q$. If this is right, in what case can this contraposition ...
3
votes
1answer
89 views

Semantics and Logical structure in Definitons

Continuation of Free and bound variables in "if" statements definitions: A number is even if it is divisible by $2$. The number is even if it is divisible by $2$. Is the usage of the ...
3
votes
5answers
112 views

Difference between bound and free variable

What is the difference between $\forall x (P(x)\implies Q(x))$ and $P(x)\implies Q(x)$ I know in the first one the variable x is bound but in the second one the variable is free. What are the ...