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)

11
votes
5answers
810 views

Why is it possible to conclude everything from a false statement? [duplicate]

Possible Duplicates: In classical logic, why is (p -> q) True if both p and q are False? Why an inconsistent formal system can prove everything? I heard a professor of mathematics ...
11
votes
3answers
1k views

How is addition defined?

I've been reading On Numbers and Games and I noticed that Conway defines addition in his number system in terms of addition. Similarly in the analysis and logic books that I've read (I'm sure that ...
11
votes
5answers
761 views

Why König's lemma isn't “obvious”?

I keep facing König's lemma "Every finitely branching infinite tree over $\mathbb{N}$ has infinite branch". Why it is not taken "obvious" but needs a careful proof? It seems somewhat obvious, but I ...
11
votes
4answers
742 views

The Maths necessary to understand Logic, Model theory and Set theory to a very high level

I am studying Philosophy but most of my interests have to do with the philosophy of Maths and Logic. I would like to be able to have a very high level of competence in the topics mentioned in the ...
11
votes
7answers
834 views

Is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$?

is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$? I read in the book that the order of quantifiers make a big difference so I was wondering if these two expressions ...
11
votes
2answers
738 views

Examples of statements which are true but not provable

Speaking informally and working, for example, in Peano Arithmetic (PA), we know that the essence of the Gödel's first incompleteness theorem is that there are true statements (in our model PA), which ...
11
votes
2answers
1k views

Do De Morgan's laws hold in propositional intuitionistic logic?

In Wikipedia page on intuitionistic logic, it is stated that excluded middle and double negation elimination are not axioms. Does this mean that De Morgan's laws, stated $$ \lnot (p \land q) \iff ...
11
votes
4answers
524 views

Statements with no counterexample

Is there some proven statement that tells us "not all X satisfy Y", but there are currently no examples of X which do not satisfy Y? Is it necessarily true that there are always explicit ...
11
votes
1answer
510 views

Do you need the Axiom of Choice to accept Cantor's Diagonal Proof?

Math people: It is my understanding that set theorists/logicians compare cardinalities of sets using injections rather than surjections. Wikipedia defines countable sets in terms of injections. ...
11
votes
3answers
418 views

When we say, “ZFC can found most of mathematics,” what do we really mean?

ZFC works as a foundation because it can prove many sentences that are "translations" of theorems from "standard" mathematics into the language of ZFC. But there's a subtlety. When we say, "ZFC can ...
11
votes
4answers
418 views

Is there a connection between length of sentence and length of proof?

My basic question is: "Do longer tautologies take longer to prove?" But obviously this is underdetermined. If you are allowed an inference rule "Tautological Implication" then any tautology has a 1 ...
11
votes
2answers
537 views

Which axioms of ZFC or PA are known to not be derivable from the others?

Which, if any, axioms of ZFC are known to not be derivable from the other axioms? Which, if any, axioms of PA are known to not be derivable from the other axioms?
11
votes
5answers
388 views

what is the definition of $=$?

what is the definition of $=$? Above is the question that I would like to be answered, below are some of my thoughts. I've been thinking about what it means to say $A = B$ I came to this from ...
11
votes
7answers
1k views

“Proof” that ZFC is inconsistent using Turing machines

I came across the following "proof" for the inconsistency of ZFC and can't find the flaw in it (if there is one...): Construct a Turing machine A which sequentially runs on all proofs in ZFC and ...
11
votes
2answers
290 views

Is second order logic even a logic?

Second order logic is a language, but, is it a logic? My understanding is that a logic (or "logical system") is an ordered pair; it is a formal system together with a semantics. However, the language ...
11
votes
3answers
435 views

Gentzen Cut elimination: Why do we have to “go infinite”?

I found some slides here that say you can't do cut elimination on PA with axioms like $$\frac{P(Z)\;\;\;\;\;\forall n,\,P(n) \implies P(Sn)}{\forall n,\,P(n)}$$ (which denotes infinitely many axioms ...
11
votes
5answers
1k views

A concrete example of Gödel's Incompleteness theorem

Gödel's incompleteness theorem says "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively ...
11
votes
2answers
812 views

Software for solving geometry questions

When I used to compete in Olympiad Competitions back in high school, a decent number of the easier geometry questions were solvable by what we called a geometry bash. Basically, you'd label every ...
11
votes
1answer
373 views

Set of All Groups

In my undergraduate Group Theory class, while discussing the impossibility of equivalence relations on groups, my professor said that the set of all groups does not exist. Are there any group ...
11
votes
1answer
573 views

Is a Gödel sentence logically valid?

This might be an elementary question, but I am just beginning to learn logic theory. From wikipedia article on Gödel's incompleteness theorems Any effectively generated theory capable of ...
11
votes
1answer
440 views

“Nice” well-orderings of the reals

I have a question which I believe could be easily resolved if I happened to look at the right source - hence my asking it here as opposed to at MathOverflow. I've tried googling it, but I haven't been ...
11
votes
1answer
432 views

Injective function and ultrafilters

An exercise left by my teacher let me think that the following statement is true: Let $\mathcal{U}$ be an ultrafilter on $\mathbb{N}$. Then every injective function ...
11
votes
3answers
615 views

In axiomatization of propositional logic, why can uniform substitution be applied only to axioms?

I'm reading an introductory book about mathematical logic for Computation (just for reference, the book is "Lógica para Computação", by Corrêa da Silva, Finger & Melo), and would like to ask a ...
11
votes
2answers
231 views

Putting down axioms for some symbols. Playing with their consequences qualitatively and symbolically. Building theories. The book?

I am interested in the design and building of theories. By building theories, I mean putting down axioms of various kinds, over various fields, exploring their perhaps interesting, or probably boring, ...
11
votes
2answers
585 views

Formalizing Those Readings of Leibniz Notation that Don't Appeal to Infinitesimals/Differentials

[disclaimer: I've studied a lot of logic but never been good at analysis, so that's the angle I'm coming from below] in my attempt to find a precise version of the 'definitions' usually given when ...
11
votes
1answer
347 views

Formalizing metamathematics

I am reading historical/philosophical stuff on the concept of "metamathematics" and am by now quite confused. Several questions emerged, but they are probably somehow confused and interrelated, I ...
11
votes
1answer
186 views

Unprovable unprovability

In general, mathematical conjectures are resolved by proof, disproof, or proof that they are neither provable nor disprovable. Is it possible that some open conjectures cannot be settled in any of ...
11
votes
1answer
183 views

The (un)decidability of Robinson-Arithmetic-without-Multiplication?

Take our old friend Robinson Arithmetic, and cut it down to a theory of successor and addition. To spell that out (just to ensure that we are singing from the same hymn sheet), take the first-order ...
11
votes
0answers
340 views

Non-axiomatisability and ultraproducts

Let $T$ be a first-order theory over a language $L$, and let $\mathcal{M}$ be a subclass of the class of models of $T$. As I understand it, if there is no theory $\hat{T}$ over $L$ whose class of ...
10
votes
3answers
558 views

Three doors logic problem

Imagine three doors where behind one door $\text{A}$ there is a new car, behind door $\text{B}$ there is a goat, and behind door $\text{C}$ there is a new car and a goat. The problem is that each ...
10
votes
7answers
7k views

Not understanding this row of truth table for logical implication

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\\ ...
10
votes
4answers
456 views

Clarification of a remark of J. Steel on the independence of Goldbach from ZFC

On page 424 of the following paper: S. Feferman, Harvey M. Friedman, P. Maddy and John R. Steel, ``Does Mathematics Need New Axioms?'' The Bulletin of Symbolic Logic, Vol. 6, No. 4 (Dec., 2000), pp. ...
10
votes
5answers
980 views

Is there a proof of Gödel's Incompleteness Theorem without self-referential statements?

For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements. My question is, what if one argues that Gödel's Incompleteness Theorem only matters ...
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 , ...
10
votes
5answers
934 views

What is a false premise?

I don't understand what a sound argument is. And what does it mean for a premise to be false? Why does case 3 (A is false, B is true) not apply in the real world? Here the author says that the first ...
10
votes
6answers
287 views

Axiomatic Foundations

I am trying to deduce how mathematicians decide on what axioms to use and why not other axioms, I mean surely there is an infinite amount of available axioms. What I am trying to get at is surely if ...
10
votes
3answers
592 views

Difference between undecidable statements in set-theory and number theory?

Do all statements about the integers have a definite truth value? For instance: Goodstein's theorem is clearly true, otherwise we could find a finite counterexample thus it would be possible to ...
10
votes
5answers
521 views

What are reasons why some symbols in mathematical logic are not standardized?

Why is so hard to find a standardisation regarding symbolism and/or terminology in Mathematical Logic ? We see again and again students asking if e.g. $\rightarrow$ and $\implies$ means the same ...
10
votes
3answers
1k views

How to prove an axiom system is consistent?

I would like to know whether systems capable of proving other systems consistent, use any methods fundamentally different then 'Add 'T is consistent' as axiom, then T is consistent, QED'. How does ...
10
votes
2answers
358 views

What is the converse of this statement and is it true?

If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$. I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
10
votes
3answers
263 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
10
votes
3answers
560 views

Solving P vs NP with computer

Is it possible to build a computer program that would (eventually) bring a solution to the P vs. NP question?
10
votes
2answers
394 views

Is Gödel's incompleteness theorem provable without any model-theoretic notion?

The entry on Gödel's incompletenss theorem in Wikipedia says: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, ...
10
votes
2answers
286 views

Are there formal systems that can not be proved to be complete or incomplete?

I'm reading GEB and was thinking about this. Are there any formal systems where the proof of their completeness/incompleteness is unprovable? This question could go ad infinitum. Could there be any ...
10
votes
4answers
466 views

which texts do you recommend to study mathematical logic?

I want to study Godel's incompleteness theorem's and I look for a text whoch provide mathematical logic with a nice way to make me able to study Godel's incompleteness theorems I didn't study ...
10
votes
1answer
195 views

Do ordered fields and archimedian ordered fields have the same first-order theory?

Let us suppose that the first-order language of ordered fields has symbols for addition, subtraction, multiplication and order, and constant symbols for 0 and 1. An ordered field is said to be ...
10
votes
2answers
472 views

A question on linear orders and elementary equivalence

Does anybody know whether the following statement is true or false? Conjecture: For every linear order $\langle A, \leq \rangle$ there is a (topologically) closed subset $X$ of $\mathbb{R}$ (the real ...
10
votes
4answers
488 views

How does one show a set of axioms is independent? (of each other?)

I am being asked to show that the groups axioms of existence of an identity, of inverses and of associativity are independent. Does this mean that none of two of them imply the third? That is: do I ...
10
votes
3answers
171 views

What do we call entities (like $\sum$) that bind variables?

In logic, we refer to entities like $\forall$ and $\exists$ as quantifiers, because they bind variables. However, variable-binding doesn't just occur at quantifiers. For example, the symbol $i$ ...
10
votes
2answers
469 views

a “natural” real number that is not computable

Most of the examples of non-computable real numbers use some kind of a diagonalization construction over some turing computable model of computation. See Are there any examples of non-computable real ...