text: list, and if there is a processor assigned to each item in the list then the task can be completed in O time logarithmic in the length of the list. In the case of a temporary tree, its depth is (log(m/n)), O and it is obtained in time (m/n). Stage 3: A list of active blocks is built. This list consists of contact segments. We use the following deﬁnitions. A set S of processors − − | | | | is large if it contains at least 1(1 f f ) S active elements, where S denotes the size of S. A 2 p s partition tree (PT in short) is a full binary tree with nodes labeled by intervals of integers. The root is labeled by [1, n]. If a node v is labeled by [a, b] and b > a + 1 then v is an internal node, its (cid:98) − (cid:99) (cid:100) (cid:101) left child is labeled by [a, (a + b 1)/2 ] and the right child is labeled by [ (a + b)/2 , b]. Leaves are labeled by intervals of unit length. A processor with physical index i is associated with node v if i belongs to the label of v. The processors associated with a node of tree PT are referred to as the group of this node. A node is large if its group is large. An active processor may check another processor p for being active, p being operational or not. This is done by scanning the block assigned to p and attempting to read each consecutive cell, until the information that the block is active is found. This information is in the ﬁrst operational non-blank cell in the block, which also happens to be this block’s contact address. The algorithm building the list works in phases corresponding to the levels of tree PT. During a phase, processors are partitioned into groups associated with nodes at the corresponding level of the tree. A group is either busy or not. If a group is busy then: 1. Each processor in the group is aware of this. 2. The active processors in the group are organized in a list, and each element of the list knows its rank, that is, the distance from the head of the list. 3. Each element knows the number of elements in the list. Groups correspond to leaves of PT during the ﬁrst phase of the algorithm. Processors in each such a group check each other, and if the group is large then the processors arrange themselves in a list, compute ranks and the group becomes busy. In general, once a phase has been completed, the computation proceeds to the next one, corresponding to the next level of PT towards the root. Let us consider such a phase, it consists of three parts. During the ﬁrst part, the busy groups corresponding to nodes being left children perform computations, while the other groups pause. The busy groups corresponding to right children perform computations in the second part, but only if their left-sibling group was idle during part one. Consider the ﬁrst part. Each processor in a busy group G is assigned a set of processors in the sibling group G as follows. The processors 1 2 in G are partitioned into as many subsets as there are active elements in G , the sizes of subsets 2 1 are constant (G is large) and diﬀer by at most one. The active processor with rank k in the list 1 in G is assigned the kth subset of group G . Each active processor of G checks on the assigned 1 2 1 subset and adds all its active blocks to the list. This completes part one. The second part is similar, but the roles between sibling groups are reversed. For each pair of sibling groups, if at least one of the groups is busy then after part two all the active processors in these groups are connected in a combined list. This list is processed during the third part. The ranks and the size of the list are computed and broadcast to all the elements of the list by the procedure of pointer jumping (see [25]). If the size of the list is big enough for the group of the parent node to become large then the group of the parent node becomes busy in the next phase. To synchronize the process, we need to control the duration of the ﬁrst two parts of a phase, when the processors check on the assigned 13 ##LTLine##

text: list,

text: and

text: if

text: there

text: is

text: a

text: processor

text: assigned

text: to

text: each

text: item

text: in

text: the

text: list

text: then

text: the

text: task

text: can

text: be

text: completed

text: in

text: O

text: time

text: logarithmic

text: in

text: the

text: length

text: of

text: the

text: list.

text: In

text: the

text: case

text: of

text: a

text: temporary

text: tree,

text: its

text: depth

text: is

text: (log(m/n)),

text: O

text: and

text: it

text: is

text: obtained

text: in

text: time

text: (m/n).

text: Stage

text: A

text: list

text: of

text: active

text: blocks

text: is

text: built.

text: This

text: list

text: consists

text: of

text: contact

text: segments.

text: We

text: use

text: the

text: following

text: deﬁnitions.

text: A

text: set

text: S

text: of

text: processors

text: is

text: large

text: if

text: it

text: contains

text: at

text: least

text: f

text: f

text: S

text: active

text: elements,

text: where

text: S

text: denotes

text: the

text: size

text: of

text: S.

text: A

text: p

text: s

text: partition

text: tree

text: (PT

text: in

text: short)

text: is

text: a

text: full

text: binary

text: tree

text: with

text: nodes

text: labeled

text: by

text: intervals

text: of

text: integers.

text: The

text: root

text: is

text: labeled

text: by

text: n].

text: If

text: a

text: node

text: v

text: is

text: labeled

text: by

text: [a,

text: b]

text: and

text: b

text: a

text: then

text: v

text: is

text: an

text: internal

text: node,

text: its

text: left

text: child

text: is

text: labeled

text: by

text: [a,

text: (a

text: b

text: and

text: the

text: right

text: child

text: is

text: labeled

text: by

text: (a

text: b].

text: Leaves

text: are

text: labeled

text: by

text: intervals

text: of

text: unit

text: length.

text: A

text: processor

text: with

text: physical

text: index

text: i

text: is

text: associated

text: with

text: node

text: v

text: if

text: i

text: belongs

text: to

text: the

text: label

text: of

text: v.

text: The

text: processors

text: associated

text: with

text: a

text: node

text: of

text: tree

text: PT

text: are

text: referred

text: to

text: as

text: the

text: group

text: of

text: this

text: node.

text: A

text: node

text: is

text: large

text: if

text: its

text: group

text: is

text: large.

text: An

text: active

text: processor

text: may

text: check

text: another

text: processor

text: p

text: for

text: being

text: active,

text: p

text: being

text: operational

text: or

text: not.

text: This

text: is

text: done

text: by

text: scanning

text: the

text: block

text: assigned

text: to

text: p

text: and

text: attempting

text: to

text: read

text: each

text: consecutive

text: cell,

text: until

text: the

text: information

text: that

text: the

text: block

text: is

text: active

text: is

text: found.

text: This

text: information

text: is

text: in

text: the

text: ﬁrst

text: operational

text: non-blank

text: cell

text: in

text: the

text: block,

text: which

text: also

text: happens

text: to

text: be

text: this

text: block’s

text: contact

text: address.

text: The

text: algorithm

text: building

text: the

text: list

text: works

text: in

text: phases

text: corresponding

text: to

text: the

text: levels

text: of

text: tree

text: PT.

text: During

text: a

text: phase,

text: processors

text: are

text: partitioned

text: into

text: groups

text: associated

text: with

text: nodes

text: at

text: the

text: corresponding

text: level

text: of

text: the

text: tree.

text: A

text: group

text: is

text: either

text: busy

text: or

text: not.

text: If

text: a

text: group

text: is

text: busy

text: then:

text: Each

text: processor

text: in

text: the

text: group

text: is

text: aware

text: of

text: this.

text: The

text: active

text: processors

text: in

text: the

text: group

text: are

text: organized

text: in

text: a

text: list,

text: and

text: each

text: element

text: of

text: the

text: list

text: knows

text: its

text: rank,

text: that

text: is,

text: the

text: distance

text: from

text: the

text: head

text: of

text: the

text: list.

text: Each

text: element

text: knows

text: the

text: number

text: of

text: elements

text: in

text: the

text: list.

text: Groups

text: correspond

text: to

text: leaves

text: of

text: PT

text: during

text: the

text: ﬁrst

text: phase

text: of

text: the

text: algorithm.

text: Processors

text: in

text: each

text: such

text: a

text: group

text: check

text: each

text: other,

text: and

text: if

text: the

text: group

text: is

text: large

text: then

text: the

text: processors

text: arrange

text: themselves

text: in

text: a

text: list,

text: compute

text: ranks

text: and

text: the

text: group

text: becomes

text: busy.

text: In

text: general,

text: once

text: a

text: phase

text: has

text: been

text: completed,

text: the

text: computation

text: proceeds

text: to

text: the

text: next

text: one,

text: corresponding

text: to

text: the

text: next

text: level

text: of

text: PT

text: towards

text: the

text: root.

text: Let

text: us

text: consider

text: such

text: a

text: phase,

text: it

text: consists

text: of

text: three

text: parts.

text: During

text: the

text: ﬁrst

text: part,

text: the

text: busy

text: groups

text: corresponding

text: to

text: nodes

text: being

text: left

text: children

text: perform

text: computations,

text: while

text: the

text: other

text: groups

text: pause.

text: The

text: busy

text: groups

text: corresponding

text: to

text: right

text: children

text: perform

text: computations

text: in

text: the

text: second

text: part,

text: but

text: only

text: if

text: their

text: left-sibling

text: group

text: was

text: idle

text: during

text: part

text: one.

text: Consider

text: the

text: ﬁrst

text: part.

text: Each

text: processor

text: in

text: a

text: busy

text: group

text: G

text: is

text: assigned

text: a

text: set

text: of

text: processors

text: in

text: the

text: sibling

text: group

text: G

text: as

text: follows.

text: The

text: processors

text: in

text: G

text: are

text: partitioned

text: into

text: as

text: many

text: subsets

text: as

text: there

text: are

text: active

text: elements

text: in

text: G

text: the

text: sizes

text: of

text: subsets

text: are

text: constant

text: (G

text: is

text: large)

text: and

text: diﬀer

text: by

text: at

text: most

text: one.

text: The

text: active

text: processor

text: with

text: rank

text: k

text: in

text: the

text: list

text: in

text: G

text: is

text: assigned

text: the

text: kth

text: subset

text: of

text: group

text: G

text: Each

text: active

text: processor

text: of

text: G

text: checks

text: on

text: the

text: assigned

text: subset

text: and

text: adds

text: all

text: its

text: active

text: blocks

text: to

text: the

text: list.

text: This

text: completes

text: part

text: one.

text: The

text: second

text: part

text: is

text: similar,

text: but

text: the

text: roles

text: between

text: sibling

text: groups

text: are

text: reversed.

text: For

text: each

text: pair

text: of

text: sibling

text: groups,

text: if

text: at

text: least

text: one

text: of

text: the

text: groups

text: is

text: busy

text: then

text: after

text: part

text: two

text: all

text: the

text: active

text: processors

text: in

text: these

text: groups

text: are

text: connected

text: in

text: a

text: combined

text: list.

text: This

text: list

text: is

text: processed

text: during

text: the

text: third

text: part.

text: The

text: ranks

text: and

text: the

text: size

text: of

text: the

text: list

text: are

text: computed

text: and

text: broadcast

text: to

text: all

text: the

text: elements

text: of

text: the

text: list

text: by

text: the

text: procedure

text: of

text: pointer

text: jumping

text: (see

text: If

text: the

text: size

text: of

text: the

text: list

text: is

text: big

text: enough

text: for

text: the

text: group

text: of

text: the

text: parent

text: node

text: to

text: become

text: large

text: then

text: the

text: group

text: of

text: the

text: parent

text: node

text: becomes

text: busy

text: in

text: the

text: next

text: phase.

text: To

text: synchronize

text: the

text: process,

text: we

text: need

text: to

text: control

text: the

text: duration

text: of

text: the

text: ﬁrst

text: two

text: parts

text: of

text: a

text: phase,

text: when

text: the

text: processors

text: check

text: on

text: the

text: assigned

text: ##LTLine##


text: Stage 6: A memory tree is constructed. First the active processors are dispersed among good segments in a balanced way, that is, they locate such segments that the distance, measured in terms of oﬀsets, between any two consecutive ones is the same, and is Θ(m/n). This is achieved as follows. A copy of the list of processors is ﬁrst made, by way of making copies of the contents of the relevant cells in the contact segments of each processor. It is then dispatched towards the leaves of the block trees, starting from the root. While on its way, this list may be partitioned into smaller lists, they are called traveling lists. These lists travel in a binary-search fashion, and when a leaf of the block tree is encountered then they continue their way through the respective temporary tree. Let L be such a list, and let it be at node v of either the block tree or a temporary tree. The processor P at the head of L reads the oﬀsets of both v and its left child, and calculates the smallest virtual address in the right child of v. This information is then broadcast to all the processors on list L by pointer jumping, in time proportional to the logarithm of the size of the list. If a processor in the list is the ﬁrst one with its address in the right subtree of v then it cuts itself from the predecessor, if any, and becomes the head of a new list consisting of the processors that follow it in the original list. This new list moves down to the right child of v, the remaining shortened one goes to the left child. Eventually the traveling lists become single nodes which traverse either the block tree or temporary trees in a binary-search fashion. The second part of this stage starts from the processors dispersed among the items of the list of good segments in a balanced way, the ﬁrst processor at the ﬁrst node of the list. The good segments between that of processor P and that of processor P are treated as the portion of i i+1 segments assigned to processor P . The sizes of such portions are 2r, for some 2r = Θ(m/n). Every i active processor can be assumed to know the number r. Each processor organizes 2r cells of its initial portion of good segments into a complete binary-search tree. The list of active processors yields a list of these trees. We apply the conversion procedure and obtain a complete binary-search tree, and this is the memory tree. O Lemma 4 It takes (log n log m) steps to build the memory tree. O Proof: Each partitioning of a traveling list takes (log n) steps. The length of the path from the O (cid:3) root of the block tree to a leaf of a temporary tree in a block is (log m). Stage 7: A decoding algorithm is run. − By Lemma 1, the number of active processors is at least γn, where γ = 1 (fp+f3). All of them 2 are arranged in a list corresponding to the list of blocks. We want to provide the ﬁrst γn processors in this list with the whole input distributed among all n processors, active or not. To this end we use a variant of information dispersal method, based on an idea similar to that underlying the Reed-Solomon error-correcting codes ([32, 39]). The original input is ﬁrst partitioned into γn input strings u , . . ., u , each comprised of some t bits. These input strings will be interpreted as 1 γn F elements of the ﬁnite ﬁeld = GF(2t). We take the smallest t such that the inequality 2t > γn (cid:104) (cid:105) (cid:104) (cid:105) (cid:104) (cid:105) holds. We assume that the input is encoded as a sequence of n packets 1, v , 2, v , . . ., n, v , (cid:104) (cid:105) 1 2 n and packet i, v is delivered to the processor with the physical index i, faulty or not. Each packet (cid:104) (cid:105) i i, v is a pair of identiﬁer i and value v . The values v are sequences of t bits each, they are i i i F F interpreted as elements of ﬁeld , with the arithmetic of operations on them deﬁned as in . The values satisfy v = g(ωi), where the following holds: i 15 ##LTLine##

text: Stage

label: paragraph

text: A

text: memory

text: tree

text: is

text: constructed.

text: First

text: the

text: active

text: processors

text: are

text: dispersed

text: among

text: good

text: segments

text: in

text: a

text: balanced

text: way,

text: that

text: is,

text: they

text: locate

text: such

text: segments

text: that

text: the

text: distance,

text: measured

text: in

text: terms

text: of

text: oﬀsets,

text: between

text: any

text: two

text: consecutive

text: ones

text: is

text: the

text: same,

text: and

text: is

text: Θ(m/n).

text: This

text: is

text: achieved

text: as

text: follows.

text: A

text: copy

text: of

text: the

text: list

text: of

text: processors

text: is

text: ﬁrst

text: made,

text: by

text: way

text: of

text: making

text: copies

text: of

text: the

text: contents

text: of

text: the

text: relevant

text: cells

text: in

text: the

text: contact

text: segments

text: of

text: each

text: processor.

text: It

text: is

text: then

text: dispatched

text: towards

text: the

text: leaves

text: of

text: the

text: block

text: trees,

text: starting

text: from

text: the

text: root.

text: While

text: on

text: its

text: way,

text: this

text: list

text: may

text: be

text: partitioned

text: into

text: smaller

text: lists,

text: they

text: are

text: called

text: traveling

text: lists.

text: These

text: lists

text: travel

text: in

text: a

text: binary-search

text: fashion,

text: and

text: when

text: a

text: leaf

text: of

text: the

text: block

text: tree

text: is

text: encountered

text: then

text: they

text: continue

text: their

text: way

text: through

text: the

text: respective

text: temporary

text: tree.

text: Let

text: L

text: be

text: such

text: a

text: list,

text: and

text: let

text: it

text: be

text: at

text: node

text: v

text: of

text: either

text: the

text: block

text: tree

text: or

text: a

text: temporary

text: tree.

text: The

text: processor

text: P

text: at

text: the

text: head

text: of

text: L

text: reads

text: the

text: oﬀsets

text: of

text: both

text: v

text: and

text: its

text: left

text: child,

text: and

text: calculates

text: the

text: smallest

text: virtual

text: address

text: in

text: the

text: right

text: child

text: of

text: v.

text: This

text: information

text: is

text: then

text: broadcast

text: to

text: all

text: the

text: processors

text: on

text: list

text: L

text: by

text: pointer

text: jumping,

text: in

text: time

text: proportional

text: to

text: the

text: logarithm

text: of

text: the

text: size

text: of

text: the

text: list.

text: If

text: a

text: processor

text: in

text: the

text: list

text: is

text: the

text: ﬁrst

text: one

text: with

text: its

text: address

text: in

text: the

text: right

text: subtree

text: of

text: v

text: then

text: it

text: cuts

text: itself

text: from

text: the

text: predecessor,

text: if

text: any,

text: and

text: becomes

text: the

text: head

text: of

text: a

text: new

text: list

text: consisting

text: of

text: the

text: processors

text: that

text: follow

text: it

text: in

text: the

text: original

text: list.

text: This

text: new

text: list

text: moves

text: down

text: to

text: the

text: right

text: child

text: of

text: v,

text: the

text: remaining

text: shortened

text: one

text: goes

text: to

text: the

text: left

text: child.

text: Eventually

text: the

text: traveling

text: lists

text: become

text: single

text: nodes

text: which

text: traverse

text: either

text: the

text: block

text: tree

text: or

text: temporary

text: trees

text: in

text: a

text: binary-search

text: fashion.

text: The

text: second

text: part

text: of

text: this

text: stage

text: starts

text: from

text: the

text: processors

text: dispersed

text: among

text: the

text: items

text: of

text: the

text: list

text: of

text: good

text: segments

text: in

text: a

text: balanced

text: way,

text: the

text: ﬁrst

text: processor

text: at

text: the

text: ﬁrst

text: node

text: of

text: the

text: list.

text: The

text: good

text: segments

text: between

text: that

text: of

text: processor

text: P

text: and

text: that

text: of

text: processor

text: P

text: are

text: treated

text: as

text: the

text: portion

text: of

text: i

text: segments

text: assigned

text: to

text: processor

text: P

text: The

text: sizes

text: of

text: such

text: portions

text: are

text: for

text: some

text: Θ(m/n).

text: Every

text: i

text: active

text: processor

text: can

text: be

text: assumed

text: to

text: know

text: the

text: number

text: r.

text: Each

text: processor

text: organizes

text: cells

text: of

text: its

text: initial

text: portion

text: of

text: good

text: segments

text: into

text: a

text: complete

text: binary-search

text: tree.

text: The

text: list

text: of

text: active

text: processors

text: yields

text: a

text: list

text: of

text: these

text: trees.

text: We

text: apply

text: the

text: conversion

text: procedure

text: and

text: obtain

text: a

text: complete

text: binary-search

text: tree,

text: and

text: this

text: is

text: the

text: memory

text: tree.

text: O

text: Lemma

text: It

text: takes

text: (log

text: n

text: log

text: m)

text: steps

text: to

text: build

text: the

text: memory

text: tree.

text: O

text: Proof:

text: Each

text: partitioning

text: of

text: a

text: traveling

text: list

text: takes

text: (log

text: n)

text: steps.

text: The

text: length

text: of

text: the

text: path

text: from

text: the

text: O

text: root

text: of

text: the

text: block

text: tree

text: to

text: a

text: leaf

text: of

text: a

text: temporary

text: tree

text: in

text: a

text: block

text: is

text: (log

text: m).

text: Stage

text: A

text: decoding

text: algorithm

text: is

text: run.

text: By

text: Lemma

text: the

text: number

text: of

text: active

text: processors

text: is

text: at

text: least

text: γn,

text: where

text: γ

text: All

text: of

text: them

text: are

text: arranged

text: in

text: a

text: list

text: corresponding

text: to

text: the

text: list

text: of

text: blocks.

text: We

text: want

text: to

text: provide

text: the

text: ﬁrst

text: γn

text: processors

text: in

text: this

text: list

text: with

text: the

text: whole

text: input

text: distributed

text: among

text: all

text: n

text: processors,

text: active

text: or

text: not.

text: To

text: this

text: end

text: we

text: use

text: a

text: variant

text: of

text: information

text: dispersal

text: method,

text: based

text: on

text: an

text: idea

text: similar

text: to

text: that

text: underlying

text: the

text: Reed-Solomon

text: error-correcting

text: codes

text: The

text: original

text: input

text: is

text: ﬁrst

text: partitioned

text: into

text: γn

text: input

text: strings

text: u

text: u

text: each

text: comprised

text: of

text: some

text: t

text: bits.

text: These

text: input

text: strings

text: will

text: be

text: interpreted

text: as

text: γn

text: F

text: elements

text: of

text: the

text: ﬁnite

text: ﬁeld

text: We

text: take

text: the

text: smallest

text: t

text: such

text: that

text: the

text: inequality

text: γn

text: holds.

text: We

text: assume

text: that

text: the

text: input

text: is

text: encoded

text: as

text: a

text: sequence

text: of

text: n

text: packets

text: v

text: v

text: n,

text: v

text: n

text: and

text: packet

text: i,

text: v

text: is

text: delivered

text: to

text: the

text: processor

text: with

text: the

text: physical

text: index

text: i,

text: faulty

text: or

text: not.

text: Each

text: packet

text: i

text: i,

text: v

text: is

text: a

text: pair

text: of

text: identiﬁer

text: i

text: and

text: value

text: v

text: The

text: values

text: v

text: are

text: sequences

text: of

text: t

text: bits

text: each,

text: they

text: are

text: i

text: i

text: i

text: F

text: F

text: interpreted

text: as

text: elements

text: of

text: ﬁeld

text: with

text: the

text: arithmetic

text: of

text: operations

text: on

text: them

text: deﬁned

text: as

text: in

text: The

text: values

text: satisfy

text: v

text: g(ωi),

text: where

text: the

text: following

text: holds:

text: i

text: ##LTLine##


text: [20] Phillip B. Gibbons. A more practical PRAM model. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 158–168, 1989. [21] Jan Friso Groote, Wim H. Hesselink, Sjouke Mauw, and Rogier Vermeulen. An algorithm for the asynchronous Write-All problem based on process collision. Distributed Computing, 14(2):75–81, 2001. [22] Tim J. Harris. A survey of PRAM simulation techniques. ACM Computing Surveys, 26(2):187– 206, 1994. [23] Maurice Herlihy. Impossibility results for asynchronous PRAM. In Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 327–336, 1991. [24] Piotr Indyk. On word-level parallelism in fault-tolerant computing. In Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1046 of Lecture Notes in Computer Science, pages 193–204. Springer, 1996. [25] Joseph J´aJ´a. An Introduction to Parallel Algorithms. Addison-Wesley, 1992. [26] Paris C. Kanellakis and Alex A. Shvartsman. Fault-Tolerant Parallel Computation. Kluwer Academic Publishers, 1997. [27] Paris C. Kanellakis and Alexander A. Shvartsman. Eﬃcient parallel algorithms can be made robust. Distributed Computing, 5(4):201–217, 1992. [28] Zvi M. Kedem, Krishna V. Palem, A. Raghunathan, and Paul G. Spirakis. Combining tentative and deﬁnite executions for very fast dependable parallel computing. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), pages 381–390, 1991. [29] Zvi M. Kedem, Krishna V. Palem, and Paul G. Spirakis. Eﬃcient robust parallel computations. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 138–148, 1990. [30] Spyros C. Kontogiannis, Grammati E. Pantziou, Paul G. Spirakis, and Moti Yung. Robust parallel computations through randomization. Theory of Computing Systems, 33(5/6):427–464, 2000. [31] Frank Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, 1992. [32] Yuh-Dauh Lyuu. Information Dispersal and Parallel Computation. Cambridge University Press, 1993. [33] Florence J. MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. North- Holland, 1977. [34] Charles U. Martel, Arvin Park, and Ramesh Subramonian. Work-optimal asynchronous algo- rithms for shared memory parallel computers. SIAM Journal on Comput., 21(6):1070–1099, 1992. 22

label: reference

text: Phillip

text: B.

text: Gibbons.

text: A

text: more

text: practical

text: PRAM

text: model.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: Symposium

text: on

text: Parallel

text: Algorithms

text: and

text: Architectures

text: (SPAA),

text: pages

text: Jan

text: Friso

text: Groote,

text: Wim

text: H.

text: Hesselink,

text: Sjouke

text: Mauw,

text: and

text: Rogier

text: Vermeulen.

text: An

text: algorithm

text: for

text: the

text: asynchronous

text: Write-All

text: problem

text: based

text: on

text: process

text: collision.

text: Distributed

text: Computing,

text: Tim

text: J.

text: Harris.

text: A

text: survey

text: of

text: PRAM

text: simulation

text: techniques.

text: ACM

text: Computing

text: Surveys,

text: Maurice

text: Herlihy.

text: Impossibility

text: results

text: for

text: asynchronous

text: PRAM.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: ACM

text: Symposium

text: on

text: Parallel

text: Algorithms

text: and

text: Architectures

text: (SPAA),

text: pages

text: Piotr

text: Indyk.

text: On

text: word-level

text: parallelism

text: in

text: fault-tolerant

text: computing.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: Symposium

text: on

text: Theoretical

text: Aspects

text: of

text: Computer

text: Science

text: (STACS),

text: volume

text: of

text: Lecture

text: Notes

text: in

text: Computer

text: Science,

text: pages

text: Springer,

text: Joseph

text: J´aJ´a.

text: An

text: Introduction

text: to

text: Parallel

text: Algorithms.

text: Addison-Wesley,

text: Paris

text: C.

text: Kanellakis

text: and

text: Alex

text: A.

text: Shvartsman.

text: Fault-Tolerant

text: Parallel

text: Computation.

text: Kluwer

text: Academic

text: Publishers,

text: Paris

text: C.

text: Kanellakis

text: and

text: Alexander

text: A.

text: Shvartsman.

text: Eﬃcient

text: parallel

text: algorithms

text: can

text: be

text: made

text: robust.

text: Distributed

text: Computing,

text: Zvi

text: M.

text: Kedem,

text: Krishna

text: V.

text: Palem,

text: A.

text: Raghunathan,

text: and

text: Paul

text: G.

text: Spirakis.

text: Combining

text: tentative

text: and

text: deﬁnite

text: executions

text: for

text: very

text: fast

text: dependable

text: parallel

text: computing.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: ACM

text: Symposium

text: on

text: Theory

text: of

text: Computing

text: (STOC),

text: pages

text: Zvi

text: M.

text: Kedem,

text: Krishna

text: V.

text: Palem,

text: and

text: Paul

text: G.

text: Spirakis.

text: Eﬃcient

text: robust

text: parallel

text: computations.

text: In

text: Proceedings

text: of

text: the

text: Annual

text: ACM

text: Symposium

text: on

text: Theory

text: of

text: Computing

text: (STOC),

text: pages

text: Spyros

text: C.

text: Kontogiannis,

text: Grammati

text: E.

text: Pantziou,

text: Paul

text: G.

text: Spirakis,

text: and

text: Moti

text: Yung.

text: Robust

text: parallel

text: computations

text: through

text: randomization.

text: Theory

text: of

text: Computing

text: Systems,

text: Frank

text: Thomson

text: Leighton.

text: Introduction

text: to

text: Parallel

text: Algorithms

text: and

text: Architectures:

text: Arrays,

text: Trees,

text: Hypercubes.

text: Morgan

text: Kaufmann

text: Publishers,

text: Yuh-Dauh

text: Lyuu.

text: Information

text: Dispersal

text: and

text: Parallel

text: Computation.

text: Cambridge

text: University

text: Press,

text: Florence

text: J.

text: MacWilliams

text: and

text: Neil

text: J.

text: A.

text: Sloane.

text: The

text: Theory

text: of

text: Error-Correcting

text: Codes.

text: North-

text: Holland,

text: Charles

text: U.

text: Martel,

text: Arvin

text: Park,

text: and

text: Ramesh

text: Subramonian.

text: Work-optimal

text: asynchronous

text: algo-

text: rithms

text: for

text: shared

text: memory

text: parallel

text: computers.

text: SIAM

text: Journal

text: on

text: Comput.,


text: 12 WILLIAM CHEN, SHIMON GARTI, AND THILO WEINERT are connected to each other by an edge and the other if they are not.) Given a β < λ and an α < β we inductively deﬁne the { | (cid:54) (cid:54) (cid:54) ∧ { } ∈ } sets Γ(λα + β) = λγ + δ α γ δ β λα + β, λγ + δ ∆ . The induction is layered. The top layer of the induction has length λ and in step β < λ we deﬁne all sets Γ(λα + β) with α < β. The second layer of the induction has length β and in step α < β we deﬁne the set Γ(λα + β). The third layer of the induction has length κ where in every step fewer than κ ordinals are added to Γ(λα + β) as elements. Suppose that we are in step ζ of the third layer of the induction and previous steps µ < ζ have added the ordinals λγ + δ (ν < ϑ , ξ < ι ) to Γ(λα + β) and have deﬁned σ . As induction hypothesis we assume that for all µ < ζ we µ,ν µ,ν,ξ µ µ,ν µ ∀ have (ϑ < κ and ν < ϑ : ι < κ). Using κ’s regularity we now choose a ρ < κ satisfying µ µ µ,ν ζ (19) ρ > sup σ , ζ ξ ξ<ζ − (cid:2)∩ { (cid:3)| ∧ } 1 (20) b (ρ ) > sup(e(β, ζ) γ µ < ζ ν < ϑ ), e(β,ζ) ζ µ,ν µ − { − (cid:2) | (cid:3) ∧ ∧ (cid:54) } 1 1 (21) b (ρ ) > sup( b b (α) µ < ζ ν < ϑ e(β, ζ) γ ), e(β,ζ) ζ γµ,ν γµ,ν µ µ,ν − { − | (cid:48) ∧ (cid:48) ∧ (cid:54) } 1 1 (cid:48) (cid:48) (cid:48) (cid:48) (22) b (ρ ) > sup( b b (γ ) µ, µ < ζ ν, ν < ϑ e(β, ζ) γ < γ ). e(β,ζ) ζ γµ,ν γµ,ν µ ,ν µ µ ,ν µ,ν and set σ := d (ρ ). Note that together with (15) and (19) this implies that ζ β ζ ∀ (23) ξ < κ(ξ < ρ < σ ). ξ ξ (cid:104) | (cid:105) Now let γ ν < ϑ be the increasing enumeration of the set ζ,ν ζ { − | ∈ \ ∧ − (cid:54) − } 1 1 1 (24) b (ξ) ξ σ ρ b (ρ ) b (ξ) e(β,ζ) ζ ζ e(β,ζ) ζ e(β,ζ)

text: WILLIAM

text: CHEN,

text: SHIMON

text: GARTI,

text: AND

text: THILO

text: WEINERT

text: are

text: connected

text: to

text: each

text: other

text: by

text: an

text: edge

text: and

text: the

text: other

text: if

text: they

text: are

text: not.)

text: Given

text: a

text: β

text: λ

text: and

text: an

text: α

text: β

text: we

text: inductively

text: deﬁne

text: the

text: sets

text: Γ(λα

text: β)

text: λγ

text: δ

text: α

text: γ

text: δ

text: β

text: λα

text: β,

text: λγ

text: δ

text: The

text: induction

text: is

text: layered.

text: The

text: top

text: layer

text: of

text: the

text: induction

text: has

text: length

text: λ

text: and

text: in

text: step

text: β

text: λ

text: we

text: deﬁne

text: all

text: sets

text: Γ(λα

text: β)

text: with

text: α

text: β.

text: The

text: second

text: layer

text: of

text: the

text: induction

text: has

text: length

text: β

text: and

text: in

text: step

text: α

text: β

text: we

text: deﬁne

text: the

text: set

text: Γ(λα

text: β).

text: The

text: third

text: layer

text: of

text: the

text: induction

text: has

text: length

text: κ

text: where

text: in

text: every

text: step

text: fewer

text: than

text: κ

text: ordinals

text: are

text: added

text: to

text: Γ(λα

text: β)

text: as

text: elements.

text: Suppose

text: that

text: we

text: are

text: in

text: step

text: ζ

text: of

text: the

text: third

text: layer

text: of

text: the

text: induction

text: and

text: previous

text: steps

text: µ

text: ζ

text: have

text: added

text: the

text: ordinals

text: λγ

text: δ

text: (ν

text: ϑ

text: ξ

text: ι

text: to

text: Γ(λα

text: β)

text: and

text: have

text: deﬁned

text: σ

text: As

text: induction

text: hypothesis

text: we

text: assume

text: that

text: for

text: all

text: µ

text: ζ

text: we

text: µ,ν

text: µ,ν,ξ

text: µ

text: µ,ν

text: µ

text: have

text: (ϑ

text: κ

text: and

text: ν

text: ϑ

text: ι

text: κ).

text: Using

text: κ’s

text: regularity

text: we

text: now

text: choose

text: a

text: ρ

text: κ

text: satisfying

text: µ

text: µ

text: µ,ν

text: ζ

text: ρ

text: sup

text: σ

text: ζ

text: ξ

text: ξ<ζ

text: b

text: (ρ

text: sup(e(β,

text: ζ)

text: γ

text: µ

text: ζ

text: ν

text: ϑ

text: e(β,ζ)

text: ζ

text: µ,ν

text: µ

text: b

text: (ρ

text: sup(

text: b

text: b

text: (α)

text: µ

text: ζ

text: ν

text: ϑ

text: e(β,

text: ζ)

text: γ

text: e(β,ζ)

text: ζ

text: γµ,ν

text: γµ,ν

text: µ

text: µ,ν

text: b

text: (ρ

text: sup(

text: b

text: b

text: (γ

text: µ,

text: µ

text: ζ

text: ν,

text: ν

text: ϑ

text: e(β,

text: ζ)

text: γ

text: γ

text: e(β,ζ)

text: ζ

text: γµ,ν

text: γµ,ν

text: µ

text: ,ν

text: µ

text: µ

text: ,ν

text: µ,ν

text: and

text: set

text: σ

text: d

text: (ρ

text: Note

text: that

text: together

text: with

text: and

text: this

text: implies

text: that

text: ζ

text: β

text: ζ

text: ξ

text: κ(ξ

text: ρ

text: σ

text: ξ

text: ξ

text: Now

text: let

text: γ

text: ν

text: ϑ

text: be

text: the

text: increasing

text: enumeration

text: of

text: the

text: set

text: ζ,ν

text: ζ

text: b

text: (ξ)

text: ξ

text: σ

text: ρ

text: b

text: (ρ

text: b

text: (ξ)

text: e(β,ζ)

text: ζ

text: ζ

text: e(β,ζ)

text: ζ

text: e(β,ζ)


text: 18 WILLIAM CHEN, SHIMON GARTI, AND THILO WEINERT • • • ∗ (cid:104) |(cid:105) | ∈ ⊆ | Let dα : α∈< be a sequ∗enc•e| witnessing ⊆. For∗ every α ∈B0, choose β(α) < ω1(cid:22) so th×at dβ Sαi . Since κ > is regula(cid:3)r, there is a B [B ]κ and β < so that d ∗ Si for all α B , and therefore c (B d ∗) is constant. 1 0 β α 1 1 β 4. Partition Relations opposite the Unbounding Number and the Stick-Principle • −(cid:54) → ℵ | Takahashi proved in [987•Ta] that one can derive ω1ω (ω1ω, 3)2 in the system ZFC +d = 1 + . The same can be done in ℵ | the system ZFC +b = 1 + as shown in [017LW]. We now show that the latter system is also suﬃcient to derive the negative partition relation shown to follow from CH by Baumgartner and Hajnal•in [987BH]. | −(cid:54) → Theorem 4.1 ([017LW]). Suppose that κ is regular and λ = κ+ = bκ = (κ). Then λκ (λκ, 3)2. • | −(cid:54) → Corollary 4.2. If κ is regular, λ = κ+ = b = (κ), then α (λκ, 3)2 for all α < λ2. κ • | −(cid:54) → Theorem 4.3. Suppose that κ is an inﬁnite regular cardinal and λ = κ+ = b = (κ). Then λ2 (λκ, 4)2. κ Proof. As in the proof of Theorem 2.9, we begin by ﬁxing ←→ (37) A bijection b : ξ κ, ξ −→ (38) an increasing function u : κ κ, ξ ∈ κ (39) a set s [λ] . ξ More speciﬁcally we do this in a way such that { | } κ (40) u ξ < λ is an unbounded family of functions in κ such that ξ ∀ ∀ (cid:54)∗ (41) ξ < λ ν < ξ(u u ), ν ξ • { | } | ∀ ∈ ∃ ⊆ λ (42) s ξ < λ witnesses (κ), i.e. X [λ] ξ < λ(s X). ξ ξ

text: WILLIAM

text: CHEN,

text: SHIMON

text: GARTI,

text: AND

text: THILO

text: WEINERT

text: Let

text: dα

text: α∈<

text: be

text: a

text: sequ∗enc•e|

text: witnessing

text: For∗

text: every

text: α

text: choose

text: β(α)

text: so

text: th×at

text: dβ

text: Sαi

text: Since

text: κ

text: is

text: there

text: is

text: a

text: B

text: [B

text: ]κ

text: and

text: β

text: so

text: that

text: d

text: Si

text: for

text: all

text: α

text: B

text: and

text: therefore

text: c

text: (B

text: d

text: is

text: constant.

text: β

text: α

text: β

label: section

text: Partition

text: Relations

text: opposite

text: the

text: Unbounding

text: Number

text: and

text: the

text: Stick-Principle

text: ℵ

text: Takahashi

text: proved

text: in

text: that

text: one

text: can

text: derive

text: ω1ω

text: in

text: the

text: system

text: ZFC

text: +d

text: The

text: same

text: can

text: be

text: done

text: in

text: ℵ

text: the

text: system

text: ZFC

text: +b

text: as

text: shown

text: in

text: We

text: now

text: show

text: that

text: the

text: latter

text: system

text: is

text: also

text: suﬃcient

text: to

text: derive

text: the

text: negative

text: partition

text: relation

text: shown

text: to

text: follow

text: from

text: CH

text: by

text: Baumgartner

text: and

text: Hajnal•in

text: Theorem

text: Suppose

text: that

text: κ

text: is

text: regular

text: and

text: λ

text: κ+

text: bκ

text: (κ).

text: Then

text: λκ

text: (λκ,

text: Corollary

text: If

text: κ

text: is

text: regular,

text: λ

text: κ+

text: b

text: (κ),

text: then

text: α

text: (λκ,

text: for

text: all

text: α

text: κ

text: Theorem

text: Suppose

text: that

text: κ

text: is

text: an

text: inﬁnite

text: regular

text: cardinal

text: and

text: λ

text: κ+

text: b

text: (κ).

text: Then

text: λ2

text: (λκ,

text: κ

text: Proof.

text: As

text: in

text: the

text: proof

text: of

text: Theorem

text: we

text: begin

text: by

text: ﬁxing

text: A

text: bijection

text: b

text: ξ

text: κ,

text: ξ

text: an

text: increasing

text: function

text: u

text: κ

text: κ,

text: ξ

text: κ

text: a

text: set

text: s

text: [λ]

text: ξ

text: More

text: speciﬁcally

text: we

text: do

text: this

text: in

text: a

text: way

text: such

text: that

text: κ

text: u

text: ξ

text: λ

text: is

text: an

text: unbounded

text: family

text: of

text: functions

text: in

text: κ

text: such

text: that

text: ξ

text: ξ

text: λ

text: ν

text: ξ(u

text: u

text: ν

text: ξ

text: λ

text: s

text: ξ

text: λ

text: witnesses

text: (κ),

text: i.e.

text: X

text: [λ]

text: ξ

text: λ(s

text: X).

text: ξ

text: ξ


text: 24 WILLIAM CHEN, SHIMON GARTI, AND THILO WEINERT ℵ ℵ sets, cf. [994JS]. The existence of a Luzin set does not entail d = 1: starting from a model of CH, add 2-many Cohen reals. Each uncountable subset of the Cohen reals is nonmeagre, since it cannot be a subset of any Borel meagre set (which lives in ℵ an intermediate extension of just countably many of the Cohen factors). However, d = in this model. 2 −(cid:54) → Theorem 5.1. Suppose there exists a Luzin set. Then there is a colouring proving ω [ω ]2 with no triangle with edges of 1 1 ω three diﬀerent colours. (cid:104) | (cid:105) ℵ (cid:54) Proof. Fix a Luzin set f α < ω of size . For α < β < ω , deﬁne ∆(α, β) to be the least n < ω such that f (n) = f (n). α 1 1 1 α β → − → Let s : ω ω be a function so that for every i < ω, s 1[i] is inﬁnite. Deﬁne the colouring c : [ω ]2 ω to be 1 c(α, β) := s(∆(α, β)). There are no triangles which get three colours from c. Claim 5.2. For distinct α, β, γ < ω , the smaller two among ∆(α, β), ∆(β, γ), ∆(γ, α) are equal. 1 (cid:54) Proof of Claim. Towards a contradiction, suppose ∆(α, γ) < ∆(β, γ) D(α, β). By deﬁnition of ∆, (cid:54) f (∆(α, γ)) = f (∆(α, γ)), α γ but since ∆(α, γ) < ∆(β, γ), f (∆(α, γ)) = f (∆(α, γ)). γ β In total, (cid:54) f (∆(α, γ)) = f (∆(α, γ)) α β (cid:13) but this contradicts ∆(α, γ) < D(α, β). c −(cid:54) → Now we show that c satisﬁes ω [ω ]2 . 1 1 ω ⊆ ∈ ∈ (cid:104) (cid:105) ⊆ Claim 5.3. If X ω2 is nonmeagre, then for all but ﬁnitely many n, there exists some t n2 and f, g X so that t(cid:95) 0 f (cid:104) (cid:105) ⊆ and t(cid:95) 0 g. ∈ Proof of Claim. Suppose not. Then there are inﬁnitely many n so that for every f X, f(n) = i (cid:22) for some i (cid:22) which f n f n (cid:22) depends only on f n. The closure cl(X) then must also have this property, which implies that the interior of cl(X) is empty, (cid:13) and hence X is nowhere dense. c

text: WILLIAM

text: CHEN,

text: SHIMON

text: GARTI,

text: AND

text: THILO

text: WEINERT

text: ℵ

text: ℵ

text: sets,

text: cf.

text: The

text: existence

text: of

text: a

text: Luzin

text: set

text: does

text: not

text: entail

text: d

text: starting

text: from

text: a

text: model

text: of

text: CH,

text: add

text: Cohen

text: reals.

text: Each

text: uncountable

text: subset

text: of

text: the

text: Cohen

text: reals

text: is

text: nonmeagre,

text: since

text: it

text: cannot

text: be

text: a

text: subset

text: of

text: any

text: Borel

text: meagre

text: set

text: (which

text: lives

text: in

text: ℵ

text: an

text: intermediate

text: extension

text: of

text: just

text: countably

text: many

text: of

text: the

text: Cohen

text: factors).

text: However,

text: d

text: in

text: this

text: model.

text: Theorem

text: Suppose

text: there

text: exists

text: a

text: Luzin

text: set.

text: Then

text: there

text: is

text: a

text: colouring

text: proving

text: ω

text: [ω

text: with

text: no

text: triangle

text: with

text: edges

text: of

text: ω

text: three

text: diﬀerent

text: colours.

text: ℵ

text: Proof.

text: Fix

text: a

text: Luzin

text: set

text: f

text: α

text: ω

text: of

text: size

text: For

text: α

text: β

text: ω

text: deﬁne

text: ∆(α,

text: β)

text: to

text: be

text: the

text: least

text: n

text: ω

text: such

text: that

text: f

text: (n)

text: f

text: (n).

text: α

text: α

text: β

text: Let

text: s

text: ω

text: ω

text: be

text: a

text: function

text: so

text: that

text: for

text: every

text: i

text: ω,

text: s

text: is

text: inﬁnite.

text: Deﬁne

text: the

text: colouring

text: c

text: [ω

text: ω

text: to

text: be

text: c(α,

text: β)

text: s(∆(α,

text: β)).

text: There

text: are

text: no

text: triangles

text: which

text: get

text: three

text: colours

text: from

text: c.

text: Claim

text: For

text: distinct

text: α,

text: β,

text: γ

text: ω

text: the

text: smaller

text: two

text: among

text: ∆(α,

text: β),

text: ∆(β,

text: γ),

text: ∆(γ,

text: α)

text: are

text: equal.

text: Proof

text: of

text: Claim.

text: Towards

text: a

text: contradiction,

text: suppose

text: ∆(α,

text: γ)

text: ∆(β,

text: γ)

text: D(α,

text: β).

text: By

text: deﬁnition

text: of

text: f

text: (∆(α,

text: γ))

text: f

text: (∆(α,

text: γ)),

text: α

text: γ

text: but

text: since

text: ∆(α,

text: γ)

text: ∆(β,

text: γ),

text: f

text: (∆(α,

text: γ))

text: f

text: (∆(α,

text: γ)).

text: γ

text: β

text: In

text: total,

text: f

text: (∆(α,

text: γ))

text: f

text: (∆(α,

text: γ))

text: α

text: β

text: but

text: this

text: contradicts

text: ∆(α,

text: γ)

text: D(α,

text: β).

text: c

text: Now

text: we

text: show

text: that

text: c

text: satisﬁes

text: ω

text: [ω

text: ω

text: Claim

text: If

text: X

text: ω2

text: is

text: nonmeagre,

text: then

text: for

text: all

text: but

text: ﬁnitely

text: many

text: n,

text: there

text: exists

text: some

text: t

text: and

text: f,

text: g

text: X

text: so

text: that

text: f

text: and

text: g.

text: Proof

text: of

text: Claim.

text: Suppose

text: not.

text: Then

text: there

text: are

text: inﬁnitely

text: many

text: n

text: so

text: that

text: for

text: every

text: f

text: X,

text: f(n)

text: i

text: for

text: some

text: i

text: which

text: f

text: n

text: f

text: n

text: depends

text: only

text: on

text: f

text: n.

text: The

text: closure

text: cl(X)

text: then

text: must

text: also

text: have

text: this

text: property,

text: which

text: implies

text: that

text: the

text: interior

text: of

text: cl(X)

text: is

text: empty,

text: and

text: hence

text: X

text: is

text: nowhere

text: dense.

text: c


text: 26 WILLIAM CHEN, SHIMON GARTI, AND THILO WEINERT We would also be interested in any relationships of these relations with the category invariants. −→ Whether ω2 (ω2, 3)2 is consistent is a long-standing open question of Baumgartner. In our •context, we would be 1 1 ℵ | ℵ interested in reducing the hypotheses used by Larson (d = ) and Weinert–Lambie-Hanson (b = = ) to prove the 1 1 negative relation. A natural mutual strengthening of these results would be: ℵ −(cid:54) → Question 6.5. Does b = imply ω2 (ω2, 3)2? 1 1 1 The arguments here from cardinal characteristics roughly calibrate the strength of negative partition relations. We can ask if there is a direct implication. −(cid:54) → −(cid:54) → Question 6.6. Does ω2 (ω ω, 4) imply ω ω (ω ω, 3)2? 1 1 1 1 −(cid:54) → ∧ −(cid:54) → −(cid:54) → Question 6.7. Does ω2 (ω ω, 4) ω2 (ω2, 3) imply ω ω (ω ω, 3)2? 1 1 1 1 1 1 In this paper, we focused on ω for the value of the cardinal characteristic in the hypothesis and for the resources in the 1 partition relations. However, it may be possible that this is not necessary. • • (cid:54) | | Question 6.8. Does b hold by way of ZFC? For which cardinals κ does λ = κ+ and (κ) = λ imply the existence of an unbounded family of cardinality λλ? • M N (cid:54) | Question 6.9. Is min(cov( ), cov( )) ? References [018GS] Shimon Garti and Saharon Shelah. Random reals and polarized colorings. Studia Sci. Math. Hungar., 2018. to appear. [017LW] Chris Lambie-Hanson and Thilo Volker Weinert. Partitioning subsets of generalised scattered orders. Submitted, 2017, https://arxiv. org/pdf/1701.05791.pdf. [017RS] Dilip Raghavan and Saharon Shelah. Two inequalities between cardinal invariants. Fund. Math., 237(2):187–200, 2017, doi:10.4064/fm253- 7-2016, http://dx.doi.org/10.4064/fm253-7-2016. [016GS] Shimon Garti and Saharon Shelah. Open and solved problems concerning polarized partition relations. Fund. Math., 234(1):1–14, 2016, doi:10.4064/fm763-10-2015, http://dx.doi.org/10.4064/fm763-10-2015.

text: WILLIAM

text: CHEN,

text: SHIMON

text: GARTI,

text: AND

text: THILO

text: WEINERT

text: We

text: would

text: also

text: be

text: interested

text: in

text: any

text: relationships

text: of

text: these

text: relations

text: with

text: the

text: category

text: invariants.

text: Whether

text: ω2

text: is

text: consistent

text: is

text: a

text: long-standing

text: open

text: question

text: of

text: Baumgartner.

text: In

text: our

text: •context,

text: we

text: would

text: be

text: ℵ

text: ℵ

text: interested

text: in

text: reducing

text: the

text: hypotheses

text: used

text: by

text: Larson

text: (d

text: and

text: Weinert–Lambie-Hanson

text: (b

text: to

text: prove

text: the

text: negative

text: relation.

text: A

text: natural

text: mutual

text: strengthening

text: of

text: these

text: results

text: would

text: be:

text: ℵ

text: Question

text: Does

text: b

text: imply

text: ω2

text: The

text: arguments

text: here

text: from

text: cardinal

text: characteristics

text: roughly

text: calibrate

text: the

text: strength

text: of

text: negative

text: partition

text: relations.

text: We

text: can

text: ask

text: if

text: there

text: is

text: a

text: direct

text: implication.

text: Question

text: Does

text: ω2

text: (ω

text: ω,

text: imply

text: ω

text: ω

text: (ω

text: ω,

text: Question

text: Does

text: ω2

text: (ω

text: ω,

text: ω2

text: imply

text: ω

text: ω

text: (ω

text: ω,

text: In

text: this

text: paper,

text: we

text: focused

text: on

text: ω

text: for

text: the

text: value

text: of

text: the

text: cardinal

text: characteristic

text: in

text: the

text: hypothesis

text: and

text: for

text: the

text: resources

text: in

text: the

text: partition

text: relations.

text: However,

text: it

text: may

text: be

text: possible

text: that

text: this

text: is

text: not

text: necessary.

text: Question

text: Does

text: b

text: hold

text: by

text: way

text: of

text: ZFC?

text: For

text: which

text: cardinals

text: κ

text: does

text: λ

text: κ+

text: and

text: (κ)

text: λ

text: imply

text: the

text: existence

text: of

text: an

text: unbounded

text: family

text: of

text: cardinality

text: λλ?

text: M

text: N

text: Question

text: Is

text: min(cov(

text: cov(

text: References

text: Shimon

text: Garti

text: and

text: Saharon

text: Shelah.

text: Random

text: reals

text: and

text: polarized

text: colorings.

text: Studia

text: Sci.

text: Math.

text: Hungar.,

text: to

text: appear.

text: Chris

text: Lambie-Hanson

text: and

text: Thilo

text: Volker

text: Weinert.

text: Partitioning

text: subsets

text: of

text: generalised

text: scattered

text: orders.

text: Submitted,

text: Dilip

text: Raghavan

text: and

text: Saharon

text: Shelah.

text: Two

text: inequalities

text: between

text: cardinal

text: invariants.

text: Fund.

text: Math.,

text: Shimon

text: Garti

text: and

text: Saharon

text: Shelah.

text: Open

text: and

text: solved

text: problems

text: concerning

text: polarized

text: partition

text: relations.

text: Fund.

text: Math.,


text: CARDINAL CHARACTERISTICS OF THE CONTINUUM AND PARTITIONS 29 Department of Mathematics, Ben-Gurion-University of the Negev, Beersheba, 8410501, Israe¨l Email address: chenwb@gmail.com Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, 91904, Israe¨l Email address: shimon.garty@mail.huji.ac.il DMG/Algebra, TU Wien, Wiedner Hauptstrasse 8-10/104, 1040 Wien, Autriche Email address: aleph omega@posteo.net ##LTLine##

text: CARDINAL

text: CHARACTERISTICS

text: OF

text: THE

text: CONTINUUM

text: AND

text: PARTITIONS

text: Department

label: author

text: of

text: Mathematics,

text: Ben-Gurion-University

text: of

text: the

text: Negev,

text: Beersheba,

text: Israe¨l

text: Email

text: address:

text: chenwb@gmail.com

label: footer

text: Institute

text: of

text: Mathematics,

text: The

text: Hebrew

text: University

text: of

text: Jerusalem,

text: Jerusalem,

text: Israe¨l

text: Email

text: address:

text: shimon.garty@mail.huji.ac.il

text: DMG/Algebra,

text: TU

text: Wien,

text: Wiedner

text: Hauptstrasse

text: Wien,

text: Autriche

text: Email

text: address:

text: aleph

text: omega@posteo.net

text: ##LTLine##

font: default


text: 2 SHIMON GARTI AND YAIR HAYUT 0. Introduction → The combinatorial deﬁnition of a Magidor cardinal λ is given by λ ℵ ℵ → [λ] 0-bd. This relation means that for every c : [λ] 0-bd λ there exists λ∈ (cid:48)(cid:48) ℵ (cid:54) A [λ]λ for which c [A] 0-bd = λ. Magidor cardinals were deﬁned in [2] through this combinatorial property. A model-theoretic characterization of these cardinals via elementary embeddings appears in [3]. → ℵ → ℵ It is easy to see that if λ [λ] 0-bd then λ [λ] 0-bd for some α < λ λ α ([2], Lemma 1.2). Given a Magidor cardinal λ, the ﬁrst such α is denoted ≥ by α (λ) or just α if λ is clear from the context. Notice that if β α M → ℵ M M then λ [λ] 0-bd as well. We shall say that α is the ﬁrst omitting cardinal β M for λ. A parallel notion arises for J´onsson cardinals. Recall that λ is J´onsson iﬀ → → λ [λ]<ω, in which case there exists a ﬁrst ordinal α for which λ [λ]<ω. λ α The ﬁrst such ordinal is denoted by α (or α (λ)), and it is a regular cardinal J J strictly below λ. Several properties of α are phrased in [2], among them the fact that it is M always a regular cardinal. Some open problems concerning α appear in [2]. M A pair of related problems is labeled there as Question 3.12 and Question 3.13. The ﬁrst one is whether α can be a successor of a singular cardinal. M In the second one we ask about the possibility that α is a large cardinal M (e.g., measurable) and also is it possible that α is a successor of a large M cardinal. We shall prove that α is not a large cardinal but it can be a M successor of a large cardinal. Thence, one can singularize this large cardinal and force α to be a successor of a singular cardinal. M Although we can force α to be a successor of a singular cardinal, the M coﬁnality of this cardinal is uncountable in our model. The last stage of singularizing our large cardinal is done with Magidor forcing and not with Prikry forcing. It is an amusing historical coincidence (Magidor cardinals were deﬁned with no connection to Magidor forcing), but it seems that Prikry forcing fails to place α at the ﬁrst point above a singular cardinal. M The reason will be explicated in the sequel, and it points to a substantial property of α . M Our notation is mostly standard. We suggest [5] for a comprehensive treatment to large cardinals. We shall use the Jerusalem notation in forcing, ≤ P ∈ P i.e. p q means that q is stronger than p. If is a forcing notion and p, q (cid:107) then p q means that p and q are compatible. The pure order in Prikry ≤∗ type forcing notions will be denoted by . We call κ supercompact iﬀ for every ordinal γ there exists an elementary → ⊆ embedding  : V M for which κ = crit() and γM M. A forcing notion P ⊆ P is κ-directed-closed iﬀ whenever A is a directed set of conditions | | ∈ P ∈ ⇒ ≤ and A < κ, there exists some q so that p A p q. We shall use Prikry and Magidor forcing, and we follow the conventions of [4]. This has a particular importance with respect to Magidor forcing, as this type of forcing notions can be written in several ways.

text: SHIMON

text: GARTI

text: AND

text: YAIR

text: HAYUT

text: Introduction

text: The

text: combinatorial

text: deﬁnition

text: of

text: a

text: Magidor

text: cardinal

text: λ

text: is

text: given

text: by

text: λ

text: ℵ

text: ℵ

text: [λ]

text: This

text: relation

text: means

text: that

text: for

text: every

text: c

text: [λ]

text: λ

text: there

text: exists

text: λ∈

text: ℵ

text: A

text: [λ]λ

text: for

text: which

text: c

text: [A]

text: λ.

text: Magidor

text: cardinals

text: were

text: deﬁned

text: in

text: through

text: this

text: combinatorial

text: property.

text: A

text: model-theoretic

text: characterization

text: of

text: these

text: cardinals

text: via

text: elementary

text: embeddings

text: appears

text: in

text: ℵ

text: ℵ

text: It

text: is

text: easy

text: to

text: see

text: that

text: if

text: λ

text: [λ]

text: then

text: λ

text: [λ]

text: for

text: some

text: α

text: λ

text: λ

text: α

text: Lemma

text: Given

text: a

text: Magidor

text: cardinal

text: λ,

text: the

text: ﬁrst

text: such

text: α

text: is

text: denoted

text: by

text: α

text: (λ)

text: or

text: just

text: α

text: if

text: λ

text: is

text: clear

text: from

text: the

text: context.

text: Notice

text: that

text: if

text: β

text: α

text: M

text: ℵ

text: M

text: M

text: then

text: λ

text: [λ]

text: as

text: well.

text: We

text: shall

text: say

text: that

text: α

text: is

text: the

text: ﬁrst

text: omitting

text: cardinal

text: β

text: M

text: for

text: λ.

text: A

text: parallel

text: notion

text: arises

text: for

text: J´onsson

text: cardinals.

text: Recall

text: that

text: λ

text: is

text: J´onsson

text: iﬀ

text: λ

text: [λ]<ω,

text: in

text: which

text: case

text: there

text: exists

text: a

text: ﬁrst

text: ordinal

text: α

text: for

text: which

text: λ

text: [λ]<ω.

text: λ

text: α

text: The

text: ﬁrst

text: such

text: ordinal

text: is

text: denoted

text: by

text: α

text: (or

text: α

text: (λ)),

text: and

text: it

text: is

text: a

text: regular

text: cardinal

text: J

text: J

text: strictly

text: below

text: λ.

text: Several

text: properties

text: of

text: α

text: are

text: phrased

text: in

text: among

text: them

text: the

text: fact

text: that

text: it

text: is

text: M

text: always

text: a

text: regular

text: cardinal.

text: Some

text: open

text: problems

text: concerning

text: α

text: appear

text: in

text: M

text: A

text: pair

text: of

text: related

text: problems

text: is

text: labeled

text: there

text: as

text: Question

text: and

text: Question

text: The

text: ﬁrst

text: one

text: is

text: whether

text: α

text: can

text: be

text: a

text: successor

text: of

text: a

text: singular

text: cardinal.

text: M

text: In

text: the

text: second

text: one

text: we

text: ask

text: about

text: the

text: possibility

text: that

text: α

text: is

text: a

text: large

text: cardinal

text: M

text: (e.g.,

text: measurable)

text: and

text: also

text: is

text: it

text: possible

text: that

text: α

text: is

text: a

text: successor

text: of

text: a

text: large

text: M

text: cardinal.

text: We

text: shall

text: prove

text: that

text: α

text: is

text: not

text: a

text: large

text: cardinal

text: but

text: it

text: can

text: be

text: a

text: M

text: successor

text: of

text: a

text: large

text: cardinal.

text: Thence,

text: one

text: can

text: singularize

text: this

text: large

text: cardinal

text: and

text: force

text: α

text: to

text: be

text: a

text: successor

text: of

text: a

text: singular

text: cardinal.

text: M

text: Although

text: we

text: can

text: force

text: α

text: to

text: be

text: a

text: successor

text: of

text: a

text: singular

text: cardinal,

text: the

text: M

text: coﬁnality

text: of

text: this

text: cardinal

text: is

text: uncountable

text: in

text: our

text: model.

text: The

text: last

text: stage

text: of

text: singularizing

text: our

text: large

text: cardinal

text: is

text: done

text: with

text: Magidor

text: forcing

text: and

text: not

text: with

text: Prikry

text: forcing.

text: It

text: is

text: an

text: amusing

text: historical

text: coincidence

text: (Magidor

text: cardinals

text: were

text: deﬁned

text: with

text: no

text: connection

text: to

text: Magidor

text: forcing),

text: but

text: it

text: seems

text: that

text: Prikry

text: forcing

text: fails

text: to

text: place

text: α

text: at

text: the

text: ﬁrst

text: point

text: above

text: a

text: singular

text: cardinal.

text: M

text: The

text: reason

text: will

text: be

text: explicated

text: in

text: the

text: sequel,

text: and

text: it

text: points

text: to

text: a

text: substantial

text: property

text: of

text: α

text: M

text: Our

text: notation

text: is

text: mostly

text: standard.

text: We

text: suggest

text: for

text: a

text: comprehensive

text: treatment

text: to

text: large

text: cardinals.

text: We

text: shall

text: use

text: the

text: Jerusalem

text: notation

text: in

text: forcing,

text: P

text: P

text: i.e.

text: p

text: q

text: means

text: that

text: q

text: is

text: stronger

text: than

text: p.

text: If

text: is

text: a

text: forcing

text: notion

text: and

text: p,

text: q

text: then

text: p

text: q

text: means

text: that

text: p

text: and

text: q

text: are

text: compatible.

text: The

text: pure

text: order

text: in

text: Prikry

text: type

text: forcing

text: notions

text: will

text: be

text: denoted

text: by

text: We

text: call

text: κ

text: supercompact

text: iﬀ

text: for

text: every

text: ordinal

text: γ

text: there

text: exists

text: an

text: elementary

text: embedding

text: V

text: M

text: for

text: which

text: κ

text: crit()

text: and

text: γM

text: M.

text: A

text: forcing

text: notion

text: P

text: P

text: is

text: κ-directed-closed

text: iﬀ

text: whenever

text: A

text: is

text: a

text: directed

text: set

text: of

text: conditions

text: P

text: and

text: A

text: κ,

text: there

text: exists

text: some

text: q

text: so

text: that

text: p

text: A

text: p

text: q.

text: We

text: shall

text: use

text: Prikry

text: and

text: Magidor

text: forcing,

text: and

text: we

text: follow

text: the

text: conventions

text: of

text: This

text: has

text: a

text: particular

text: importance

text: with

text: respect

text: to

text: Magidor

text: forcing,

text: as

text: this

text: type

text: of

text: forcing

text: notions

text: can

text: be

text: written

text: in

text: several

text: ways.


text: 14 SHIMON GARTI AND YAIR HAYUT generic. | Then V [G] = α (λ) = κ++, provided that λ is still Magidor in V [G]. M Proof. ℵ → ∈ Let f : [λ] 0-bd κ++ be a name of a coloring. We have to ﬁnd A [λ]λ such˜that the interpretation of f restricted to countable subsets of A omits colors from λ. We may assum˜e that 2κ = κ+ in the ground model. For ∈ ∩ every x [λ]<κ+-bd V we deﬁne: { ∈ ∃ (cid:13) ⊆ ∧ ∈ ℵ ∃ ∈ P (cid:13) } g(x) = sup α κ++ : τ, P τ xˇ τ [λ] 0-bd, q , q f(τ) = α . ∈ ˜ ˜ ˜ ˜ ˜ Notice that g V as the forcing relation is deﬁnable in V . Observe also ∈ ∈ ∩ that g(x) κ++ for every x [λ]<κ+-bd V . This is true since the number of names τ which appear in the deﬁnition of g(x) is at most 2κ = κ+, and by ˜ P the chain condition of the value of f(τ) is determined by at most κ-many conditions. As each α is an ordinal˜in˜κ++ (recall that the range of f is ∈ κ++) we see that g(x) κ++. ˜ By the assumption that α<κ+(λ) = κ++ in the ground model, there is a ∈ M ⊆ set A [λ]λ and an ordinal µ < λ such that Rang(g) µ. It follows that ⊆ Rang(f) µ in the generic extension, so we are done. (cid:3) ˜ 2.3 Our next goal is to show that the assumptions of the above claim are consistent. Claim 2.4. Assume that λ is I1. ℵ ( ) It is consistent that µ < λ, µ is supercompact and α<µ+(λ) = µ++. ((cid:105)) It is consistent that µ < λ, µ is supercompact and αM<µ(λ) = µ+. M Proof. (cid:116) Choose µ < κ < λ so that I1(κ, λ) and µ is supercompact. Force ∈ λ,δ for some δ = cf(δ) (µ, κ) with respect to the stationary sets S≤η where µ η < λ, cf(η) = δ and we force the quilshon at every such η. As in the proof of Theorem 1.12, this can be done while preserving I1(κ, λ) on the one hand and the supercompactness of µ on the other hand. Notice that α<µ+(λ) > µ+ after forcing the quilshon. This is our preparation for the M ℵ collapse, and we deal now with part ( ) of the statement. Let α = ((α<µ+(λ))µ)+. Since λ is a strong limit cardinal we see that M Q α < λ. Now we force with = Le´vy(µ++, < α) and one can verify that α<µ+(λ) = µ++ in the generic extension by Q, as done in the proof of M Theorem 1.12. (cid:105) A similar argument proves part ( ), but here it is possible to force α<µ(λ) = µ+. Indeed, the pertinent chain condition will be just µ+-cc, M as the elements that we color are of size strictly less than µ. Consequently, Le´vy(µ+, < α) is suﬃcient. (cid:3) 2.4

text: SHIMON

text: GARTI

text: AND

text: YAIR

text: HAYUT

text: generic.

text: Then

text: V

text: [G]

text: α

text: (λ)

text: κ++,

text: provided

text: that

text: λ

text: is

text: still

text: Magidor

text: in

text: V

text: [G].

text: M

text: Proof.

text: ℵ

text: Let

text: f

text: [λ]

text: κ++

text: be

text: a

text: name

text: of

text: a

text: coloring.

text: We

text: have

text: to

text: ﬁnd

text: A

text: [λ]λ

text: such˜that

text: the

text: interpretation

text: of

text: f

text: restricted

text: to

text: countable

text: subsets

text: of

text: A

text: omits

text: colors

text: from

text: λ.

text: We

text: may

text: assum˜e

text: that

text: 2κ

text: κ+

text: in

text: the

text: ground

text: model.

text: For

text: every

text: x

text: [λ]<κ+-bd

text: V

text: we

text: deﬁne:

text: ℵ

text: P

text: g(x)

text: sup

text: α

text: κ++

text: τ,

text: P

text: τ

text: xˇ

text: τ

text: [λ]

text: q

text: q

text: f(τ)

text: α

text: Notice

text: that

text: g

text: V

text: as

text: the

text: forcing

text: relation

text: is

text: deﬁnable

text: in

text: V

text: Observe

text: also

text: that

text: g(x)

text: κ++

text: for

text: every

text: x

text: [λ]<κ+-bd

text: V

text: This

text: is

text: true

text: since

text: the

text: number

text: of

text: names

text: τ

text: which

text: appear

text: in

text: the

text: deﬁnition

text: of

text: g(x)

text: is

text: at

text: most

text: 2κ

text: κ+,

text: and

text: by

text: P

text: the

text: chain

text: condition

text: of

text: the

text: value

text: of

text: f(τ)

text: is

text: determined

text: by

text: at

text: most

text: κ-many

text: conditions.

text: As

text: each

text: α

text: is

text: an

text: ordinal˜in˜κ++

text: (recall

text: that

text: the

text: range

text: of

text: f

text: is

text: κ++)

text: we

text: see

text: that

text: g(x)

text: κ++.

text: By

text: the

text: assumption

text: that

text: α<κ+(λ)

text: κ++

text: in

text: the

text: ground

text: model,

text: there

text: is

text: a

text: M

text: set

text: A

text: [λ]λ

text: and

text: an

text: ordinal

text: µ

text: λ

text: such

text: that

text: Rang(g)

text: µ.

text: It

text: follows

text: that

text: Rang(f)

text: µ

text: in

text: the

text: generic

text: extension,

text: so

text: we

text: are

text: done.

text: Our

text: next

text: goal

text: is

text: to

text: show

text: that

text: the

text: assumptions

text: of

text: the

text: above

text: claim

text: are

text: consistent.

text: Claim

text: Assume

text: that

text: λ

text: is

text: ℵ

text: It

text: is

text: consistent

text: that

text: µ

text: λ,

text: µ

text: is

text: supercompact

text: and

text: α<µ+(λ)

text: µ++.

text: It

text: is

text: consistent

text: that

text: µ

text: λ,

text: µ

text: is

text: supercompact

text: and

text: αM<µ(λ)

text: µ+.

text: M

text: Proof.

text: Choose

text: µ

text: κ

text: λ

text: so

text: that

text: λ)

text: and

text: µ

text: is

text: supercompact.

text: Force

text: λ,δ

text: for

text: some

text: δ

text: cf(δ)

text: (µ,

text: κ)

text: with

text: respect

text: to

text: the

text: stationary

text: sets

text: S≤η

text: where

text: µ

text: η

text: λ,

text: cf(η)

text: δ

text: and

text: we

text: force

text: the

text: quilshon

text: at

text: every

text: such

text: η.

text: As

text: in

text: the

text: proof

text: of

text: Theorem

text: this

text: can

text: be

text: done

text: while

text: preserving

text: λ)

text: on

text: the

text: one

text: hand

text: and

text: the

text: supercompactness

text: of

text: µ

text: on

text: the

text: other

text: hand.

text: Notice

text: that

text: α<µ+(λ)

text: µ+

text: after

text: forcing

text: the

text: quilshon.

text: This

text: is

text: our

text: preparation

text: for

text: the

text: M

text: ℵ

text: collapse,

text: and

text: we

text: deal

text: now

text: with

text: part

text: of

text: the

text: statement.

text: Let

text: α

text: ((α<µ+(λ))µ)+.

text: Since

text: λ

text: is

text: a

text: strong

text: limit

text: cardinal

text: we

text: see

text: that

text: M

text: Q

text: α

text: λ.

text: Now

text: we

text: force

text: with

text: Le´vy(µ++,

text: α)

text: and

text: one

text: can

text: verify

text: that

text: α<µ+(λ)

text: µ++

text: in

text: the

text: generic

text: extension

text: by

text: Q,

text: as

text: done

text: in

text: the

text: proof

text: of

text: M

text: Theorem

text: A

text: similar

text: argument

text: proves

text: part

text: but

text: here

text: it

text: is

text: possible

text: to

text: force

text: α<µ(λ)

text: µ+.

text: Indeed,

text: the

text: pertinent

text: chain

text: condition

text: will

text: be

text: just

text: µ+-cc,

text: M

text: as

text: the

text: elements

text: that

text: we

text: color

text: are

text: of

text: size

text: strictly

text: less

text: than

text: µ.

text: Consequently,

text: Le´vy(µ+,

text: α)

text: is

text: suﬃcient.


text: THE FIRST OMITTING CARDINAL FOR MAGIDORITY 15 The fact that Prikry forcing at µ might increase α only to µ++ is sug- M gestive. A more illuminating formulation of this fact is that basically (un- der some convenient assumptions that we made) Prikry forcing at µ makes α = (µω)+. Philosophically this is the correct point for α since one can M M code ω-sequences of µ in the generic extension by old µ-sets, thus covering all the colors of µω but maintaining (µω)+ to omit colors. Mathematically it suggests that if we singularize µ in such a way that µω = µ in the generic extension then we can force α = (µω)+ = µ+ M while µ > cf(µ). This is hopeless with Prikry forcing but it can be done by another Prikry-type forcing notion which makes µ > cf(µ) > ω. We let Magidor forcing into the discussion at this point. A natural question arose in the wake of Prikry’s work. Is it possible to change the coﬁnality of a measurable cardinal κ into uncountable coﬁnality without collapsing cardinals? A positive answer was given by Magidor in [8], nowadays known as Magidor forcing. The deﬁnition of the forcing is more involved than the classical Prikry forcing, and in particular the required largeness of the cardinal which changes its coﬁnality is much more than just measurability. There are other diﬀerences between Prikry and Magidor forcing, the most important for us is mirrored in the covering properties of countable sets. If P { ∈ } is Prikry forcing for κ and x = x : n ω is a coﬁnal Prikry sequence, n then x cannot be covered by a set of size less than κ from the ground model. M But if is Magidor forcing then the situation changes a bit. The following claim shows that Magidor forcing has a better covering property when new countable sets are considered. Claim 2.5. Assume that λ is a Magidor cardinal, κ < λ and κ is suﬃciently M large (e.g. κ is supercompact). Let be Magidor forcing which makes κ > cf(κ) > ω. M ℵ ∈ M If τ is any -name of an element in [λ] 0-bd then there are p , θ < κ ˜ ∈ | | (cid:13) ⊆ and x V such that x = θ and p τ xˇ. ˜ Proof. ∈ M (cid:104) (cid:105) A condition p is a ﬁnite sequence d , . . . , d , (κ, A) where each d is 1 (cid:104) n (cid:105) i either an ordinal or a pair (ν, A ). The part d , . . . , d is the stem of p, and ν (cid:107) 1 n if p, q share the same stem then p q. Inasmuch as the number of possible M stems is κ, is κ+-cc. ⊆ M Fix a generic subset G . Let τ be a name of a countable set of ordinals. Each element in τ is determined by an antichain of size at most G ˜ κ, hence by collecting all the possibilities we construct (in V ) a set B of | | ≤ (cid:13) ⊆ ∈ | | ordinals, B κ such that M τ Bˇ. Since B V, B = κ one can ﬁx a → ˜ bijection h : κ B. (cid:13) Let σ be a name for a countable set of ordinals of κ, such that M σ = h−1(τ)˜. The interpretation of σ in the generic extension is a bounded sub˜set | ∈ ˜ ˜ of κ, since V [G] = cf(κ) > ω. Hence for some β κ there is a condition p ∈ M such that p (cid:13) σ ⊆ βˇ. It follows that p (cid:13) τ ⊆ h(cid:48)(cid:48)β. Denote h(cid:48)(cid:48)β by ˜ ˜

text: THE

text: FIRST

text: OMITTING

text: CARDINAL

text: FOR

text: MAGIDORITY

text: The

text: fact

text: that

text: Prikry

text: forcing

text: at

text: µ

text: might

text: increase

text: α

text: only

text: to

text: µ++

text: is

text: sug-

text: M

text: gestive.

text: A

text: more

text: illuminating

text: formulation

text: of

text: this

text: fact

text: is

text: that

text: basically

text: (un-

text: der

text: some

text: convenient

text: assumptions

text: that

text: we

text: made)

text: Prikry

text: forcing

text: at

text: µ

text: makes

text: α

text: (µω)+.

text: Philosophically

text: this

text: is

text: the

text: correct

text: point

text: for

text: α

text: since

text: one

text: can

text: M

text: M

text: code

text: ω-sequences

text: of

text: µ

text: in

text: the

text: generic

text: extension

text: by

text: old

text: µ-sets,

text: thus

text: covering

text: all

text: the

text: colors

text: of

text: µω

text: but

text: maintaining

text: (µω)+

text: to

text: omit

text: colors.

text: Mathematically

text: it

text: suggests

text: that

text: if

text: we

text: singularize

text: µ

text: in

text: such

text: a

text: way

text: that

text: µω

text: µ

text: in

text: the

text: generic

text: extension

text: then

text: we

text: can

text: force

text: α

text: (µω)+

text: µ+

text: M

text: while

text: µ

text: cf(µ).

text: This

text: is

text: hopeless

text: with

text: Prikry

text: forcing

text: but

text: it

text: can

text: be

text: done

text: by

text: another

text: Prikry-type

text: forcing

text: notion

text: which

text: makes

text: µ

text: cf(µ)

text: ω.

text: We

text: let

text: Magidor

text: forcing

text: into

text: the

text: discussion

text: at

text: this

text: point.

text: A

text: natural

text: question

text: arose

text: in

text: the

text: wake

text: of

text: Prikry’s

text: work.

text: Is

text: it

text: possible

text: to

text: change

text: the

text: coﬁnality

text: of

text: a

text: measurable

text: cardinal

text: κ

text: into

text: uncountable

text: coﬁnality

text: without

text: collapsing

text: cardinals?

text: A

text: positive

text: answer

text: was

text: given

text: by

text: Magidor

text: in

text: nowadays

text: known

text: as

text: Magidor

text: forcing.

text: The

text: deﬁnition

text: of

text: the

text: forcing

text: is

text: more

text: involved

text: than

text: the

text: classical

text: Prikry

text: forcing,

text: and

text: in

text: particular

text: the

text: required

text: largeness

text: of

text: the

text: cardinal

text: which

text: changes

text: its

text: coﬁnality

text: is

text: much

text: more

text: than

text: just

text: measurability.

text: There

text: are

text: other

text: diﬀerences

text: between

text: Prikry

text: and

text: Magidor

text: forcing,

text: the

text: most

text: important

text: for

text: us

text: is

text: mirrored

text: in

text: the

text: covering

text: properties

text: of

text: countable

text: sets.

text: If

text: P

text: is

text: Prikry

text: forcing

text: for

text: κ

text: and

text: x

text: x

text: n

text: ω

text: is

text: a

text: coﬁnal

text: Prikry

text: sequence,

text: n

text: then

text: x

text: cannot

text: be

text: covered

text: by

text: a

text: set

text: of

text: size

text: less

text: than

text: κ

text: from

text: the

text: ground

text: model.

text: M

text: But

text: if

text: is

text: Magidor

text: forcing

text: then

text: the

text: situation

text: changes

text: a

text: bit.

text: The

text: following

text: claim

text: shows

text: that

text: Magidor

text: forcing

text: has

text: a

text: better

text: covering

text: property

text: when

text: new

text: countable

text: sets

text: are

text: considered.

text: Claim

text: Assume

text: that

text: λ

text: is

text: a

text: Magidor

text: cardinal,

text: κ

text: λ

text: and

text: κ

text: is

text: suﬃciently

text: M

text: large

text: (e.g.

text: κ

text: is

text: supercompact).

text: Let

text: be

text: Magidor

text: forcing

text: which

text: makes

text: κ

text: cf(κ)

text: ω.

text: M

text: ℵ

text: M

text: If

text: τ

text: is

text: any

text: -name

text: of

text: an

text: element

text: in

text: [λ]

text: then

text: there

text: are

text: p

text: θ

text: κ

text: and

text: x

text: V

text: such

text: that

text: x

text: θ

text: and

text: p

text: τ

text: xˇ.

text: Proof.

text: M

text: A

text: condition

text: p

text: is

text: a

text: ﬁnite

text: sequence

text: d

text: d

text: (κ,

text: A)

text: where

text: each

text: d

text: is

text: n

text: i

text: either

text: an

text: ordinal

text: or

text: a

text: pair

text: (ν,

text: A

text: The

text: part

text: d

text: d

text: is

text: the

text: stem

text: of

text: p,

text: and

text: ν

text: n

text: if

text: p,

text: q

text: share

text: the

text: same

text: stem

text: then

text: p

text: q.

text: Inasmuch

text: as

text: the

text: number

text: of

text: possible

text: M

text: stems

text: is

text: κ,

text: is

text: κ+-cc.

text: M

text: Fix

text: a

text: generic

text: subset

text: G

text: Let

text: τ

text: be

text: a

text: name

text: of

text: a

text: countable

text: set

text: of

text: ordinals.

text: Each

text: element

text: in

text: τ

text: is

text: determined

text: by

text: an

text: antichain

text: of

text: size

text: at

text: most

text: G

text: κ,

text: hence

text: by

text: collecting

text: all

text: the

text: possibilities

text: we

text: construct

text: (in

text: V

text: a

text: set

text: B

text: of

text: ordinals,

text: B

text: κ

text: such

text: that

text: M

text: τ

text: Bˇ.

text: Since

text: B

text: V,

text: B

text: κ

text: one

text: can

text: ﬁx

text: a

text: bijection

text: h

text: κ

text: B.

text: Let

text: σ

text: be

text: a

text: name

text: for

text: a

text: countable

text: set

text: of

text: ordinals

text: of

text: κ,

text: such

text: that

text: M

text: σ

text: The

text: interpretation

text: of

text: σ

text: in

text: the

text: generic

text: extension

text: is

text: a

text: bounded

text: sub˜set

text: of

text: κ,

text: since

text: V

text: [G]

text: cf(κ)

text: ω.

text: Hence

text: for

text: some

text: β

text: κ

text: there

text: is

text: a

text: condition

text: p

text: M

text: such

text: that

text: p

text: σ

text: βˇ.

text: It

text: follows

text: that

text: p

text: τ

text: Denote

text: by


text: 16 SHIMON GARTI AND YAIR HAYUT | | | | x and β = x by θ. Observe that p forces that τ is contained in the set x ∈ ˜ and x V . Since θ < κ, we are done. (cid:3) ℵ2.5 One can modify the above claim to elements in [λ]η-bd where η > , 0 provided that M forces cf(κ) > η. In this way one can obtain α<η(λ) = µ+ M where µ > cf(µ) > η as we shall prove below. We focus on the usual α M (that is, with respect to countable sets). Theorem 2.6. Let λ be I1. Then one can force α (λ) = µ+ where µ is a singular cardinal with un- M countable coﬁnality. Proof. Our starting point is a strongly Magidor cardinal λ with a supercompact cardinal µ such that µ < λ and α<µ(λ) = µ+. This can be arranged by (cid:105) M M part ( ) of Claim 2.4. We shall force with Magidor forcing to make µ > cf(µ) > ω and our task is to show that α (λ) = µ+ in the generic M M extension by . Before proving this statement we need a preliminary assertion which re- duces the number of the pertinent names for the coloring that we wish to M deﬁne. Assume that κ is supercompact and is Magidor forcing at κ. Let | | A be a set of ordinals such that A < κ. We claim that there exists a set | | ≤ ∈ M T of names, T κ such that for any name τ and any condition p for which p (cid:13) τ ⊆ Aˇ∧ |τ| = ℵ there exists a nam˜e σ ∈ T and a condition q ≥ p (cid:13)˜ ˜ 0 ˜ so that q σ = τ. | | ˜ ˜ For proving this assertion suppose that A = θ < κ. Fix a bijection → A { } h : A θ. Let = p : i < κ be a maximal antichain of conditions which i force an element into the Magidor sequence above θ. For every i < κ ﬁx an ordinal α > θ which is forced to be in the Magidor sequence by p . (cid:104) i (cid:105) i Let di , . . . , di be the stem of p for every i < κ. There exists m = ∈ 1 n(i) i m(i) [∈1, n(i)] such that αi appears in dim (either dim = αi or dim =M(ν, Aν∼) and α A ). A fundamental property of Magidor forcing is that /p = M ≤i × Mν i /p m /p>m and new subsets of α are forced only by the lower part M i≤ i i M ≤ /p m. Notice that the number of names in /p m for subsets of α is i i i at most 2αi < κ. Let T be the set of all such names for every i < κ, so | | ≤ · T κ κ = κ. We claim that T is as required. M ∈ M (cid:13) ⊆ ∧ | | ℵ Indeed, assume that τ is an -name, p and p τ Aˇ τ = . A˜ ∈ A (cid:107) ˜ ∈˜M 0 By the maximality of choose p so that p p , and let q be a ≥ i (cid:13) ⊆ ∧ i| | ℵ ≥ condition which satisﬁes q p, p . Now q τ Aˇ τ = as q p and (cid:13) ∈ i ≥ ˜ ˜ 0 q σ = τ for some σ T since q p . This completes the proof of the i ˜ ˜ ˜ assertion. ⊆ M | Let G be generic. We try to show that V [G] = α (λ) = µ+. By M the fact that λ is I1 in V we can see that λ is I1 (and hence Magidor) in ℵ → V [G]. Assume that f : [λ] 0-bd µ+. Let A be a bounded subset of λ of ˜

text: SHIMON

text: GARTI

text: AND

text: YAIR

text: HAYUT

text: x

text: and

text: β

text: x

text: by

text: θ.

text: Observe

text: that

text: p

text: forces

text: that

text: τ

text: is

text: contained

text: in

text: the

text: set

text: x

text: and

text: x

text: V

text: Since

text: θ

text: κ,

text: we

text: are

text: done.

text: One

text: can

text: modify

text: the

text: above

text: claim

text: to

text: elements

text: in

text: [λ]η-bd

text: where

text: η

text: provided

text: that

text: M

text: forces

text: cf(κ)

text: η.

text: In

text: this

text: way

text: one

text: can

text: obtain

text: α<η(λ)

text: µ+

text: M

text: where

text: µ

text: cf(µ)

text: η

text: as

text: we

text: shall

text: prove

text: below.

text: We

text: focus

text: on

text: the

text: usual

text: α

text: M

text: (that

text: is,

text: with

text: respect

text: to

text: countable

text: sets).

text: Theorem

text: Let

text: λ

text: be

text: Then

text: one

text: can

text: force

text: α

text: (λ)

text: µ+

text: where

text: µ

text: is

text: a

text: singular

text: cardinal

text: with

text: un-

text: M

text: countable

text: coﬁnality.

text: Proof.

text: Our

text: starting

text: point

text: is

text: a

text: strongly

text: Magidor

text: cardinal

text: λ

text: with

text: a

text: supercompact

text: cardinal

text: µ

text: such

text: that

text: µ

text: λ

text: and

text: α<µ(λ)

text: µ+.

text: This

text: can

text: be

text: arranged

text: by

text: M

text: M

text: part

text: of

text: Claim

text: We

text: shall

text: force

text: with

text: Magidor

text: forcing

text: to

text: make

text: µ

text: cf(µ)

text: ω

text: and

text: our

text: task

text: is

text: to

text: show

text: that

text: α

text: (λ)

text: µ+

text: in

text: the

text: generic

text: M

text: M

text: extension

text: by

text: Before

text: proving

text: this

text: statement

text: we

text: need

text: a

text: preliminary

text: assertion

text: which

text: re-

text: duces

text: the

text: number

text: of

text: the

text: pertinent

text: names

text: for

text: the

text: coloring

text: that

text: we

text: wish

text: to

text: M

text: deﬁne.

text: Assume

text: that

text: κ

text: is

text: supercompact

text: and

text: is

text: Magidor

text: forcing

text: at

text: κ.

text: Let

text: A

text: be

text: a

text: set

text: of

text: ordinals

text: such

text: that

text: A

text: κ.

text: We

text: claim

text: that

text: there

text: exists

text: a

text: set

text: M

text: T

text: of

text: names,

text: T

text: κ

text: such

text: that

text: for

text: any

text: name

text: τ

text: and

text: any

text: condition

text: p

text: for

text: which

text: p

text: τ

text: Aˇ∧

text: |τ|

text: ℵ

text: there

text: exists

text: a

text: nam˜e

text: σ

text: T

text: and

text: a

text: condition

text: q

text: p

text: so

text: that

text: q

text: σ

text: τ.

text: For

text: proving

text: this

text: assertion

text: suppose

text: that

text: A

text: θ

text: κ.

text: Fix

text: a

text: bijection

text: A

text: h

text: A

text: θ.

text: Let

text: p

text: i

text: κ

text: be

text: a

text: maximal

text: antichain

text: of

text: conditions

text: which

text: i

text: force

text: an

text: element

text: into

text: the

text: Magidor

text: sequence

text: above

text: θ.

text: For

text: every

text: i

text: κ

text: ﬁx

text: an

text: ordinal

text: α

text: θ

text: which

text: is

text: forced

text: to

text: be

text: in

text: the

text: Magidor

text: sequence

text: by

text: p

text: i

text: i

text: Let

text: di

text: di

text: be

text: the

text: stem

text: of

text: p

text: for

text: every

text: i

text: κ.

text: There

text: exists

text: m

text: n(i)

text: i

text: m(i)

text: n(i)]

text: such

text: that

text: αi

text: appears

text: in

text: dim

text: (either

text: dim

text: αi

text: or

text: dim

text: =M(ν,

text: Aν∼)

text: and

text: α

text: A

text: A

text: fundamental

text: property

text: of

text: Magidor

text: forcing

text: is

text: that

text: /p

text: M

text: ≤i

text: Mν

text: i

text: /p

text: m

text: /p>m

text: and

text: new

text: subsets

text: of

text: α

text: are

text: forced

text: only

text: by

text: the

text: lower

text: part

text: M

text: i≤

text: i

text: i

text: M

text: /p

text: m.

text: Notice

text: that

text: the

text: number

text: of

text: names

text: in

text: /p

text: m

text: for

text: subsets

text: of

text: α

text: is

text: i

text: i

text: i

text: at

text: most

text: κ.

text: Let

text: T

text: be

text: the

text: set

text: of

text: all

text: such

text: names

text: for

text: every

text: i

text: κ,

text: so

text: T

text: κ

text: κ

text: κ.

text: We

text: claim

text: that

text: T

text: is

text: as

text: required.

text: M

text: M

text: ℵ

text: Indeed,

text: assume

text: that

text: τ

text: is

text: an

text: -name,

text: p

text: and

text: p

text: τ

text: Aˇ

text: τ

text: A˜

text: A

text: ∈˜M

text: By

text: the

text: maximality

text: of

text: choose

text: p

text: so

text: that

text: p

text: p

text: and

text: let

text: q

text: be

text: a

text: i

text: i|

text: ℵ

text: condition

text: which

text: satisﬁes

text: q

text: p,

text: p

text: Now

text: q

text: τ

text: Aˇ

text: τ

text: as

text: q

text: p

text: and

text: i

text: q

text: σ

text: τ

text: for

text: some

text: σ

text: T

text: since

text: q

text: p

text: This

text: completes

text: the

text: proof

text: of

text: the

text: i

text: assertion.

text: M

text: Let

text: G

text: be

text: generic.

text: We

text: try

text: to

text: show

text: that

text: V

text: [G]

text: α

text: (λ)

text: µ+.

text: By

text: M

text: the

text: fact

text: that

text: λ

text: is

text: in

text: V

text: we

text: can

text: see

text: that

text: λ

text: is

text: (and

text: hence

text: Magidor)

text: in

text: ℵ

text: V

text: [G].

text: Assume

text: that

text: f

text: [λ]

text: µ+.

text: Let

text: A

text: be

text: a

text: bounded

text: subset

text: of

text: λ

text: of


text: THE FIRST OMITTING CARDINAL FOR MAGIDORITY 3 Laver proved in [6] that if κ is supercompact then one can deﬁne a forcing P notion which makes κ indestructible upon any further extension by κ- P directed-closed forcing notions. The forcing is a set forcing, based on the so-called Laver’s diamond. Arrows notation in this paper is coherent with the common literature. ℵ The notation [λ] 0-bd refers to all bounded subsets of λ whose cardinality ℵ is , regardless of their order type. We shall use the notation [λ]ω-bd if 0 we restrict ourselves to bounded sets of order type ω. We mention here → ℵ only the less frequent relation λ [λ] 0-bd which means that for every ℵ → ∈ ν,<ν | (cid:48)(cid:48) ℵ | f : [λ] 0-bd ν there exists A [λ]λ for which f [A] 0-bd < ν. In general, the arrows notation is designed in order to keep monotonicity, but this need → ℵ not hold for λ [λ] 0-bd with respect to the subscript. ν,<ν We shall mention cardinals in the family of rank-into-rank, so let us recall the deﬁnitions of I0 and I1. A cardinal λ is I1 iﬀ there exists a non-trivial → elementary embedding  : V V . A cardinal λ is I0 iﬀ there is → λ+1 λ+1  : L(V ) L(V ) so that crit() < λ. Every I1 cardinal λ is Magidor, λ+1 λ+1 by a simple observation of Menachem Magidor ([5], Question 24.1). Finally, we shall have to know that under some circumstances the as- sertion I1(κ, λ) is preserved by forcing. We shall use, for this end, Silver’s criterion. We phrase the pertinent theorem in a bit more generality than we actually need, see [1], Proposition 9.1: Theorem 0.1. Silver’s criterion. → Let  : M N be an elementary embedding, where M, N are transitive P ∈ ⊆ P models of ZFC. Let M be a forcing notion, and G a generic subset P over M. Assume H is a generic subset of ( ) over N. Then the following two statements are equivalent: ∈ ∈ (a) (p) H for every p G. → (b) There exists an elementary embedding + : M[G] N[H] so that (cid:22) +(G) = H and + M = . (cid:3) 0.1

text: THE

text: FIRST

text: OMITTING

text: CARDINAL

text: FOR

text: MAGIDORITY

text: Laver

text: proved

text: in

text: that

text: if

text: κ

text: is

text: supercompact

text: then

text: one

text: can

text: deﬁne

text: a

text: forcing

text: P

text: notion

text: which

text: makes

text: κ

text: indestructible

text: upon

text: any

text: further

text: extension

text: by

text: κ-

text: P

text: directed-closed

text: forcing

text: notions.

text: The

text: forcing

text: is

text: a

text: set

text: forcing,

text: based

text: on

text: the

text: so-called

text: Laver’s

text: diamond.

text: Arrows

text: notation

text: in

text: this

text: paper

text: is

text: coherent

text: with

text: the

text: common

text: literature.

text: ℵ

text: The

text: notation

text: [λ]

text: refers

text: to

text: all

text: bounded

text: subsets

text: of

text: λ

text: whose

text: cardinality

text: ℵ

text: is

text: regardless

text: of

text: their

text: order

text: type.

text: We

text: shall

text: use

text: the

text: notation

text: [λ]ω-bd

text: if

text: we

text: restrict

text: ourselves

text: to

text: bounded

text: sets

text: of

text: order

text: type

text: ω.

text: We

text: mention

text: here

text: ℵ

text: only

text: the

text: less

text: frequent

text: relation

text: λ

text: [λ]

text: which

text: means

text: that

text: for

text: every

text: ℵ

text: ν,<ν

text: ℵ

text: f

text: [λ]

text: ν

text: there

text: exists

text: A

text: [λ]λ

text: for

text: which

text: f

text: [A]

text: ν.

text: In

text: general,

text: the

text: arrows

text: notation

text: is

text: designed

text: in

text: order

text: to

text: keep

text: monotonicity,

text: but

text: this

text: need

text: ℵ

text: not

text: hold

text: for

text: λ

text: [λ]

text: with

text: respect

text: to

text: the

text: subscript.

text: ν,<ν

text: We

text: shall

text: mention

text: cardinals

text: in

text: the

text: family

text: of

text: rank-into-rank,

text: so

text: let

text: us

text: recall

text: the

text: deﬁnitions

text: of

text: and

text: A

text: cardinal

text: λ

text: is

text: iﬀ

text: there

text: exists

text: a

text: non-trivial

text: elementary

text: embedding

text: V

text: V

text: A

text: cardinal

text: λ

text: is

text: iﬀ

text: there

text: is

text: L(V

text: L(V

text: so

text: that

text: crit()

text: λ.

text: Every

text: cardinal

text: λ

text: is

text: Magidor,

text: by

text: a

text: simple

text: observation

text: of

text: Menachem

text: Magidor

text: Question

text: Finally,

text: we

text: shall

text: have

text: to

text: know

text: that

text: under

text: some

text: circumstances

text: the

text: as-

text: sertion

text: λ)

text: is

text: preserved

text: by

text: forcing.

text: We

text: shall

text: use,

text: for

text: this

text: end,

text: Silver’s

text: criterion.

text: We

text: phrase

text: the

text: pertinent

text: theorem

text: in

text: a

text: bit

text: more

text: generality

text: than

text: we

text: actually

text: need,

text: see

text: Proposition

text: Theorem

text: Silver’s

text: criterion.

text: Let

text: M

text: N

text: be

text: an

text: elementary

text: embedding,

text: where

text: M,

text: N

text: are

text: transitive

text: P

text: P

text: models

text: of

text: ZFC.

text: Let

text: M

text: be

text: a

text: forcing

text: notion,

text: and

text: G

text: a

text: generic

text: subset

text: P

text: over

text: M.

text: Assume

text: H

text: is

text: a

text: generic

text: subset

text: of

text: over

text: N.

text: Then

text: the

text: following

text: two

text: statements

text: are

text: equivalent:

text: (a)

text: (p)

text: H

text: for

text: every

text: p

text: G.

text: (b)

text: There

text: exists

text: an

text: elementary

text: embedding

text: M[G]

text: N[H]

text: so

text: that

text: +(G)

text: H

text: and

text: M