Existence and uniqueness proofs

A

Aion

Junior Member
Joined
May 8, 2018
Messages
193
Hey, can someone help me with question (b) of this problem?

Recall that symmetric difference is associative; in other words, for all sets [MATH]A, B[/MATH] and [MATH]C, A\Delta(B\Delta C)=(A\Delta B)\Delta C[/MATH]. And clearly symmetric difference is commutative; in other words, for all sets [MATH] A[/MATH] and [MATH] B, A\Delta B = B\Delta A[/MATH].

(a) Prove that there is a unique identity element for the symmetric difference. In other words, there is a unique set [MATH]X[/MATH] such that for every set [MATH]A, A\Delta X=A[/MATH].

Definition: Let [MATH]P(X)[/MATH] be the statement [MATH]\forall A( A= A\Delta X)[/MATH]
Goal: [MATH]\exists ! X \forall A( A= A\Delta X)[/MATH]
Exsistence Proof:

  1. Let [MATH]X = \varnothing [/MATH]
  2. Let [MATH]A[/MATH] be an arbitrary set.
  3. Suppose [MATH]x[/MATH] is an arbitrary element of [MATH]A\Delta X[/MATH] [Hypothesis]
  4. [MATH]x\epsilon A\Delta \varnothing [/MATH] (1), (3)
  5. [MATH]x \epsilon A \setminus \varnothing \vee x \epsilon \varnothing \setminus A[/MATH] [Definition of [MATH]\Delta[/MATH]]
  6. [MATH](x\epsilon A \wedge x \notin \varnothing) \vee (x \in \varnothing \wedge x \notin A)[/MATH] (5) [Definition of [MATH]\setminus[/MATH]]
  7. [MATH]x\epsilon A[/MATH] [Since [MATH]x \in \varnothing \wedge x \notin A[/MATH] is a contradiction. And [MATH] x \notin \varnothing[/MATH] is a tautology.]
  8. [MATH]x \epsilon A\Delta X \to x \epsilon A[/MATH] [Gm. Hyp. (3)-(7)]
  9. Suppose [MATH]x[/MATH] is an arbitrary element of [MATH]A[/MATH] [Hypothesis]
  10. [MATH]x \epsilon A [/MATH] (9)
  11. [MATH]x \epsilon A \wedge x \notin \varnothing [/MATH] [Conjunction introduction]
  12. [MATH](x \epsilon A \wedge x \notin \varnothing ) \vee (x \epsilon \varnothing \wedge x \notin A) [/MATH] [Disjunction introduction]
  13. [MATH]x \epsilon A \Delta \varnothing[/MATH] (12), [Definition of [MATH]\Delta[/MATH]]
  14. [MATH]x\epsilon A \to x\epsilon A\Delta \varnothing[/MATH] [Gm. Hyp. (9)-(13)]
  15. [MATH](x \epsilon A\Delta \varnothing \to x \epsilon A) \wedge (x\epsilon A \to x\epsilon A\Delta \varnothing)[/MATH] (8), (13) [Conjunction introduction]
  16. [MATH]x \epsilon A\Delta \varnothing \leftrightarrow x \epsilon A\Delta \varnothing[/MATH] (14) [Definition of [MATH]\leftrightarrow[/MATH]]
  17. [MATH]\forall x (x \epsilon A \leftrightarrow x \epsilon A\Delta \varnothing)[/MATH] (2) [Since x was arbitrary]
  18. [MATH]A = A\Delta \varnothing [/MATH] (17) [Definition of [MATH]=[/MATH]]
  19. [MATH]\forall A( A= A\Delta \varnothing)[/MATH] (2), (18) [Since A was arbitrary]
  20. [MATH]\exists X\forall A( A= A\Delta X)[/MATH] (1), (19)
  21. [MATH]\exists X P(X)[/MATH] (20) [Definition of [MATH]P(X)[/MATH]]
Uniqueness proof:
  1. Let Z and Y be arbitrary sets.
  2. [MATH]P(Z) \wedge P(Y) [/MATH] [Hypothesis]
  3. [MATH]\forall A( A= A\Delta Z) \wedge \forall A( A= A\Delta Y)[/MATH] (2) [Definition of [MATH]P(Z)[/MATH] and [MATH]P(Y)[/MATH]]
  4. [MATH] Y = Y\Delta Z[/MATH] (3) [Universal instantiation]
  5. [MATH] Z = Z\Delta Y[/MATH] (3) [Universal instantiation]
  6. [MATH] Y\Delta Z = Z\Delta Y [/MATH] [Commutativity]
  7. [MATH] Y = Z [/MATH] (4), (5), (6)
  8. [MATH]P(Y) \wedge P(Z) \to Y = Z[/MATH] [Gm. Hyp. (2)-(7)]
  9. [MATH]\forall Y \forall Z (P(Y)\wedge P(Z) \to Y = Z)[/MATH] [Since Y and Z was arbitrary]
Thus we have proved [MATH]\exists ! X \forall A( A= A\Delta X)[/MATH]
(b) Prove that every set has a unique inverse for the operation of symmetric difference. In other words, for every set A there is a unique set B such that [MATH]A\Delta B =X[/MATH], where X is the identity element from part(a),

Given:
[MATH]\exists X\forall A( A= A\Delta X)[/MATH], i.e. [MATH]\forall A( A= A\Delta \varnothing)[/MATH]
Goal: [MATH]\forall A\exists !B(A\Delta B = X)[/MATH], i.e. [MATH]\forall A\exists !B(A\Delta B = \varnothing)[/MATH]
 
Last edited:
Aion said:
Hey, can someone help me with question (b) of this problem?
(b) Prove that every set has a unique inverse for the operation of symmetric difference. In other words, for every set A there is a unique set B such that [MATH]A\Delta B =X[/MATH], where X is the identity element from part(a),
Given: [MATH]\exists X\forall A( A= A\Delta X)[/MATH], i.e. [MATH]\forall A( A= A\Delta \varnothing)[/MATH]Goal: [MATH]\forall A\exists !B(A\Delta B = X)[/MATH], i.e. [MATH]\forall A\exists !B(A\Delta B = \varnothing)[/MATH]
Click to expand...
Is it clear to you that each set is its own inverse?
What if \(\displaystyle A\Delta B=\emptyset~\&~A\ne B~?\)
What does it mean to say \(\displaystyle A\ne B~?\)
 
pka said:
Is it clear to you that each set is its own inverse?
Click to expand...
Do you mean that \(\displaystyle \forall A (A\Delta A =\emptyset)\)?
pka said:
What if \(\displaystyle A\Delta B=\emptyset~\&~A\ne B~?\)
Click to expand...
I suppose this is the reason why I'm stuck. I don't know.

pka said:
What does it mean to say \(\displaystyle A\ne B~?\)
Click to expand...

[MATH] A \nsubseteq B \lor B \nsubseteq A [/MATH]
Well I've tried to simply it... if I'm correct it also means

[MATH]\exists x(x \epsilon (A \cup B) \setminus (A\cap B))[/MATH] which is the same as [MATH]\exists x(x \epsilon A \Delta B)[/MATH]
pka said:
What if \(\displaystyle A\Delta B=\emptyset~\&~A\ne B~?\)
Click to expand...

If my above reasoning is correct. We can reformulate the givens into this:

[MATH] \forall x ( x \notin A \Delta B) \wedge \exists x (x \in A \Delta B)[/MATH] which yeilds a contradiction.
 
Last edited:
Suppose that \(\displaystyle A\Delta B=\emptyset\) where \(\displaystyle A\ne B\).
Now we have \(\displaystyle \exists u\in A\setminus B\vee\exists v\in B\setminus A\), Please explain why.
Does that contradict \(\displaystyle A\Delta B=\emptyset~?\)

 
Thanks, I think I've figured it out now.

Goal: [MATH]\forall A\exists !B(A\Delta B = X)[/MATH], i.e. [MATH]\forall A\exists !B(A\Delta B = \varnothing)[/MATH]
1. Let A be an arbitrary set.

Existence part

2. Let [MATH]B = A[/MATH]3. [MATH]A\Delta B = A \Delta A = \varnothing[/MATH]4. [MATH]\exists B(A\Delta B = \varnothing)[/MATH]
Uniqueness part

5. Let Z and H be arbitrary sets.
6. [MATH]A\Delta Z = \varnothing \wedge A \Delta H = \varnothing[/MATH]. [Hyp.]
7. [MATH]H \neq Z[/MATH] [Indirect. Hyp.]
8. [MATH]\exists u ( u \in Z \setminus H) \vee \exists v ( v \in H \setminus Z)[/MATH]
9. Case (1): [MATH]\exists u ( u \in Z \setminus H)[/MATH]10. [MATH]u_0 \in Z \setminus H[/MATH]11. [MATH]u_0 \in Z[/MATH]12. [MATH]u_0 \in Z \wedge u_0 \notin A[/MATH]13. [MATH](u_0 \in Z \setminus A) \vee (u_0 \in A \setminus Z)[/MATH]14. [MATH]u_0 \in A \Delta Z[/MATH]16. [MATH]\perp[/MATH]
17. Case (2) [MATH]\exists v ( v \in H \setminus Z)[/MATH]18. [MATH]v_0 \in H \wedge v_0 \notin Z[/MATH]19. [MATH]v_0\in H[/MATH]20. [MATH]v_0 \in H \wedge v_0 \notin A[/MATH]21. [MATH](v_0 \in H \setminus A) \vee (v_0 \in A \setminus H)[/MATH]22. [MATH]v_0 \in A \Delta H[/MATH]23.[MATH]\perp[/MATH]
24. [MATH]H = Z [/MATH] [Gm. Ind. Hyp. (7)-(24)]
 
Last edited:
Aion said:
Thanks, I think I've figured it out now.

Goal: [MATH]\forall A\exists !B(A\Delta B = X)[/MATH], i.e. [MATH]\forall A\exists !B(A\Delta B = \varnothing)[/MATH]
1. Let A be an arbitrary set.

Existence part

2. Let [MATH]B = A[/MATH]3. [MATH]A\Delta B = A \Delta A = \varnothing[/MATH]4. [MATH]\exists B(A\Delta B = \varnothing)[/MATH]
Uniqueness part

5. Let Z and H be arbitrary sets.
6. [MATH]A\Delta Z = \varnothing \wedge A \Delta H = \varnothing[/MATH]. Hyp.
7. [MATH]H \neq Z[/MATH] (Indirect. Hyp.)
8. [MATH]\exists u ( u \in Z \setminus H) \vee \exists v ( v \in H \setminus Z)[/MATH]
9. Case (1): [MATH]\exists u ( u \in Z \setminus H)[/MATH]10. [MATH]u_0 \in Z \setminus H[/MATH]11. [MATH]u_0 \in Z[/MATH]12. [MATH]u_0 \in Z \wedge u_0 \notin A[/MATH]13. [MATH](u_0 \in Z \setminus A) \vee (u_0 \in A \setminus Z)[/MATH]14. [MATH]u_0 \in A \Delta Z[/MATH]16. [MATH]\perp[/MATH]
18. Case (2) [MATH]\exists v ( v \in H \setminus Z)[/MATH]19. [MATH]v_0 \in H \wedge v_0 \notin Z[/MATH]20. [MATH]v_0\in H[/MATH]21. [MATH]v_0 \in H \wedge v_0 \notin A[/MATH]22. [MATH](v_0 \in H \setminus A) \vee (v_0 \in A \setminus H)[/MATH]23. [MATH]v_0 \in A \Delta H[/MATH]24.[MATH]\perp[/MATH]
29. [MATH]H = Z [/MATH] [Gm. Ind. Hyp. (7)-(24)]
Click to expand...
You have made the proof of uniqueness far too complicated
If \(\displaystyle A\) is a set then \(\displaystyle A\Delta A=\emptyset\) so existence is proven, every set is its own inverse.
So suppose that \(\displaystyle A\Delta B=\emptyset~\&~A\ne B\).
That means that \(\displaystyle \exists s\in A\setminus B\vee\exists t\in B\setminus A\).
But in either of those cases \(\displaystyle A\Delta B\ne\emptyset\)
 
pka said:
You have made the proof of uniqueness far too complicated
If \(\displaystyle A\) is a set then \(\displaystyle A\Delta A=\emptyset\) so existence is proven, every set is its own inverse.
So suppose that \(\displaystyle A\Delta B=\emptyset~\&~A\ne B\).
That means that \(\displaystyle \exists s\in A\setminus B\vee\exists t\in B\setminus A\).
But in either of those cases \(\displaystyle A\Delta B\ne\emptyset\)
Click to expand...
Goal:[MATH]\forall A\exists !B(A\Delta B = \varnothing)[/MATH]
Okey so is this a better proof?

The following are equivalent.
[MATH]\exists x (P(x) \wedge \forall y(P(y) \to y = x))[/MATH][MATH]\exists x \forall y(P(y) \longleftrightarrow y = x))[/MATH][MATH] \exists x P(x) \wedge \forall y \forall z ((P(y) \wedge P(z)) \to y = z)[/MATH]
Goal: [MATH]\forall A\exists !B(A\Delta B = \varnothing)[/MATH]
Let [MATH]P(B)[/MATH] be defined as the statement [MATH]A \Delta B = \varnothing [/MATH]
Suppose [MATH]A[/MATH] is an arbitrary set.

1. Let [MATH] A = B.[/MATH]2.[MATH] A \Delta B = A \Delta A = \varnothing[/MATH]3.[MATH] P(B)[/MATH]
4. Let [MATH]y[/MATH] be an arbitrary set.
5.[MATH] A \Delta y = \varnothing[/MATH] [Hyp.]
6.[MATH] B \Delta y = \varnothing[/MATH]7.[MATH] y \ne B[/MATH] [Ind. Hyp.]
8.[MATH] \exists s \in y \setminus B \vee \exists t \in B \setminus y[/MATH]9.[MATH] \perp [/MATH]10.[MATH] y = B[/MATH] [Gm. Ind. Hyp. (7)-(9)]
10.[MATH] A \Delta y = \varnothing \to y = B[/MATH] [Gm. Hyp. (5)-(10)]
11.[MATH] \forall y(A \Delta y = \varnothing \to y = B)[/MATH]12.[MATH] \forall y(P(y) \to y = B)[/MATH]13.[MATH] P(B) \wedge \forall y(P(y) \to y = B)[/MATH]14.[MATH] \exists B (P(B) \wedge \forall y(P(y) \to y = B))[/MATH]15.[MATH] \exists !B (P(B))[/MATH]16.[MATH] \exists !B (A\Delta B = \varnothing)[/MATH]17.[MATH] \forall A \exists !B (A\Delta B = \varnothing)[/MATH]
 
Last edited:
(c) Prove that for any sets A and B there is a unique set C such that [MATH]A \Delta C = B[/MATH].

1. Suppose A and B are arb. sets.

Existence part
2. Let [MATH]C = A \Delta B[/MATH]3. [MATH]A \Delta C = A \Delta (A \Delta B) = (A \Delta A) \Delta B = \varnothing \Delta B =B[/MATH]4. [MATH]\exists C (A \Delta C = B)[/MATH]
Uniqueness part
5. Let [MATH]y[/MATH] and [MATH]z[/MATH] be arb. sets.
6. [MATH]A \Delta y = B \wedge A \Delta Z = B[/MATH] [Hyp.]
7. [MATH]y = A \Delta B \wedge z = A \Delta B[/MATH]8. [MATH]y = z[/MATH]
 
Last edited:
You must log in or register to reply here.
Top