Proving x=y & y in z Implies x in z in ZFC

  • Thread starter Thread starter Fredrik
  • Start date Start date
  • Tags Tags
    Zfc
Click For Summary
The discussion centers on whether the implication x=y and y in z implies x in z follows from the axioms of Zermelo-Fraenkel set theory with choice (ZFC). Participants explore the relationship between the meaning of equality and formal proofs, questioning if proofs should rely on the interpretation of symbols. The axiom of extensionality is highlighted as crucial, with some arguing that equality should be treated as a non-logical symbol in formal proofs. The conversation also touches on the complexities of defining equality within first-order logic and the implications for formalizing mathematics. Ultimately, the consensus leans towards recognizing the necessity of treating equality as a fundamental relation in formal systems.
  • #31
That's ok Fredrik - I quite enjoyed thinking about it. I haven't seen this system before, and it's interesting seeing how one can use it to prove things one is used to taking for granted.
 
Physics news on Phys.org
  • #32
I think I got it now, after studying parts of the next few pages of the book. It gets easier if we consider a couple of simpler problems first. First we prove

\{p,q\}\vdash p\land q

This is a special case of one of the theorems Kunen proves in the book. It's kind of funny that I couldn't figure out how to prove that p and q proves "p and q" without using the book. :smile: The proof is based on the observation that p\rightarrow(q\rightarrow p\land q) is a tautology, which I see that you're already using in your pdf.

\begin{align*}1.\quad & p\hspace{8 cm} & \in\{p,q\}\\ 2.\quad & q & \in\{p,q\}\\ 3.\quad & p\rightarrow(q\rightarrow p\land q) & \text{tautology}\\ 4.\quad & q\rightarrow p\land q &\text{MP 1,3}\\5.\quad & p\land q & \text{MP 2,4}\end{align*}

Hm, the "align" environment behaves strangely here, but it looks good enough. Now consider the slightly more difficult problem

\{\forall x p(x),\forall x q(x)\}\vdash\forall x(p(x)\land q(x))

\begin{align*}1.\quad &amp; \forall x p(x) &amp; \in\{\forall x p(x),\forall x q(x)\}\\ 2.\quad &amp; \forall x q(x) &amp; \in\{\forall x p(x),\forall x q(x)\}\\ 3.\quad &amp; \forall x( p(x)\rightarrow(q(x)\rightarrow p(x)\land q(x))) &amp; \text{tautology}\\ 4.\quad &amp; \forall x( p(x)\rightarrow(q(x)\rightarrow p(x)\land q(x))) \rightarrow (\forall x p(x)\rightarrow\forall x(q(x)\rightarrow p(x)\land q(x)) &amp;\text{axiom 3}\\ 5.\quad &amp; \forall x p(x)\rightarrow\forall x(q(x)\rightarrow p(x)\land q(x)) &amp; \text{MP 3,4}\\ 6.\quad &amp;\forall x(q(x)\rightarrow p(x)\land q(x)) &amp; \text{MP 1,5}\\ 7.\quad &amp; \forall x q(x)\rightarrow \forall x(p(x)\land q(x)) &amp; \text{axiom 3}\\ 8.\quad &amp; \forall x(p(x)\land q(x)) &amp;\text{MP 2,7}<br /> \end{align*}

The claim we want to prove is

\emptyset\vdash\forall x(\forall y(x\in y\leftrightarrow x\in y)\ \land\ \forall y(y\in x\leftrightarrow y\in x))

Let's define p(x) and q(x) to be the \forall y(\text{blah-blah}) formulas above, so that what we want to prove takes the form

\emptyset\vdash\forall x(p(x)\land q(x))

With this notation, the proof is exactly identical to the proof of the second theorem above. Only the motivation for the first two lines will be different. This time, the text motivating the first two lines should say "tautology".
 
Last edited:
  • #33
Fredrik said:
It's kind of funny that I couldn't figure out how to prove that p and q proves "p and q" without using the book. :smile:
It's not too different than proving things like (-1)x = -x from the ring axioms. The basic calculus was presented with very reduced functionality, and so to use it, it takes some clever arguments to construct the simple things we take for granted.
 
  • #34
Hurkyl said:
It's not too different than proving things like (-1)x = -x from the ring axioms. The basic calculus was presented with very reduced functionality, and so to use it, it takes some clever arguments to construct the simple things we take for granted.
That's certainly true. I remember struggling with 0x=0 for vector spaces, and 1>0 for ordered fields. (The latter one quite recently actually :smile:).
 
Last edited:

Similar threads

  • · Replies 40 ·
2
Replies
40
Views
4K
  • · Replies 2 ·
Replies
2
Views
2K
Replies
14
Views
4K
  • · Replies 4 ·
Replies
4
Views
528
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 15 ·
Replies
15
Views
2K
Replies
4
Views
2K
Replies
8
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K