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
1answer
331 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
512 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 ...
4
votes
2answers
277 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 ...
10
votes
3answers
1k 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
343 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
2k views

Negation of Uniqueness Quantifier

Is there a negation of uniqueness quantifier? I need to negate an expression which includes a uniqueness quantifier.
3
votes
1answer
240 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
164 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
136 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
200 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 ...
58
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
176 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
182 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
271 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
147 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
148 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
657 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 ...
17
votes
4answers
2k 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
172 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
232 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
120 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
288 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
321 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 ...
1
vote
1answer
712 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
147 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
342 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
160 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
733 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 ...
11
votes
8answers
10k views

In classical logic, why is $(p\Rightarrow q)$ True if $p$ is False and $q$ is True?

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
2
votes
2answers
208 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
306 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
97 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
173 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
84 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
151 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
111 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 ...
15
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
82 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
183 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?
10
votes
1answer
4k 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
223 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
378 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 ...
7
votes
1answer
344 views

How is this argument of Edward Nelson's not flawed?

Edward Nelson has started writing out the details of a proof of the inconsistency of a version of arithmetic. I'm an undergraduate trying to read through this slowly and carefully. I've run into a ...
1
vote
2answers
943 views

What does a condition being sufficient as well as necessary indicates?

I have a question in a book I am solving(Discrete Structures by Kolman, Busby & Ross). I am unable to make sense from the question. It is stated below, Show that k is odd is a necessary and ...
3
votes
2answers
132 views

Stuck with proof techniques

I have to prove the following question, Let A and B are subsets of a universal set U. Prove that A is a subset of B iff B' is a subset of A' Now I don't understand how do I prove this using ...
2
votes
4answers
5k views

What is the logical connective for Either.. Or?

I have a statement, Either p or q and I have to write it in terms of logical connectives but I don't get which logical connector should I be using? Here is what I did (I think there could have ...
2
votes
3answers
8k views

Determining the truth value of a statement

I am stuck with the following question, Determine the truth value of each of the following statments(a statement is a sentence that evaluates to either true or false but you can not be ...
9
votes
5answers
9k views

what is the difference between only if and iff

I have read this question. I am now stuck with the difference between if and only if and only if. Please help me out. Thanks
2
votes
1answer
125 views

Need help in logic and statements

I am stuck with some questions. Please help me out. Thanks. If $P(x):x^2 < 12$, then $P(1.5)$ is a statement (I think yes. As the Universe of $x$ is not given but can be taken as set of Real ...