New answers tagged

1

See Prenex Normal Form: $(\forall x\phi )\rightarrow \psi$ is equivalent to $\exists x(\phi \rightarrow \psi )$ under the assumption that $x$ is not free in $\psi$. In your example, $y$ is not free in $L(x , \text {Toronto})$. Why the above equivalence (in classical logic)? Transform $(\forall x\phi )\rightarrow \psi$ into $\lnot (\forall x\phi )\lor \psi$ ...


2

In the second formulation, we are considering all of the pairs of buildings. What it says, is that for any two buildings in which one ($x$) is higher than the other ($y$), then the former building must be in Toronto. In ($1$) however, we are restricting to the case where $x$ is a particular building that is higher than every other building.


1

We have to use (A4) to "import" all the needed transformations: $(D \lor B) \to (B \lor D)$ --- (A3) Thus, using (A4), we have: $[C \lor (D \lor B)] \to [C \lor (B \lor D)]$. Consider now: $[(C \lor D) \lor (B \lor B)]$. By (A1) using (A4) we get: $[(C \lor D) \lor (B \lor B)] \to [(C \lor D) \lor B]$ We need also the Associativity Lemma: $\...


3

Consider first a simpler example: The set of even numbers $E$ is the smallest $X\subseteq \mathbb{N}$ with the following two properties: $0\in X$, and if $n\in X$ then $n+2\in X$. The two bulletpoints alone do not pin down $E$! For example, both $\mathbb{N}$ itself and $E\cup\{n\in\mathbb{N}: n\ge 17\}$ satisfy them. Basically, the minimality clause is ...


0

Your understanding is correct; the slides are somewhat confusingly written. The function $f_{\bf 0}$ is not the desired $m$-reduction. Indeed it can't possibly be since the arity is wrong: an $m$-reduction is unary, but $f_{\bf 0}$ is binary. Instead, $f_{\bf 0}$ is an oddly-packaged description of the outputs of the intended $m$-reduction of $K$ to $\{x: \...


0

Question 2. There might be a better way, or shorter ways, but this is what I got: Using the definition of exclusive or: $$\begin{align} r \overbrace{\oplus}^{\text{xor}} s \equiv \\( \sim r \land s) \lor (\sim s \land r) \equiv\\ \sim( \sim r \land s) \rightarrow (\sim s \land r) \equiv\\ (r \lor \sim s)\rightarrow ( \sim ( \sim (r \land \sim s))) \equiv \\ (...


3

Only your last step is wrong: $$\neg(p \lor q) \equiv (\neg p \land \neg q)$$


0

This is an alternative rount, and corrects for your misuse of DeMorgan's in the last step. $$(\lnot(p\lor(\lnot p\land q))) \equiv \lnot p \land \lnot(\lnot p \land q)\tag{DeMorgan's}$$ $$\equiv \lnot p \land (p \lor \lnot q)\tag{DeMorgan's}$$ $$\equiv (\lnot p \land p) \lor (\lnot p \land \lnot q)\tag{Distributive Law}$$ $$\equiv F\lor (\lnot p \land \lnot ...


1

You are right. Here is a proof of the "full" Generalization Theorem. First of all, we can "relax" the $\forall$-Introduction rule (page 31): $A \to B \vdash A \to \forall x B$, provided that $x$ is not free in $A$. Thus: $\Gamma \vdash A$ $\vdash A \to (y=y \to A)$ --- it is an instance of a tautology: $y$ new $\Gamma \vdash y=y \to A$ ...


1

Yes.   $\bot$ is valued as false by its definition in propositional logic, so cannot be valued as true by any world in any frame of modal logic. When $\mathsf W=\{a\}$ and $\operatorname R=\{\langle a,a\rangle\}$, then $a\Vdash\square\varphi$ if and only if $a\Vdash\varphi$.   Since $a\nVdash\bot$ by definition, therefore $a\nVdash\square\bot$ in such a ...


0

Simone Ramello is correct in identifying Schwabhäuser's Metamathematische Methoden in Der Geometrie as the proper reference for this subject, but as he suggests this book has not been translated into English. That said, you only need translations from two pages. I omit a discussion of Tarski's axioms, which can be found on Wikipedia or, in a more digestible ...


0

$\def\fitch#1#2{~~\begin{array}{|l}#1\\\hline#2\end{array}}$ Here's the Fitch style layout for this proof. $$\fitch{~~1.~\forall x~\exists y~A(x,y)}{\fitch{~~2.~\exists x~\forall y~\lnot A(x,y)}{\fitch{~~3.~[b]~\forall y~\lnot A(b,y)}{~~4.~\exists y~A(b,y)\hspace{8ex}{\forall}\mathsf E~1\\\fitch{~~5.~[c] A(b,c)}{~~6.~\lnot A(b,c)\hspace{8ex}{\forall}\mathsf ...


3

There isn't a substantive difference between the two (and I've never heard the term "Robinson semantics" before - I've seen both approaches subsumed by the term "Tarskian semantics"). Basically, in order to recursively define the satisfaction relation for normal sentences, it turns out that we have to consider some kind of "...


1

There is hardly anything to do here: irreflexive is obvious because of the set $\text{Id}_X$ we take away. Asymmetric: Suppose that $xR^\ast y$ and $yR^\ast x$ would both hold. As then also $xRy,yRx$ hold as well, the fact that $R$ is a partial order (so antisymmetric) tells us that $x=y$ which is a contradiction as we know that not $xR^\ast x$ holds. So $R^\...


1

I have solved it. Suppose that \begin{align*} A := \{ i \in \omega \mid F(g_1(i),\ldots, g_k(i),f(i)) \leq 0 \} \notin \mathcal{F}. \end{align*} Since $M^\wedge/ \mathcal{F} \models \mathrm{RCF}$ and $\mathrm{RCF}$ is an $o$-minimal theory, there are $h^-_1,\ldots, h^-_m,h_1^+,\ldots, h_m^+, h_1,\ldots,h_n \in M^\wedge$ where maybe $h_1^-$ and $h_m^+$ are ...


0

As per supinf's hints. How about this argument: Suppose that $\exists y$ such that $P(y)$ is true, but $\forall y P(y)$ is false. Also suppose that $Q(x)$ is false for any $x$. Then the first logical statement is false since for such a $y$ where $P(y)$ is true, we would have there exists an $x$ such that $P(y) \implies Q(x)$ is true, which is false, and so ...


1

hint 1: Your statement, that the first statement is true if $\forall y P(y)$ is false, was a mistake. In your comment it seems like you thought that if $\forall yP(y)$ does not hold, then $P(y)$ is always false. It can also happen that $P(y)$ is false for some $y$ and true for some $y$. You actually should assume, that $\forall y P(y)$ is false, but there is ...


1

We are told $P\implies Q$. There are $4$ hypothetical possibilities. $P$ is not true and $Q$ is not true. This could happen. $P$ is not true and $Q$ is true. The could happen. $P$ is true and $Q$ is not true. This can not happen. We we told $P\implies Q$ so if we have $P$ we must have $Q$ be true. This is just not possible. $P$ is tru and $Q$ is true....


0

With false and true respectively $0$ and $1$, the statements are$$\max_yP(y)\le\max_xQ(x)$$ and$$\min_yP(y)=1\implies\max_xQ(x)=1.$$These statements differ in truth value if$$\min_yP(y)=0,\,\max_yP(y)=1,\,\max_xQ(x)=0.$$


1

For 2, the statement is: for all $x, y$, there exists $z$ such that [$y = xz \implies x \ne 0$ is true]. Consider when $x= y= 0$. We can choose $z=0$, then $y=xz$ is true while $x\ne 0$ is false, and [true implies false] is false. This shows that 2 is false.


2

You can even prove by contradiction, if $b$ is not a tautology, then there must be a substitution such that $b$ is false, but then $a \implies b$ would not be a tautology because $(\top \implies \bot) \equiv \bot$ thus $b$ must be a tautology.


2

Use the fact that $(a\implies b) \iff ((\neg a) \vee b)$


1

$\lnot(∀x)A(x)$ means that in the "universe" $\text U$ not every object is an $A$. In the "universe" $\mathbb N$ of natural numbers, not every number is even. Thus, there is some object that is a not-$A$, i.e. $(∃x)\lnot A(x)$. In $\mathbb N$ there are numbers that are not-even, i.e. odd. And vice-versa.


1

The first examples is not very clear. The second one looks like: Every argument that Follow the rules is a Valid argument (this is an A proposition: $\text {Afv}$). The provided argument Follows the rules. Therefore: The provided argument is a Valid argument. The argument is valid but it is not, strictly speaking, a syllogism, because the second premise ...


1

In Categorical logic (AEIO) I and O are subcontraries. They both can not be False at the same time. What happens after integrating existential import? Seems like you got this just the wrong way around. With (i.e. after integrating existential import) Existential import (i.e. that the domain cannot be empty), any I and O pair of statements cannot both be ...


2

See Temporal Logic for the basic definition and the condition expressing "dense" in term of the precedence operator: $<$. Suppose that the temporal model $\mathcal M$ is dense. Consider a valuation $v$ such that $\mathcal M, t \vDash \text F p[v]$. By the clause for $\text F$ operator we have that $\mathcal M, t' \vDash p[v]$ for some $t' > ...


1

Van Dalen's approach is explained in the previous paragraph: "The introduction of the rank function above is not a mere illustration of the ‘definition by recursion’, it also allows us to prove facts about propositions by means of plain complete induction (or mathematical induction). We have, so to speak, reduced the tree structure to that of the ...


0

Edit: Looks like you updated the link to a new page (was abstraction of potential realizability, is now the abstraction of actual infinity). I will take a look and see how that changes my answer below. Edit 2: I don't think the link update really changes the general ideas in my response below. The first link was about disregarding that reaching infinity is ...


0

See Brouwer’s Development of Intuitionism: on Brouwer’s view, there is no determinant of mathematical truth outside the activity of thinking, a proposition only becomes true when the subject has experienced its truth (by having carried out an appropriate mental construction); similarly, a proposition only becomes false when the subject has experienced its ...


1

Welcome to MSE! We skolemize so that we can find explicit witnesses to existential quantifiers. That is, if $\forall x . \exists y . P(x,y)$ we should be able to choose such a $y$ for each $x$. But a consistent way of making such a choice is exactly the function $f_P$ so that $\forall x . P(x, f_P x)$. Let's think about what $\lnot \forall x . \exists y . P(...


1

There is a difference between the Traditional Square of Oppositions and the modern standard translation of so-called Categorical propositions. According to Aristotle's Logic, the Universal Affirmative ($\text {Aab}$): "a belongs to all b" implies the corresponding Particular ($\text {Iab}$): "a belongs to some b". With modern ...


2

As per discussions on previous similar posts we have many terms with similar meaning. Maybe the first one is Formal language: an alphabet made of an initial (usually finite) stock of basic symbols and a set (usually finite) of rules to produce expressions (usually with finite length) that are called formulas. With it we build a Formal system (also called a ...


2

As Eric Wofsey comments, "sentence" should be "formula." I wouldn't call this a typo however; I think it's a deliberate choice to increase readability for a non-logic audience. E.g. consider the line on page $125$: The first of these principles expresses the fact that ${}^*M$ is a model of $M$. To a logic audience this would be a ...


1

But is a set meta-operator. It means "Union NOT". Everything BUT the kitchen sink. {not K} Nothing BUT the kitchen sink. {K} All kitchen sinks BUT the ones with pink plugs. {K Subset not P} (All)Kitchen sinks with pink plugs BUT in the case of round sinks only the sinks that are Metal {K Subset P Union (M Intersection R) BUT, BUT ONLY - is an ...


3

The natural numbers $\mathbb{N} = \{0,1,2,3,\ldots\}$ is the smallest set $I$ with the property that $0 \in I$ and whenever $n \in I$ then $n+1 \in I$ ($I$ is an inductive set). What do we mean when we say 'smallest' though? In this context we aren't talking about cardinality, but about set containment. So saying that $\mathbb{N}$ is the smallest set with ...


1

Hint $1.$ Think about $\sin \alpha$; $2.$ Think about $x^2=\sqrt{3}$.


4

Hint. Solve the differential equation $y''=y$ and choose those such that $y'\ne y$. Play with $\sqrt{2}$.


1

Truth-Tables are for propositional logic only. They don;t work for full first-order logic statements with quantifiers. If you are ok doing this in propositional logic, you can use $A,B,C$ for the three people being truth-tellers respectively, and use the statement: $$(A \land B \land \neg C) \lor (A \land \neg B \land C) \lor (\neg A \land B \land C)$$ So, ...


0

You can consider a truth table for the statement: $$\begin{bmatrix} & | & A & \neg A \\ \hline B & | & T \lor F \lor F \lor F = T & F \lor F \lor T \lor F = T \\ \neg B & | & F \lor T \lor F \lor F = T & F \lor F \lor F \lor T = T \end{bmatrix}$$


0

This is a more longwinded approach to help clarify what's going on. But be explicit in how you define 'between'. In this sense, between could be interpreted as $100 \leq x \leq 500$ or $100 < x < 500$. As long as you are explicit about your assumption, you're fine. The sentence "Define the set of even natural numbers between 100 and 500" can ...


2

Yes. The definition of presupposition is $$A \text{ presupposes } C \text{ iff } A \vDash C \text{ and } \neg A \vDash C \text{ and } \nvDash C$$ That is, $A$ presupposes $C$ iff $C$ follows both from $A$ and its negation but $C$ is not tautological. If $A \Leftrightarrow B$, then $\neg A \Leftrightarrow \neg B$. So $\begin{align*} & A \text{ presupposes ...


0

This answer follows the comment provided by Mauro ALLEGRANZA in the comments: The statement "$n$ is an odd negative integer" can be translated to "$n$ is an integer AND $n$ is odd AND $n$ is negative". Converting this to formal logic we can write: "$n$ is an integer" == $n \in \mathbb{Z}$ "$n$ is negative" == $n < ...


0

We can write "$n$ is a negative integer" as $$n\in\mathbb{Z}^-$$ And "$n$ is odd" as $$\exists k\in\mathbb{Z}.\ n=2k-1$$ Combine both: $$\exists k\in\mathbb{Z}.\ n=2k-1 \wedge n\in\mathbb{Z}^-$$ Or alternatively, $$\exists k\in\mathbb{Z}.\ \mathbb{Z}^-\ni n=2k-1$$ Hope this helps. :)


2

Call this theory "$T$." Showing that $T$ is not uncountably categorical is straightforward. Keep in mind that a model of $T$ is gotten by adjoining to the prime model (= one equivalence class of size $n$ for each finite $n$) an arbitrary number (possibly $0$) of equivalence classes of arbitrary infinite cardinalities. Now given $\kappa$ infinite, ...


0

If A is a liar then A and B are not the same hence B is a reliable. Then B says one one of us is reliable hence pointing to himself. Therefore the statement is true. However if A is reliable then both B and A the same contradicting B's statement of only one reliable between both of them. Contradiction. Hence A is a liar and B is reliable B is the answer. ...


0

A and B cannot be in the same category, since - if A and B are both liars, then A's statement ('I and B are the same') is true. But A is a liar, so A will always speak falsehoods, and not true statements, thus A and B cannot be both liars. if A and B are both reliable, then B's statement ('From us, only one is reliable') is false. But B is reliable, ...


1

There are only $16$ possible boolean functions of two arguments. They have the outputs $$0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111.$$ From these, we can withdraw those that are independent of one or two arguments. Remain $$0001,0010,0100,0110,0111,1000,1001,1011,1101,1110.$$ We can also withdraw those obtained by ...


0

The way I addressed this problem was to demonstrate that each of the 16 possible truth functions on 2 variables was derivable using the set of connectives provided. You can cut corners on that by demonstrating equivalence of various combinations of those connectives with other connectives, e.g. showing that $\lnot$ and $\land$ can make $\lor$, and hence ...


1

Hint: every Boolean formula can be written in CNF (conjunctive normal form) or DNF (disjunctive normal form), quite constructively.


3

They both work. However, I don't actually think that the second one is more natural: it involves first proving the second incompleteness theorem, which is nontrivial and not obviously relevant to the specific problem at hand. By contrast, in the first approach we give a method for building models of $\mathsf{ZFC}$ + "There are no inaccessibles" ...


Top 50 recent answers are included