0
$\begingroup$

I'm trying to prove set algebras's absoption laws without using DeMorgan's laws.

Absoption laws :

  1. $A \cup (A \cap B) = A$
  2. $A \cap (A \cup B) = A$

Is this possible?

I would like to prove these laws using only set algebra's laws , without analysing the sentences set theoretically in terms of membership relation.

I can prove , for example, that $A \cup ( A \cap B)$ is included in $A$ , by proving that

$( A \cup (A \cap B)) \cap A^\complement = \emptyset$

( here I use the fact that : $X \subseteq Y \iff X \cap Y^\complement= \emptyset$).

But the reverse inclusion, applying the same strategy, would require me to use De Morgan's laws).

Following Wikipedia I take

(1) As axioms & definitions

  • commutativity of U and Inter

  • associativity of U and Inter

  • distributivity of U over Inter , and reciprocally

  • identity laws

  • complement laws

  • duality law

  • definition of inclusion

  • definition of equality ( as reciprocal inclusion)

(2) As derived laws ( provable using axioms and definitions)

  • idempotent laws for U and Inter ( Which I managed to prove)

  • domination laws ( Which I managed to prove)

  • absoption laws ( Here, I am stuck)

  • DeMorgan's laws ( Here, also stuck)

  • etc.

$\endgroup$
  • $\begingroup$ The "axioms" say almost nothing on complements so it's no wonder you cannot show de Morgan, I think. $\endgroup$ – Henno Brandsma Apr 17 at 21:03
  • $\begingroup$ @HennoBrandsma. I first would like to prove absoption laws, in order to go from more basic to less basic, as if I were constructing a deductive system. $\endgroup$ – Eleonore Saint James Apr 17 at 21:07
2
$\begingroup$

$A \cup (A \cap B) \subseteq A$ follows from $A \subseteq A$ and $A \cap B \subseteq A$ right away, doesn't it? (interpreting $\cap$ as $\land$ (the infimum in a lattice) and $\cup, \lor$ as the supremum in a lattice )

It might be clearer if you state what "laws" you consider as "axioms" exactly. The absorption law holds in any lattice, as I just sketched. This is basically from the definitions of sup and inf.

Trying to use your linked axioms: $A \cup (A \cap B)$ by distributivity equals $(A \cup A) \cap (A \cup B)$ and by idempotency (proved on your page from your axioms) this equals $A \cap (A \cup B)$ which equals by distributivity again : $(A \cap A) \cup (A \cap B)$ and we're back at $A \cup (A \cap B)$ again. The linked page does not give a definition of inclusion really, but some equivalent statements for $A \subseteq B$, that I think do not derive from these axioms but from simple "element considerations".

$\endgroup$
  • $\begingroup$ Henno Brandsma.- I've edited my question to clarify which propositions I would like as primitive, and which ones as derived laws. $\endgroup$ – Eleonore Saint James Apr 17 at 20:35
  • $\begingroup$ @EleonoreSaintJames what Wikipedia page? You can include links... $\endgroup$ – Henno Brandsma Apr 17 at 20:36
  • $\begingroup$ @HennoBrandsma.Sorry I forgot to include the link : en.wikipedia.org/wiki/… $\endgroup$ – Eleonore Saint James Apr 17 at 20:47

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.