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$
2
  • $\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, 2019 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$
    – user654868
    Apr 17, 2019 at 21:07

1 Answer 1

Reset to default
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$
3
  • $\begingroup$ Henno Brandsma.- I've edited my question to clarify which propositions I would like as primitive, and which ones as derived laws. $\endgroup$
    – user654868
    Apr 17, 2019 at 20:35
  • $\begingroup$ @EleonoreSaintJames what Wikipedia page? You can include links... $\endgroup$
    – Henno Brandsma
    Apr 17, 2019 at 20:36
  • $\begingroup$ @HennoBrandsma.Sorry I forgot to include the link : en.wikipedia.org/wiki/… $\endgroup$
    – user654868
    Apr 17, 2019 at 20:47

You must log in to answer this question.