Ogni funzione simmetrica può essere scritta come una funzione di una somma?
Sto cercando un semplice controesempio a un "teorema" sulle funzioni simmetriche rivendicato in un articolo pubblicato. L'affermazione afferma, tra molte altre cose, che ci sono funzioni$\sigma$e$\rho$tale che, per tutti$x,y\in\mathbb R$,$$ \max(x,y) = \sigma(\rho(x) + \rho(y)). $$Il documento non specifica il dominio di$\sigma$, che è, ovviamente, anche la gamma di$\rho$. Indicherò questo sconosciuto con$G$. E supponiamo che$G$è un tipo ben noto di oggetto matematico, in cui l'addizione è convenzionalmente definita, ad esempio un semigruppo abeliano.
Può$\sigma$e$\rho$essere trovato, se$G$è un (semi)gruppo abeliano? Cosa succede se$X$è un insieme e$G = \mathbb R^X$è l'insieme delle funzioni da$X$a$\mathbb R$?
In realtà, dal momento che i numeri reali non possono essere gestiti da una macchina di Turing, e la rivista in cui compare l'articolo è dedicata all'informatica, preferirei una discussione in cui i reali fossero sostituiti in tutto il passaggio precedente dagli interi. Mi aspetto che l'affermazione sia errata per qualsiasi contesto ragionevole (non finito).
Se i reali sono sostituiti da un intervallo chiuso finito di numeri reali, qualsiasi funzione simmetrica continua può essere approssimata da un polinomio simmetrico, e quindi si possono usare le identità di Newton per ottenere un risultato approssimativo. Forse questo è ciò che l'autore dell'articolo in questione pensava, ma non affermava.
Risposte
Rispondo alla tua domanda per$\mathbb{R} \to \mathbb{R}$.
Permettere$r(x,y) = p(x) + p(y)$. La tua domanda si riduce al fatto che esista$p$tale che$r$è iniettiva fino alla simmetria.
Da$\mathbb{R}$ha una dimensione innumerevole$\mathbb{Q}$, esiste per ciascuno$x \in \mathbb{R}$alcuni$t_x \in \mathbb{R}$tale che il set$\{t_x \}_x$è linearmente indipendente. Impostare$p(x) = t_x$, Così$r$è iniettiva e quindi esiste a$\sigma$come desiderato.
(Questo usa l'assioma della scelta.)
Modifica: immagino che utilizzi anche l'ipotesi del continuum. Immagino che dovrebbe esserci una prova per evitare alcuni di questi?
Modifica 2: come sottolineato nei commenti, CH non è necessario.
Per numeri interi: Let$ρ(x) = 2^x$per ogni numero intero$x$. Poi dato$ρ(x)+ρ(y)$puoi guardare la forma binaria per determinare$x,y$e quindi il loro massimo.
Una versione più concreta dell'idea dalla risposta di user21820 , per la situazione in cui il dominio del discorso sono i numeri interi:
Definire$\rho(x) = 4^x$, e definire$\sigma(t) = \lfloor \log_4 t\rfloor$, dove$\log_4$è il logaritmo in base 4.
Per davvero: Let$d(x,k) = \lfloor x·2^k \rfloor$per ogni$x∈ℝ$e naturale$k$. Permettere$ρ(x) = \{ ⟨k,2^{d(x,k)}⟩ : k∈ℕ \}$per ogni$x∈ℝ$. Quindi$ρ(x)$rappresenta una sequenza univoca da$ℕ$per ciascuno$x∈ℝ$. Definisci addizione su sequenze da$ℕ$essere un'addizione puntuale. Quindi per qualsiasi$x,y∈ℝ$, possiamo determinare$z = \max(x,y)$da$ρ(x)+ρ(y)$come segue.
Possiamo facilmente ottenere$S(k) = \{d(x,k),d(y,k)\}$per ciascuno$k∈ℕ$. E$d(z,k) = \max(d(x,k),d(y,k))$per ogni$k∈ℕ$. Per capire perché, nota che: (1) per qualsiasi$m∈ℕ$abbiamo che se$d(x,m) > d(y,m)$poi$d(x,k) > d(y,k)$per ogni$k∈ℕ_{>m}$anche; (2) se$x > y $poi$d(x,m) > d(y,m)$per alcuni$m∈ℕ$. Quindi possiamo ottenere$z$poiché è univocamente determinato da$\{ ⟨k,d(z,k)⟩ : k∈ℕ \}$.
Questo è completamente costruttivo (ciascuna delle funzioni desiderate è calcolabile dove ogni input o output$x$è dato come un oracolo per$d(x,•)$).
La soluzione per numeri interi si generalizza a una soluzione costruttiva per numeri reali, come segue.
Definire$\rho$, per prima cosa applica una mappa costruttiva rigorosamente crescente da ridurre al caso in cui tutti i nostri numeri si trovano tra$0$e$1$. Una di queste trasformazioni è$x' = \frac12 + \frac1\pi \arctan x$.
Quindi, dato un valore$x' \in (0,1)$, annotare la sequenza di zeri e uno:
- Un blocco di lunghezza$3$in cui la$\lceil 2x'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$.
- Un blocco di lunghezza$4$in cui la$\lceil 3x'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$.
- Un blocco di lunghezza$5$in cui la$\lceil 4x'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$.
- E così via. In generale, per ciascuno$n$, un blocco di lunghezza$n+1$in cui la$\lceil nx'\rceil^{\text{th}}$po' è un$1$, e gli altri lo sono$0$. Si noti che l'ultimo bit in ogni blocco è$0$.
Allora prendi$\rho(x) \in (0,1)$essere il numero la cui espansione binaria è questa sequenza.
Dato$\rho(x) + \rho(y)$, possiamo trovare$\max\{x,y\}$come segue. La somma dei blocchi di lunghezza$n+1$ci dice$2^{\lceil nx'\rceil} + 2^{\lceil ny'\rceil}$, da cui possiamo dedurre$\lceil nx'\rceil$e$\lceil ny'\rceil$fino alla permutazione. Possiamo capirlo per arbitrariamente grande$n$, che ci fornisce una sequenza di approssimazioni arbitrariamente buone a$x'$e$y'$, da cui$x$e$y$può anche essere trovato.