Imagens de conjuntos, relações de equivalência e negação lógica
Introduzido| English | Significado |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | pré-imagem |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | relação de equivalência |
| negation/nɪˈɡeɪʃn/ | negação |
Dois registros, um rótulo
- Uma função hash envia arquivos distintos $a$ e $b$ para o mesmo rótulo $L$. Com $A=\{a\}$ e $B=\{b\}$, a imagem de $A\cap B$ é vazia, mas $f(A)\cap f(B)=\{L\}$.
- O mesmo rótulo não significa necessariamente a mesma entrada. Essa distinção conecta pré-imagens, relações de equivalência e negação lógica.
Enuncie os dois universos
- Fixe $f:X\to Y$. Para $A\subseteq X$, sua imagem é $f(A)=\{f(x):x\in A\}$. Para $C\subseteq Y$, sua pré-imagem é $f^{-1}(C)=\{x\in X:f(x)\in C\}$.
- O símbolo $f^{-1}(C)$ descreve um conjunto de entradas, mesmo quando $f$ não possui função inversa. Complementos devem nomear seu universo: $X\setminus A$ e $Y\setminus C$ vivem em conjuntos diferentes.
Por que imagens preservam uniões
- Se $y\in f(A\cup B)$, alguma entrada $x\in A\cup B$ mapeia para $y$. Essa entrada está em $A$ ou $B$, logo $y\in f(A)\cup f(B)$.
- Reciprocamente, a pertença a qualquer imagem fornece uma entrada em $A\cup B$. As duas inclusões provam $f(A\cup B)=f(A)\cup f(B)$, sem qualquer suposição de injetividade.
Interseções: uma entrada ou duas?
- If $y\in f(A\cap B)$, one input belongs to both sets and maps to $y$. Thus $f(A\cap B)\subseteq f(A)\cap f(B)$. In the reverse direction, the two inputs might differ: squaring sends both $-1$ and $1$ to $1$.
- Se $f$ for injetiva, saídas iguais forçam essas entradas a concordarem, resultando em igualdade. Igualdade para todo par $A,B$ também força injetividade: uma colisão dá singulares disjuntos com imagens sobrepostas. Igualdade para um único par, como $A=B$, nada prova sobre injetividade.
For every function $f$ and sets $A, B$ in its domain, which always holds?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Union equality holds for every map. The other equalities/inclusion become valid for every pair under injectivity, but can fail for a map with a collision. A particular pair can still give equality without injectivity.
Let $a,b$ be distinct and $f(a)=f(b)=L$. For $A=\{a\}$ e $B=\{b\}$, what are $f(A\cap B)$ e $f(A)\cap f(B)$?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The input intersection is empty, but both image sets contain L.
Diferenças e complementos podem falhar
- Sempre $f(A)\setminus f(B)\subseteq f(A\setminus B)$: uma saída ausente de $f(B)$ não tem entrada em $B$. A recíproca pode falhar. Se $f(a)=f(b)=L$, então $A=\{a\}$ e $B=\{b\}$ dão $\{L\}$ à direita, mas o conjunto vazio à esquerda.
- Seja $X=\{a,b,c\}$, $Y=\{L,M,N\}$, com $a,b\mapsto L$ e $c\mapsto M$. Para $A=\{a\}$, a imagem de $X\setminus A$ é $\{L,M\}$, enquanto $Y\setminus f(A)=\{M,N\}$. Preservar complementos relativos a todo $Y$, para cada $A$, exige uma bijeção.
Prove that images preserve unions and give intersection inclusion. Then use a collision to disprove image-difference equality.
Compare os quantificadores, universos dos conjuntos e testemunhas explícitas no seu raciocínio.
Pré-imagens preservam operações de conjuntos
- Para $C,D\subseteq Y$, uma entrada mapeia dentro de $C\cup D$ exatamente quando mapeia dentro de pelo menos um conjunto. Mapeia dentro de $C\cap D$ exatamente quando mapeia dentro de ambos. Logo, pré-imagens preservam tanto uniões quanto interseções.
- Também $f^{-1}(Y\setminus C)=X\setminus f^{-1}(C)$: ambos os lados contêm exatamente as entradas cujas saídas estão fora de $C$. Nenhuma dessas identidades precisa de injetividade ou sobrejetividade.
$f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ for every function $f$.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
An input maps into C ∩ D exactly when it maps into both C and D; injectivity is unnecessary.
Ir e voltar
- A identidade $f(f^{-1}(C))=C\cap f(X)$ mantém apenas saídas alcançáveis. No mapa finito acima, $C=\{L,N\}$ tem pré-imagem $\{a,b\}$ e imagem-da-pré-imagem $\{L\}$: saída ausente $N$ não pode aparecer.
- Sempre $A\subseteq f^{-1}(f(A))$. Esta viagem de ida e volta adiciona toda entrada que compartilha uma saída com $A$. Para $A=\{a\}$, isso resulta em $\{a,b\}$. Igualdade para cada $A$ ocorre exatamente quando $f$ é injetiva.
Válido para todo o mapa?
Distinguir identidades universais de afirmações que exigem hipóteses adicionais.
A favor $f(x)=x^2$ on $\mathbb R$ e $A=\{-2\}$, how many elements belong to $f^{-1}(f(A))$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
f(A)={4}, whose preimage is {-2,2}. The round trip can add inputs.
Let $X=\{a,b,c\}$, $Y=\{L,M,N\}$, $f(a)=f(b)=L$, $f(c)=M$, and $C=\{L,N\}$. Find $f(f^{-1}(C))$.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Only L is in both C and the image {L,M}. No input maps to N.
Use $a,b\mapsto L$, $c\mapsto M$ from $X=\{a,b,c\}$ até $Y=\{L,M,N\}$. For $A=\{a\}$ e $C=\{L,N\}$, find $f^{-1}(f(A))$, $f(f^{-1}(C))$, and $f^{-1}(Y\setminus C)$. Explain each change.
Compare os quantificadores, universos dos conjuntos e testemunhas explícitas no seu raciocínio.
Três propriedades de relação
- A relation on a set $S$ is reflexive if $x\sim x$ for every $x\in S$, and symmetric if $x\sim y$ implies $y\sim x$ for every pair. A single failing element or pair disproves the corresponding property.
- A transitividade exige que $x\sim y$ e $y\sim z$ impliquem $x\sim z$ para todo triplo. Uma relação de equivalência possui as três propriedades. Sempre mencione $S$: alterar os elementos permitidos pode mudar a resposta.
Por que classes de equivalência particionam um conjunto
- Defina $[x]=\{y\in S:y\sim x\}$. A reflexividade coloca $x$ em $[x]$, assim as classes cobrem $S$. Cada classe é não vazia.
- If $z\in[x]\cap[y]$, symmetry and transitivity give $x\sim y$. Any $w\sim x$ then also satisfies $w\sim y$, so $[x]\subseteq[y]$; reversing the roles gives equality. Distinct classes are therefore disjoint: together they form a partition.
Restos fornecem classes completas
- On $\mathbb Z$, let $x\sim y$ mean $4$ divides $x-y$. Reflexivity follows from $x-x=0$; symmetry from changing the sign; transitivity from adding two differences divisible by $4$.
- As quatro classes são $[0],[1],[2],[3]$, com $[r]=\{r+4k:k\in\mathbb Z\}$. Inteiros negativos também pertencem: $-1\in[3]$. Substituir $4$ por $6$ resulta em exatamente seis classes, pois todo inteiro possui um único resto de $0$ a $5$.
How many equivalence classes does “same remainder mod 6” have on $\mathbb Z$?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Two integers are related when they leave the same remainder on division by 6. The possible remainders 0, 1, …, 5 give exactly 6 classes.
Quadrados iguais, classe igual
- On $\mathbb R$, $x\sim y$ when $x=\pm y$, equivalently $x^2=y^2$. Equality of these outputs is reflexive, symmetric and transitive, so this is an equivalence relation.
- Para $x\ne0$, a classe é $\{x,-x\}$; a classe do zero é apenas $\{0\}$. De forma geral, qualquer função agrupa entradas em classes de equivalência por saída igual, independentemente da função ser injetora ou não.
Encontre a propriedade que falha
- Em $\mathbb R$, $|x-y|\le1$ falha na transitividade usando $0,1,2$. Em $\mathbb Z$, diferença ímpar falha na reflexividade porque $x-x=0$; também falha na transitividade usando $1,2,3$. Ambas as relações são simétricas.
- A relação $x\le y$ sobre $\mathbb R$ falha na simetria usando $0,1$. A relação $xy>0$ sobre $\mathbb R\setminus\{0\}$ é equivalência por sinal, mas em todo o conjunto de $\mathbb R$ falha na reflexividade no zero. O universo faz parte da questão.
Relação de equivalência?
Verifique reflexividade, simetria e transitividade juntas.
Ativo $\mathbb Z$, the relation “$x - y$ is odd” is
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
It fails reflexivity because x − x = 0 is even. It is symmetric (x − y odd ⇒ y − x odd) but not transitive: 1 − 2 and 2 − 3 are odd, yet 1 − 3 is even.
The relation $xy>0$ is an equivalence relation on all of $\mathbb R$.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
At x=0, x² is not positive, so reflexivity fails. Removing zero gives an equivalence relation with two sign classes.
Prove that $6\mid(x-y)$ defines an equivalence relation on $\mathbb Z$ and describe its classes. Explain why replacing “divisible by 6” by “odd” fails.
Compare os quantificadores, universos dos conjuntos e testemunhas explícitas no seu raciocínio.
Implicação e seu contrapositivo
- $P\Rightarrow Q$ é falso exatamente quando $P$ é verdadeiro e $Q$ é falso. Se $P$ for falso, a implicação é verdadeira. Por exemplo, “se $3$ é divisível por $4$, então $3$ é par” tem premissa falsa e é uma implicação verdadeira.
- A contrapositiva $\neg Q\Rightarrow\neg P$ tem o mesmo valor-verdade que $P\Rightarrow Q$. A recíproca $Q\Rightarrow P$ pode ter diferente: divisibilidade por $4$ implica paridade para inteiros, mas o número par $2$ não é divisível por $4$.
$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is ____.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Truth table of implication.
Negue toda a afirmação
- Negar uma implicação resulta em $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$. As leis de De Morgan trocam “e” por “ou”: por exemplo, $\neg(Q\wedge R)\equiv\neg Q\vee\neg R$.
- Combinando as regras, a negação de $P\Rightarrow(Q\wedge R)$ é $P\wedge(\neg Q\vee\neg R)$. A premissa deve ser verdadeira e pelo menos uma conclusão prometida deve falhar. O “ou” inclui a possibilidade de ambas as conclusões falharem.
A ordem dos quantificadores controla a afirmação
- Em $\mathbb R$, “para todo $x$ existe $y>x$” é verdadeiro: escolha $y=x+1$. “Existe $y$ maior que todo $x$” é falso: defina $x=y$. Mover um quantificador existencial para frente impede que sua escolha dependa de variáveis posteriores.
- Negue um quantificador por vez, mantendo a ordem e os domínios: $\neg(\forall x\,\exists y\,S)\equiv\exists x\,\forall y\,\neg S$. Assim, “todo arquivo armazenado tem hash” é falso exatamente quando algum arquivo armazenado não tem hash; isso não significa que nenhum arquivo tenha hash.
Ativo $\mathbb R$, “for every $x$ there is $y>x$” is equivalent to “there is $y$ such that $y>x$ for every $x$.”
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
The first holds using y=x+1. The second fails by taking x=y for any proposed y.
Negando convergência para zero
- Para uma sequência real, convergir para zero significa: para todo $\varepsilon>0$, existe um inteiro não negativo $N$ tal que todo inteiro positivo $n>N$ satisfaz $|a_n|<\varepsilon$. O limiar $N$ pode depender de $\varepsilon$.
- Sua negação é: existe $\varepsilon>0$ tal que para todo limiar $N$, algum inteiro $n>N$ satisfaz $|a_n|\ge\varepsilon$. Mantenha a condição estrita $n>N$; negue apenas a conclusão $|a_n|<\varepsilon$, incluindo a igualdade em sua falha.
The negation of “for every $\varepsilon > 0$ there is $N$ with $|a_n| < \varepsilon$ for all $n > N$” is
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Flip ∀ε, ∃N, ∀n>N to ∃ε, ∀N, ∃n>N, in that order. Failure of a strict inequality includes equality. Alternating zeros and ones fails at ε=1/2 but has late zeros, and ε=2 never fails.
Arbitrariamente tardio não é eventualmente sempre
- Seja $a_n=1$ para ímpares $n$ e $a_n=0$ para pares $n$. Escolha $\varepsilon=1/2$. Além de qualquer limiar há um índice ímpar com $|a_n|\ge\varepsilon$, logo a sequência não converge para zero.
- Porém, não é eventualmente limitado longe de zero: índices pares fornecem zeros arbitrariamente tarde. Nem toda tolerância positiva falha: $\varepsilon=2$ contém toda a sequência. Uma única tolerância falhada basta; seus índices ruins não precisam incluir todos os índices posteriores.
If a real sequence does not converge to zero, there must be a positive tolerance which every sufficiently late term exceeds or equals in absolute value.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Alternating 1 and 0 has arbitrarily late terms outside ε=1/2, but also arbitrarily late zeros. Some late term for every cutoff is weaker than all terms beyond one cutoff.
Let $a_n=1$ when $n$ is a power of $2$ e $a_n=0$ otherwise. Negate convergence to zero and verify the negation. Does the sequence eventually stay away from zero?
Compare os quantificadores, universos dos conjuntos e testemunhas explícitas no seu raciocínio.
Resumo
- Uma pré-imagem é o conjunto de entradas cujas saídas pertencem a um conjunto especificado. Pré-imagens preservam uniões, interseções e complementos em seus universos declarados; imagens sempre preservam uniões, mas a igualdade da interseção para cada par exige injetividade.
- Uma relação de equivalência é uma relação reflexiva, simétrica e transitiva; suas classes particionam o conjunto subjacente. Uma negação é a afirmação verdadeira exatamente quando a original é falsa. Negue os quantificadores na ordem, mantendo seus domínios e qualquer dependência entre escolhas.