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)

4
votes
2answers
924 views

Which are the Bound and Free Variables in these Expressions?

Preceding my question below are two definitions from P29 of Daniel Velleman's How to Prove It: The free variables in a statement stand for objects that the statement says something about...The ...
4
votes
2answers
127 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
210 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
312 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
217 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
627 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
483 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
380 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
1answer
37 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
98 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
60 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
93 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
88 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
110 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 ...
3
votes
6answers
225 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 ...
3
votes
2answers
163 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 ...
3
votes
3answers
129 views

General Strategy for Derivations in Propositional Logic

In Propositional Logic, one is often tasked with showing that some particular formula is a theorem of a given deductive system, i.e. $\emptyset \vdash \psi$. These formulas can look very simple and ...
3
votes
1answer
60 views

The effects of requiring a recursive vs. a recursively enumberable axiomatization in the incompleteness theorem

I believe that the (paraphrased) original statement of Gödels first incompleteness theorem (including Rosser's trick) is If T is a sufficiently strong recursive axiomatization of the natural ...
3
votes
2answers
173 views
3
votes
2answers
525 views

De Morgan's laws in logic and set theory

In logic De Morgan's law means $\lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B$ In set theory De Morgan's law means $(A \cap B)^C = A^C \cup B^C$ I'm surprised that the same idea is true in ...
3
votes
2answers
354 views

How to prove consistency of Natural Deduction systems

In Dag Prawitz, Natural Deduction A Proof-Theoretical Study (1965), we have the system I of intuitionistic (first-order) logic based on eleven introduction- and elimination-rules : the 3 couples for ...
3
votes
1answer
123 views

Non-self-referential undecidable sentences in arithmetic

Are there any known undecidable sentences for PA are neither "self-referential" (like a sentence equivalent to its own nonprovability) nor imply consistency of PA (like in the Paris Harrington ...
3
votes
1answer
68 views

Computably enumerable sets are not algorithmically random

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would ...
3
votes
2answers
377 views

Validity vs. Tautology and soundness

I see that valid formula (proposition or statement) is the one that is valid under every interpretation. But this is a tautology. Is there any difference between tautology and valid formula? They also ...
3
votes
1answer
99 views

Some general questions on first-order logic

I'm currently working through Peter Smith's 'Introduction to Godel's Theorems'. I'm wondering how a formalization of first-order logic that allows us to prove the incompleteness theorems, etc. might ...
3
votes
2answers
227 views

axioms of equality

Every text I've come across uses the Axiom of Extensionality to describe the fact that sets are equal iff they contain each other's elements. $$(\forall x)(\forall y)\bigl((\forall a)(a\in x \iff a\in ...
3
votes
3answers
102 views

proof by contradiction - making more than one assumption

I have a pet peeve with a proof by contradiction. Such proofs begin by an assumption which is shown to lead to a contradiction thereby leading us to conclude that our initial assumption must have been ...
3
votes
1answer
188 views

Some questions about Gödel's theorems of completeness and incompleteness

I am taking a course where we are covering a bit of logic, and I am trying to understand a some nuances of Gödel's theorems of completeness and incompleteness. Q1) Is it correct to say that Gödel's ...
3
votes
2answers
493 views

Is it true that all of the euclidean geometry problem in the IMO(international mathematical olympiad) could all be solve by the analytical geometry?

Is it true that all of the euclidean geometry problem in the IMO(international mathematical olympiad) or even generalize to say that all the plane geometry problem and 3d-geometry could be solve by ...
3
votes
2answers
112 views

How can you pick the odd marble by 3 steps in this case?

Imagine i have 12 marbles, all identical in every aspect except that 11 of them have exactly the same weight but you do not know the weight of the 12th one (it may be bigger ot smaller than the ...
3
votes
1answer
90 views

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
3
votes
1answer
332 views

Trying to prove that cardinality of power sets are equal

So if we have two sets $X$ and $Y$, we know that if $|X| = |Y|$, then $|P(X)| = |P(Y)|$. This means that there is a bijection $f: X → Y$. What would a function be that maps elements of $P(X)$ to ...
3
votes
1answer
196 views

Proof of $(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge (Q\Rightarrow P))$

Hi I've been working through Applied Mathematics for Database Professionals and I'm stuck trying to proof this equivalence: $$(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge ...
3
votes
3answers
300 views

Proof of $A \lor B, \lnot A\models B$ with natural deduction

Prove that: $A \lor B, \lnot A\models B$ Looks easy but im stuck, and i dont know if to start with an OR elimination or with NOT introduction. Also, different books/texts/etc about Natural ...
3
votes
2answers
267 views

Is it possible to derive all the other boolean functions by taking other primitives different of $NAND$?

I was reading the TECS book (The Elements of Computing Systems), in the book, we start to build the other logical gates with a single primitive logical gate, the $NAND$ gate. With it, we could easily ...
3
votes
4answers
236 views

Proving $q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$ using only natural deduction.

I'm trying to prove $$q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$$ using only the natural deduction rules in this handout. Any hints? I am not allowed to do transformational stuff, ...
3
votes
0answers
60 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
3
votes
1answer
143 views

Recursion schema and the arithmetical hierarchy

In computability we define the following basic functions, the zero function, the successor function, and the functions $I_{n,k}(x_1,\ldots,x_n)=x_k$ for $k\leq n$. Next we define three schemata for ...
3
votes
2answers
261 views

Why implication ($\phi x \Rightarrow \psi x$) is always true according to Russell?

In the chapter XV of the Intro. to Philosophical Math, Russell says that every propositional function (PF) of the form: "$\phi x$ implies $\psi x$" is always true. Russell gives the following ...
3
votes
2answers
218 views

Is $\vDash \exists x ( Q x \to \forall x Qx)$ a valid sentence?

Is $\vDash \exists x ( Q x \to \forall x Qx)$ a valid sentence? $Q$ is a unitary relation. I suppose that $\vDash Q x \to \forall x Qx$ , which is equivalent to $\vDash Q x \to \forall y Qy$ is ...
3
votes
2answers
2k views

What is the difference between an axiom and a postulate?

I here about axioms is set theory and postulates in geometry, but they seem like the same thing. Do the mean the same thing but then are used in different instances or what? Is one word more ...
3
votes
2answers
335 views

Automorphisms of saturated models

This is basically Exercise 10.1.5(c) in Hodges's Model theory. First, a reminder of some definitions: Let $\lambda$ be a cardinal, and let $\Sigma$ be a finitary first-order signature. A ...
3
votes
2answers
328 views

What's the sense in “Implies” logic? [duplicate]

Possible Duplicate: In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False? How to interpret material conditional and explain it to freshmen? We're told that ...
3
votes
5answers
409 views

$[\frac{1}{x} = 1$ for all real numbers $x]$ is not true or false

I have a follow-up to a previous question: True or false or not-defined statements. (In the following I might use the word statement incorrectly.) In that question/answer I learned that the ...
3
votes
2answers
1k views

Formation sequence for a logic formula

I will start with some definitions from An Introduction to Mathematical Logic and Type Theory: To Truth through Proof by Peter B. Andrews then give the exercise that I am working along with my attempt ...
3
votes
4answers
8k views

Truth Table for If P then Q [duplicate]

Possible Duplicate: In classical logic, why is (p -> q) True if both p and q are False? The Logic table for If P then Q is as follows: ...
3
votes
1answer
566 views

Unpacking the Diagonal Lemma

I am studying from Boolos' Computability & Logic (3rd edition). I need help unpacking what the Diagonal Lemma states, and understanding its proof. The Diagonal lemma is formalized on page 105 from ...
3
votes
2answers
462 views

Absurd = Inconsistent?

I think too much about the foundations of mathematics. I'm not sure whether this is standard terminology, but I will refer, for some theory $\Gamma$, to statements as follows: A statement $P$ is ...