Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators  Can someone give a hint?
122643
Earlier this day I ask about the assignmet:  Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators.  I was given the hint that I could use De Morgan law to show that $p \vee q$ is logically equivalent to $\neg (\neg p \wedge \neg q)$.  $$\neg (\neg p \wedge \neg q) \equiv \neg (\neg p) \vee \neg (\neg q)$$  $$\neg (\neg p) \vee \neg (\neg q) \equiv p \vee q$$  But I cannot figure out? am I done?
32490
$(p∨q) ∧ (p∨r) ∧ (q∨r) \iff (p∧q) ∨ (p∧r) ∨ (q∧r)$  Without using set theory, how can I prove this using logical equivalences? I've tried to approach this problem with De Morgan and I've also tried the property of distributivity but I keep reaching a dead end.   How should I approach this problem?  Thank  you.
105983
I have a question for my exam and I find it hard to understand.  I have to prove that the following formula is logically valid:    The professor told me to "push" all the symbols inside the brackets, and use the deduction theorem.  But I don't know how to do it, because I can't find the identities to push the "exist" symbol inside the brackets.  Your help is appriciated, thank you.  Alan
35166
There are several proofs I have seen of this, but they all seem to use choice subtely at some point. Is there any way to prove this without choice, or is it possibly unproveable?
124023
(c) Let $\mathcal{L}^*\subseteq\mathcal{L}^{\text{FOPC}}$ be a first order language of predicate calculus consisting of three unary function symbols $f,g,h$.  (i) Write down an $\mathcal{L}^*$-sentence $\phi$ such if $\mathcal{A}$ is an $\mathcal{L}^*$-structure with $\mathcal{A}\vDash\phi$ then the restriction of $h_\mathcal{A}$ to the range of $f_\mathcal{A}$ gives a one-to-one function onto the range of $g_\mathcal{A}$.  (ii) Write down an $\mathcal{L}^*$-sentence $\psi$ such that if $\mathcal{A}$ is an $\mathcal{L}^*$-structure with $\mathcal{A}\vDash\psi$ and the domain $A$ of $\mathcal{A}$ is finite then the cardinality $|A|$ is a square.    Part (i) is easy enough, but I'm having trouble with part (ii). I assume that you can use part (i). My initial idea was to use $h$ to ensure $|Range(f_A)| =|Range(g_A)|$ but I'm not sure where to go from there. Thanks.
38223
How can someone prove, that over a Hilbert space $\mathcal{H}$ with $dim \mathcal{H} \geq 2$, the set of all self-adjoint operators doesn't form a lattice?  I found a result from Kadison, that if two self adjoint operators $A, B$ are not comparable, then they don't have a least upper bound. In 2 dimensions, I got two upper bounds of the (standard) projections $P_1, P_2$, which are not comparable. I think its not enough, but I can't go any further.   Please help!
74389
And the same goes for the existential quantifier: $\exists x \in A : P(x) \; \Leftrightarrow \; \exists x (x \in A \wedge P(x))$. Why couldn’t it be: $\exists x \in A : P(x) \; \Leftrightarrow \; \exists x (x \in A \implies P(x))$ and $\forall x \in A : P(x) \; \Leftrightarrow \; \forall x (x \in A \wedge P(x))$?
50635
Question    Suppose we are dealing with real valued functions $f(x)$ of one real variable $x$. We say that the limit of $f(x)$ at point $a$ exists and equals to $L$ if and only if  $$\exists L:\left( {\forall \varepsilon  &gt; 0,\exists \delta  &gt; 0:\left( {\forall x,0 &lt; \left| {x - a} \right| &lt; \delta  \implies \left| {f(x) - L} \right| &lt; \varepsilon } \right)} \right)$$  and show this by the symbolism  $$\mathop {\lim f(x)}\limits_{x \to a}  = L$$  Now, what do we say when we want to state that the limit of function $f(x)$ does not exist at $a$? In fact, what is the negation of the above statement? I am interested to obtain the negation with a step by step approach using tautologies in logic. To be specific, I want to start from  $$\neg \left[ {\exists L:\left( {\forall \varepsilon  &gt; 0,\exists \delta  &gt; 0:\left( {\forall x,0 &lt; \left| {x - a} \right| &lt; \delta  \implies \left| {f(x) - L} \right| &lt; \varepsilon } \right)} \right)} \right]$$  and then go through it to get the final form of negation (See the example below).    My Thought  I just wrote down the two following negations without going through a step by step approach.  $$\forall L,\exists \varepsilon  &gt; 0:\left( {\forall \delta  &gt; 0,\exists x:0 &lt; \left| {x - a} \right| &lt; \delta  \implies \left| {f(x) - L} \right| \ge \varepsilon } \right)$$  or  $$\nexists L:\left( {\forall \varepsilon  &gt; 0,\exists \delta  &gt; 0:\left( {\forall x,0 &lt; \left| {x - a} \right| &lt; \delta  \implies \left| {f(x) - L} \right| &lt; \varepsilon } \right)} \right)$$  I want to know weather these are true or not.       Example    I will give an example of what I mean by a step by step approach. Consider the following statement  $${P}\implies R$$  I want to take a step by step approach to obtain the negation of the above statement. Here is what they usually do in logic  \begin{align} \, \neg \left( {P \implies R} \right) &amp;\iff \neg \left( {\neg P \vee R} \right) &amp; \text{Conditional  Disjunction} \\ \qquad \qquad \quad &amp;\iff \neg \neg P \wedge \neg R &amp; \text{Demorgan's  Law} \\ \qquad \qquad \quad &amp;\iff P \wedge \neg R &amp; \text{Double  Negation} \end{align}
56312
Can someone help me? I can't even understand what the question is asking for.     Let $S = \{x_1,x_2,x_3,\ldots,x_n\}$. Show that ${\sim}[\forall x\in S,P(x)\lor Q(x)]\iff \exists x\in S,[{\sim}P(x)\land {\sim}Q(x)]$
86376
If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$   Here, a set of formulas is inconsistent means they syntactically imply some formula as well as its negation. Syntactic implication here consists of (1) given formulas, (2) all first-order logical axioms, (3) modus ponens.  I have tried to explicitly construct a syntactic proof for the conclusion but failed to come up with one.
108774
I would like to know if my answers are all correct, if someone willing to check it it will be greatly appreciated ...Thanks!😊  Universal/Union = { a,b,c,d,e,f,g,h}  A = {a,b,c,d}             A' = {e,f,g,h}  B = {e,f,g,h}.             B' = {a,b,c,d}  C = {a,d,h}                C' = {b,c,e,f,g}  D = {c,d,f,g}              D' = {a,b,e,h}  E = {a,b,c,f,g,h}         E' = {d,e}  Sets:  1.)[ [ [(A' ∩ B')' ∩ (C' ∩ D')']' - [(B-D')'- (A-C')']' ]' - E ]'  2.) [ [ [ [ (A' - B')' -C' ]' - D' ]' - E' ]' ∩ [ ( A' ∪ B')' ∩ (E' ∩ D')' ]' ]' ∩ ( B' '- C' ')' '  3.)[ B' ∩ [ (B' ∪ C')' - ( D' ∩ D)' ] ' ]' ∩ [( E ∪ E')' ∩ (C' - E)']'  Answer no. 1   A' ∩ B' = { }  (A' ∩ B')' = {a,b,c,d,e,f,g,h}   C' ∩ D' = {b,e}  (C' ∩ D')' = {a,c,d,f,g,h}  (A' ∩ B')' ∩ (C' ∩ D')'= {a,c,d,f,g,h}  [(A' ∩ B')' ∩ (C' ∩ D')']' = { b,e}  B - D' = {f,g}  (B - D')' = {a,b,c,d,e,h}  A - C' = {a,d}  (A' - C')' = {b,c,e,f,g,h}  ( B - D')' - (A - C')' = {a,d}  [(B - D')' - (A - C')']' = {b,c,e,f,g,h}  [( A' ∩ B')' ∩ (C' ∩ D')']' - [( B - D')' - (A - C')']' = { }  [[ (A' ∩ B')' ∩ (C' ∩ D')']' - [( B - D')' - (A - C')']']' = {a,b,c,d,e,f,g,h}  [[ (A' ∩ B')' ∩ (C' ∩ D')']' - [( B - D')' - (A - C')']']' - E = { e,d}  Final Answer:  [ [[ (A' ∩ B')' ∩ (C' ∩ D')']' - [( B - D')' - (A - C')']']' - E ]' = {a,b,c,f,g,h}  Answer no. 2   A' - B' = { }  (A' - B')' = {a,b,c,d,e,f,g,h}   (A' - B')' - C' = {a,d,h}  [(A' - B')' - C']' = {b,c,e,f,g}  [(A' - B')' - C']' - D' = {c,f,g}  [ [(A' - B')' - C']' - D' ]' = {a,b,d,e,h}  [ [(A' - B')' - C']' - D' ]' - E' = {a,b,h}  [ [ [(A' - B')' - C']' - D' ]' - E' ]' = {c,d,e,f,g}  A' ∪ B' = {a,b,c,d,e,f,g,h}  (A' ∪ B')' = { }  E' ∩  D' = {e}  (E' ∩ D')' = { a,b,c,d,f,g,h}  (A' ∪ B')' ∩ (E' ∩ D')' = { }  [(A' ∪ B')' ∩ (E' ∩ D')']' = {a,b,c,d,e,f,g,h}  [ [ [(A' - B')' - C']' - D' ]' - E' ]' ∩ [(A' ∪ B')' ∩ (E' ∩ D')']' = {c,d,e,f,g}  [ [ [ [(A' - B')' - C']' - D' ]' - E' ]' ∩ [(A' ∪ B')' ∩ (E' ∩ D')']' ] ' = {a,b,h}  *I cancel out  B' ' - C ' '   (B - C)' = {a,b,c,d,h}  [(B - C)']' = {e,f,g}  Final Answer:  [ [ [ [(A' - B')' - C']' - D' ]' - E' ]' ∩ [(A' ∪ B')' ∩ (E' ∩ D')']' ] ' ∩ [(B - C)']' = { }   Answer no. 3   B' ∪ C' = {a,b,c,d,e,f,g}  (B' ∪ C')' = {h}  D' ∩ D = { }  (D' ∩ D)' = {a,b,c,d,e,f,g,h}  (B' ∪ C')' - (D' ∩ D)' = { }  [(B' ∪ C')' - (D' ∩ D)']' ={ a,b,c,d,e,f,g,h}  B' ∩ [(B' ∪ C')' - (D' ∩ D)']' = {a,b,c,d}  [ B' ∩ [(B' ∪ C')' - (D' ∩ D)']' ]' ={e,f,g,h}  E ∪ E' = {a,b,c,d,e,f,g,h}  (E ∪ E')' = { }  C' - E = {e}  (C' - E)' = {a,b,c,d,f,g,h}  (E ∪ E')' ∩ (C' - E)' = { }  [ (E ∪ E')' ∩ (C' - E)' ] ' = {a,b,c,d,e,f,g,h}  Final Answer:  [ B' ∩ [(B' ∪ C')' - (D' ∩ D)']' ]' ∩ [ (E ∪ E')' ∩ (C' - E)' ] ' = { e,f,g,h}
45556
The Baier and Katoen textbook references this paper     E. M. Clarke and I. A. Draghicescu. Expressibility results for   linear-time and branching-time logics, pages 428–437. Springer Berlin   Heidelberg, Berlin, Heidelberg, 1989.   to say that, given a CTL formula P, if there exists an equivalent LTL one, it can be obtained by dropping all branch quantifiers (i.e. A and E) from P.   Is there a syntactic criterion that provides a guarantee that if a CTL formula passes the test, then an equivalent LTL formula does exist?
93154
I'm having problems with this; the strategy is to show the left side is in the right side, and vice versa. Thus far I can only show that both sides of the equality are in A\B. Can I use "the empty set = A and not A" as a fact? Because then it works. Or just show me how to do it!
68581
I have to show that set of all $x$ such that $x \in P$ and $x \notin Q$ exists. So, I think I have to assume that sets $P$ and $Q$ already exist. So, with that, I can use  . This axiom is $$ \forall w_1,\cdots, w_n \, \forall A \,\exists B \,\forall x \left( x \in B \Longleftrightarrow [ x \in A \wedge \varphi(x,w_1, \cdots , w_n, A)] \right) $$ So, I will let $\varphi(x, Q, P) = x \in P \text{ and } x \notin Q $. Also, I will let $A = P$ and  $w_1 = Q $. So using universal instantiation, I get the following $$ \exists B \,\forall x \left( x \in B \Longleftrightarrow [ x \in P \wedge \varphi(x, Q, P)] \right) $$ And using, existential instantiation, there exists a set $B$ such that $$ \forall x \left( x \in B \Longleftrightarrow [ x \in P \wedge \varphi(x, Q, P)] \right) $$ Using the definition of $\varphi(x, Q, P)$, this can be simplified as following $$ \forall x \left( x \in B \Longleftrightarrow [ x \in P \wedge x \in P \wedge x \notin Q] \right) $$ $$ \forall x \left( x \in B \Longleftrightarrow [ x \in P \wedge x \notin Q] \right)$$ $$ \forall x \left( x \in B \Longleftrightarrow x \in \{ x \,| x \in P \text{ and } x \notin Q \} \right)$$ Now, using , it will follow that $$ B = \{ x \,| x \in P \text{ and } x \notin Q \}  $$ And, since $B$ exists, this means that $\{ x \,| x \in P \text{ and } x \notin Q \} $ also exists. Is the proof good ?
59678
Here's Prob. 21 in Sec. 17 of the book Topology by James R. Munkres, 2nd edition:  Consider the collection of all subsets $A$ of the topological space $X$. The operations of closure $A \to \overline{A}$ and complementation $A \to X-A$ are functions from this collection to itself. (a) Show that, starting with a given set $A$, one can form no more than $14$ distinct sets by applying these two operations successively. (b) Find a subset $A$ of $\mathbb{R}$ (in its usual topology) for which the maximum of $14$ is obtained.  My effort: Based on the feedback I've had from the valued Mathematics Stack Exchange community, I would like to ammend my effort as follows: Let $\mathcal{P} (X)$ denote the power set (i.e. the collection of all the subsets ) of $X$, and let the functions $f \colon \mathcal{P} (X) \to \mathcal{P} (X) $, $g \colon \mathcal{P} (X) \to \mathcal{P} (X) $, and $i \colon \mathcal{P} (X) \to \mathcal{P} (X) $ be defined as follows: $$f(A) \colon= \overline{A} \ \ \ \mbox{ for all } \ \ \ A \in \mathcal{P} (A),$$ $$g(A) \colon= X - A \ \ \ \mbox{ for all } \ \ \ A \in \mathcal{P} (A),$$ and $$i(A) \colon= \mathrm{Int} (A) \ \ \ \mbox{ for all } \ \ \ A \in \mathcal{P} (X).$$ Then we have the following couple of results $$f(f(A)) = f(A), \ \ \ i(i(A) = i(A), \ \ \ \mbox{ and } \ \ \ g(g(A)) = A \ \ \ \mbox{ for all } \ A \in \mathcal{P}(X).$$ Moreover, we also have the following two relations: $$f(g(A)) = g(i(A)) \ \ \ \mbox{ and } \ \ \ g(f(A)) = i(g(A)) \ \ \ \mbox{ for all } \ A \in \mathcal{P} (X).$$ How do we show that $$f(g(f(g(f(g(f(g(A)))))))) = f(g(f(g(A))))$$ and  $$g(f(g(f(g(f(g(f(A)))))))) = g(f(g(f(A))))$$ for all $A \in \mathcal{P} (X)?$. Please also refer to  link.
103477
Let $F(\mathbb{R},\mathbb{R})$ be the vector space of all functions from $\mathbb{R}$ to $\mathbb{R}$. Prove that for all $n\in\mathbb{N}$, the set of vectors $$\left\{sin(x), sin(2x),sin(2^2x),\dots,sin(2^nx)\right\}$$   form a linearly independent subset of $F(\mathbb{R},\mathbb{R})$.  I know that to form a linearly independent subset the set must be closed under addition, closed under scalar multiplication, and contain the neutral element.  Showing that it contains the neutral element is relativley straight forward since when $x=0$ every element also equals $0$. Therefore this subset contains the neutral element. However, I am having a hard time coming up with a way to approach the parts showing that it is closed under scalar multiplication and addition for all $x$. Do you have a piece of advice or a hint on how to approach those part?
43893
I am self-studying Hoffman and Kunze's book Linear Algebra. This is Exercise 3.6.3(Linear Transformation-The Double Dual) from page 111.     Let $S$ be a set, $\mathbb{F}$ a field, and $V(S,\mathbb{F})$ the   space of all functions from $S$ into $\mathbb{F}:$   $$(f+g)(x)=f(x)+g(x)\hspace{0.5cm}(\alpha f)(x)=\alpha f(x).$$ Let $W$ be any $n$-dimensional subspace of $V(S,\mathbb F)$. Show   that there exist points $x_{1},\ldots,x_{n}\in S$ and functions   $f_{1},\ldots, f_{n}\in W$ such that $f_{i}(x_{j})=\delta_{ij}$.   Since $W$ is an $n$-dimensional subspace of $V(S,\mathbb{F})$ we can say find a basis $\mathcal{B}=\{f_{1},\ldots, f_{n}\}$. But I got stuck here. I don't know what to do from now on. I mean, what should I do in order to find those points $x_{1},\ldots,x_{n}\in S$ such that $f_{i}(x_{j})=\delta_{ij}$.