Skip to main content
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 ...
Z. A. K.'s user avatar
  • 11.7k
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 ...
David Gao's user avatar
  • 9,370
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 ...
Noah Schweber's user avatar
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 ...
Z. A. K.'s user avatar
  • 11.7k
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 ...
spaceisdarkgreen's user avatar
14 votes

Is proof of the law of identity a case of circular reasoning?

I don't understand where you think the circularity is coming from. We have an intuition about equality, namely "everything is equal to itself". We'd like to formalize this intuition as a ...
Alex Kruckman's user avatar
14 votes
Accepted

Is "first-orderizability" a requirement for "legitimate" mathematical reasoning?

Yes, when someone says that ZFC is a suitable foundation for mathematics, that means that all standard mathematical notions can be expressed in the language of ZFC using first-order logic and all ...
Mitchell Spector's user avatar
13 votes
Accepted

Finding a property that is true for every left ideal but not for right ideals

Here is an example. Fix a prime $p>0$ and let $\mathbb{F}_p$ denote the field with $p$ elements, and consider the ring $R=\begin{bmatrix} \mathbb{Z} &\mathbb{F}_p\times\mathbb{F}_p \\ 0 & \...
Atticus Stonestrom's user avatar
13 votes
Accepted

Confusion on using "unless" more than once in proposition

I would just rewrite the highlighted sentence like this: If the correctness of a computer program has not been established by some means, then no amount of testing can show that it produces the ...
Lee Mosher's user avatar
  • 123k
10 votes

Understanding ZFC

You asked: If one is to do mathematics rigorously, they would like every concept they mention, such as a function or relation, to have a precise definition. How can we do that with ZFC if ZFC does ...
Mikhail Katz's user avatar
  • 44.3k
10 votes
Accepted

Does independence-friendly logic have a completeness theorem?

In a precise sense the answer is no. In terms of expressive power, IF-logic is equivalent to existential second-order logic ESO. Now while ESO is reasonably tame in several ways (e.g. compactness and ...
Noah Schweber's user avatar
10 votes

Statements which feel like they shouldn't be first-order expressible, but are

A very important example of this is the incredible expressive power of first-order arithmetic. For instance, in the structure $(\mathbb{N},+,\cdot)$ it is possible to express the fundamental theorem ...
Eric Wofsey's user avatar
9 votes
Accepted

Is "non-rigid" first-order axiomatisable?

Let $L' = L\cup \{\sigma\}$, where $\sigma$ is a unary function symbol not in $L$. Let $T'$ be $T$ together with axioms asserting that $\sigma$ is a non-trivial-automorphism (non-triviality is $\...
Alex Kruckman's user avatar
9 votes
Accepted

Definition of transitivity of relations

The two are not equivalent, and your teacher's (EDIT: per the OP's comment below, they miscopied the definition) proposed definition is wrong. In particular, the property your teacher describes is ...
Noah Schweber's user avatar
9 votes

Nonstandard infinite / hyperfinite sum in IST

You asked several questions that should really be separate posts, but let me start by answering one. You asked: "If anyone could provide a detailed proof that a sum indexed by an unlimited ...
Mikhail Katz's user avatar
  • 44.3k
9 votes
Accepted

What exactly is the unique union of a family of sets?

The uniqueness is in the formula used to define the "unique union": $\{x \mid ∃!A(A∈F \land x∈A) \}$. This means that if an element $a$ belongs to e.g. two sets $A_1$ and $A_2$ of the ...
Mauro ALLEGRANZA's user avatar
8 votes

How do we compare the set of natural numbers in different models of ZFC

Let $(M,\varepsilon)$ and $(M',\varepsilon')$ be models of ZFC. Remember that $M$ and $M'$ are sets (in our ambient set-theoretic universe), and $\varepsilon$ and $\varepsilon'$ are binary relations ...
Alex Kruckman's user avatar
8 votes

Confusion about Löb's theorem

If you prove the Riemann hypothesis, then before believing that the Riemann hypothesis is true, I'd ask you what assumptions (axioms) you used in the proof. If you used any false assumptions, I won't ...
Andreas Blass's user avatar
8 votes

Is $\forall x\exists x(x < x)$ a sentence?

Yes, it is. The $\forall x$ isn’t quantifying any free variables, since there are no free variables in $\exists x \ x<x$, and the $\forall x$ is therefore called a ‘null quantifier’. However, using ...
Bram28's user avatar
  • 101k
8 votes

Prenex Normal Form of a Simple Proposition Reads Strangely.

It is equivalent, and your confusion is called the drinker's paradox (where "$x$ drinks" means "$|a - b| < x$"). If $a = b$, then you can pick any $\epsilon > 0$ and the ...
Naïm Favier's user avatar
  • 1,472
8 votes

Confusion on using "unless" more than once in proposition

I agree with Lee Mosher's characterization of the sentence. I'll offer up this suggested rewrite: No amount of testing can show that a computer program produces the desired output for all input ...
Matthew Leingang's user avatar
8 votes

Confusion on using "unless" more than once in proposition

You shouldn't be rephrasing "unless" using "implies". Instead, simply replace it with "or", and it works: EITHER the correctness of a computer program is established OR ...
user21820's user avatar
  • 59.1k
7 votes

Is proof of the law of identity a case of circular reasoning?

There is a difference between $a=a$ and $\forall x[x=x]$. The second one has a quantifier. Of course passing from one to the other is completely trivial, given the introduction rule for the universal ...
Captain Lama's user avatar
  • 26.3k
7 votes
Accepted

Why does first-order logic lack of a description like the Stone duality?

This got longer than I thought; skip to the end if you just want a couple possibly-useful references! There is, unsurprisingly, extensive work on algebraic and topological aspects/interpretations of ...
Noah Schweber's user avatar
7 votes
Accepted

Is axiom of replacement nicely stateable in the language of ETCS?

You'll likely be interested in a discussion about replacement that happened in the category theory mailing list a few years ago. You can find it here. Just grep for "replacement" and you'll ...
Chris Grossack's user avatar
7 votes

Do we really need the axiom of regularity?

We don't really need the Axiom of Regularity in ZFC. Having it is a matter of convenience. We've known since the 1930s that if the variant of Zermelo-Fraenkel set theory that lacks the axiom of ...
Z. A. K.'s user avatar
  • 11.7k
7 votes

Statements which feel like they shouldn't be first-order expressible, but are

Many important classes of finite groups can be described by some family of sentences in the first-order language of group theory. See these slides of John Wilson. Finite soluble groups of derived ...
J.-E. Pin's user avatar
  • 40.7k
7 votes

Prenex Normal Form of a Simple Proposition Reads Strangely.

It's equivalent to the original statement. The reason it reads strangely (which is somewhat subjective, but I agree that it does) may be that it's not immediately apparent that $\varepsilon$ can (...
mjqxxxx's user avatar
  • 41.9k
7 votes
Accepted

Can we build multiple models of PA within one the same model of ZFC?

Yes. Being (hopefully helpfully!) very pedantic, the compactness theorem - and its consequence that $\mathsf{PA}$ has nonstandard models - is provable in $\mathsf{ZFC}$, so any model $M$ of $\mathsf{...
Noah Schweber's user avatar
7 votes
Accepted

Theory $\mathcal{T}$ with predicate $P$ that is satisfied by countably many elements in every model of $\mathcal{T}$?

Assuming you meant countable as “countably infinite”, then no, with the same proof as the proof that the entire model cannot be restricted to being countable: Add to the language uncountably many ...
David Gao's user avatar
  • 9,370

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