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
2answers
369 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$ ...
15
votes
4answers
1k 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?
15
votes
6answers
1k views

Proving $(p \to (q \to r)) \to ((p \to q) \to (p \to r))$

I'm looking for a way to prove $$ (p \to (q \to r)) \to ((p \to q) \to (p \to r)) $$ from the axioms $$ \begin{align} & p \to (q \to p) \\ & (p \to (p \to q)) \to (p \to q) \\ & (p ...
15
votes
2answers
627 views

Comparing countable models of ZFC

Let us consider the class $\cal C$ of countable models of ZFC. For ${\mathfrak A}=(A,{\in}_A)$ and ${\mathfrak B}=(B,{\in}_B)$ in $\cal C$ I say that ${\mathfrak A}<{\mathfrak B}$ iff there is a ...
15
votes
1answer
977 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 ...
15
votes
4answers
866 views

An (apparently) vicious circle in logic

Can someone please help me with this following exercise 4.4 (p. 114) from the Mathematical Logic book of Ebbinghaus et al(this is not homework, but rather something that has been bugging me for a long ...
15
votes
1answer
1k views

Infinite Set is Disjoint Union of Two Infinite Sets

A finite set is a set such that there exists a bijection from it to some finite ordinal. An infinite set is a set that is not finite. In ZF, can you prove that every infinite set is the union of two ...
15
votes
1answer
365 views

Is $\Bbb R$ definable in $(\Bbb C,0,1,+,*,\exp)$?

Is there a first-order formula ϕ(x) with exactly one free variable $x$ in the language of fields together with the unary function symbol $\exp$ such that in the standard interpretation of this ...
15
votes
3answers
2k 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 ...
15
votes
4answers
679 views

What did Whitehead and Russell's “Principia Mathematica” achieve?

In philosophical contexts, the Principia Mathematica is sometimes held in high regard as a demonstration of a logical system. But what did Whitehead and Russell's Principia Mathematica achieve for ...
15
votes
1answer
490 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 ...
15
votes
1answer
401 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
284 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
579 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 ...
15
votes
1answer
580 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 ...
15
votes
1answer
271 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
2answers
306 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
2k views

Why do statements which appear elementary have complicated proofs?

The motivation for this question is : Rationals of the form $\frac{p}{q}$ where $p,q$ are primes in $[a,b]$ and some other problems in Mathematics which looks as if they are elementary but their ...
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
3k 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
9answers
13k 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. ...
14
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 ...
14
votes
5answers
2k 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
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.
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

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
5answers
3k 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
518 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
3answers
978 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
883 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. ...
14
votes
5answers
856 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
2answers
503 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
372 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
1answer
318 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?
14
votes
2answers
455 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
1answer
262 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
1k 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
537 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
512 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
2answers
468 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
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 ...
13
votes
4answers
1k 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 ...
13
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 ...
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
3k views

What precisely is a vacuous truth?

Is there a proper and precise definition that goes something like this? Definition. A statement $S$ is a vacuous truth if ... ...
13
votes
2answers
440 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 ...
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
8answers
4k views

Tricks for Constructing Hilbert-Style Proofs

Several times in my studies, I've come across Hilbert-style proof systems for various systems of logic, and when an author says, "Theorem: $\varphi$ is provable in system $\cal H$," or "Theorem: the ...
13
votes
1answer
642 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 ...