Wikipedia e la cardinalità dell'insieme delle parti

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

Wikipedia e la cardinalità dell'insieme delle parti

Messaggioda nicoletta il gio 25 set 2008, 12:44

Seguendo questo link è possibile leggere una dimostrazione per induzione sulla cardinalità dell'insieme delle parti (paragrafo "insiemi finiti") .

La dimostrazione vine fatta sull'insieme S; nell'ipotesi induttiva viene usato l'insieme T.
Mi domando, ma lo sviluppo del passo induttivo non va fatto sempre rispetto a S, usando T solo per definire una "legge" ?
nicoletta
 
Messaggi: 2
Iscritto il: gio 25 set 2008, 12:39

Messaggioda vl4d il ven 26 set 2008, 8:48

La tua obiezione mi sembra corretta: in quella dim. T viene usato sia per denotare S che per
definire la legge... anche con questa notazione però il "senso" della dimostrazione rimane chiaro...
spostato in teoria - vl4d
Carlo Comin
Avatar utente
vl4d
 
Messaggi: 140
Iscritto il: ven 13 giu 2008, 13:54

Messaggioda desh il ven 26 set 2008, 15:17

Sbaglio o è possibile, formalizzando l'osservazione
wikipedia ha scritto:(Si può - come si fa abitualmente con i computer - rappresentare gli elementi di \mathcal{P}(S) come numeri a n bit; l'n-mo bit si riferisce alla presenza o all'assenza dell' n-mo elemento di S. Ci sono 2n di tali numeri.)

Scrivere una dimostrazione che non utilizzi l'induzione?
desh
 
Messaggi: 115
Iscritto il: mar 17 giu 2008, 16:39

Messaggioda pic il ven 26 set 2008, 16:02

Ci sono molti modi di dimostrare quella cosa, anche senza induzione. Il problema è cosa ci fa questo thread in Logica. Ora lo metto in Combinatoria.
Avatar utente
pic
 
Messaggi: 693
Iscritto il: gio 12 giu 2008, 14:32
Località: London, UK

Messaggioda MindFlyer il gio 2 ott 2008, 6:22

@ pic:
Abbi pazienza, ma la teoria degli insiemi, fino a prova contraria, è logica. Risposto in Logica --> Teoria e lascio un thread-ombra in Combinatoria --> Teoria.

@ desh & pic:
Per niente, sei costretto ad usare l'induzione per dimostrare quella cosa. Magari tu riesci a scrivere una dimostrazione senza dire "induzione", ma è perché la stai scrivendo in Italiano e non in linguaggio matematico. Prova a dimostrarla con gli assiomi di Peano, togliendo l'induzione...

@ nicoletta:
In genere si sconsiglia di consultare la wikipedia italiana su argomenti di matematica. Quella inglese, per esempio, non contiene errori molto grossolani. Io personalmente consulto quella italiana solo quando ho bisogno di sapere come si traducono certe parole, quindi solo per consultazioni sulla "terminologia".

@ nicoletta & vlad:
(finalmente in topic :rolleyes: )
La dimostrazione scritta così è formalmente ineccepibile, anche se scritta all'italiana (i.e. coi piedi). S o T sono solo nomi: la proposizione da dimostrare è che insiemi con cardinalità n hanno insieme delle parti con cardinalità 2^n, e l'induzione è su n e non su altro.
"Victorious warriors win first and then go to war, while defeated warriors go to war first and then seek to win."
Sun Tzu ~ The Art of War
Avatar utente
MindFlyer
 
Messaggi: 90
Iscritto il: ven 13 giu 2008, 18:09

Messaggioda pic il ven 3 ott 2008, 21:07

Ok, in effetti il thread parla della dimostrazione più che del fatto in sé.
:bye:
Avatar utente
pic
 
Messaggi: 693
Iscritto il: gio 12 giu 2008, 14:32
Località: London, UK

Messaggioda Oblomov il sab 4 ott 2008, 17:27

Lungi dal dubitare dell'affermazione di Mind, eh...

Se ci troviamo in insiemi finiti si può usare un metodo classico: ogni elemento dell'insieme di partenza A (il quale ha, con grande fantasia, n elementi) può trovarsi o meno in un dato insieme che è elemento di P(A), quindi abbiamo due possibilità per ogni elemento di A. Poiché A ha n elementi, si conclude che P(A) deve avere 2^n elementi.

MindFlyer ha scritto:@ desh & pic:
Per niente, sei costretto ad usare l'induzione per dimostrare quella cosa. Magari tu riesci a scrivere una dimostrazione senza dire "induzione", ma è perché la stai scrivendo in Italiano e non in linguaggio matematico. Prova a dimostrarla con gli assiomi di Peano, togliendo l'induzione...

Ecco, io mi rendo conto che quanto soprascritto non sia certo una dimostrazione nel senso più rigoroso del termine, ma non vedo perché non possa essere "tradotta" in termini formali (penso a giochetti come far corrispondere a ogni elemento di P(A) un opportuno numero binario et similia). In altre parole: hai una dimostrazione di quanto affermi? (ah,adoro la ricorsività :mrgreen: ).

A questo punto vorremmo almeno un linkino a una dimostrazione "a prova di bomba" facente uso solo degli assiomi di Peano... si può?

Grazie Mind e scusa per la seccatura.
Saluti
Ob
Oblomov
 
Messaggi: 18
Iscritto il: sab 14 giu 2008, 0:00

Messaggioda MindFlyer il dom 5 ott 2008, 15:44

Oblomov ha scritto:A questo punto vorremmo almeno un linkino a una dimostrazione "a prova di bomba" facente uso solo degli assiomi di Peano... si può?
Grazie Mind e scusa per la seccatura.

Nessuna seccatura!!

Allora, non ho un linkino ad una dimostrazione di quel fatto, scritta usando gli assiomi di Peano. Né ho intenzione di scriverla io, perché richiederebbe un lavoro di formalizzazione dell'enunciato, e di pianificazione della dimostrazione tutt'altro che breve!!

La cosa che posso fare (probabilmente più utile) è proporre un esercizio classico --molto classico--, che può far capire meglio i limiti di PA^-, ossia la teoria di Peano senza assioma/i d'induzione.
Eccolo!
"Victorious warriors win first and then go to war, while defeated warriors go to war first and then seek to win."
Sun Tzu ~ The Art of War
Avatar utente
MindFlyer
 
Messaggi: 90
Iscritto il: ven 13 giu 2008, 18:09

Messaggioda fields il dom 5 ott 2008, 22:25

Gia', senza induzione non si dimostra un cavolo. Nemmeno che \forall x\ x+1=1+x :rotfl:
fields
 
Messaggi: 72
Iscritto il: ven 13 giu 2008, 14:44

Messaggioda MindFlyer il lun 6 ott 2008, 7:18

fields ha scritto:Gia', senza induzione non si dimostra un cavolo. Nemmeno che \forall x\ x+1=1+x :rotfl:

Questo dipende da come definisci il +, e dal linguaggio su cui definisci la teoria. Per esempio, se includi il + nel linguaggio, vorrai mettere tutti gli assiomi di monoide abeliano (e in questo caso hai gratis la tua proposizione). Di solito si includono anche * e <, nel linguaggio "standard", per un totale di una quindicina di assiomi, esclusa l'induzione. Resta il fatto che, anche con questi assiomi che definiscono le operazioni e l'ordinamento, è impossibile dimostrare che ogni numero è pari oppure dispari, senza induzione.
"Victorious warriors win first and then go to war, while defeated warriors go to war first and then seek to win."
Sun Tzu ~ The Art of War
Avatar utente
MindFlyer
 
Messaggi: 90
Iscritto il: ven 13 giu 2008, 18:09

Prossimo

Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite