A computable model of ZFA without infinity

In this file we define finite hereditary lists. This is useful for calculations in naive set theory.

We distinguish two kinds of ZFA lists:

• Atoms. Directly correspond to an element of the original type.
• Proper ZFA lists. Can be thought of (but aren't implemented) as a list of ZFA lists (not necessarily proper).

For example, Lists ℕ contains stuff like 23, [], [37], [1, [[2], 3], 4].

Implementation note

As we want to be able to append both atoms and proper ZFA lists to proper ZFA lists, it's handy that atoms and proper ZFA lists belong to the same type, even though atoms of α could be modelled as α directly. But we don't want to be able to append anything to atoms.

This calls for a two-steps definition of ZFA lists:

• First, define ZFA prelists as atoms and proper ZFA prelists. Those proper ZFA prelists are defined by inductive appending of (not necessarily proper) ZFA lists.
• Second, define ZFA lists by rubbing out the distinction between atoms and proper lists.

Main declarations

• Lists' α false: Atoms as ZFA prelists. Basically a copy of α.
• Lists' α true: Proper ZFA prelists. Defined inductively from the empty ZFA prelist (Lists'.nil) and from appending a ZFA prelist to a proper ZFA prelist (Lists'.cons a l).
• Lists α: ZFA lists. Sum of the atoms and proper ZFA prelists.
• Finsets α: ZFA sets. Defined as Lists quotiented by Lists.Equiv, the extensional equivalence.

inductive Lists' (α : Type u) : Bool → Type u

Prelists, helper type to define Lists. Lists' α false are the "atoms", a copy of α. Lists' α true are the "proper" ZFA prelists, inductively defined from the empty ZFA prelist and from appending a ZFA prelist to a proper ZFA prelist. It is made so that you can't append anything to an atom while having only one appending function for appending both atoms and proper ZFC prelists to a proper ZFA prelist.

• atom: {α : Type u} → α → Lists' α false
• nil: {α : Type u} → Lists' α true
• cons': {α : Type u} → {b : Bool} → Lists' α b → Lists' α true → Lists' α true

instance instDecidableEqLists' : {α : Type u_2} → {a : Bool} → [inst : DecidableEq α] → DecidableEq (Lists' α a)

Equations

• instDecidableEqLists' = decEqLists'✝

def Lists (α : Type u_2) : Type u_2

Hereditarily finite list, aka ZFA list. A ZFA list is either an "atom" (b = false), corresponding to an element of α, or a "proper" ZFA list, inductively defined from the empty ZFA list and from appending a ZFA list to a proper ZFA list.

Equations

• Lists α = ((b : Bool) × Lists' α b)

instance Lists'.instForAllBoolInhabitedLists' {α : Type u_1} [Inhabited α] (b : Bool) : Inhabited (Lists' α b)

Equations

• Lists'.instForAllBoolInhabitedLists' x = match x with | true => { default := Lists'.nil } | false => { default := Lists'.atom default }

def Lists'.cons {α : Type u_1} : Lists α → Lists' α true → Lists' α true

Appending a ZFA list to a proper ZFA prelist.

Equations

• Lists'.cons x✝ x = match x✝, x with | { fst := fst, snd := a }, l => Lists'.cons' a l

def Lists'.toList {α : Type u_1} {b : Bool} : Lists' α b → List (Lists α)

Converts a ZFA prelist to a List of ZFA lists. Atoms are sent to [].

Equations

• Lists'.toList (Lists'.atom a) = []
• Lists'.toList Lists'.nil = []
• Lists'.toList (Lists'.cons' a l) = { fst := b, snd := a } :: Lists'.toList l

theorem Lists'.toList_cons {α : Type u_1} (a : Lists α) (l : Lists' α true) : Lists'.toList (Lists'.cons a l) = a :: Lists'.toList l

def Lists'.ofList {α : Type u_1} : List (Lists α) → Lists' α true

Converts a List of ZFA lists to a proper ZFA prelist.

Equations

• Lists'.ofList [] = Lists'.nil
• Lists'.ofList (a :: l) = Lists'.cons a (Lists'.ofList l)

@[simp]

theorem Lists'.to_ofList {α : Type u_1} (l : List (Lists α)) : Lists'.toList (Lists'.ofList l) = l

@[simp]

theorem Lists'.of_toList {α : Type u_1} (l : Lists' α true) : Lists'.ofList (Lists'.toList l) = l

inductive Lists.Equiv {α : Type u_1} : Lists α → Lists α → Prop

Equivalence of ZFA lists. Defined inductively.

• refl: ∀ {α : Type u_1} (l : Lists α), Lists.Equiv l l
• antisymm: ∀ {α : Type u_1} {l₁ l₂ : Lists' α true}, Lists'.Subset l₁ l₂ → Lists'.Subset l₂ l₁ → Lists.Equiv { fst := true, snd := l₁ } { fst := true, snd := l₂ }

inductive Lists'.Subset {α : Type u_1} : Lists' α true → Lists' α true → Prop

Subset relation for ZFA lists. Defined inductively.

• nil: ∀ {α : Type u_1} {l : Lists' α true}, Lists'.Subset Lists'.nil l
• cons: ∀ {α : Type u_1} {a a' : Lists α} {l l' : Lists' α true}, Lists.Equiv a a' → a' ∈ Lists'.toList l' → Lists'.Subset l l' → Lists'.Subset (Lists'.cons a l) l'

instance Lists'.instHasSubsetLists'True {α : Type u_1} : HasSubset (Lists' α true)

Equations

• Lists'.instHasSubsetLists'True = { Subset := Lists'.Subset }

instance Lists'.instMembershipListsLists' {α : Type u_1} {b : Bool} : Membership (Lists α) (Lists' α b)

ZFA prelist membership. A ZFA list is in a ZFA prelist if some element of this ZFA prelist is equivalent as a ZFA list to this ZFA list.

Equations

• Lists'.instMembershipListsLists' = { mem := fun (a : Lists α) (l : Lists' α b) => ∃ (a' : Lists α), a' ∈ Lists'.toList l ∧ Lists.Equiv a a' }

theorem Lists'.mem_def {α : Type u_1} {b : Bool} {a : Lists α} {l : Lists' α b} : a ∈ l ↔ ∃ (a' : Lists α), a' ∈ Lists'.toList l ∧ Lists.Equiv a a'

@[simp]

theorem Lists'.mem_cons {α : Type u_1} {a : Lists α} {y : Lists α} {l : Lists' α true} : a ∈ Lists'.cons y l ↔ Lists.Equiv a y ∨ a ∈ l

theorem Lists'.cons_subset {α : Type u_1} {a : Lists α} {l₁ : Lists' α true} {l₂ : Lists' α true} : Lists'.cons a l₁ ⊆ l₂ ↔ a ∈ l₂ ∧ l₁ ⊆ l₂

theorem Lists'.ofList_subset {α : Type u_1} {l₁ : List (Lists α)} {l₂ : List (Lists α)} (h : l₁ ⊆ l₂) : Lists'.ofList l₁ ⊆ Lists'.ofList l₂

theorem Lists'.Subset.refl {α : Type u_1} {l : Lists' α true} : l ⊆ l

theorem Lists'.subset_nil {α : Type u_1} {l : Lists' α true} : l ⊆ Lists'.nil → l = Lists'.nil

theorem Lists'.mem_of_subset' {α : Type u_1} {a : Lists α} {l₁ : Lists' α true} {l₂ : Lists' α true} : l₁ ⊆ l₂ → a ∈ Lists'.toList l₁ → a ∈ l₂

theorem Lists'.subset_def {α : Type u_1} {l₁ : Lists' α true} {l₂ : Lists' α true} : l₁ ⊆ l₂ ↔ ∀ (a : Lists α), a ∈ Lists'.toList l₁ → a ∈ l₂

@[match_pattern]

def Lists.atom {α : Type u_1} (a : α) : Lists α

Sends a : α to the corresponding atom in Lists α.

Equations

• Lists.atom a = { fst := false, snd := Lists'.atom a }

@[match_pattern]

def Lists.of' {α : Type u_1} (l : Lists' α true) : Lists α

Converts a proper ZFA prelist to a ZFA list.

Equations

• Lists.of' l = { fst := true, snd := l }

def Lists.toList {α : Type u_1} : Lists α → List (Lists α)

Converts a ZFA list to a List of ZFA lists. Atoms are sent to [].

Equations

• Lists.toList x = match x with | { fst := fst, snd := l } => Lists'.toList l

def Lists.IsList {α : Type u_1} (l : Lists α) : Prop

Predicate stating that a ZFA list is proper.

Equations

• Lists.IsList l = (l.fst = true)

def Lists.ofList {α : Type u_1} (l : List (Lists α)) : Lists α

Converts a List of ZFA lists to a ZFA list.

Equations

• Lists.ofList l = Lists.of' (Lists'.ofList l)

theorem Lists.isList_toList {α : Type u_1} (l : List (Lists α)) : Lists.IsList (Lists.ofList l)

theorem Lists.to_ofList {α : Type u_1} (l : List (Lists α)) : Lists.toList (Lists.ofList l) = l

theorem Lists.of_toList {α : Type u_1} {l : Lists α} : Lists.IsList l → Lists.ofList (Lists.toList l) = l

instance Lists.instInhabitedLists {α : Type u_1} : Inhabited (Lists α)

Equations

• Lists.instInhabitedLists = { default := Lists.of' Lists'.nil }

instance Lists.instDecidableEqLists {α : Type u_1} [DecidableEq α] : DecidableEq (Lists α)

Equations

• Lists.instDecidableEqLists = id inferInstance

instance Lists.instSizeOfLists {α : Type u_1} [SizeOf α] : SizeOf (Lists α)

Equations

• Lists.instSizeOfLists = id inferInstance

def Lists.inductionMut {α : Type u_1} (C : Lists α → Sort u_2) (D : Lists' α true → Sort u_3) (C0 : (a : α) → C (Lists.atom a)) (C1 : (l : Lists' α true) → D l → C (Lists.of' l)) (D0 : D Lists'.nil) (D1 : (a : Lists α) → (l : Lists' α true) → C a → D l → D (Lists'.cons a l)) : PProd ((l : Lists α) → C l) ((l : Lists' α true) → D l)

A recursion principle for pairs of ZFA lists and proper ZFA prelists.

Equations

• One or more equations did not get rendered due to their size.

def Lists.mem {α : Type u_1} (a : Lists α) : Lists α → Prop

Membership of ZFA list. A ZFA list belongs to a proper ZFA list if it belongs to the latter as a proper ZFA prelist. An atom has no members.

Equations

• Lists.mem a x = match x with | { fst := false, snd := snd } => False | { fst := fst, snd := l } => a ∈ l

instance Lists.instMembershipLists {α : Type u_1} : Membership (Lists α) (Lists α)

Equations

• Lists.instMembershipLists = { mem := Lists.mem }

theorem Lists.isList_of_mem {α : Type u_1} {a : Lists α} {l : Lists α} : a ∈ l → Lists.IsList l

theorem Lists.Equiv.antisymm_iff {α : Type u_1} {l₁ : Lists' α true} {l₂ : Lists' α true} : Lists.Equiv (Lists.of' l₁) (Lists.of' l₂) ↔ l₁ ⊆ l₂ ∧ l₂ ⊆ l₁

theorem Lists.equiv_atom {α : Type u_1} {a : α} {l : Lists α} : Lists.Equiv (Lists.atom a) l ↔ Lists.atom a = l

theorem Lists.Equiv.symm {α : Type u_1} {l₁ : Lists α} {l₂ : Lists α} (h : Lists.Equiv l₁ l₂) : Lists.Equiv l₂ l₁

theorem Lists.Equiv.trans {α : Type u_1} {l₁ : Lists α} {l₂ : Lists α} {l₃ : Lists α} : Lists.Equiv l₁ l₂ → Lists.Equiv l₂ l₃ → Lists.Equiv l₁ l₃

instance Lists.instSetoidLists {α : Type u_1} : Setoid (Lists α)

Equations

• Lists.instSetoidLists = { r := fun (x x_1 : Lists α) => Lists.Equiv x x_1, iseqv := (_ : Equivalence fun (x x_1 : Lists α) => Lists.Equiv x x_1) }

@[deprecated]

def Lists.Equiv.decidableMeas {α : Type u_1} : (_ : Lists α) ×' Lists α ⊕' (_ : Lists' α true) ×' Lists' α true ⊕' (_ : Lists α) ×' Lists' α true → ℕ

Auxiliary function to prove termination of decidability checking

Equations

• One or more equations did not get rendered due to their size.

theorem Lists.sizeof_pos {α : Type u_1} {b : Bool} (l : Lists' α b) : 0 < sizeOf l

theorem Lists.lt_sizeof_cons' {α : Type u_1} {b : Bool} (a : Lists' α b) (l : Lists' α true) : sizeOf { fst := b, snd := a } < sizeOf (Lists'.cons' a l)

instance Lists.Equiv.decidable {α : Type u_1} [DecidableEq α] (l₁ : Lists α) (l₂ : Lists α) : Decidable (Lists.Equiv l₁ l₂)

Equations

• Lists.Equiv.decidable { fst := false, snd := l₁ } { fst := false, snd := l₂ } = decidable_of_iff' (l₁ = l₂) (_ : Lists.Equiv { fst := false, snd := l₁ } { fst := false, snd := l₂ } ↔ l₁ = l₂)
• Lists.Equiv.decidable { fst := false, snd := l₁ } { fst := true, snd := l₂ } = isFalse (_ : Lists.Equiv { fst := false, snd := l₁ } { fst := true, snd := l₂ } → False)
• Lists.Equiv.decidable { fst := true, snd := l₁ } { fst := false, snd := l₂ } = isFalse (_ : Lists.Equiv { fst := true, snd := l₁ } { fst := false, snd := l₂ } → False)
• Lists.Equiv.decidable { fst := true, snd := l₁ } { fst := true, snd := l₂ } = decidable_of_iff' (l₁ ⊆ l₂ ∧ l₂ ⊆ l₁) (_ : Lists.Equiv (Lists.of' l₁) (Lists.of' l₂) ↔ l₁ ⊆ l₂ ∧ l₂ ⊆ l₁)

instance Lists.Subset.decidable {α : Type u_1} [DecidableEq α] (l₁ : Lists' α true) (l₂ : Lists' α true) : Decidable (l₁ ⊆ l₂)

Equations

• Lists.Subset.decidable Lists'.nil x = isTrue (_ : Lists'.Subset Lists'.nil x)
• Lists.Subset.decidable (Lists'.cons' a l₁) x = decidable_of_iff' ({ fst := b, snd := a } ∈ x ∧ l₁ ⊆ x) (_ : Lists'.cons { fst := b, snd := a } l₁ ⊆ x ↔ { fst := b, snd := a } ∈ x ∧ l₁ ⊆ x)

instance Lists.mem.decidable {α : Type u_1} [DecidableEq α] (a : Lists α) (l : Lists' α true) : Decidable (a ∈ l)

Equations

• Lists.mem.decidable x Lists'.nil = isFalse (_ : x ∈ Lists'.nil → False)
• Lists.mem.decidable x (Lists'.cons' b_1 l₂) = decidable_of_iff' (Lists.Equiv x { fst := b, snd := b_1 } ∨ x ∈ l₂) (_ : x ∈ Lists'.cons' b_1 l₂ ↔ Lists.Equiv x { fst := b, snd := b_1 } ∨ x ∈ l₂)

theorem Lists'.mem_equiv_left {α : Type u_1} {l : Lists' α true} {a : Lists α} {a' : Lists α} : Lists.Equiv a a' → (a ∈ l ↔ a' ∈ l)

theorem Lists'.mem_of_subset {α : Type u_1} {a : Lists α} {l₁ : Lists' α true} {l₂ : Lists' α true} (s : l₁ ⊆ l₂) : a ∈ l₁ → a ∈ l₂

theorem Lists'.Subset.trans {α : Type u_1} {l₁ : Lists' α true} {l₂ : Lists' α true} {l₃ : Lists' α true} (h₁ : l₁ ⊆ l₂) (h₂ : l₂ ⊆ l₃) : l₁ ⊆ l₃

def Finsets (α : Type u_2) : Type u_2

Finsets are defined via equivalence classes of Lists

Equations

• Finsets α = Quotient Lists.instSetoidLists

instance Finsets.instEmptyCollectionFinsets {α : Type u_1} : EmptyCollection (Finsets α)

Equations

• Finsets.instEmptyCollectionFinsets = { emptyCollection := ⟦Lists.of' Lists'.nil⟧ }

instance Finsets.instInhabitedFinsets {α : Type u_1} : Inhabited (Finsets α)

Equations

• Finsets.instInhabitedFinsets = { default := ∅ }

instance Finsets.instDecidableEqFinsets {α : Type u_1} [DecidableEq α] : DecidableEq (Finsets α)

Equations

• Finsets.instDecidableEqFinsets = id Quotient.decidableEq