Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

learn more… | top users | synonyms (1)

15
votes
1answer
395 views

A *finite* first order theory whose finite models are exactly the $\Bbb F_p$?

Since this question turned out to be trivial, I'm now asking this strengthened version: Is there a finitely axiomatized first order theory $T$ in the language of rings such that its finite models ...
15
votes
2answers
271 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 ...
15
votes
1answer
269 views

If a first-order theory $T$ has an infinite model, does $T$ necessarily have two isomorphic models that look non-isomorphic inside a subuniverse?

Assume a proper class of inaccessibles. I find the following general question interesting: for which isomorphism classes $C$ of first-order structures sharing a common signature does there exist a ...
15
votes
0answers
385 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 ...
15
votes
2answers
295 views

How much math do we need to prove all simple numeric identities?

Consider real numeric expressions build only from integers, operators $+,-,\times,/$ and taking a positive expression to a power (no variables involved), e.g. $$\frac{2}{7},\ 2^{1/2},\ ...
14
votes
7answers
1k views

Applications of ultrafilters

I'm looking for some interesting applications of ultrafilters and also everything of interest involving ultrafilters. Do you know some applications or interesting things involving ultrafilters? I'm ...
14
votes
3answers
2k views

“IFF” (if and only if) vs. “TFAE” (the following are equivalent)

If $P$ and $Q$ are statements, $P \iff Q$ and The following are equivalent: $(\text{i}) \ P$ $(\text{ii}) \ Q$ Is there a difference between the two? I ask because formulations ...
14
votes
3answers
550 views

What's the point of modal logic?

I was just reading about modal logic at wikipedia, and it seems that the usual approach is to introduce two new operations $\Diamond$ and $\square$ that mean 'possibly' and 'necessarily' respectively. ...
14
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 ...
14
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 ...
14
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 ...
14
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 ...
14
votes
2answers
361 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$ ...
14
votes
5answers
2k views

How is exponentiation defined in Peano arithmetic?

How would exponentiation be defined in Peano arithmetic? Unless $n$ is fixed natural number, $x^n$ seems to be hard to define. Edit 2: So, what would be the way to define $x^n+y^n = z^n$ using ...
14
votes
3answers
501 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 ...
14
votes
5answers
851 views

Odd proof method

I read on the wikipedia article for the Riemann Hypothesis that some theorems have been proved by assuming the hypothesis to be true and then false and proving the certain theorem from both cases. ...
14
votes
5answers
913 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 ...
14
votes
3answers
938 views

Can multiplication be defined in terms of divisibility?

Peano Arithmetic has two axioms which use the multiplication symbol: ∀x:x*0=0 and ∀x:∀y:x*Sy=x+x*y. The 2-term relation "x divides y" can be expressed as D(x,y) := ∃z:z*x=y. Multiplication is a ...
14
votes
1answer
934 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 ...
14
votes
2answers
465 views

Is there a “tree-like” proof of compactness theorem in the case of uncountably many variables?

I like proofs using trees and König's lemma, since they are very visual. One of the applications of König's lemma you can show to students is proving compactness theorem for propositional calculus, ...
14
votes
1answer
360 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 ...
14
votes
2answers
452 views

What is an example of a Transfinite Argument?

I was in a discussion today with a philosopher about the merit of the technique of "proof by contradiction." He mentioned the Law of Excluded Middle, wherein we (typically as mathematicians) assume ...
14
votes
5answers
3k 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 ...
14
votes
3answers
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 ...
14
votes
1answer
255 views

Are sets constructed using only ZF measurable using ZFC?

Suppose $S$ is a subset of $\mathbb{R}$ which can be defined without using the axiom of choice, i.e. which can be proved to exist using only the axioms of ZF. Does it follow that $S$ is measurable? ...
14
votes
3answers
980 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 ...
14
votes
1answer
519 views

What underlies formal logic (or math, generally)?

I read a useful definition of the word understanding. I can't recall it verbatim, but the notion was that understanding is 'data compression': understanding happens when we learn one thing that ...
14
votes
1answer
511 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?
14
votes
1answer
549 views

Could it be that Goldbach conjecture is undecidable?

The result closest to Goldbach conjecture is Chen's theorem [Sci. Sinica 16 157–176], the proposition ``1+2''. It is natural to ask if it is likely that under our arithmetic axioms the Goldbach ...
14
votes
1answer
567 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 ...
14
votes
2answers
448 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
3k 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
7k views

Example of set which contains itself

I am trying to understand Russells's paradox How can a set contain itself? Can you show example of set which is not a set of all sets and it contains itself.
13
votes
1answer
831 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. ...
13
votes
3answers
697 views

Proving the existence of a proof without actually giving a proof

In some areas of mathematics it is everyday practice to prove the existence of things by entirely non-constructive arguments that say nothing about the object in question other than it exists, e.g. ...
13
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 ...
13
votes
1answer
600 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 ...
13
votes
3answers
457 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 ...
13
votes
1answer
301 views

Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
13
votes
1answer
1k 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 ...
13
votes
2answers
377 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. ...
12
votes
4answers
885 views

Set builder notation: Colon or Vertical Line

I remember once hearing offhandedly that in set builder notation, there was a difference between using a colon versus a vertical line, e.g. $\{x: x \in A\}$ as opposed to $\{x\mid x \in A\}$. I've ...
12
votes
5answers
3k 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 ...
12
votes
10answers
689 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
9answers
486 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 ...
12
votes
3answers
681 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 ...
12
votes
9answers
11k views

Prove that the union of countably many countable sets is countable.

I am doing some homework exercises and stumbled upon this question. I don't know where to start. Prove that the union of countably many countable sets is countable. Just reading it confuses me. ...
12
votes
2answers
1k 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 ...
12
votes
4answers
617 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 ...