3

I am learning set theory through Charles C.Pinter's textbook. In the book, there are no nice explanation for definition or properties of 'such that'. This is my problem. I tried to solve the problem:

If G, H and J are graphs, $$(H \cup J) \circ G = (H \circ G) \cup (J \circ G)$$

And this is what I tried based on the definition of the book $$\begin{align}&(x,y) \in (H \cup J) \circ G \\ &\Leftrightarrow \exists z \text{ such that } (x,z) \in G \wedge (z,y) \in H \cup J \\ &\Leftrightarrow \exists z \text{ such that } (x,z) \in G \wedge ((z,y) \in H \vee (z,y) \in J) \\ &\Leftrightarrow \exists z \text{ such that }[((x,z) \in G \wedge (z,y) \in H) \vee ((x,z) \in G \wedge (z,y) \in J)] \\ &\Leftrightarrow (??) [\exists z \text{ such that }((x,z) \in G \wedge (z,y) \in H)] \vee [\exists z \text{ such that} ((x,z) \in G \wedge (z,y) \in J)] \\ &\Leftrightarrow (x,y) \in H \circ G \vee (x,y) \in J \circ G \\ &\Leftrightarrow (x,y) \in (H \circ G) \cup (J \circ G) \end{align}$$

However, I think the (??) part is not logically proven. If the statement was made of $\wedge$ instead of $\vee$, then intuitively such that is not distributive! $$(\exists z \text{ such that }[((x,z) \in G \wedge (z,y) \in H) \vee ((x,z) \in G \wedge (z,y) \in J)]$$ this is not distributive for 'such that', intuitively) How should I solve this problem and interpret the answer?

Asaf Karagila
  • 393,674
Kyle
  • 79

2 Answers2

4

The 'such that' is not a thing to be distributed; it is a punctuation mark separating the quantifier variable from the predicate.   You do not distribute over it any more than you distribute over parenthesis.

What you are distributing is the quantifier.

Existance distributes over disjunction like so: $\exists x~[P_x\vee Q_x]\iff \exists x~P_x~\vee~\exists x~Q_x$.   If something satisfies P or Q, then something satisfies P or something satisfies Q, and vice versa.

So, with that correction, you proof is:

$$\begin{align}&(x,y) \in (H \cup J) \circ G \\[1ex] \iff & \exists z~\big[ (x,z) \in G \,\wedge\, (z,y) \in H \cup J\big] \\[1ex] \iff & \exists z~\Big[ (x,z) \in G \,\wedge\, \big((z,y) \in H \,\vee\, (z,y) \in J\big)\Big] \\[1ex] \iff & \exists z~\Big[ \big((x,z) \in G \,\wedge\, (z,y) \in H\big) ~\vee~ \big((x,z) \in G \,\wedge\, (z,y) \in J\big)\Big] \\[1ex] \iff & \tag{!} \exists z~\big[ (x,z) \in G \,\wedge\, (z,y) \in H\big] ~\color{purple}\vee~ \exists z~\big[(x,z) \in G \wedge (z,y) \in J\big] \\[1ex] \iff & (x,y) \in H \circ G ~\vee~ (x,y) \in J \circ G \\[1ex] \iff & (x,y) \in (H \circ G) \cup (J \circ G) \end{align}$$

Graham Kemp
  • 129,094
0

Let's prove the rule $\exists x [P(x) \vee Q(x)] \iff [\exists x P(x)] \vee[\exists x Q(x)]$

Assume $\exists x [P(x) \vee Q(x)]$. Supposed $x_0$ is such that $P(x_0) \vee Q(x_0)$ is true. If $P(x_0)$, then $\exists x P(x)$, so $[\exists x P(x)] \vee[\exists x Q(x)]$ because we can tack anything on with the "$\vee$". If $P(x_0)$ is not true, then $Q(x_0)$ must be true, otherwise our assumption is false. Then $\exists x Q(x)$, so $[\exists x P(x)] \vee[\exists x Q(x)]$. This proves: $$\exists x [P(x) \vee Q(x)] \implies [\exists x P(x)] \vee[\exists x Q(x)]$$

Let's now do the other direction. Assume $[\exists x P(x)] \vee[\exists x Q(x)]$. At least one of them has to be true, so without loss of generality, let $\exists x P(x)$ be true (we could just as easily have let $\exists x Q(x)$ be true). So then $P(x_0)$ is true for some $x_0$; that means $P(x_0) \vee Q(x_0)$ is true for some $x_0$. This proves: $$[\exists x P(x)] \vee[\exists x Q(x)] \implies\exists x [P(x) \vee Q(x)]$$

Larry B.
  • 3,384