Questions about 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)

14
votes
2answers
500 views

What practical proofs work in intuitionistic but not minimal logic?

Intuitionistic logic contains the rule $\bot \rightarrow \phi$ for every $\phi$. In the formulations I have seen this is a separate axiom, and the logic without this axiom(?) is termed "minimal ...
14
votes
1answer
440 views

Mendelson's $\mathit{Mathematical\ Logic}$ and the missing Appendix on the consistency of PA

In the first edition of Elliott Mendelson's classic Introduction to Mathematical Logic (1964) there is an appendix, giving a version of Schütte's (1951) variation on Gentzen's proof of the consistency ...
14
votes
2answers
391 views

What is the most influential work of Grothendieck in mathematics?

Recently Alexander Grothendieck has passed away but his mathematical wave is still alive and passes its growth ages. It is hard to describe the influence of such a great man in mathematics just in few ...
13
votes
4answers
2k views

Proof by Contradiction, Circular Reasoning?

Suppose we wish to prove $P$ implies $Q$. We assume $P$. Proof by contradiction begins by assuming not $Q$, and from these two assumptions, a "contradiction" is derived. Now, sometimes that ...
13
votes
5answers
1k 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 ...
13
votes
5answers
1k 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 ...
13
votes
6answers
2k views

What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
13
votes
4answers
838 views

Does proof by contradiction assume that math is consistent?

The standard proof by contradiction goes like It is known that $P$ is true. Assume that $Q$ is true. Using the laws of logic, deduce that $P$ is false. Rejecting this contradiction, we are forced to ...
13
votes
2answers
2k 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 ...
13
votes
2answers
334 views

A sentence false in a field of characteristic $0$ but true in all fields of positive characteristic?

Consider the language $L=\{+,\cdot, 0, 1\}$ of rings. It is easy to show using compactness that if $\sigma$ is a sentence that holds in all fields of characteristic $0$, there is some $N\in \mathbb N$ ...
13
votes
4answers
858 views

Is there a statement whose undecidability is undecidable?

We know there are statements that are undecidable/independent of ZFC. Can there be a statement S, such that (ZFC $\not\vdash$ S and ZFC $\not\vdash$ ~S) is undecidable?
13
votes
1answer
814 views

(Why) is topology nonfirstorderizable?

Is it the right point of view to say, that topology is nonfirstorderizable (only) because the union of arbitrarily many open sets has to be open? And if "arbitrarily many" was relaxed to "finitely ...
13
votes
2answers
1k 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 ...
13
votes
1answer
327 views

Do you need the Axiom of Choice to assert that every real vector space has a norm?

Math people: This question is 95% answered (the first answer) at Does every $\mathbb{R},\mathbb{C}$ vector space have a norm? and Vector Spaces and AC . The questions, answers, and links found there ...
13
votes
3answers
827 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 ...
13
votes
1answer
493 views

Is quantum logic producing interesting/different mathematics?

Is quantum logic producing interesting/different mathematics? Is it different from the intuitionist approach to mathematics? How?
13
votes
2answers
322 views

What does it mean to say that a particular mathematical theory is a foundation for mathematics?

We usually hear that set theory is a foundation for contemporary mathematics. Category theory is also another foundation of maths. There are other theories which deemed to be a foundation for maths. ...
13
votes
1answer
531 views

successful absurd formalities

Has anyone published in print or on a web site or elsewhere a compilation of successful illogical formal arguments? By those I mean arguments that follow a form in disregard of the legality of its ...
12
votes
10answers
639 views

Quantifier Notation

What's the difference between $\forall \space x \space \exists \space y$ and $\exists \space y \space \forall \space x$ ? I don't believe they mean the same thing even though the quantifiers are ...
12
votes
7answers
12k views

Is XOR a combination of AND and NOT operators?

I'm not sure whether this is the best place to ask this, but is the XOR binary operator a combination of AND+NOT operators?
12
votes
4answers
586 views

Number Theory in a Choice-less World

I was reading this article on the axiom of choice (AC) and it mentions that a growing number of people are moving into school of thought that considers AC unacceptable due to its lack of constructive ...
12
votes
2answers
2k 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 ...
12
votes
3answers
353 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 ...
12
votes
1answer
437 views

What's the theory in which incompleteness of PA is proved?

Maybe this is a dumb question, but I have to admit that it is not really clear to me what the theory is, in which incompleteness of PA and stronger theories is proved. The texts I did study so far are ...
12
votes
1answer
5k 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 ...
12
votes
3answers
2k views

Proper way to read $\forall$ - “for all” or “for every”?

I was asked in class the other day by a professor for whom English is a second language why $\forall$ is sometimes read "for all" while other times read "for every." Is there a rule for this? I was ...
12
votes
2answers
370 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 ...
12
votes
1answer
661 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. ...
12
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 ...
12
votes
2answers
904 views

What's an example of a theory that's consistent yet has no model?

By the completeness theorem for first order logic, if a theory is consistent then it has a model. But what's a counterexample to this : what's an example of a logic where some theory is consistent ...
12
votes
1answer
194 views

Can all math results be formalized and checked by a computer?

Can all math results, that have been correctly proven so far, be formalized and checked by a computer? If so, what type of logic would need to be used there? I've heard that the first-order logic is ...
12
votes
3answers
211 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$ ...
12
votes
5answers
582 views

Which texts to study mathematical logic, for subsequently studying Godel's incompleteness theorems?

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

Is there a simple group of any (infinite) size?

I'm trying to show that for any infinite cardinal $\kappa$ there is a simple group $G$ of size $\kappa$, I tried to use the compactness theorem and then ascending Löwenheim-Skolem, but this is ...
12
votes
1answer
501 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 ...
12
votes
1answer
780 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 ...
12
votes
2answers
965 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 ...
12
votes
3answers
422 views

On Pudlak's “Life in an Inconsistent World”

In his Logical Foundation of Mathematics and Computational Complexity (2013), Pavel Pudlak invites the readers to ponder about fictitious people whose natural numbers are nonstandard. His exposition ...
12
votes
3answers
564 views

Does every complete theory admit quantifier elimination?

Does every complete theory admit quantifier elimination? I know that at least in some simple cases the reverse is true; such as some reducts of number theory.Thanks
12
votes
2answers
271 views

Is it possible to formalize the relationship between different proofs of the same theorem?

Some theorems have many proofs. Examples include the Pythagorean Theorem and the Law of Quadratic Reciprocity. I was wondering if one could formalize the relationship between these proofs. Sure, they ...
12
votes
2answers
236 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 ...
12
votes
2answers
178 views

Two styles of semantics for a first-order language: what's to choose?

The usual classical semantics for FOL gets presented in two styles. Suppressing details irrelevant for the headline question, suppose the $L$-wff $\varphi(x)$ has only $x$ free, and let $I$ be a fixed ...
12
votes
1answer
998 views

The Power of Lambda Calculi

A simple question here, which likely demands a somewhat complex answer... Or rather, a set of related questions. What are the advantages of typed lambda calculus over untyped lambda calculus in ...
12
votes
3answers
730 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 ...
12
votes
1answer
388 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 ...
12
votes
1answer
223 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 ...
12
votes
1answer
171 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
12
votes
0answers
287 views

complete, finitely axiomatizable, theory with 3 countable models

Does it exist a complete, finitely axiomatizable, first-order theory $T$ with exactly 3 countable non-isomorphic models? A few relevant comments: There is a classical example of a complete theory ...
12
votes
0answers
412 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 ...
11
votes
5answers
2k views

Example of non-isomorphic structures which are elementarily equivalent

I just started learning model theory on my own, and I was wondering if there are any interesting examples of two structures of a language L which are not isomorphic, but are elementarily equivalent ...