MHB Why Is $\{ x: \phi(x) \}$ a Set Given $Y$?

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Proof Theorem
AI Thread Summary
The discussion revolves around the theorem that establishes the existence of the set $\{ x: \phi(x) \}$ given a set $Y$ where all elements satisfying the property $\phi$ are contained. The proof utilizes the Axiom schema of specification, which allows the formation of a set $B$ from elements of $Y$ that satisfy $\phi$. It clarifies that while one cannot form a set of all objects satisfying $\phi$ indiscriminately, one can form such a set from a defined set $Y$. The key point is that since all elements satisfying $\phi$ are already in $Y$, collecting these elements results in the set $\{ x: \phi(x) \}$. This confirms that the set of all $x$ satisfying $\phi$ can indeed be formed under the specified conditions.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Smile)

Theorem:

Let $\phi$ a type. We suppose that the set $Y$ exists, such that: $\forall x (\phi(x) \rightarrow x \in Y)$. Then there is the set $\{ x: \phi(x) \}$.

Proof:

From the Axiom schema of specification

("Let $\phi$ a type. For each set $A$, there is a set $B$, that consists of these elements of $A$, that satisfy the identity $\phi$, so:

$$ \exists B \forall x (x \in B \leftrightarrow x \in A \wedge \phi(x))$$

so: $B=\{ x: x \in A \wedge \phi(x) \}$ is a set."
)

there is the set $Z=\{ x \in Y: \phi(x) \}$

$$x \in Z \leftrightarrow (x \in Y \wedge \phi(x) ) \leftrightarrow \phi(x)$$

Therefore:

$$Z=\{ x: \phi(x) \}$$

and so, $\{x: \phi(x) \}$ is a set.Could you explain me the proof of the theorem? (Worried) (Thinking)
 
Physics news on Phys.org
Intuitively, one is not allowed to form the set of all objects $x$ satisfying $\phi(x)$. One is, however, allowed to pick such objects (i.e., those that satisfy $\phi$) from a previously constructed set $A$, and call the result a set. That is, if you ask the set-robot: "Collect everything satisfying $\phi$", it will answer: "Sorry, can't do. Too much work. The search scope is undefined". But if you say, "Collect everything satisfying $\phi$ from the set continuum to the power continuum", the robot will say, "Here you are".

In your proof, all sets satisfying $\phi$ are already in $Y$, so if you collect all elements of $Y$ satisfying $\phi$ (which is allowed by the axiom schema of specification), you'll get the set of all sets satisfying $\phi$ at all, whether in $Y$ or not.

For more help, please write the specific place in the proof you don't understand and what you think about it.
 
Evgeny.Makarov said:
Intuitively, one is not allowed to form the set of all objects $x$ satisfying $\phi(x)$. One is, however, allowed to pick such objects (i.e., those that satisfy $\phi$) from a previously constructed set $A$, and call the result a set. That is, if you ask the set-robot: "Collect everything satisfying $\phi$", it will answer: "Sorry, can't do. Too much work. The search scope is undefined". But if you say, "Collect everything satisfying $\phi$ from the set continuum to the power continuum", the robot will say, "Here you are".

In your proof, all sets satisfying $\phi$ are already in $Y$, so if you collect all elements of $Y$ satisfying $\phi$ (which is allowed by the axiom schema of specification), you'll get the set of all sets satisfying $\phi$ at all, whether in $Y$ or not.

For more help, please write the specific place in the proof you don't understand and what you think about it.
Axiom schema of specification:
"Let $\phi$ a type. For each set $A$, there is a set $B$, that consists of these elements of $A$, that satisfy the identity $\phi$, so:

$$ \exists B \forall x (x \in B \leftrightarrow x \in A \wedge \phi(x))$$

so: $B=\{ x: x \in A \wedge \phi(x) \}$ is a set."

We know that $\exists Y$, such that $\forall x(\phi(x) \rightarrow x \in Y)$

From the above theorem, $\exists$ a set $B$, that contains these elements of $Y$, that satisfy $\phi$, so:

$\exists B \forall (x \in B \leftrightarrow x \in Y \wedge \phi(x))$

so: $B=\{ x: x \in Y \wedge \phi(x) \}$ is a set.

But, why will we get then the set of all sets satisfying $\phi$ at all, whether in $Y$ or not, although it is:

$$x \in Z \leftrightarrow (x \in Y \wedge \phi(x))$$

? (Thinking)
 
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...

Similar threads

Back
Top