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)

0
votes
2answers
197 views

Trouble with boolean algebra as used in logic

I'm having trouble knowing how to continue on with this problem, I don't know what to turn the equivalent sign into and I cant really continue with that side, can anyone help me out? Do I just say ...
10
votes
1answer
312 views

Is Hilbert's second problem about the real numbers or the natural numbers?

In his famous "23 problems" speech, Hilbert gave his second problem as follows: The axioms of arithmetic are essentially nothing else than the known rules of calculation, with the addition of the ...
4
votes
2answers
544 views

First-order logic: nested quantifiers for same variables

Doing some homework, I'm asked to determine if the following formula is satisfiable, valid or neither. I am confused by the nesting quantifiers for the same variables. Using sequent calculus, I ...
2
votes
3answers
71 views

expanding requirements for equivalent conditions

We have all seen statements about equivalent conditions, such as If any one of the following three conditions hold, then all three conditions hold. Are there any examples of three conditions which ...
2
votes
1answer
94 views

Two questions regarding formal proofs

Assume that in a formal proof I have $T \cup \{ \varphi \} \vdash \varphi$ $T \cup \{ \varphi \} \vdash \lnot \varphi$ Question 1: can I then deduce $T \cup \{ \varphi ...
3
votes
2answers
97 views

$\Sigma_1 \cup \Sigma_2$ has a model

Let $\Sigma_1$ and $\Sigma_2$ be sets of $L$-sentences such that no symbol of $L$ occurs in both $\Sigma_1$ and $\Sigma_2$. Suppose $\Sigma_1$ and $\Sigma_2$ have infinite models. Then $\Sigma_1 \cup ...
4
votes
1answer
269 views

A question about the deduction theorem

The deduction theorem states that if $T \cup \{ \psi \} \vdash \varphi $ and the generalisation rule is not used to prove $\varphi$ then $T \vdash \psi \rightarrow \varphi $. If I apply the ...
4
votes
1answer
410 views

What's the difference between $P \to Q$ and $P \implies Q$? [duplicate]

Possible Duplicate: What's the difference between material implication and logical implication? background: I am trying to fully understand the meaning of implication which i understand ...
3
votes
2answers
230 views

How does a recursive definition fit into a formal proof?

I understand a proof as a series of statements that are either axioms or follow from previous statements by a small set of rules of inference. I understand a recursive definition to be something like ...
8
votes
0answers
369 views

Irreversible chess [closed]

Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
9
votes
3answers
950 views

Axiom of choice, non-measurable sets, countable unions

I have been looking through several mathoverflow posts, especially these ones http://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice , ...
1
vote
2answers
277 views

If-Then statements

I am trying to prove a statement of the form: If A and B, then C. Is this equivalent to the following statement? Given A, if B, then C.
3
votes
3answers
1k views

Negation of Uniqueness Quantifier

Is there a negation of uniqueness quantifier? I need to negate an expression which includes a uniqueness quantifier.
2
votes
1answer
174 views

How to express Con(PA) as a first-order statement?

I read from somewhere that Fact 1. PA, which refers to the first-order version, is not finitely axiomatizable. At the same time, the second incompleteness theorem says that there is no proof in ...
0
votes
1answer
135 views

Translation of nabla modality with box and diamond modalities

I got an exercise from my teacher to translate formulas of modal logic with modal operator $\nabla$ into formulas with operators $\Box$ and $\Diamond$. If the set of possible worlds is $X$, the ...
3
votes
1answer
132 views

What is a relatively bound variable?

edit: Interestingly, the authors also state at one point that the choice of introduction rule is determined by the structure of the previous goal and the list of introduction rules; but at another ...
7
votes
2answers
183 views

Complexity of the set of computable ordinals

According to http://en.wikipedia.org/wiki/Analytical_hierarchy The set of all natural numbers which are indices of computable ordinals is a $\Pi^1_1$ set which is not $\Sigma^1_1$. However, "the ...
51
votes
2answers
2k views

Help me put these enormous numbers in order: googol, googol-plex-bang, googol-stack and so on

Popular mathematics folklore provides some simple tools enabling us compactly to describe some truly enormous numbers. For example, the number $10^{100}$ is commonly known as a googol, and a googol ...
0
votes
3answers
157 views

Bijection for a function $ \mathbb{Z}^+ \times \mathbb{Z}^+$ to $\mathbb{Z}^+ $ [duplicate]

Possible Duplicate: Countable Sets and the Cartesian Product of them Consider the following question: Describe a function $ \mathbb{Z}^+ \times \mathbb{Z}^+$ to $\mathbb{Z}^+ $ that is ...
4
votes
2answers
175 views

What does a nonstandard proof of Con(PA) look like?

As in Godel's incompleteness theorem natural numbers encode proofs of theorems. Due to Godel's completeness theorem there is a natural number (in some nonstandard model) that proves $Con(PA)$. What ...
6
votes
1answer
258 views

Simple functions and axiom of choice

The question I have is more of a curiosity, and that is why I decided to post here instead of Mathoverflow. Before posing the question, let me set up some background. Background: Let $\Omega$ be a ...
1
vote
2answers
144 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
0
votes
2answers
140 views

Making $\exists x \forall y [xy = 1]$ provable

I am trying to prove or disprove the statement: $\mathcal{U} = \mathbb{R} > 0$ $\exists x \forall y [xy = 1]$ However, I have not learned the rule on how to do so. Does it somehow follow the ...
6
votes
5answers
422 views

Logical NOT of an implication

I was looking through my notes but I was unable to find the answer to this, which I need to start am assignment question. What would the following be, in terms on moving the negation inside the ...
13
votes
1answer
1k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
1
vote
1answer
160 views

Quantitative version of Godel's incompleteness theorem

Let $A$ be a list of axioms which we assume to be sound (for example, PA or ZFC). Godel's incompleteness theorems imply that if we add only finitely many (true) axioms to $A$, the new list $B$ will ...
2
votes
1answer
214 views

Truth and undecidability

I believe this is more of a philosophical question. Given a consistent theory T and a statement S independent of T. Can S be true or false in T? (I don't see any contradiction with that) I read that ...
3
votes
2answers
110 views

Upper and Lower bounds on proof length

Given a First Order language say, for arithmetic $\langle 0, 1, +,\cdot ,^\wedge, S \rangle$, Can one establish any lower or upper bounds on the length of proofs from certain recursively enumerable ...
2
votes
2answers
263 views

$\psi \to (\exists x)\phi(x) \Leftrightarrow (\exists x)(\psi \to \phi(x))$, etc

My textbooks states the following equivalences without proof: $$(\psi \to (\exists x)\phi(x)) \Leftrightarrow (\exists x)(\psi \to \phi(x))$$ $$(\psi \to (\forall x)\phi(x)) \Leftrightarrow (\forall ...
2
votes
2answers
287 views

Catalog of named tautologies

Some propositional taulogies have names, for example, Modus Ponens, Modus Tollens, Contrapositon, ... Is there a catalog of all named propositional taulogies? In particular, does the following ...
2
votes
1answer
504 views

Prove by contradiction or contrapositive? If $|x+y|<|x|+|y|$, then $x<0$ or $y<0$.

Prove: If $|x+y|<|x|+|y|$, then $x<0$ or $y<0$ This looks as though it's true from the start. Take $x=-4, y=4$. $|-4+4|<|-4|+|4|$ $0<8$ is true. The question is asking for a ...
1
vote
2answers
134 views

Can you quantify over an ordered set in first order logic?

If you are working in first-order logic, can you define a sequence $f_{n}$ of $n$-ary functions (i.e. the $n$th function takes in $n$ inputs), and then later say $(\exists n)(u = f_{n}(x_{1}, ...
2
votes
2answers
323 views

Confused about Wikipedia definition of NP

I've been checking my understanding of the definitions of NP and NP-complete and I am confused by some of the definitions given on Wikipedia; for example, the article about NP-complete describes NP ...
3
votes
1answer
149 views

Can we collapse $\omega_1$ without adding a dominating real?

The question is exactly that in the title: is there a forcing which collapses $\omega_1$ to $\omega$ but does not add a dominating real ("real" here meaning "element of $\omega^\omega$")? It seems ...
4
votes
3answers
618 views

How to approach number guessing game(with a twist) algorithm?

I posted this on stackoverflow, but was advised to also post here. It's kind of a math/algo question so I think it's kind of stuck between both worlds of math and computer science. I believe this to ...
9
votes
5answers
6k views

not understanding this row of truth table for logical implication

provided we have this truth table where "p->q" means "if p then q": | p | q | p->q | | T | T | T | | T | F | F | | F | T | T | | F | F | T | My ...
2
votes
2answers
190 views

Predicate Logic

I'm studying for an exam, and I'm not really sure how to portray this. The domain is all people. $V (w) = w$ is a voter $P (w) = w$ is a politician $K (y, z) = y$ knows $z$ $T (y, z) = y$ trusts $z$ ...
1
vote
2answers
276 views

What is the origin of the prefix logic notation used in WFF 'N PROOF?

The classic "modern logic" game of WFF 'N PROOF uses a set of symbols to represent logical relations that I've seen used nowhere else: $C$ for then; $A$ for or; $K$ for and; $E$ for if and only if; ...
1
vote
1answer
90 views

are these statements the same?

If I show this statement: $$x\in \left] a,b \right[ \Rightarrow \exists n \in \mathbb{N} : x\in \left] -\frac1{n}, 1+\frac1{n}\right[$$ Have I then shown this statement: $$]a,b[ \subseteq ...
4
votes
1answer
91 views

Predicate Logic Equivalencies?

Are the following two equivalent: $$ \forall x \space \exists y \space [ \space A(x) \rightarrow B(y) \space ] $$ and $$ \forall x \space [ \space A(x) \rightarrow \exists y \space B(y) \space ] ...
1
vote
3answers
164 views

$x \vee y \Rightarrow z \vee t$ - logic

I show that $x \Rightarrow z$ and $y \Rightarrow t$ are true. Is $x \vee y \Rightarrow z \vee t$ then true?
0
votes
1answer
83 views

Contraposition. Statement with intervals

I want to obtain the contrapositive statement to: $$ x\in \bigcap_{n=1}^{\infty} \left] -\frac1{n}, 1+\frac1{n}\right[ \Rightarrow x\in \left[ 0,1 \right]$$ My guess is: $$x<0 \text{ or } x>1 ...
3
votes
1answer
133 views

Turning a non-effective proof into an effective one can be arbitrarily long?

Let $T$ be a theory at least as strong as Peano arithmetic. We assume that we have a complete arithmetization of $T$ so that statements like $T \vdash \phi$ can be defined inside $T$, and for each ...
1
vote
1answer
108 views

Is it always possible to decide if either a statement or its negation is provable in a given axiomatic system?

The question is essentially in the title. Given an axiomatic system of unspecified power (it could be set theory or it could be propositional logic) and a statement A, can I always decide if either A ...
13
votes
7answers
2k views

True vs. Provable

Gödel's first incompleteness theorem states that "...For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system". What ...
5
votes
1answer
81 views

Independent statements that cannot be weakened

Let $T$ be a theory and let $\phi,\psi$ be statements that are independent of $T$. Say that $\psi$ is a $T$-weakening of $\phi$ if $T$ proves $\phi \Rightarrow \psi$ but cannot prove $\psi \Rightarrow ...
1
vote
3answers
171 views

Are these statements about even numbers called symmetrical statements?

I have these following statements. x is a even number $\Rightarrow$ xy is a even number y is a even number $\Rightarrow$ xy is a even number Can I call them symmetrical statements?
7
votes
1answer
3k views

What's the difference between material implication and logical implication?

When I read the definitions of material and logical implications, they seem to me pretty much equivalent. Could someone give me an example illustrating the difference? (BTW, I have no problem with ...
2
votes
3answers
209 views

math into logic

How does one translate Godel sentence about the integers into "This sentence is not provable" and Rosser's sentence into "If this sentence is provable, there is a shorter proof of its negation". If I ...
6
votes
2answers
359 views

Puzzle: Can arithmetic be axiomatized with a single two-term relation?

Following my question about defining multiplication in terms of divisibility, can all of arithmetic be axiomatized with a single two-term relation? Asaf Karagila comments on my question that the ...