# Tag Info

Accepted

### Are there more truths than proofs?

That's correct, but it is not very interesting: we don't have "access" to most mathematical facts. It is not even clear what a proof of an arbitrary mathematical fact would mean, because to ...
• 16.2k
Accepted

### How do we know what natural numbers are?

How do the mathematicians that write standard natural numbers have formal consensus on what they are talking about? Mathematicians work in a meta-system (which is usually ZFC unless otherwise stated)....
• 59.5k
Accepted

### Do we have to prove how parentheses work in the Peano axioms?

In formal language theory (most relevantly, context-free languages), there is the notion of an abstract syntax tree. A decent chunk of formal language theory is figuring out how to turns flat, linear ...
• 25.3k

### With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then?

Did people really thought that for every theory and a given formula, either it or its negation are semantically valid, i.e. fulfilled by every model? (Emphasis added). No, of course not. It's easy to ...

### Can you give me an example of an implicit use of Godel's Completeness Theorem, say for example in group theory?

A simple example might be something like the following: Proposition: An element $g \in G$ of a group and any of its conjugates $hgh^{-1} \in G$ have the same order. This is a collection of first-...
• 441k

### How do we know what natural numbers are?

Yes, as you phrased it in a comment: So even the academic usage of the term standard natural number trusts in our intuitive understanding from preschool? That's exactly how it is. We believe, ...
Accepted

Here are some possible ways to make these kinds of numerical claims in general: 'At least n' (Method 1) "There is at least 1 P" : $\exists x P(x)$ "There are at least 2 P's" : $\exists x \exists y (... • 102k 22 votes Accepted ### What exactly is a contradiction and how does it differ from falsity? Your understanding is correct. Put simply, a contradiction is a sentence that is always false. More precisely, A statement is a contradiction iff it is false in all interpretations. In propositional ... • 10.7k 20 votes Accepted ### With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then? EDIT: I've added here some of the facts from the discussion between me and the OP in the comments below the question. These doesn't address the actual OP - "why was Godel's theorem surprising?" - but ... • 251k 19 votes Accepted ### Convert "Only Believers respect God" to predicate logic. OP's proposed solution is that there exists at least one believer, who also respects God. This is not equal to the original request, and indeed need not even be true. For example, if nobody ... • 83.2k 19 votes ### How to think about theories that prove their own inconsistency? When we think about theories like ZFC or PA, we often view them foundationally: in particular, we often suppose that they are true. Truth is very strong. Although it's difficult to say exactly what it ... • 251k 19 votes Accepted ### What will be the negation of this statement: Yes, that works. In logic, the original is:$\forall x (S(x) \rightarrow \exists y (H(y) \land I(y,x) \land \exists z (P(z) \land L(z,y) \land ((R(x) \land B(x)) \lor (E(x) \land K(x)))))$If you ... • 102k 19 votes ### With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then? It may be useful to point out that there are (at least) two purposes for which axiomatic theories are created and, as a result, two sorts of theories, for which we may have very different expectations.... • 73.4k 19 votes Accepted ### In his 1931 incompleteness proof, how does Godel's definition of "immediate consequence" work? Welcome to Math.SE! Maybe every other mode of logical consequence is in some sense equivalent to modus ponens? Yes, modus ponens is the only propositional inference rule defined in Principia ... • 11.9k 18 votes ### Understanding ZFC ZFC does generate a “theory”. Formally speaking, a theory is simply a set of sentences in the given formal language. Any set of axioms generates a theory, namely the collection of sentences provable ... • 12.8k 18 votes Accepted ### The meaning of an implication with the existential quantifier Example c was written:$ \exists x (C(x) \to F(x))$The answer to that example was given as "Someone is a comedian and that means they are funny" That is an incorrect translation. Imagine a ... • 10.5k 17 votes ### Distributive Property of Quantifiers here are some basic distributive properties in quantifiers, hope it might help someone. ∀x(P(x) ∧ Q(x)) ≡ (∀xP(x) ∧ ∀xQ(x)) ∃x(P(x) ∧ Q(x)) → (∃xP(x) ∧ ∃xQ(x)) ∀x(P(x) ∨ Q(x)) ← (∀xP(x) ∨ ∀xQ(... • 171 17 votes Accepted ### Second-order logic as the basis for set theory The thing about the second-order of$\sf ZFC$is that$M$is a model of second-order$\sf ZFC$if and only if$M$is isomorphic to$V_\kappa$for an inaccessible$\kappa$. So right off the bat you ... • 399k 17 votes Accepted ### Are quantifiers redundant by treating free variables as implicitly universally quantified? The problem with replacing$\exists$with$\neg\forall\neg$to not have to worry about the order of quantifiers becomes apparent if you actually try doing so and omitting the quantifiers. For ... • 335k 16 votes ### Are these arguments invalid? A nice tool for analyzing these kinds of categorical syllogisms are Venn Diagrams. Let's do this for the first argument. First, draw a Venn diagram for the 3 sets of things involved in the argument: ... • 102k 16 votes Accepted ### Why do first order languages have at most countably many symbols? You can have as many symbols as you like in your language! For instance, with a possibly uncountable language$L$, the Lowenheim-Skolem theorem becomes: If$\mathcal{M}$is an$L$-structure, then ... • 251k 16 votes ### Set theoretic concepts in first order logic The questions assumes that there is some notion of "set" in first-order logic itself, but there is not. We use sets to study first-order logic, particularly the semantics (models) aspect. But these ... • 82.6k 16 votes ### Why not ban nested quantifiers over the same variable? It could be done, as described in the other answers. But it would not make capture-avoiding substitution easier to define, so there's no real benefit. On the other hand, we would lose the sometimes ... 16 votes Accepted ### How do we compare the set of natural numbers in different models of ZFC We cannot compare the$\omega$s in different models, can we? If we say that one is embeddable into another, an embedding$\omega\rightarrow\omega'$between the two sets of natural numbers in different ... • 251k 16 votes Accepted ### Nonstandard infinite / hyperfinite sum in IST Welcome to Math.SE! You did not indicate how much background you have in Internal Set Theory (IST) - but based on what you wrote, it seem like you have a few misconceptions about it. Let us start by ... • 11.9k 16 votes Accepted ### Confusion about Löb's theorem Say that the formal system is$\sf PA + \lnot Con(PA).$Then the system proves every statement is provable in$\sf PA$, but surely it doesn't prove every statement (unless it is inconsistent, which by ... • 61.2k 15 votes Accepted ### Infinitely many axioms of ZFC vs. finitely many axioms of NBG This is because the framework described by the NBG axioms is strictly richer than that which the ZFC axioms describe. This is not an isolated phenomenon. Let me show you diffrent, perhaps a bit less ... • 36.2k 15 votes ### Applications of intuitionistic logic One fun answer is "programming languages". It turns out a good way to study programming languages is by viewing them as proof systems, and the programming languages you get in this way tend ... • 39.1k 14 votes Accepted ### What is wrong with this naive approach to Hilbert's 10th problem? The problem is that it's possible$f$has no integer roots, but there is no proof of this fact (in whatever theory of arithmetic you are using). You're right that if$f\$ does have a root, then you ...
• 335k

Only top scored, non community-wiki answers of a minimum length are eligible