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
3answers
317 views

Unnecessary property in definition of topological space

A set $X$ with a subset $\tau\subset \mathcal{P}(X)$ is called a topological space if: $X\in\tau$ and $\emptyset\in \tau$. Let $L$ be any set. If $\{A_\lambda\}_{\lambda\in ...
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
519 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
503 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
416 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
416 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
528 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
386 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
289 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
428 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
1answer
368 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
2answers
662 views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
11
votes
1answer
570 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
436 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
431 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
2answers
193 views

Founding Arithmetic on geometry

In the past I found some fleeting references that some (Frege in his later years being one of them) tried to found arithmetic not on set-theory and logic but on geometry and logic. Unfortunedly Frege ...
11
votes
3answers
609 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
230 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
579 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
344 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
184 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
0answers
169 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
335 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
554 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
4answers
446 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
957 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
5answers
747 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 ...
10
votes
3answers
992 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
924 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
3answers
587 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
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
5answers
511 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
2answers
724 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 ...
10
votes
6answers
279 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
2answers
355 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
559 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
382 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
285 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
2answers
799 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 ...
10
votes
4answers
459 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
194 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
478 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
170 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
466 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 ...
10
votes
2answers
114 views

Growth-rate vs totality

How can one prove the statement, "If a function grows fast enough, it cant be proven total in PA, unless PA is inconsistent"? How fast must it grow to be not provably total?
10
votes
1answer
369 views

Any branch of math can be expressed within set theory, is the reverse true?

Set theory seems to have the property of being "universal", in the sense that any branch of math can be expressed on its language. Is there any other branch of math with this property? I am asking ...