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)

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
821 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
331 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
845 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
5answers
759 views

Purpose of the Peano Axioms

Wikipedia says the Peano Axioms are a set of axioms for the natural numbers. Is the purpose of the axioms to create a base on which we can build the rest of mathematicas formally? If this is true ...
13
votes
1answer
799 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
987 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
324 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
5answers
2k 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 ...
13
votes
1answer
492 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
303 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
526 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
626 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
11k 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
574 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
1k 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
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 ...
12
votes
3answers
350 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
434 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
1answer
649 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
2answers
357 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
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
880 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
183 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
207 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
561 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
756 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
492 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
2answers
942 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
1answer
711 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
3answers
420 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
542 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
269 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
220 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
176 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
3answers
791 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 ...
12
votes
1answer
975 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
713 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
385 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
218 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
0answers
270 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
403 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
9answers
294 views

If $x^2=x$, then $x=1$. Is this statement true or false?

I understand that this equation has two solutions, that is $x=1$ or $x=0$. But if you say this statement is false, you are like saying that $x=1$ is not the solution for the equation. If a basket ...
11
votes
3answers
825 views

Why truth table is not used in logic?

One day, I bought Principia Mathematica and saw a lot of proofs of logical equations, such as $\vdash p \implies p$ or $\vdash \lnot (p \wedge \lnot p)$. (Of course there's bunch of proofs about ...
11
votes
5answers
1k 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 ...
11
votes
2answers
964 views

How to find the shortest proof of a provable theorem?

Roughly speaking, there are some fundamental theorems in mathematics which have several proofs (e.g. Fundamental Theorem of Algebra), some short and some long. It is always an interesting question ...
11
votes
4answers
543 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. ...