Come creare un combinatore K nella foresta incantata? (Mock a Mockingbird)

Question

Ricordiamo che il combinatore K è una funzione costante. Esso restituisce sempre il suo primo argomento:

Kxy = x for all y 

Nel libro prendere in giro a Mockingbird l'autore presenta un esempio di una foresta incantata contenente uccelli parlanti. Gli uccelli hanno un comportamento:

Dati gli uccelli A e B, se chiami il nome di B in A, allora A risponderà chiamando il nome di un uccello per te: questo uccello designeremo da AB.

Supponiamo che la foresta consista di tre uccelli, A, B e C. È possibile che almeno uno degli uccelli si comporti come il combinatore K?

Di seguito è una tabella che mostra un possibile insieme di comportamenti per gli uccelli nella foresta incantata. La prima colonna ha il nome di ciascun uccello nella foresta. La riga superiore ha i nomi che possono essere chiamati a ogni uccello. Il corpo è la risposta di un uccello a un nome. Ad esempio, se si chiama il nome di A per l'uccello A, l'uccello A risponderà con C (vedere la riga 2, colonna 2). In breve, AA = C. Se chiami il nome di B nell'uccello A, l'uccello A risponderà con B (vedi riga 2, colonna 3). In breve, AB = B. Quale valore dovrebbe andare nello slot vuoto per AC?

| A B C 
------------------ 
A | C B 
B | B B B 
C | A A A 

Vediamo se possiamo far sì che l'uccello A si comporti come il combinatore K. L'insieme di valori sopra sembra promettente:

• AA = C e Cy = A per tutti y. Cioè, (AA) y = A per tutti y.

• AB = B e By = B per tutti y. Cioè, (AB) y = B per tutti y.

Quale valore deve essere inserito nello slot vuoto (CA)? Considerare tutti i casi:

• Se AC = A allora il valore di Ay deve essere C per ogni y, che è chiaramente falso. Pertanto, A non può essere il valore corretto per lo slot vuoto.

• Se AC = B, allora il valore di By deve essere C per tutti y, che è chiaramente false. Pertanto, B non può essere il valore corretto per lo slot vuoto.

• Se AC = C, il valore di Cy deve essere C per tutti y, che è chiaramente false. Pertanto C non può essere il valore corretto per lo slot vuoto.

Pertanto nessun valore può essere inserito nello slot vuoto per soddisfare la condizione (AC) y = C, per ogni y.

Per quanto posso dire, è impossibile far si che un uccello si comporti come un combinatore K. Spero che mi dimostrerai sbagliato.

Answer 1

Mi piace la risposta di Judge Mental, quindi per coloro che hanno problemi a ottenerlo, lo spiegherò di più.

---

Sia G l'insieme di tutte le funzioni.

Sia F un sottoinsieme G tale che | F | > 1 e ∀f ∈ F (f: F → F). (F è il set di uccelli.)

Diamo 1 _F sia la funzione identità di F.

Supponiamo per una contraddizione che ci ∃k ∈ F (∀ (f, g) ∈ (F × F) (kfg = f)). Risolvi un tale k. In altre parole, ∀f ∈ F (kf è costante). Per definizione, ∀f ∈ F (kkf = k). Quindi ∀f ∈ F (kf = 1 _F perché k ha un inverso a sinistra per Lemma sotto). Quindi abbiamo ∀f ∈ F (kf è costante e kf = 1 _F), che è chiaramente assurdo perché | F | > 1.

Lemma: Sia (f, g) ∈ (F × F) tale che kf = kg. Per definizione di k, ∀h ∈ F (kfh = f). Quindi ∀h ∈ F (f = kfh = (kf) h = (kg) h = kgh = g). Questo può accadere solo se f = g. Quindi k iniettabile. Quindi k deve avere l'inversa a sinistra.

Answer 2

Sei corretto. È impossibile per un numero finito di uccelli superiore a 1.

L'argomento semplice è se ci fosse un tale uccello K, ogni uccello nell'immagine di K sarebbe costante (per definizione), e ogni uccello sarebbe nell'immagine di K (per un argomento di cardinalità), tra cui K stesso, che è ovviamente non costante.