4
$\begingroup$

I can't find anything on this topic elsewhere. I'd like to know what keywords/sites I should be using to find what I'm looking for if this is to elementry of a question. (been using discrete math, set theory, proofs, symmetric difference, for a given number.)

Given sets A and B,

the symmetric difference A Δ B is defined by A Δ B = ( A - B ) ∪ ( B - A ) = ( A ∪ B ) - ( A ∩ B ).

let X = {1,2,3, ...271}

a) ∀A∈P(X), ∃B∈P(X), 271 ∈ AΔB. Prove it true or false.

So this is my understanding is as follows with what I think my mistake might be in brackets.

"∀A∈P(X)" For any possible A set, it will be a member of the power set of X.

( So I view A as all possible P(X), otherwise it would be written "A∈P(X)" right ? )

"∃B∈P(X)" There is a B set, that is a member of the power set of X.

( I view B as a single possible set from P(X). )

"271 ∈ A Δ B" 271 is a member of the symmetric difference between A and B.

( So, "when all possible sets of P(x) are compared to a specific set of P(X), the result would be "271 ∈ AΔB" every time." is the statement? )

I think it's false.
Because regardless of whether the B set does or doesn't have 271, there is going to be a possible A set that also does or doesn't have 271 as well.

Unless you separate A into subsets of "has 271" and "doesn't have 271", then it would be true for half, and false for the other half.

But I don't understand how to put my answer (if it's even right) into written form.

I'm doing several questions but I think if I can figure out how this is done, I can do the rest.

$\endgroup$
  • $\begingroup$ Your reasoning seems sound to me. Essentially $A \Delta B$ consists of all elements that are in exactly one of $A$ and $B$ (like XOR). So it contains $271$ if and only if either $A$ or $B$ contains it, but not both. Write your proof down in terms of $A \cup B$ and $A \cap B$: When do those sets contain $271$, and when do they not? $\endgroup$ – Brian Tung Jul 30 '15 at 1:14
  • 1
    $\begingroup$ This question is very well-asked: You've shown us a lot of your thought processes, which helps people give you appropriate answers. Kudos! $\endgroup$ – pjs36 Jul 30 '15 at 1:18
3
$\begingroup$

The order of the quantifiers is important. The statement as you have interpreted it would be written

$$(\exists B\in P(X))(\forall A\in P(X))(271\in A\Delta B).$$

That is, there exists a fixed set $B$ such that for every set $A$, we have $271\in A\Delta B$. In other words, first you fix $B$, then you have to check it against all $A$. But the statement as written is

$$(\forall A\in P(X))(\exists B\in P(X))(271\in A\Delta B).$$

That is, for every set $A$, there exists a set $B$ (possibly depending on $A$) such that $271\in A\Delta B$. In other words, $A$ can be chosen arbitrarily, but you don't have to pick a fixed $B$ - you just need to come up with a rule that, given an $A$, selects an appropriate $B$.

If that distinction makes sense, then hopefully you can see why the statement as written is true.

$\endgroup$
1
$\begingroup$

This is partly a question of quantifiers: You are trying to prove "For all A, there exists a B such that ...".

From the definition of $A \Delta B$, you should be able to prove that

$B = (A \Delta B) \Delta A$

So for any $A$, you are free to choose an $A \Delta B$ that contains $271$ (or any element, or elements, you choose), and the appropriate $B$ is guaranteed to exist.

$\endgroup$
1
$\begingroup$

If 271 belongs to A ,let B be the empty set.If 271 does not belong to A, let B=X.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.