Tag Info

New answers tagged

0

There is a concept in logical reasoning called a "canonical form". Most of the time when someone says "simplest form" they are implicitly talking about a canonical form. A canonical form is one where equivalence can be determined lexicographically. For example, two polynomials $-4x + 5x^2 - 2$ and $(5x-4)x - 3$, when put into canonical form $5x^2 - 4x - ...


0

Your expression is in simplest form because you cannot further combine like terms (terms with the same variable part) and there are no longer any sets of parenthesis. If you were to use this definition in any algebra class, it would fly, but perhaps you're looking for a more rigorous explanation.


0

Every structure does satisfy some statements and fails to satisfy the negations of the statements that it satisfies. Every set of statements defines some class of structures: those that satisfy the statements in the set. Some sets of axioms and some classes of structures are worth more attention than others. Not all algebraic structures satisfy the field ...


2

One way to formalize the idea is to say the following: the category of classical propositional theories is a reflective subcategory of the category of intuitionistic propositional theories. In order to make sense of that claim, it's best to pass from "theories" to "algebras." Each classical theory corresponds to a Boolean algebra, and each intuitionistic ...


0

See George Tourlakis, Mathematical Logic (2008), page 93 : 3.2.1 Metatheorem (Post's Tautology Theorem) : If $\Gamma \vDash_{TAUT} A$, then $\Gamma \vdash A$. Proof. It is most convenient to prove the contrapositive, namely, if $\Gamma \nvdash A$, , then $\Gamma \nvDash_{TAUT} A$ Some facts are needed : Claim One. There is an enumeration ...


1

Following my answer to your previous post, we can say that a formal system is made by an alphabet (the set of symbols), a gramamr (the formation rules, defining the "correct" expressions, i.e. the set of well-formed formulas) and a proof system or deductive calculus. See Enderton, page 110 : We will introduce formal proofs but we will call them ...


0

Thanks for asking this, I'd wanted to ask almost the exact same question, word for word! I don't have a very good answer, but I think the introductory book by Halmos and Givant 1988 ("Logic as algebra") is helpful. Is that one of the 2 books you mentioned? Knowing some algebraic geometry (such as the use of ideals) may help in understanding the book. See ...


0

The "complicated" formula : $¬A∨¬(¬B∧(¬A∨B))$ can be re-written, due to the equivalence between $P \rightarrow Q$ and $\lnot P \lor Q$, as : $A \rightarrow \lnot ((A \rightarrow B) \land \lnot B)$. But $P \rightarrow Q$ is also equivalent to $\lnot (P \land \lnot Q)$; so the formula it is simply : $A \rightarrow ((A \rightarrow B) ...


3

Some comments Plain "formula" is usually used as to mean the same as "well-formed formula". If we do really mean to talk about an arbitrary string of symbols, we might say "expression", or indeed "arbitrary string". A (well-formed) formula is an expression that obeys certain syntactic construction rules. Some ways of setting up the syntax of first-order ...


3

Depends on the logical system, but generally there will be a difference between arbitrary strings of symbols, wffs, and statements/sentences. Arbitrary strings are just arbitrary concatenations of symbols. Wffs are formulas formed according to the syntax in question. Finally, statements or sentences will generally be closed formulas, where by closed is ...


0

I'm assuming that the 1 and 2 subscripts are supposed to be $i$ and $j$ subscripts. Both expressions you have written are fine, although with the first one you would need to describe elsewhere that $\tan\theta = \min\Big(\Big|\frac{y_i-y_j}{x_i-x_j}\Big|, \Big|\frac{x_i-x_j}{y_i-y_j}\Big|\Big)$. Here is an even more clean description: Let ...


0

As I mentioned in the comment, I think it is bad form to overload the $\tan$ function. If you are doing many trigonometric operations with this triangle, then it is best to clearly define all its parts. Doing so allows you to use cases to choose the appropriate angle, and then the trigonometric functions can have their usual meaning. If you just need this ...


0

$$\tan(A) = \begin{cases} |y_2 - y_1| \ge |x_2 - x_1| &: \huge{\frac{|y_2 - y_1|}{|x_2 - x_1|}} \\ \\ \\ |y_2 - y_1| \le |x_2 - x_1| &: \huge{\frac{|x_2 - x_1|}{|y_2 - y_1|}} \\ \end{cases}$$


3

$\tan(A)=\dfrac{\max(|x_2-x_1|,|y_2-y_1|)}{\min(|x_2-x_1|,|y_2-y_1|)}$ Or: $\tan(A)=\max\left(\dfrac{|x_2-x_1|}{|y_2-y_1|},\dfrac{|y_2-y_1|}{|x_2-x_1|}\right)$ where $\max(a,b)$ equals the greatest of $a$ and $b$


3

You can approach this literally, more or less. We are being told that there does not exist an $x$ such that $x$ is both naive ($N(x)$) and bad ($B(x)$). It makes sense to let "all people" to be the domain (or universe) in which $x$ resides. $$\begin{align} \lnot \exists x(N(x) \land B(x)) & \equiv \forall x \lnot(N(x) \land B(x)) \\ \\&\equiv ...


0

Let $Nx$ be "$x$ is naive" and $Bx$ be "$x$ is bad". Well, if $x$ is naive, $x$ can't be bad. So $$\forall x(Nx\rightarrow \neg Bx)$$


2

There doesn't seem to be anything strictly wrong with your strategy -- assumptions don't have to come from anywhere as long as they get properly discharged. But it seems to be a detour. Most natural deduction systems have a rule that allows you to infer directly from $P$ to $P\lor Q$. Doesn't yours? On the other hand, most natural deduction systems don't ...


0

The "usual" way to define the negation : $\lnot$ is to introduce a propositional constant (or $0$-connective) : $\bot$. See Dirk van Dalen, Logic and Structure (5th ed - 2013), page 30 : As usual “$\lnot \varphi$” is used here as an abbreviation for “$\varphi \rightarrow \bot$”. In this way, in classical logic, the semantics for $\lnot$ is "reduced ...


2

There's no need to use distribution since $p \lor(\lnot q \lor r) \equiv p \lor \lnot q \lor r$ due to associativity of $\lor$, and by commutativity of $\lor$, that gives us $$\lnot q \lor p \lor r \equiv \lnot q \lor (p \lor r) \equiv q\rightarrow (p \lor r)$$ What is highly questionable in your proof is the second line of the following: $(q → p) ∨ (p∨r)$ ...


3

We can agree that there is some "variability" in the practice, regarding the definition (if any) of logical symbols in first-order logic. According to the definition in Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001), of First-Order Languages [page 69], we have : A. Logical symbols $0$. Parentheses: $(,)$. $1$. Sentential ...


4

An $n$-ary (or $n$-place) function symbol is an expression which combines with $n$ terms to form another term. (If you like, think of the symbol coming with $n$ slots to be filled in; and when the slots are filled, we then get a complete term.) For example, in arithmetic the function symbol '$+(\ldots,\ldots)$' combines with the two numerals '$2$' and '$4$' ...


3

As Thomas Andrews pointed out in a comment, this terminology is not something where one can expect consistency from book to book. However, as a practical matter, when one specifies that the non-logical language of a particular theory is such-and-such, it is highly unusual to have to say, "oh, and there are variables too". Variables are just supposed to be ...


4

The bolded sentence you quote from Wikipedia is wrong -- true and false can indeed be represented as $\neg p\lor p$ and $\neg p\land p$ for any well-formed-formula $p$. In some logics, such as intuitionistic logic, $\neg p\lor p$ may not be unambiguously true, but then at least $p\to p$ will be. The only way to make the sentence true would be to somehow ...


1

I would say it like this: "Statistically a person has on average a half child." It is different from your wording. An average person cannot have a half child. Mathematical formulation: $x_i:$Number of children of person i $x_i \in \mathbb N$ $\overline x:$ Average number of children per person.


1

I agree with Carl's answer: a formal system is the "syntactic specification" of a mathematical theory. We are interested in it because we are interested into the theory and its models. But we can study also formal sysems per se; see for example : Formal grammar. Thus, I will suggest some further hints,following the answer to this previous post. According ...


3

For a formal system to be of much interest, it needs to be consistent -- it needs to have at least one model. In that model, the axioms of the system will be true. It doesn't make much sense to talk about the truth of axioms apart from models. The formal systems of the most interest -- such as Peano arithmetic and Zermelo-Fraenkel set theory - come with ...


0

Logic is a particular kind of formal system in which we call validity truth, and invalidity falsehood. Whether you choose to call the valid propositions of a given formal system true is a matter of semantics. So, you could choose to call your axioms true, however to do so would likely cause some confusion, as it could be seen as implying that you are ...


2

Every statement can be proved or disproved. If $\varphi$ is a statement which is always true (e.g. $\forall x(x=x)$), then it is always provable, if its negation is always provable -- then $\varphi$ is always disprovable. Otherwise, $\{\varphi\}$ proves $\varphi$ and $\{\lnot\varphi\}$ disproves $\varphi$. So every statement is either always true, or ...


0

Tetori gave a great technical answer. I just wanted to contribute an alternative approach: In $[∀xS(x)→∃yR(y)]→[∀x∃y(S(x)→R(y))]$, the antecedent is saying: "If all x are Sx then there is y that is Ry". The consequent is saying:"If an x is Sx, then a y is Ry". Note that the antecedent is a sub-theorem of the consequent: In the case where all x are Sx, we ...


2

Before we talk about the validity of the formula, we must define a notion of the validity. In the case of propositional logic, a given formula $\varphi$ is valid iff $\varphi$ is true for each truth assignment. But then, how to define the notion of validity in predicate logic? Unlike propositional logic, predicate logic has quantifiers so we do not use the ...


1

The proof is from Keisler's Model Theory for Infinitary Logic and the result is due to Makkai which is closely related to earlier work of Henkin and Smullyan: Fix a language $L$. Now let $C$ be a countable set of new constant symbols, and let $M$ be the language formed by adding each $c \in C$ to $L$. Then, we can make the infinitary logic $M_{\omega_1 ...


2

The statements $\left[\left|X\right|\geq0\wedge\left|Y\right|\geq0\right]\Rightarrow Q$ and $Q$ are equivalent. So proving the first statement comes to the same as proving the second. Underlying reason: statement $\left|X\right|\geq0\wedge\left|Y\right|\geq0$ is true.


1

You need not consider any cases; you only need to prove that Q is true.


4

Note that "$|X|=0 \text{ or } |Y|= 0$" is logically the same as "1, 2 or 3" from the 4 cases that you've listed. So, in your second consideration, you consider 3 out of the 4 cases simultaneously.


3

Yes, the existence of maximal ideals (in non-trivial rings with unit) implies Zorn's Lemma. A reference is: Marcel Erné, A primerose path from Krull to Zorn, pdf-link


0

For Theorem L10: Suppose $( \sim B \implies \sim A)$ holds. We want to show $(A \implies B)$ is true. Since $\sim B \implies \sim A$ is true, then its negation, $\sim B \wedge A$, is false. But then, the negation of this statement, which is $B \vee \sim A$, is true. But $B \vee \sim A$ is equivalent to $\sim (\sim (B \vee \sim A)) \equiv \text{ }\sim ...


2

I won't go into the detail of which logic uses which rules of inference, but in an informal sense you should associate $\exists$ with $\text{ or }$. For example: $$\exists x \in \mathbb N : P(x)$$ is the same thing as $$P(0) \text{ or } P(1) \text{ or } P(2) \dots$$ which is why many logics will have as a rule of inference: $$\exists x : (P(x) \text{ ...


1

The simbology is not so clear to me, but I think that, basically, we have that the conjunct $T_i$ in the $k$-CNF is a disjunction of literals : i.e. boolean vars or negated boolean vars. I assume that the variables $x_j$ are the boolena variables; if so, they occur into $T_i$ as is or negated. We introduce an "auxiliary" function $a_i$ associated to $T_i$ ...


1

I'll consider Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)). The proof system [see page 112] is based on modus ponens as only rule of inference and : The logical axioms are all generalizations of wffs of the following forms, where $x$ and $y$ are variables and $\alpha$ and $\beta$ are wffs: 1. Tautologies; 2. $\forall ...


4

See the Wikipedia pages List of statements undecidable in ZFC and List of undecidable problems. Note that the lists are different in flavor, e.g. compare Independence and Undecidable problem. Other examples of statements whos truth can't be determined are wrong ones. Also note that "theorem" is a technical term in the context of formal logic and here I would ...


0

I'll consider Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)). We need some provable equivalences; see Enderton, page 121 and page 130 : (Q2A) -- $\vdash (\alpha \rightarrow \forall x \beta) \leftrightarrow \forall x (\alpha \rightarrow \beta)$, if $x$ does not occur free in $\alpha$ (Q2B) -- $\vdash (\alpha \rightarrow \exists ...


0

This is an application of the compactness theorem. If the theory $$\{\neg \varphi_i | i \in \mathbb{N} \} $$ is satisfied (has valuations for every finite subset) then it has a valuation for the entire set. This is the contrapositive of what you want to show.


4

Yes it can all be formalized in ZFC, or even in number theory, including the self reference. Note that you are arithmetizing the syntax of logic, or in plain language, coding the symbols by numbers. So you are talking about numbers but they really stand for ideas from logic. Gödel's theorem says for example $$\exists n\, \forall m\, \neg \text{Proof} ...


0

The formula : $(∀x¬α → ¬α^x_c) \rightarrow (α^x_c → ∃xα)$ is a valid formula of first-order logic. Usually, the use of tautology is restricted to propositional logic. But we have also another prossibility : we can say that a formula of f-o logic is an instance of a tautology, in which case it is obviously valid. To show this, we must assume that ...


1

See Elliott Mendelson, Introduction to mathematical logic (4ed - 1997), page 69. We need at least a third propositional axiom, like : (A3) --- $(\lnot γ → \lnot β) → ((\lnot γ → β) → γ)$ to be able to prove all tautologies. In addition, I assume two axioms for the predicate calculus (and two further axioms for equality : we do not need them here) : ...


2

There's a big difference between: a liar sentence the continuum hypthesis (i.e. the sentence "the continuum hypothesis is true") The continuum hypothesis is a statement, and a perfectly good statement at that. Its kind of like the statement "for all $x$ and $y$, we have $xy=yx$" in group theory. The axioms of group theory cannot prove this statement ...


7

You have made the well known confusion between true and provable. (And throughout this answer I will assume we work in classical first-order logic.) Truth value is given in a particular structure. The continuum hypothesis has a truth value, it just can be different in different models of $\sf ZFC$. And in every model of $\sf ZF$ the axiom of choice has a ...


0

You are "mixing" two different (but related) concepts : that of tautology and that of tautological implication. We say that $\alpha$ is a tautology : $\vDash \alpha$, iff : $\alpha$ is true for all truth assigments. We say that $\beta$ is a tautological consequence of $\alpha$, or that $\alpha$ tautologically implies $\beta$, : $\alpha \vDash \beta$, ...


1

I think this question is a much more significant than might seem at first. And a mathematician's perspective on it would depend a lot on what kind of math they're involved in. First of all, there is no mathematical definition of the word "paradox." Notice how the definitions you'll find in dictionaries have something to do with how a statement is ...


1

For any infinite $A\subseteq\mathbb N$ (in particular, for any non-recursive $A\subseteq\mathbb N$), we have infinitely many $n$ such that $A\cap W_n$ is infinite, because there are infinitely many $n$ such that $W_n=\mathbb N$ and thus $A\cap W_n=A$. If, in addition, $A$ is r.e., then there are also infinitely many $n$ with $W_n=A$, which again implies ...



Top 50 recent answers are included