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
4answers
838 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
730 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
791 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
942 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
317 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
491 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
293 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
524 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
622 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
10k 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
572 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
346 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
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
629 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
349 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
862 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
180 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
5answers
553 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
739 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
476 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
930 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
685 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
417 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
1answer
488 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 ...
12
votes
3answers
516 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
263 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
217 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
768 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
3answers
700 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
376 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
213 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
248 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
396 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
3answers
822 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
953 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
539 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. ...
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
4answers
942 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
6answers
517 views

How do we know that we'll never prove a contradiction in Math

I know that we can prove a contradiction in naive set theory. Let D be a set of all sets that don't contain itself. Say D does not contain D. Then D contains D. That means D contains itself. A ...
11
votes
6answers
345 views

Axiomatic Foundations

I am trying to deduce how mathematicians decide on what axioms to use and why not other axioms, I mean surely there is an infinite amount of available axioms. What I am trying to get at is surely if ...
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
3answers
548 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
4answers
457 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 ...