Inﬁnite combinatorics

(1)

Infinite combinatorics

(2)

Almost disjointness

Definition

Sets x , y are disjoint if x ∩ y = ∅.

Remark. Let X be a set of cardinality κ (for example κ itself). Let A be a family of pairwise disjoint subsets of X . How many members can A contain?

A family of disjoint subsets of a set of cardinality κ has cardinalty at most κ.

In fact there exists a maximal disjoint family A of cardinality κ: working on X = κ × κ, let A = {Aα| α < κ} where

Aα= {(α, β) ∈ κ × κ | β < κ}. Since S A = κ, family A is maximal. What if we weaken the condition of disjointness?

(3)

Almost disjointness

Definition

In fact there exists a maximal disjoint family A of cardinality κ: working on X = κ × κ, let A = {Aα| α < κ} where

(4)

Almost disjointness

Definition

In fact there exists a maximal disjoint family A of cardinality κ:

working on X = κ × κ, let A = {Aα| α < κ} where

(5)

Almost disjointness

Definition

In fact there exists a maximal disjoint family A of cardinality κ: working on X = κ × κ, let A = {A_α| α < κ} where

Aα= {(α, β) ∈ κ × κ | β < κ}.

SinceS A = κ, family A is maximal. What if we weaken the condition of disjointness?

(6)

Almost disjointness

Definition

Aα= {(α, β) ∈ κ × κ | β < κ}. Since S A = κ, family A is maximal.

What if we weaken the condition of disjointness?

(7)

Almost disjointness

Definition

Aα= {(α, β) ∈ κ × κ | β < κ}. Since S A = κ, family A is maximal.

What if we weaken the condition of disjointness?

(8)

Almost disjointness

Definition

Let κ be an infinite cardinal, x , y ⊆ κ. Then x , y are almost disjoint (a.d.) if |x ∩ y | < κ.

An almost disjoint family is some A ⊆ P(κ) such that:

I ∀x ∈ A |x| = κ

I ∀x, y ∈ A (x 6= y ⇒ |x ∩ y | < κ)

A maximal almost disjoint (m.a.d.) family is an ad family A such that for no ad family B one has A ⊂ B.

(9)

Almost disjointness

Definition

I ∀x ∈ A |x| = κ

I ∀x, y ∈ A (x 6= y ⇒ |x ∩ y | < κ)

(10)

Almost disjointness

Definition

I ∀x ∈ A |x| = κ

I ∀x, y ∈ A (x 6= y ⇒ |x ∩ y | < κ)

(11)

Almost disjointness

Theorem

Let κ be regular. Then:

1. If A ⊆ P(κ) is an ad family with |A| = κ, then A is not maximal 2. There is a mad family B ⊆ P(κ) of cardinality ≥ κ⁺

Proof.

(1) It is proved that there is some D ⊆ κ, D /∈ A such that D is a.d. with all elements of A. Let A = {Aξ | ξ < κ}. Let

Bξ= Aξ\S

η<ξAη = Aξ\S

η<ξ(Aξ∩ Aη). So Bξ6= ∅ by regularity of κ. Let bξ ∈ Bξ. Since the Bξ are pairwise disjoint, the bξ are all distinct. So D = {bξ| ξ < κ} has cardinality κ. Finally, if bξ ∈ Aη then η ≥ ξ. Thus D ∩ Aη⊆ {bξ | ξ ≤ η} has cardinality less than κ.

(2) Let A ⊆ P(κ) be an a.d. family of cardinality κ (for example a disjoint family). By Zorn’s lemma, let B a m.a.d.f. with A ⊆ B. By part (1), |B| > κ.

(12)

Almost disjointness

Theorem

Proof.

(1) It is proved that there is some D ⊆ κ, D /∈ A such that D is a.d. with all elements of A.

Let A = {Aξ | ξ < κ}. Let Bξ= Aξ\S

η<ξAη = Aξ\S

(13)

Almost disjointness

Theorem

Proof.

(1) It is proved that there is some D ⊆ κ, D /∈ A such that D is a.d. with all elements of A. Let A = {A_ξ | ξ < κ}.

Let Bξ= Aξ\S

η<ξAη = Aξ\S

(14)

Almost disjointness

Theorem

Proof.

(1) It is proved that there is some D ⊆ κ, D /∈ A such that D is a.d. with all elements of A. Let A = {A_ξ | ξ < κ}. Let

Bξ = Aξ\S

η<ξAη = Aξ\S

η<ξ(Aξ∩ Aη).

So Bξ6= ∅ by regularity of κ. Let bξ ∈ Bξ. Since the Bξ are pairwise disjoint, the bξ are all distinct. So D = {bξ| ξ < κ} has cardinality κ. Finally, if bξ ∈ Aη then η ≥ ξ. Thus D ∩ Aη⊆ {bξ | ξ ≤ η} has cardinality less than κ.

(15)

Almost disjointness

Theorem

Proof.

Bξ = Aξ\S

η<ξAη = Aξ\S

η<ξ(Aξ∩ Aη). So Bξ6= ∅ by regularity of κ.

Let bξ ∈ Bξ. Since the Bξ are pairwise disjoint, the bξ are all distinct. So D = {bξ| ξ < κ} has cardinality κ. Finally, if bξ ∈ Aη then η ≥ ξ. Thus D ∩ Aη⊆ {bξ | ξ ≤ η} has cardinality less than κ.

(16)

Almost disjointness

Theorem

Proof.

Bξ = Aξ\S

η<ξAη = Aξ\S

Let bξ ∈ Bξ.

Since the Bξ are pairwise disjoint, the bξ are all distinct. So D = {bξ| ξ < κ} has cardinality κ. Finally, if bξ ∈ Aη then η ≥ ξ. Thus D ∩ Aη⊆ {bξ | ξ ≤ η} has cardinality less than κ.

(17)

Almost disjointness

Theorem

Proof.

Bξ = Aξ\S

η<ξAη = Aξ\S

Let bξ ∈ Bξ. Since the Bξ are pairwise disjoint, the bξ are all distinct.

So D = {bξ| ξ < κ} has cardinality κ. Finally, if bξ ∈ Aη then η ≥ ξ. Thus D ∩ Aη⊆ {bξ | ξ ≤ η} has cardinality less than κ.

(18)

Almost disjointness

Theorem

Proof.

Bξ = Aξ\S

η<ξAη = Aξ\S

Let bξ ∈ Bξ. Since the Bξ are pairwise disjoint, the bξ are all distinct. So D = {bξ| ξ < κ} has cardinality κ.

Finally, if bξ ∈ Aη then η ≥ ξ. Thus D ∩ Aη⊆ {bξ | ξ ≤ η} has cardinality less than κ.

(19)

Almost disjointness

Theorem

Proof.

Bξ = Aξ\S

η<ξAη = Aξ\S

Let bξ ∈ Bξ. Since the Bξ are pairwise disjoint, the bξ are all distinct. So D = {bξ| ξ < κ} has cardinality κ. Finally, if bξ ∈ Aη then η ≥ ξ.

Thus D ∩ Aη⊆ {bξ | ξ ≤ η} has cardinality less than κ.

(20)

Almost disjointness

Theorem

Proof.

Bξ = Aξ\S

η<ξAη = Aξ\S

(21)

Almost disjointness

Theorem

Proof.

Bξ = Aξ\S

η<ξAη = Aξ\S

(22)

Almost disjointness

So under GCH any m.a.d. family in P(κ) has cardinality κ⁺= 2^κ.

In general, the following holds:

Theorem

Let κ be an infinite cardinal. If 2^<κ= κ, then there is an ad family A ⊆ P(κ) of cardinality 2^κ.

This holds, for example, for κ = ω; or for κ = ω₁ under CH.

Proof.

Let I = {x ⊆ κ | sup x < κ}. So, |I | = κ, as 2^<κ= κ. For any X ⊆ κ with |X | = κ, let AX = {X ∩ α | α < κ} be the family of initial cuts of X . So |AX| = κ. Moreover, suppose X 6= Y and let β be an element belonging to exactly one of the two sets. Then

AX∩ AY ⊆ {X ∩ α | α ≤ β}. This means that

A = {AX | X ⊆ κ ∧ |X | = κ} is an a.d. family of subsets of I of cardinality 2^κ. Trasferring this to κ via a bijection I → κ, one gets the assertion.

(23)

Almost disjointness

So under GCH any m.a.d. family in P(κ) has cardinality κ⁺= 2^κ. In general, the following holds:

Theorem

Let κ be an infinite cardinal. If 2^<κ= κ,

then there is an ad family A ⊆ P(κ) of cardinality 2^κ.

Proof.

(24)

Almost disjointness

Theorem

Proof.

(25)

Almost disjointness

Theorem

Proof.

Let I = {x ⊆ κ | sup x < κ}. So, |I | = κ, as 2^<κ= κ.

For any X ⊆ κ with |X | = κ, let AX = {X ∩ α | α < κ} be the family of initial cuts of X . So |AX| = κ. Moreover, suppose X 6= Y and let β be an element belonging to exactly one of the two sets. Then

(26)

Almost disjointness

Theorem

Proof.

Let I = {x ⊆ κ | sup x < κ}. So, |I | = κ, as 2^<κ= κ. For any X ⊆ κ with |X | = κ, let AX = {X ∩ α | α < κ} be the family of initial cuts of X .

So |AX| = κ. Moreover, suppose X 6= Y and let β be an element belonging to exactly one of the two sets. Then

(27)

Almost disjointness

Theorem

Proof.

Let I = {x ⊆ κ | sup x < κ}. So, |I | = κ, as 2^<κ= κ. For any X ⊆ κ with |X | = κ, let AX = {X ∩ α | α < κ} be the family of initial cuts of X . So |AX| = κ.

Moreover, suppose X 6= Y and let β be an element belonging to exactly one of the two sets. Then

(28)

Almost disjointness

Theorem

Proof.

AX ∩ AY ⊆ {X ∩ α | α ≤ β}.

This means that

(29)

Almost disjointness

Theorem

Proof.

AX ∩ AY ⊆ {X ∩ α | α ≤ β}. This means that

A = {AX | X ⊆ κ ∧ |X | = κ} is an a.d. family of subsets of I of cardinality 2^κ.

Trasferring this to κ via a bijection I → κ, one gets the assertion.

(30)

Almost disjointness

Theorem

Proof.

AX ∩ AY ⊆ {X ∩ α | α ≤ β}. This means that

(31)

Almost disjointness: independent statements

In the theorem, the hypothesis 2^<κ= κ, used to grant that |I | = κ, which allowed to work on |I | instead of κ, cannot be dropped. For example, the existence of an a.d. family in P(ω1) of cardinality 2^ω¹ is independent of ZFC .

A somehow dual question:

Suppose 2^κ> κ⁺. Is there a m.a.d. family of cardinality κ⁺? This too is independent of ZFC. This is related to Martin’s axiom.

(32)

Suppose 2^κ> κ⁺. Is there a m.a.d. family of cardinality κ⁺?

This too is independent of ZFC. This is related to Martin’s axiom.

(33)

Suppose 2^κ> κ⁺. Is there a m.a.d. family of cardinality κ⁺? This too is independent of ZFC. This is related to Martin’s axiom.

(34)

Quasi-disjointness

Another weakening of disjointness is quasi-disjointness.

Definition

A family A of sets is quasi-disjoint, or a ∆-system, if there is a fixed set r , called the root of the ∆-system, such that

∀a, b ∈ A (a 6= b ⇒ a ∩ b = r ).

(35)

The ∆-system lemma

Theorem

Let κ be an infinite cardinal.

Let θ > κ be regular and such that

∀λ < θ λ^<κ< θ. If |A| ≥ θ and ∀x ∈ A |x | < κ, there there is B ⊆ A such that |B| = θ and B is a ∆-system.

For instance: let κ = ω, θ = ω₁. Then:

Corollary

If A is an uncountable family of finite sets, there is an uncountable

∆-system B ⊆ A.

Exercise. Give a direct proof of this corollary.

(36)

Theorem

Let κ be an infinite cardinal. Let θ > κ be regular and such

that

Corollary

∆-system B ⊆ A.

(37)

Theorem

Let κ be an infinite cardinal. Let θ > κ be regular and such that

∀λ < θ λ^<κ< θ.

If |A| ≥ θ and ∀x ∈ A |x | < κ, there there is B ⊆ A such that |B| = θ and B is a ∆-system.

Corollary

∆-system B ⊆ A.

(38)

Theorem

∀λ < θ λ^<κ< θ. If |A| ≥ θ and ∀x ∈ A |x | < κ,

there there is B ⊆ A such that |B| = θ and B is a ∆-system.

Corollary

∆-system B ⊆ A.

(39)

Theorem

Corollary

∆-system B ⊆ A.

(40)

Theorem

Corollary

∆-system B ⊆ A.

(41)

Theorem

Corollary

∆-system B ⊆ A.

(42)

Theorem

Corollary

∆-system B ⊆ A.

(43)

Proof.

By shrinking, one can assume |A| = θ,

so that |S A| ≤ θ, so that one can also assume |S A| ⊆ θ, i.e. A ⊆ P(θ). Then each x ∈ A has some order type < κ. Since θ is regular and θ > κ, there is ρ < κ such that A1= {x ∈ A | x has order type ρ} has cardinality θ. It is enough to extract the ∆-system from A1.

Fix α < θ. The subsets of α of cardinality less than κ are at most

|α|^<κ < θ. SoS A1 is unbounded in θ. For any x ∈ A1, ξ < ρ, let x (ξ) be the ξ-th element of x . Since θ is regular, there is a least ξ0such that {x(ξ0) | x ∈ A1} is unbounded in θ. Let

α0= sup{x (η) + 1 | x ∈ A1, η < ξ0}. Then α0< θ and

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

Define inductively, for µ < θ, elements xµ∈ A1so that xµ(ξ0) is bigger than α₀and of all elements of all x_ν, for ν < µ. Let A₂be the collection of such elements. Then |A₂| = θ and ∀x, y ∈ A2(x 6= y ⇒ x ∩ y ⊆ α₀). Each x ∩ α₀is a subset of α₀of cardinality less that κ. Since there are at most |α₀|^<κ< θ of them, there are r ⊆ α₀, B ⊆ A₂such that |B| = θ and ∀x ∈ B x ∩ α₀= r , which implies ∀x , y ∈ B(x 6= y ⇒ x ∩ y = r ).

(44)

Proof.

By shrinking, one can assume |A| = θ, so that |S A| ≤ θ,

so that one can also assume |S A| ⊆ θ, i.e. A ⊆ P(θ). Then each x ∈ A has some order type < κ. Since θ is regular and θ > κ, there is ρ < κ such that A1= {x ∈ A | x has order type ρ} has cardinality θ. It is enough to extract the ∆-system from A1.

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

(45)

Proof.

By shrinking, one can assume |A| = θ, so that |S A| ≤ θ, so that one can also assume |S A| ⊆ θ, i.e. A ⊆ P(θ).

Then each x ∈ A has some order type < κ. Since θ is regular and θ > κ, there is ρ < κ such that A1= {x ∈ A | x has order type ρ} has cardinality θ. It is enough to extract the ∆-system from A1.

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

(46)

Proof.

By shrinking, one can assume |A| = θ, so that |S A| ≤ θ, so that one can also assume |S A| ⊆ θ, i.e. A ⊆ P(θ). Then each x ∈ A has some order type < κ.

Since θ is regular and θ > κ, there is ρ < κ such that A1= {x ∈ A | x has order type ρ} has cardinality θ. It is enough to extract the ∆-system from A1.

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

(47)

Proof.

By shrinking, one can assume |A| = θ, so that |S A| ≤ θ, so that one can also assume |S A| ⊆ θ, i.e. A ⊆ P(θ). Then each x ∈ A has some order type < κ. Since θ is regular and θ > κ, there is ρ < κ such that A1= {x ∈ A | x has order type ρ} has cardinality θ.

It is enough to extract the ∆-system from A1.

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

(48)

Proof.

By shrinking, one can assume |A| = θ, so that |S A| ≤ θ, so that one can also assume |S A| ⊆ θ, i.e. A ⊆ P(θ). Then each x ∈ A has some order type < κ. Since θ is regular and θ > κ, there is ρ < κ such that A1= {x ∈ A | x has order type ρ} has cardinality θ. It is enough to extract the ∆-system from A1.

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

(49)

Proof.

Fix α < θ.

The subsets of α of cardinality less than κ are at most

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

(50)

Proof.

|α|^<κ < θ.

SoS A1 is unbounded in θ. For any x ∈ A1, ξ < ρ, let x (ξ) be the ξ-th element of x . Since θ is regular, there is a least ξ0such that {x(ξ0) | x ∈ A1} is unbounded in θ. Let

∀x ∈ A1 ∀η < ξ0 x (η) < α0.

(51)

Proof.

|α|^<κ < θ. SoS A1 is unbounded in θ.

For any x ∈ A1, ξ < ρ, let x (ξ) be the ξ-th element of x . Since θ is regular, there is a least ξ0such that {x(ξ0) | x ∈ A1} is unbounded in θ. Let

∀x ∈ A1 ∀η < ξ0 x (η) < α0.