## Mathematicist Genesis

Next
• 3.1k
Would it be fair to say that thus far, we have only discussed the language by which we would reason about any kinds of objects, but (other than for examples) we have not yet formally introduced any objects about which to reason?

IMHO you can start wherever you like, the "existence" of any object that satisfies some property is really only relative to some other object. Like "the naturals exist inside the reals" or "the continuous functions exist inside the differentiable functions". "Existence" is just a question of whether an object exists inside another one.

You can "introduce" an object without it existing. "imagine a signature with these rules, then this follows", this is like the deduction theorem (with a big abuse of notation):

If you have $\{\mathbb{N},+\}\vdash \Gamma$ then you have $\vdash \{\mathbb{N},+\} \implies \Gamma$ .

There is an object with the structure, so it has these properties.
vs
If there was an object with this structure, it would have these properties

In this regard, the reason I've waited to talk about set theory is that the model of set theory contains sub objects which model all the structures we've talked about. If you want to start from "something fundamental", this "contained object" or "the theory of ZFC is a supertheory of the theory of natural numbers", say, is a good intuition for why ZFC is in some sense "fundamental".
• 3.1k

But yes, thinking about it again, what you've said is accurate. I've not written down what sets are, natural numbers are, rational numbers are etc; but I've gone some way of showing a system in which you can talk about them formally.
• 965
That’s what I meant yeah, thanks! And also I’m totally on board with ambivalence about the “existence” of mathematical objects, ala:

If there was an object with this structure, it would have these properties
vs
There is an object with the structure, so it has these properties.

As I understand it, we’re really saying “all objects with this structure have these properties”, but that’s technically true whether or not there “really” are any objects with that structure at all. All bachelors are unmarried, even if there are no bachelors.
• 3.1k
As I understand it, we’re really saying “all objects with this structure have these properties”, but that’s technically true whether or not there “really” are any objects with that structure at all. All bachelors are unmarried, even if there are no bachelors.

I think this is about right. Though it's clearly true that not every first order structure has the empty domain as a model; eg "There exists an x such that x+1 = 2" is not true in the empty domain, but it is true in the naturals with addition.

Something that gives me that Pascal feeling of infinity vertigo is that we can say things like:

"If you interpret the the Peano axioms in the usual way, then..."

Which conjures up a meta language to talk about an implication from a meta-language item to an object language item. It seems the formalism always has to stop at some point, but the reason (and conceptual content) doesn't.
• 7.3k
Since the syntax and semantics are formally distinct, this highlights the possibility of a gap between syntax and semantics of a formal language; and this gap is a site of interesting questions.

Yep.
• 965
"If you interpret the the Peano axioms in the usual way, then..."

Yeah, this is what I really take the truth of mathematical or more generally logical statements to be about. “All bachelors are unmarried” isn’t really a necessary truth by itself, but “If bachelor means ‘unmarried man of marriageable age’ then all bachelors are unmarried” is. I take mathematical truths to be truths about the implications from axioms to theorems. None of the theorems are themselves necessarily true, but it’s necessarily true that they are implied by their axioms.

So it is only necessarily true that some axioms imply the existence of the natural numbers with their usual properties including some natural number x such that x+1=2, but that is a conditional statement that is therefore equivalent to some “all A are B” statement that I don’t care to reconstruct right now, and is thus true even in an empty universe.
• 3.1k
None of the theorems are themselves necessarily true, but it’s necessarily true that they are implied by their axioms.

Only once you've fixed the underlying logic, I think. I'm not too happy with bringing in an exterior sense of modality to the theorems. If we're in a context sufficiently abstract to start playing around with the rules of logic, then necessity and possibility ideas might be perturbed too.

Edit: though, again, I generally agree with what you've said. I might just be being pedantic here.
• 3.1k

Regarding the sense of necessity thing, maybe this helps spell out my suspicions that it doesn't tell us much.

Define that a given statement x is possible with respect to a given axiomatic system z if and only if (the theory of z & x) is consistent.
Define that a given statement x is necessary with respect to a given axiomatic system z if and only if (the theory of z & not(x)) is inconsistent.

If we have a list of axiomatic systems as the set of possible worlds, with the same underlying logic, and we fix a theory like arithmetic, arithmetic will be possible for axiomatic systems that don't make any of its theorems false (IE, possible worlds look like augmented arithmetic with rules consistent with all of its rules, or weakened arithmetic by deleting rules or modifying them to weaker versions), and arithmetic will be necessary for axiomatic systems that make all of the theorems of arithmetic true (IE, the axiomatic system under consideration contains all theorems of arithmetic in its theory, like set theory or Russel's type theory).

If we have a list of possible worlds that contained all satisfiable combinations of well formed formulae of the logic, the only statements true in all possible worlds would be those that we can derive from any world; the tautologies of the underlying logic.

Are the theorems concerning natural numbers necessary in the above sense? Well no, for example the rational numbers and how to manipulate fractions are in the above list of possible worlds; and for the fractions, it's false that every fraction is the successor of some other fraction (under their usual ordering).

(It's false that every element of the structure $\{\mathbb{Q},+,-,\times,\lt \}$ is the successor of some other number, but it is true for its sub-structure $\{\mathbb{N},+,-,\times,\lt \}$, in the arithmetic of fractions there will be a sub-arithmetic of naturals that has the successor function behaving normally, but this weakens the $\forall x$ in successor axiom statements about natural numbers to $\forall x \in \mathbb{N}$, in some sense they're the same statement since they're about the same object, but the universality of the successor property still breaks for the larger object of all fractions.)

If we go back one layer and allow the rules of logic to vary (over the set of well formed formulae); the only necessities would be the shared tautologies of every logic under consideration.

If we can vary the set of logics to include just one logic which has, say $\lnot(P \leftrightarrow \lnot \lnot P)$ as satisfiable, not even all the consequences of propositional logic would be necessary (because there exists a satisfiable theory/possible world which is inconsistent with double negation elimination).
• 965
This reminds me vaguely of a philosophical or logical problem I read about once, and can't remember the resolution to at the moment.

The argument for the problem was that it seems like an inference like "P, if P then Q, therefore Q" depends on a hidden premise, "if (P and if P then Q) then Q", which in turn depends on yet another hidden nested conditional premise, and so on ad infinitum. Whenever you have some premises from which you think you can derive a conclusion, you're implicitly using a hidden premise that says you can derive that conclusion from those premises, but even once you've explicated that hidden premise you still have the same problem and need to add another hidden premise, on and on forever.

This sounds like that problem in that, say, a theorem of arithmetic may be necessitated by ZFC, but ZFC is not necessitated by propositional logic, you can use other axiomatic systems that maybe don't necessitate that theorem; and even if ZFC were necessitated by propositional logic, that may not be necessitated by anything, as there are for example paraconsistent logics. You keep falling back on earlier and earlier sets of rules that say that you're allowed to use the rules you tried to use earlier, but who says you can use those earlier rules?

This also reminds me of Kripkean relative modality, where something can be be necessary inasmuch as it is true in all worlds accessible from a reference world, even if it's not true in absolutely every world.

I don't have much more well-sorted thoughts on the topic now besides those comparisons to other problems.
• 3.1k
This also reminds me of Kripkean relative modality, where something can be be necessary inasmuch as it is true in all worlds accessible from a reference world, even if it's not true in absolutely every world.

I think that's the general picture involved with it, yeah. When you fix a starting point (of assumptions), you fix what is necessary for it (what can't fail to be true given the assumptions), what's consistent/possible with it (what can be true at the same time as the assumptions) and what's necessarily not for it (what can't be true at the same time as the assumptions).

Anyway, onto ZFC.

What's the purpose of ZFC? Well, historically, it arises at the time a foundation for mathematics was a popular research program. What it does is attempt to provide an axiomatic system in which all the usual theorems of mathematics are provable. How it does this is by showing that all these usual mathematical statements are secretly statements about sets; or rather, we can construct sets (in accordance with the axioms of ZFC) which interpret the theory of other structures (like continuous functions, arithmetic, fractions, etc).

How does ZFC achieve this? It forms an axiomatisation of sensible rules for combining, comparing and transforming collections of objects. One important property of all the rules is a notion of closure. Closure is a general mathematical property that says that "every way we can act on something in ways described by our stipulated rules produces something which obeys those rules". In the abstract, this maybe doesn't make much sense, but here are some examples:

Reveal
Of course, studying it has its own merits, but for our purposes all we need are the tools to build sets.

When we add two numbers in {0,1,2,3,...}, we're guaranteed to get another number. This says that {0,1,2,3,...} is closed under addition.

When we multiply two numbers in {0,1,2,3,...}, we're guaranteed to get another number. This says {0,1,2,3,...} is closed under multiplication.

But when we divide a number by another in {0,1,2,3,...}, we might get a fraction, like 0.5, which is not a number in {0,1,2,3,...}, and so {0,1,2,3,...} is not closed under division.

The axioms of ZFC give us various things we can do to sets to produce other sets. That is to say, if we follow the axioms of ZFC, we will stay within the structure; we'll still be talking about sets. Axiomatising something generally requires that the structure is closed under its stipulated rules and if the structure is not closed, that's seen as a defect/opportunity to introduce further axioms and/or objects.

ZFC stipulates rules that we can use to make and transform sets and get other sets out in a way that is sufficiently flexible to interpret usual mathematical objects as objects of ZFC - as sets.

Reveal
Some of you familiar with types might notice a correspondence; the closure of an object under some rules induces an object type of belonging to the object.

Reveal
We've already seen two incidences of closure before, with regard to the construction of well formed formulae (you can't make a non-well formed formula from a well formed formula using the production rules) and with regard to the theory of an axiomatic system; a theory of an axiomatic system is a closure of that axiomatic system under syntactic derivation; the collection of all consequences of a bunch of axioms is closed under inference.
• 3.1k
The first step is to introduce the relevant symbols for ZFC. It inherits the language and inference rules for first order logic, but it needs to be augmented with a relation symbol $\in$, which denotes a set being a member of another set. EG

$1 \in \{1,2\}$

says "1 is a member of the set containing 1 and 2". The bracket notation means "the set consisting of the elements inside the brackets { }"

It also needs a symbol for the empty set, the set containing no elements. This is $\emptyset$. With the previous membership relation, the emptyset can be characterised as:

$\emptyset = \forall x \{x \notin \emptyset \}$

Which says the empty set is the name for the set with no elements - for all sets x, x is not in the empty set. $\notin$ is the negation of $\in$. EG $3 \notin \{1,2\}$ since 3 is not an element of the set {1,2}.

This makes the signature of ZFC $\{X, \in, \emptyset \}$. The existence of the empty set can be entailed by other axioms, so it doesn't really need to be thrown into the signature as a constant, but I'll do it anyway. We could also include a symbol for equality of sets $=$, but since I've left that out of the previous discussions I'll leave it out here too.* Furthermore, we're going to postpone discussion of precisely what "X" is, but suffice now to say that it's a collection of (names of) all the sets.

*
It certainly makes things a bit fuzzier to equivocate between the ideas of equality in the underlying logic and equality in the first order theory using the logic, but considering that the only context this distinction is likely to crop up in is in distinguishing equal objects of the logic from equal objects of the theory, I'm going to just assume that the context will be sufficient to disambiguate the use of the symbol.

The first rule we'll need to talk about sets is a criterion for when they're equal - how can we tell whether two sets are actually the same set? This principle is encoded in the axiom of extensionality, which states "two sets are equal when and only when they share all and only the same elements", eg {1,2} = {1,2}, or {2-1,2}={1,2}, since they share all and only the same elements. {1,2} isn't equal to {1,2,3} even though all the elements of {1,2} are in {1,2,3} because {1,2,3} has the additional element 3 (which is not in {1,2}). Prosaically, a set is the same as another if the other contains no more, no less, and no different elements from the first.

Formally, the axiom can be written as:

$(A = B) \leftrightarrow (\forall x (x \in A \leftrightarrow x \in B))$

"For two given sets A and B, and for all sets x, a set A is equal to a set B when (if an x is in A when and only when it is also B)". "All and only the same elements" is what is formalised here.
The first bit says $A = B$ is logically equivalent to the rest... the $\forall x$ formalises the "All sets", the $(x \in A \leftrightarrow x \in B)$ formalises A having x as a member if B has it and vice versa. This posits what it means for two sets to be equal.
• 965
I think that last bit has some small errors in the explanation of ∀A∀B(∀x(x∈A↔x∈B)↔A=B), and it might be clearer to switch the places of the biimplicants in that anyway, so ∀A∀B(A=B↔∀x(x∈A↔x∈B)). "For all sets A and B, set A is equal to set B when and only when (for all x, x is in A when and only when it is also B)". It's not ∀A∀B(∀x(x∈A↔x∈B)) that is equivalent to A=B, but rather for all A and all B ("∀A∀B"), just ∀x(x∈A↔x∈B) is equivalent to A=B.
• 3.1k

Better now?
• 965
Looks good enough for me. :)
• 3.1k
The axiom of extensionality defined what it means for two sets to be equal. They were equal if they contained the same things.

An analogy - shopping lists. Two shopping lists are the same if they have the same items in them.

The next axiom is the axiom of pairing, which states that if you have two sets, you can make a another set which contains only those two sets as elements.

Shopping list wise - this means that if you have two shopping lists for different shops, you could make a shopping list for both shops by combining them.

Then there's the axiom of (restricted) comprehension - if you have a set, you can take a subset of it whose elements are the only elements which satisfy some property. If A = {1,2,3,4}, we can construct the set.

{x in A, x is even}

and get {2,4}. All the axiom of comprehension does is ensure the existence of a subset of a set which satisfies a specified property. It's called the axiom of restricted comprehension because it requires that we begin with a set (like A) then apply a property to it to get a subset (like {2,4}). If we could 'conjure up' a set into the language of set theory solely by specifying a property:

{x , x satisfies P}

Then we can make P whatever we like. Notoriously, this gives

$\{x, x \notin x\}$

The Russel set. This must exist if we stipulated "we can conjure up a set through a property", and P is a property of set theory since it's a well formed formula of the language of set theory. If something belongs to the set, it doesn't belong to it, if something does not belong to the set, then it belongs to it. The reason why mathematicians rejected this axiom was because it entails a contradiction, and through the principle of explosion (discussed earlier), makes the theory prove everything it can state, even the falsehoods. Restricted comprehension saves the theory from the paradox by making sure you start with a set to apply properties to, rather than conjuring up a set from the logic using a property. If you change the underlying logic to one that is more resistant to contradictions, you might still want the unrestricted version (like in a paraconsistent logic).

Shopping list wise - this says that we can select sub lists by specifying elements. "What vegetables will we buy?" is answered by the sub list of vegetables.

The next is the axiom of union. This says that for every collection of sets, there's a set which consists of the elements of all of them taken together.

Shopping list wise, this says that you can make a larger shopping list out of any collection of shopping lists. A shopping list of meat items taken with a shopping list of vegetables becomes another shopping list which consists of the meat items and the vegetables.

The next is the axiom of powerset. This says that for every set, there exists a set which consists of all the subsets of that set.

Shopping list wise, if we have the list:

Carrots
Potatoes
Eggs

This says we must be able to construct the lists

Carrots, Potatoes, Eggs, {Carrots, Potatoes}, {Carrots, Eggs}, {Potatoes, Eggs},
{Carrots, Potatoes, Eggs}, and the empty list (what you would buy if you bought everything on a blank page).

Then make a list of all those shopping lists and the blank bit of paper. That whole new list is the powerset of the original shopping list.

The powerset of a set is always larger than the original set. If you had a set of infinite size (to be introduced later), this makes there be more than one size of infinity. If we considered an object which would be a model of set theory, because of the power set axiom, intuitively it would have to have a size larger than any set, in particular larger than the natural numbers! Unfortunately this does not hold, there are countable models of ZFC (called Skolem's Paradox). Such a model does not satisfy the intuition, but entails no contradictions; a model in some sense sets out a meaning of terms, a countable model of ZFC doesn't have the statements in it mean precisely the same thing.
Next
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal