1
$\begingroup$

Given

$$E = \{1,2,3,4,5,6,7,8\}$$ $$A \subseteq P(E)$$

With axioms:

$$(1): (X \in A \land Y \in A) \implies X \cup Y \in A$$ $$(2): X \in A \implies \overline{X} \in A$$ $$(3): \{1,2,3\} \in A$$ $$(4): \{1\} \in A$$

Demonstrate

$\{1,2\} \notin A \implies \{2\} \notin A$

A bit puzzled. I'm not entirely sure how can taking $\{1,2\} \notin A$ let me conclude that $\{2\} \notin A$.

One idea is that it can be simplified to a different form. The above should be equal to

$\{1,2\}\in A \lor \{2\} \notin A$

So, the demonstration would be complete if I can prove either of those propositions?

This sounds fishy - I'm not sure if I am allowed to do this, because I think that I am supposed to assume that $\{1,2\} \notin A$, so proving $\{1,2\} \in A$ would not make sense.

Is the above permitted? How else can I approach this demonstration?


I just managed to solve it with a different method, but I would still like to hear the answer for the above. Anyway, if you're curious, this is what I did:

Proving the contrapositive, that is,

$\{2\} \in A \implies \{1,2\} \in A$

So now I am taking $\{2\} \in A$ and attempting to get $\{1,2\} \in A$.

Since axiom (4) tells me that $\{1\} \in A$, I can use axiom (1) to conclude that

$\{1\} \in A \land \{2\} \in A \implies \{1\} \cup \{2\} \in A$

Which basically means that

$\{1,2\} \in A$

$\endgroup$
  • $\begingroup$ If you were able to prove that for all $A$ satisfying the hypotheses, it must be that $\{1,2\} \in A$, then the implication you need to demonstrate would turn out to be trivially true. If you were able to show that for all $A$ satisfying the hypotheses, it must be that $\{2\} \notin A$, the implication you need to demonstrate would turn out to be vacuously true. More typically, you would show that for all $A$ satisfying the hypothesis, it must be that $\{1,2\}\in A \lor \{2\} \notin A$ by showing that for some $A$, $\{1,2\}\in A$ is true and for all other $A$, $ \{2\} \notin A$ is true. $\endgroup$ – Steve Kass Sep 26 '13 at 3:53
0
$\begingroup$

Prove the contrapositive :

$\{2\} \in A \implies \{1,2\} \in A$

To do that, use property (4) and property (1)

$\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.