0

On this page is a very simple theorem (Theorem 1.1) $$\text{If }\;m\in\mathbb{Z}\;\text{ is even, then }\;m^2\text{ is even}$$

How would you prove this theorem using ZFC set theory? What would it look like? How is the theorem represented using sets?

Or does ZFC not apply here?

I am trying to learn how to write proofs and I've read that ZFC is the modern foundation for math now-a-days. But I am having trouble understanding how to use it.

Thanks!

Asaf Karagila
  • 393,674
sphere100
  • 25
  • 2
    Welcome to MSE. Please, type your question. Show some effort if you want other people spend some time helping you. – jjagmath Feb 05 '21 at 00:21

2 Answers2

4

Asking how to prove a theorem about $m^2$ in $\Bbb Z$ using $\sf ZFC$ is similar to asking how to write a JavaScript interpreter from complete scratch, in machine code. It's not that it's not possible, but it's just that this is not what you're supposed to do if you want to write a JavaScript interpreter. For one, it's a lot easier to use an operating system that someone else already wrote, and maybe a different programming language (although you can definitely still insist on writing machine code instructions by hand if you really want to).

When we say that $\sf ZFC$ is a foundation of mathematics, we don't mean that we want to, or even should be able to prove every theorem of mathematics in the language of set theory. For one, much like machine code, the language of set theory is very minimal and is untyped. In particular, the symbol $\Bbb Z$, the concept of "even integer", and the notion of multiplication are not part of this language.

So what do we mean, and how do we do it? Well, we show that in $\sf ZFC$ we can interpret the integers $\Bbb Z$, as some set, and indeed there are many different ways to arrive to such a set. We should prove that any two interpretations of $\Bbb Z$ are isomorphic, and that if we treat $\Bbb Z$ as a ring (i.e. with $0,1,+$ and $\cdot$, and maybe even $\leq$) then this isomorphism is unique. This means that now it doesn't matter which copy of $\Bbb Z$ we used for our proof, we can translate it to any other interpretation.

Finally, we show that all the rules of logic that we are used to naively, or at least "pre-set theory" and are not obviously contradictory can be interpreted in $\sf ZFC$. This allows us to take any proof that we write in the usual language of rings, and turn it into a proof from $\sf ZFC$.

So how do you prove that? Well, you first prove all of those other things. You build an operating system, a compiler for higher-level language, and with that another even higher-level language, and finally, we write an interpreter, and we compile it. And then we have an interpreter. We didn't write the machine code from scratch, we didn't even write the machine code inside the operating system. But we still ended up with an interpreter.

Similarly, you can write a proof that shows pretty much all the things that I wrote, but then, at the very end, your proof will just be a lot of machinery, and the same proof that you know from every other freshman course, or whatever. Because $2$ is a prime number, and prime numbers satisfy $p\mid nm\iff p\mid n$ or $p\mid m$:

$$2\mid m^2\iff 2\mid m\text{ or }2\mid m\iff 2\mid m.$$

(Or some ad-hoc proof of this fact.)

Asaf Karagila
  • 393,674
  • Thank you for your response. It was very helpful. Could you explain your last statement above? I have not seen that notation before with the | (pipes) -- not sure how to read it without parenthesis. Also, is there any beginner material on writing in ZFC? I've seen Metamath, not sure if that's a good resource or not. Regardless, I will continue writing proofs in more standard ways. Thanks again! – sphere100 Feb 05 '21 at 21:24
  • It's the divisibility relation, i.e. $x\mid y$ if and only if there is some $z$ such that $x\cdot z=y$. For example, $3\mid 9$, but $3\nmid 8$. – Asaf Karagila Feb 05 '21 at 21:25
  • Maybe you could help me better understand! I understand how $$2\mid m^2\iff 2\mid m\text{ or }2\mid m$$, but why the additional implication $$\iff 2\mid m$$? – sphere100 Feb 06 '21 at 00:44
  • Because you want to get to $2\mid m$. It's a trivial equivalence. – Asaf Karagila Feb 06 '21 at 00:45
  • Is that because by getting there we show that m is even? – sphere100 Feb 06 '21 at 00:48
  • Yes. I've initially misread your question as asking to prove a slightly more complicated statement (i.e. $m$ is even if and only if $m^2$ is even). – Asaf Karagila Feb 06 '21 at 00:50
1

Building $\Bbb Z$ and establishing basic properties of arithmetic starting with just the axioms of ZFC is a complex task (e.g. one rigorous formal proof that $2+2=4$ is almost 3,000 steps long)!

This process includes introducing notation and terminology for numbers and numeric operations (defined in terms of set operations) and proving useful theorems (e.g. commutativity of addition) using those new symbols. This effectively "hides" the fact that we're "technically" still talking about sets, so ultimately we get to write proofs in a natural, intuitive style like the one you referenced. By unpacking many layers of definitions, we could "trace it all back" to sets and the ZFC axioms, and knowing this reassures us that our arguments are valid as long as ZFC is consistent, but it's rarely useful to actually do the translation--the resulting statements in the language of set theory would be huge, unrecognizable symbolic expressions.

Karl
  • 11,446