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
11answers
3k views

Logic nonsense/paradox

I'm not sure if this is a paradox or a nonsense or neither of both. Anyway this is the "problem" if we can call it like that: A: B is True B: A is False How can ...
15
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 ...
15
votes
10answers
2k views

Having hard time understanding proofs by contradiction.

I am reading an introductory book on mathematical proofs and I don't seem to understand the mechanics of proof by contradiction. Consider the following example. $\textbf{Theorem:}$ If $P \rightarrow ...
15
votes
9answers
14k 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. ...
15
votes
3answers
1k views

Why do we show that structures aren't isomorphic by exhibiting a property not shared by one of them?

If someone asks me how to prove that two order structures $\langle A,\leq \rangle$ and $\langle B,\preceq \rangle$ are isomorphic I would immediately suggest: try to find a function $f:A\to B$ such ...
15
votes
6answers
21k 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?
15
votes
3answers
572 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. ...
15
votes
3answers
1k views

Proof that $\mathbb N $ is finite

Obviously this is a false proof. It relies on Berry's paradox. Assume that $\mathbb{N}$ is infinite. Since there are only finitely many words in the English language, there are only finitely many ...
15
votes
2answers
1k views

Gödel's incompleteness theorem and real closed fields

I am familiar with the result of Gödel's incompleteness theorem. I find it hard though, to convince myself that when we replace normal number arithmetic with real closed fields, that there is an ...
15
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 ...
15
votes
2answers
377 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
641 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
1k 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
915 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
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 ...
15
votes
1answer
375 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
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
404 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
291 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
769 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
586 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
272 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
313 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},\ \sqrt[5]{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
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
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
8k 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
557 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
988 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
918 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
857 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. I.e....
14
votes
4answers
1k 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 ...
14
votes
1answer
678 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 ...
14
votes
2answers
515 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
380 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
328 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
458 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
1answer
270 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
575 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
519 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
480 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 ...