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

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
798 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
5answers
631 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 ...
12
votes
4answers
442 views

Existence Proofs

This may be a stretch, but are there examples of proofs that prove that a proof exists for a theorem. For example, if A is a theorem, and it is too tedious to prove that, is it possible to show that ...
12
votes
2answers
1k views

Classic type theory textbooks

There are many classic textbooks in set and category theory (as possible foundations of mathematics), among many others Jech's, Kunen's, and Awodey's. Are there comparable classic textbooks in ...
12
votes
1answer
694 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
624 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
395 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
2answers
794 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 ...
12
votes
3answers
433 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
257 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
212 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
167 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
386 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 ...
12
votes
2answers
235 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
1answer
202 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 ...
11
votes
4answers
803 views

Are there any non-constructive proofs for which an example was never constructed?

By non-constructive I mean the following: A mathematical object is proven to exist yet it is not constructed in the proof. Are there any examples of proofs like this where the mathematical object ...
11
votes
3answers
796 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
7answers
9k 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?
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
3answers
1k views

How is addition defined?

I've been reading On Numbers and Games and I noticed that Conway defines addition in his number system in terms of addition. Similarly in the analysis and logic books that I've read (I'm sure that ...
11
votes
5answers
897 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 ...
11
votes
4answers
851 views

The Maths necessary to understand Logic, Model theory and Set theory to a very high level

I am studying Philosophy but most of my interests have to do with the philosophy of Maths and Logic. I would like to be able to have a very high level of competence in the topics mentioned in the ...
11
votes
7answers
1k views

Is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$?

is $\forall x\,\exists y\, Q(x, y)$ the same as $\exists y\,\forall x\,Q(x, y)$? I read in the book that the order of quantifiers make a big difference so I was wondering if these two expressions ...
11
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 ...
11
votes
3answers
542 views

Statements with no counterexample

Is there some proven statement that tells us "not all X satisfy Y", but there are currently no examples of X which do not satisfy Y? Is it necessarily true that there are always explicit ...
11
votes
1answer
566 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. ...
11
votes
4answers
432 views

Is there a connection between length of sentence and length of proof?

My basic question is: "Do longer tautologies take longer to prove?" But obviously this is underdetermined. If you are allowed an inference rule "Tautological Implication" then any tautology has a 1 ...
11
votes
2answers
583 views

Which axioms of ZFC or PA are known to not be derivable from the others?

Which, if any, axioms of ZFC are known to not be derivable from the other axioms? Which, if any, axioms of PA are known to not be derivable from the other axioms?
11
votes
3answers
272 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
11
votes
5answers
403 views

what is the definition of $=$?

what is the definition of $=$? Above is the question that I would like to be answered, below are some of my thoughts. I've been thinking about what it means to say $A = B$ I came to this from ...
11
votes
4answers
1k views

What is the intuition behind the “par” operator in linear logic?

I'm $\DeclareMathOperator{\par}{\unicode{8523}}$ trying to wrap my mind around the $\par$ ("par") operator of linear logic. The other connectives have simple resource interpretations ($A\otimes B$ ...
11
votes
1answer
867 views

Big Bang Theory Reference to Formal Logic

In the second episode "The Junior Professor Solution" of the 8th season of the Big Bang Theory, there exists a brief moment where Sheldon Cooper references one of his boards with what for a brief ...
11
votes
3answers
493 views

Gentzen Cut elimination: Why do we have to “go infinite”?

I found some slides here that say you can't do cut elimination on PA with axioms like $$\frac{P(Z)\;\;\;\;\;\forall n,\,P(n) \implies P(Sn)}{\forall n,\,P(n)}$$ (which denotes infinitely many axioms ...
11
votes
2answers
875 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 ...
11
votes
1answer
431 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 ...
11
votes
3answers
184 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$ ...
11
votes
1answer
466 views

“Nice” well-orderings of the reals

I have a question which I believe could be easily resolved if I happened to look at the right source - hence my asking it here as opposed to at MathOverflow. I've tried googling it, but I haven't been ...
11
votes
1answer
439 views

Any branch of math can be expressed within set theory, is the reverse true?

Set theory seems to have the property of being "universal", in the sense that any branch of math can be expressed on its language. Is there any other branch of math with this property? I am asking ...
11
votes
1answer
434 views

Injective function and ultrafilters

An exercise left by my teacher let me think that the following statement is true: Let $\mathcal{U}$ be an ultrafilter on $\mathbb{N}$. Then every injective function ...
11
votes
3answers
692 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 ...
11
votes
2answers
237 views

Putting down axioms for some symbols. Playing with their consequences qualitatively and symbolically. Building theories. The book?

I am interested in the design and building of theories. By building theories, I mean putting down axioms of various kinds, over various fields, exploring their perhaps interesting, or probably boring, ...
11
votes
2answers
639 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 ...
11
votes
1answer
335 views

Does a nonlinear additive function on R imply a Hamel basis of R?

A function is additive if $f(x+y) = f(x) + f(y)$. Intuitively, it might seem that an additive function from R to R must be linear, specifically of the form $f(x) = kx$. But assuming the axiom of ...
11
votes
1answer
370 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 ...
11
votes
0answers
151 views

What does it take to divide by $2$ (or even $3$)?

Theorem 1 [ZFC, classical logic]: If $A,B$ are sets such that $\textbf{2}\times A\cong \textbf{2}\times B$, then $A\cong B$. That's because the axiom of choice allows for the definition of ...
11
votes
0answers
163 views

How much set theory does the category of sets remember?

Question. Let $M$ be a model of enough set theory. Then we can form a category $\mathbf{Set}_M$ whose objects are the elements of $M$ and whose morphisms are the functions in $M$. To what extent is ...
11
votes
0answers
367 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 ...
10
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 ...
10
votes
8answers
9k views

Not understanding this row of truth table for logical implication

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...