$ % 17-Mar-2025 \def\Nat{\mathbb{N}} \def\N{\Nat} \def\Seq#1{{#1}^{\star}} \def\alt#1#2{[#1,#2]} \def\ana#1{(\hskip -1ex[#1]\hskip -1ex )} \def\atmost{\subseteq} \def\bang{{!}} \def\cata#1{(\hskip -1.1pt[\hskip 0.1pt #1 \hskip 0.1pt]\hskip -1.1pt)} \def\comp{\mathbin\cdot} \def\conj#1#2{\mathopen{\langle} #1, #2\mathclose{\rangle}} \def\conv#1{#1^\circ} \def\crflx#1{\Phi_{#1}} \def\dom#1{\delta {#1}} \def\fB{\fun B} \def\from{\leftarrow} \def\fun#1{\mathsf{#1}} \def\i#1{\mathit{i}_{#1}} \def\img#1{\mathbf{img}\ {#1}} \def\implied{\Leftarrow} \def\implies{\Rightarrow} \def\inT{\mathsf{in}} \def\iso{\cong} \def\just#1#2{\\& \mathopen{\{}~\mbox{#2}~\mathclose{\}}\\&&} \def\cjust#1#2{\just{#1}{ ..................................................................... }} \def\ker#1{\mathbf{ker}\ {#1}} \def\kons#1{\underline{#1}} \def\larrow#1#2#3{#3\ \xleftarrow{#2}\ #1} \def\ldiv{\mathbin{/}} \def\mcond#1#2#3{#1 \rightarrow #2\;,\;#3} \def\more{\\&&} \def\outT{\mathsf{out}} \def\p#1{\pi_{#1}} \def\plus{\mathbin{\dagger}} \def\rarrow#1#2#3{#1\ \xrightarrow{#2}\ #3} \def\rcb#1#2#3#4{\mathopen{\langle}#1 #2 : #3 : #4\mathclose{\rangle}} \def\rdiv{\mathbin{\setminus}} \def\scata#1{⦅\, #1 \,⦆} \def\sep{\rule{15em}{0.3pt}} \def\sep{\rule{15em}{0.3pt}} \def\shrunkby{\mathbin{\upharpoonright}} \def\sse#1#2{{#1}\subseteq{#2}} \def\start{&&} \def\syd#1#2{\frac{#1}{#2}} \def\to{\rightarrow} \def\trans#1{\overline{#1}} \newenvironment{lcbr}{\left\{\begin{array}{l}}{\end{array}\right.} %-------- \def\Varid#1{\mathbin{#1}} \def\ensuremath#1{#1} \def\Conid#1{\mathbin{#1}} $
Q1 - Na questão 1.3 da primeira ficha prática pede-se para representar a propriedade \begin{eqnarray} J \subseteq \top \comp S \comp \leq \end{eqnarray} como um "quadrado mágico". Como só tenho uma relação $J$ no lado inferior, pensei em: \begin{eqnarray} J \comp id \subseteq \top \comp (S \comp \leq) \end{eqnarray} É isto que era pedido?
R: Sim, não sendo a única resposta válida. Por exemplo, $id \comp J \subseteq (\top \comp S) \comp \leq$ estaria igualmente bem.
Q2 - No exercício 24, para provar que $R \cup S$ é inteira que $R$ ou $S$ o forem, desenvolvi $\ker{(R \cup S)}$ mas não estou a chegar a lado nenhum. Sugestões?
R: A sugestão é basear-se na regra "larger than entire (surjective) is entire (surjective)".
Q3 - No exercício 18, comecei por $R \atmost \conv R$, o que me levou a: \begin{eqnarray} \conv{sq} \comp (1-) \comp {sq} \atmost \conv{sq} \comp \conv{(1-)} \comp {sq} \end{eqnarray} Para andar para a frente, dava-me jeito ter $(1-) \atmost \conv{(1-)}$. Posso assumir isso?
R: Assumir não, mas pode facilmente prová-lo: introduza variáveis em $(1-) \atmost \conv{(1-)}$ e avalie o que obteve.
Q4 - Estava a fazer o exercício 41 e cheguei às leis Distribution (1) e Distribution (2). Contudo, o exercício pede para dizer entre $R$ e $S$S qual é a relação simples e a injetiva. Como posso verificar isso?
R: Não é bem assim: repare que as duas leis que refere têm "side conditions". Já no exercício 41 não aparecem essas condições. Isso significa que passam a ser verdadeiras quando uma das relações $R$ e $S$ é ou simples ou injectiva. É o que precisa de verificar, em cada caso.
Q5 - Tenho uma dúvida no exercício 37 dos slides: não entendo bem o que é suposto fazer-se.
R: Substitua simplicity e $M \cup N$ is simple por injectivity e $M \cup N$ is injective, respectivamente, e desenvolva como fez no exercício anterior.
Q6 - Estou um pouco perdido no exercício 42 dos slides - não sei por onde começar para fazer a prova.
R: A estratégia é sempre começar pelo que queremos demonstrar, que neste caso é: \begin{eqnarray} \ker{\conj R S} = {\ker R}\cap{\ker S} \end{eqnarray} Sabendo que $\ker R = \conv R \comp R$ e expandindo nos três sítios onde aparece, é imediato aplicar o resultado anterior e fica provado.
Q7 - No exercício 51 dos slides, tendo de mostrar que $R$ é inteira e simples, estava a tentar fazer da seguinte forma: $\ker R \atmost id$ e $id \atmost \img R$. Admito que para simplificar tenha de seguir as regras usuais e depois as regras da união; ou existe um caminho mais fácil que me está a escapar?
R: Sim, há uma forma mais rápida de abordar o exercício reparando que $in$ é um isomorfismo (uma função bijectiva, portanto). De facto, a regra (29) dos slides vai poder ser usada aqui - investigue como e porquê.
Q8 - No exercício 56 dos slides, partindo de $a(R \rdiv S)c$, pela (123) tenho $a(Rº/Sº)ºc$. Contudo, como poderia tirar o converso mais exterior?
R: É fácil: quaisquer que sejam $R$, $x$ e $y$, tem-se $x(\conv R)y \equiv y R x$.
Q9 - Na aula (exercício 72 dos slides) porque é que pudemos descer o lado superior de $R \atmost R \cdot \conv R \cdot R$ para $R \cdot \dom R$? Não entendo o porquê de $\dom R \atmost \conv R \comp R$.
R: Tem-se $\dom R$ contido em $\conv R \comp R$ pois $\dom R = id \cap R \comp R$ e, por cancelamento da lei universal-$\cap$, $X \cap Y \atmost Y$.
Q10 - No 2º teste de 2023/24 (questão 6) tem-se a certo ponto $S \comp \conv R \cap id \atmost \bot$, que se converte em: $S \comp \conv R \atmost (id \implies \bot)$. Mas, segundo a regra (5.148), não deveria ser $id \atmost (S \comp \conv R \implies \bot)$?
R: Estão ambas certas pois a interseção é comutativa, i.é $S \comp \conv R \cap id = id \cap S \comp \conv R$ (etc).
Q11 - Na ficha 3 (último exercício) eu comecei por escrever a propriedade pedida de forma pointwise:\begin{eqnarray} \rcb \forall{a,b}{b R a \vee b S a}{ \rcb\exists{c}{}{c I a} } \end{eqnarray} com o objetivo de dizer que se um número tem uma nota atribuída por $R$ ou por $S$ então esse número tem de corresponder a um nome. A questão é, então: como posso tirar o existencial para conseguir escrever isto de forma pointfree?
R: Repare que a ausência de âmbito em $\rcb\exists{c}{}{c I a}$ corresponde a ter âmbito incondicionalmente verdadeiro, i.é $\rcb\exists{c}{True}{c I a}$. Veja como converter esse $True$ em algo que lhe abra a porta a uma composição de relações.