2.1 Sets and Operations: Describing Object Scope via Membership

An access control policy consists of three lists: project members, frozen users, and temporary auditors. The requirement is: "Allow non-frozen project members and on-duty auditors to read logs." If the scope of these lists and the operations defining them are not clearly specified, the term "non-frozen user" could be interpreted as all users in the organization, or it might strictly mean only project members.

Set theory addresses two fundamental questions: which objects are under discussion, and which of those objects belong to the current set.

Sets Are Defined by Their Members

A set is an unordered collection of objects. Notation:

x ∈ A     x is an element of A
x ∉ A     x is not an element of A

The principle of extensionality states that two sets are equal if and only if they contain exactly the same elements.

A = B  ⇔  ∀x (x ∈ A ↔ x ∈ B)

Therefore:

{1, 2, 3} = {3, 2, 1}
{1, 1, 2} = {1, 2}

Order and multiplicity do not define the identity of a mathematical set. If your application cares about order, use a sequence; if it cares about counts of duplicates, use a multiset. This distinction will be explored further in Lesson Three, in the context of program data structures and SQL.

Two Common Notations

Enumeration

P = {read, write, delete}

Suitable for finite sets with a small number of elements.

Set-Builder Notation

E = {n ∈ ℤ | n is an even number}

The vertical bar is read as "such that." In descriptive notation, it's essential to specify the domain from which elements are drawn. Writing only {x | x > 0} leaves ambiguous whether x refers to integers, real numbers, or some other type.

Modern axiomatic set theory does not permit unrestricted "collection of all objects" based on arbitrary properties. While this course does not analyze the axiomatic systems, it's safer to adopt the practice of filtering elements from a known set:

{x ∈ U | P(x)}

Empty Set, Singleton Sets, and Nesting Levels

The empty set is denoted as ∅ or {} and contains no elements:

∀x (x ∉ ∅)

{∅} is not the empty set; it contains one element, and that element is the empty set itself:

|∅| = 0
|{∅}| = 1

It's important to distinguish between an element and a singleton set:

1 ∈ {1, 2}
{1} ⊆ {1, 2}

1 and {1} reside at different structural levels. In JSON, a number 1 cannot be interchanged with an array [1].

Subsets and Proper Subsets

A ⊆ B  ⇔  ∀x (x ∈ A → x ∈ B)

The empty set is a subset of every set, because there are no elements in the empty set that could violate the condition.

If A ⊆ B and A ≠ B, then A is a proper subset of B, commonly denoted as A ⊊ B. Different textbooks may use ⊂, but this symbol can sometimes denote a regular subset and at other times a proper subset; usage should be clarified in advance.

A common way to prove that two sets are equal is to show mutual containment:

A = B  ⇔  (A ⊆ B) ∧ (B ⊆ A)

Four Basic Operations

Given a universe U, with A ⊆ U and B ⊆ U:

A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B}
A ∩ B = {x ∈ U | x ∈ A ∧ x ∈ B}
A \ B = {x ∈ U | x ∈ A ∧ x ∉ B}
Aᶜ    = {x ∈ U | x ∉ A}

• Union A ∪ B: belongs to at least one of the sets;
• Intersection A ∩ B: belongs to both sets;
• Difference A \ B: belongs to A but not to B;
• Complement Aᶜ: elements not in A relative to the declared universe U.

The complement depends on the universe. For example, A={2,4}:

If U = {1,2,3,4,5}, then Aᶜ = {1,3,5}
If U = ℤ, then Aᶜ consists of all integers except 2 and 4

Without specifying U, the complement has no unique definition.

Proving Identities with Membership

Prove De Morgan's Law:

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

Pick any x ∈ U:

x ∈ (A ∪ B)ᶜ
⇔ x ∉ A ∪ B
⇔ ¬(x ∈ A ∨ x ∈ B)
⇔ (x ∉ A ∧ x ∉ B)
⇔ (x ∈ Aᶜ ∧ x ∈ Bᶜ)
⇔ x ∈ Aᶜ ∩ Bᶜ

Since every x satisfies the same membership condition on both sides, the two sets are equal. A Venn diagram can help build intuition, but the membership chain provides a checkable proof.

Common Set Identities

Commutative Law: A ∪ B = B ∪ A
                A ∩ B = B ∩ A

Associative Law: (A ∪ B) ∪ C = A ∪ (B ∪ C)
                (A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive Law: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
                 A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Absorption Law: A ∪ (A ∩ B) = A
                A ∩ (A ∪ B) = A

These laws derive from the logical equivalences corresponding to membership conditions. Translate compound membership conditions into propositional formulas using ∧, ∨, and ¬, then reuse the previous chapter’s equivalences.

Back to Access Control Policies

Definition:

M: Project members
F: Frozen users
A: On-duty auditors
U: All identifiable users in the project

The set of users allowed to read logs:

(M \ F) ∪ A

This also hides a business decision: can a frozen auditor still read logs? The current formula permits it, because A is outside the set difference. If freezing should apply to all roles, the expression should be written as:

(M ∪ A) \ F

The two formulas differ only in parentheses, yet their policy implications are distinct. Set expressions make these differences explicit and reviewable, enabling clear analysis, testing, and audit.

Use Python 3’s built-in sets to give frozen on-duty auditor u2 a concrete role in the comparison:

universe = {"u1", "u2", "u3", "u4"}
members = {"u1", "u2"}
frozen = {"u2", "u4"}
auditors = {"u2", "u3"}
assert (members | frozen | auditors) <= universe

role_exception = (members - frozen) | auditors
deny_all_roles = (members | auditors) - frozen
print(sorted(role_exception))  # ['u1', 'u2', 'u3']
print(sorted(deny_all_roles))   # ['u1', 'u3']
assert role_exception - deny_all_roles == auditors & frozen

The first policy grants exactly the additional frozen auditors in A ∩ F. Every list uses the same universe and is assumed to reflect trusted state at one instant; correct set arithmetic does not prove freshness. Python’s empty set is set(), while {} creates a dictionary, so mathematical notation is not always executable syntax.

Completion Check

Given:

U={1,2,3,4,5,6}
A={1,2,3}
B={3,4,5}
C={2,4,6}

1. Compute (A ∪ B) ∩ C;
2. Compute A \ (B ∪ C);
3. Prove A \ (B ∪ C) = (A \ B) ∩ (A \ C) using membership;
4. Determine the truth value of {1} ∈ { {1}, {2} } and {1} ⊆ { {1}, {2} };
5. Write a set expression for the permission rule "disabled state overrides any role".

References

• Open Logic Project