Tag Info

New answers tagged

3

Hint: For the countable case, think along these lines: Is every element in your domain named by one of the constants? What happens if they are not? Edit1: Further to your comment; suppose that every element of $M\models{T}$ is named by one of the constants and $N\models{T}$ has exactly one element that is not named by the constants (here $M$, $N$ are ...


2

Answer: neither of those is happy. In a natural deduction framework -- and talk of introduction and elimination rules has its natural(!) home here -- the canonical formulation of $\lor$-elimination looks like this: $${}\quad \quad \quad [A] \quad \quad \quad [B]\\ \quad \quad \quad \vdots \quad \quad \quad \;\;\vdots\\ (A \lor B)\quad \quad \quad C \quad ...


0

The first is false, the second is true, regardless of whether $0 \in \Bbb N$. $(\forall x \in \mathbb{N}:x^2=x) \vee(\forall x \in \mathbb{N}:x>1)$ is a distjunction of two universally qualified sentences. The first is false for $x=2$, the second is false for $x=1$, so both are false. it is a bit clearer is you write the equivalent $(\forall x ...


1

The first sentences says 'every natural number is equal to its square or every natural number is greater than one'. This is false since both sentences on the sides of the 'or' are false. The other sentence is true. It says 'Every natural number is equal to its square or is greater than one'. Since the only natural number that is equal to its square is 1, ...


3

You won't be surprised to learn that in the last seventy-plus years since Tarski's book was first published in English, many other books have been appeared which will perhaps serve better as introductions to modern logic. And if you have downloaded my Teach Yourself Logic, you will have seen my "entry-level" suggestions on formal logic at the beginning of ...


1

(I) (∀x∈R)(∃n∈N)(nx<1) (II)(∃n∈N)(∀x∈R)(nx≥1) how is the negation of (II) equal to (I)? The negation of (II) is not (I). The negation of (II) is $(\forall n\in N)(\exists x\in R)(nx<1)$


2

No, for example: let $A = \{\frac 1 k \mid k \in \mathbb N\}$, $N = \mathbb N$. Then $$ \exists n \in N \forall x \in A \colon xn \ge 1 $$ is false, since for a fixed $n \in \mathbb N$ we have $\frac 1 {n+1} \in A$ and $n \cdot \frac 1 {n+1} < 1$. On the other hand $$ \forall x \in A \exists n \in N \colon nx \ge 1 $$ is true. (Given $x = \frac 1 k \in A$ ...


1

The difference between : $\exists x \forall y$ and $\forall y \exists x$ is clearly shown by this example regarding natural numbers : $\forall n \ \exists m \ (n < m)$ is clearly true in $\mathbb N$, while : $\exists m \ \forall n \ (n < m)$ is false in $\mathbb N$.


2

(ii) Exists an $M$ such that for each $x$ real, $|f(x)| \leq M$. (iii) For each $x$ real there exists an $M$ such that $|f(x)| \leq M$. In the first case $M$ is unique for all $x$. In the second case $M$ depends on $x$. In this sense, we can restate (iii) as follows: (iii) For each $x$ real there exists an $M(x)$ such that $|f(x)| \leq M(x)$. The ...


2

The statement $\exists x (\varphi(x))$ says that there is some value of $x$ for which $\varphi(x)$ is true. Fix such a value of $x$, say $a$. We now know that $\varphi(a)$ is true. The statement $\forall x (\varphi(x) \to A)$ says that whenever you substitute a value for $x$ into the formula $\varphi(x) \to A$, what you get is a true statement. So, ...


0

If you are familiar with types, another way to state the answer is as follows: If two models are isomorphic, they must realize the same types. However the type (over the empty set) realized by $c$ in $^*R$ is not realized in $R$.


4

Assume $a \to b$. Assume $\lnot b$. Assume $a$. Then $b$. Then $\bot$. Eliminating (3), $\lnot a$. Eliminating (2), $\lnot b \to \lnot a$. Eliminating (1), $(a \to b) \to (\lnot b \to \lnot a)$. I think everything is clear up to step 5; beyond that you need a clear grasp of the notion of conditional proof. (You also need to remember that $\lnot x$ is an ...


1

Assume "a => b" and "not b". Then "not a" because: If "a", then "b", but we assumed "not b". Contradiction, so "not a" holds.


0

There is a small list on Wikipedia: https://en.wikipedia.org/wiki/Riemann_hypothesis#Excluded_middle


3

For any cardinal $\kappa$, you can define the product measure on $2^{\kappa}$ where $0, 1$ are assigned one half measure each. This measure is defined on the sigma algebra generated by clopen subsets of $2^{\kappa}$. Let us call the corresponding measure algebra $\text{Random}(\kappa)$. The class of measure algebras thus obtained forms the building block for ...


2

One can (as the OP suggests in a Comment on the Question) "just keep adding axioms that are consistent" to any first-order theory, and thus in the limit obtain a complete (therefore decidable, modulo an "oracle" for the extended axioms) first-order theory. The "rub" as Asaf suggests is that this recipe for a complete theory does not necessarily produce a ...


4

Probability is not just defined on a set. It's also defined on a $\sigma$-algebra of subsets. Namely, a probability structure is made of three parts: The underlying set, say $X$. The sets to which you can assign probability. The function which assigns probability. There are several axioms which we require of these structures, such as the sets to which ...


4

If you wonder why so far only the "trivial" example of a Dirac measure has been mentioned, there is actually a good reason for this. The young Ulam wondered whether there is an uncountable set $X$ for which there is a probability measure $$ \mu \colon \mathcal P(X) \rightarrow [0,1] $$ that vanishes on singletons (i.e. $\mu(\{x\})= 0$ for all $x \in X$). He ...


2

Let $T(f_1,\dots,f_n)$ be any term in $n$ variables in this language. By an easy induction, your axioms (plus the axioms for a commutative ring) imply that $T$ is equal to some polynomial in $Id$ and the (iterated) derivatives of the $f_i$. To show that there are no other universal equations that hold in $S$, it thus suffices to show the following: if $P$ ...


0

This may not be formal enough for an answer, but it doesn't seem like you're looking for a purely formal answer. I would say that $X = Y$ is meant to express that in certain contexts (sometimes explicit and sometimes less explicit), anything that is sufficiently involved in $X$ by some witness can be turned into something sufficiently involved in $Y$ by an ...


1

I think you got the rough idea. We have symbolic expressions and objects, which are two different things. We cannot take the objects themselves and put them on paper, but we can write symbolic expressions that refer to objects, and the objects they refer to are called their values. We might have multiple symbolic expressions that refer to the same object, in ...


3

In first-order logic, equality is a binary relation for which these two statements are true: Any variable or constant is equal to itself. We call this the Reflexive property, and it can be written $$\text{For all $x$, }x=x$$ or, more formally, $$\forall x(x=x)$$ If two items are equal, anything we can say about the first item in our logical system we ...


0

The problem with your method is that the interpretation of $\{c_x \ | \ x \in \mathbb{R}\}$ in a model of $\Gamma$ could be any uncountable set. For instance, you could interpret all $c_x$ as distinct elements of $[0;1]$ and $c$ as $2$ in $\mathbb{R}$. Another solution using non elementary model theoritic and algebraic results, but provinding an archimedean ...


1

In general for any set $A$ is possible give the probability of dirac, $i.e$ let $x\in X$ and $U\subset A$ we define $\delta_x(U)=1$ if $x\in U$ and $\delta_x(U)=0, \, else.$ so Always is possible give a measure of probability of any set.


0

I'm adding some notation and further examples to Danikar's answer. Denote "A thinks (B thinks C knows no errors) and (D knows no errors)" as A:(B:(C:0), D:0) Each & every prof is proud and assumes that she hasn't made a mistake until it is necessarily true. one prof A:0 A thinks there are no mistakes. Prof X declares that someone made a mistake... ...


3

As has been pointed out in comments, we do not need to add a constant symbol for every element of $\mathbb{R}$. Let $L$ be the usual first-order language for ordered fields. Extend $L$ to $L'$ by adding a constant symbol $c$. Let $T$ be the set of all sentences of $L$ true in the reals, under the usual interpretation. Make a new theory $T'$ by adding to $T$ ...


1

According to Change/Keisler, "Model theory", 3rd edition, page 209, the double vertical bar turnstile means the "finite forcing relation". The detailed explanation is somewhat technical. PS. Much the same definition for the double vertical turnstile is given by Smullyan/Fitting, "Set theory and the continuum problem", page 210. They say that $p\Vdash X$ ...


3

Instead of compactness, you can try an ultrapower argument. Let $\cal U$ be a nonprincipal ultrafilter on $\Bbb N$. Then $\Bbb{R^N}/\cal U$ is elementarily equivalent to the reals. And it is not hard to show it has the wanted cardinality, and that it is non-standard.


0

So there are two directions to prove here. Show that any assignment satisfying E can be extended to an assignment satisfying D. Assume that $v$ is a truthassignments such that $v(E)=T$ but $v(D)=F$. Thus for each $i$, $v(L_i) = F$. However then note what happens in $E$: $v(L_1 \vee L_2 \vee C_1) = T$ and thus $v(C_1)= T$. Now by induction we ...


2

The first and second term go like this $$ \frac{\lvert L \rvert \epsilon}{3(1+\lvert L \rvert)} = \frac{\epsilon}{3} \underbrace{\frac{\lvert L \rvert}{1+\lvert L \rvert}}_{< 1} < \frac{\epsilon}{3} $$ the third is clear, I hope. This gives $$ \lvert f(x) g(x) - LM \rvert < \underbrace{\frac{\lvert L \rvert \epsilon}{3(1+\lvert L ...


0

It looks like what you want to mark is not derivability but inference. Inferences are the atomic steps from formula to formula, by means of which derivations are constructed. One convention for marking steps of inference is to use the sign $\therefore$. But this doesn't work very well for derivations involving successive inferences, since an inference ...


0

As long as you are using a sound deductive system, to prove $\phi\equiv\psi$ you have to assume $\phi$ then deduce $\psi$ from this assumption and assume $\psi$ then deduce $\phi$ from this assumption. Since a sound deductive system is truth preserving, this ensures that if $\phi$ is true then $\psi$ is true and if $\psi$ is true then $\phi$ will be true - ...


1

This is mechanized in Maple. For example, with(Logic): Export(Normalize(`&and`(`&or`(p, q), `&or`(q, `&not`(r))))), form = DNF)); $$ p \land q \lor p \land \neg r \lor q \lor q \land \neg r $$ See ?Logic for info. PS. It should be noted that the original Maple input is not exactly represented in the above code.


1

$$ 1.\quad (p\vee q)\wedge (q\vee\neg r) = q\wedge(p\vee q) \vee\neg r\wedge(p\vee q) = q \vee \neg r p\vee \neg rq = q\vee p\neg r $$ $$ 2. \quad (p\wedge q)\vee (q\wedge\neg r) = q(p\vee\neg r) $$


1

Yes. Let's pick a few. Obviously $\mathbb{N}$ itself All the even numbers All the odd numbers All the prime numbers (these are infinite, right?) So forth. (I have exhibited a few infinite sets $\in\mathcal{P}(\mathbb{N})$ thus shown the claim: $\exists S\in\mathcal{P}(\mathbb{N})$ with $|S|=|\mathbb{N}|$ which is to say $S$ is countably infinite)


0

Yes, for example you can use DeMorgan's laws: $$a \vee b = \neg((\neg a) \wedge (\neg b))$$ $$a \wedge b = \neg((\neg a) \vee (\neg b))$$ As well as distributivity over the operators: $$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c) $$ $$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c) $$ And there are a lot of more rules you can use to simplify ...


5

As Noah points out, in the context of $\sf PA$ we have a unique "very nice" model which has very nice properties. $\Bbb N$, we can show that any well-founded model of $\sf PA$ is isomorphic to it, and we know that this model exists, if we assume a sufficient meta-theory. So in the context of arithmetic, we can say "the standard model" and confuse between ...


0

I believe a rigorous account of mathematical beauty is key to building an optimal theorem proving agent. Some work in that direction has been done by Jürgen Schmidhuber (http://people.idsia.ch/~juergen/) who has linked beauty in general to the concept of compression.Taking algorithmic information theory as the basis we can then define "interesting" (or ...


8

The crux of the matter is that (people claim) we have evidence that PA is consistent, but we do not have similar evidence that CH is true. Note that "true in the standard model of set theory" is (basically) synonymous with "true." Why is this? Well, let's begin with: why do we believe PA is consistent? Usually, actually, a stronger assertion is made: PA is ...


0

The quantity "$240$ minutes" describes the amount of time shown on the clock. Since we know the clock is inaccurate, these "$240$ minutes" do not reflect "real" time. They reflect "clock" time. $40$ minutes of "clock" time elapse in one hour of real time. So $40n$ minutes of "clock" time is $n$ hours of real time. Letting $240 = 40n$, we want to solve for ...


2

Consider the following related sentence: "If this statement is true, then I am a space alien." On the one hand, if the statement is true, then it is true - so I am a space alien. On the other hand, if it is false, then - since it is of the form "$A\implies B$" - the hypothesis must be true and the conclusion false. But, if the hypothesis is true, then the ...


1

Hm, this is interesting. As you've noted, "this sentence" takes the form $P \Rightarrow \lnot Q$, where $P$: This sentence is true $Q$: Tomorrow will rain. Suppose "this sentence is false". Then $P \Rightarrow \lnot Q$ is false. The only way that can happen is if $P$ is true and $\lnot Q$ is false. But $P$ is "This sentence is true", and so we have a ...


1

For the other inclusion: suppose $x \in B$. Then we know that $x \in A$, as $B \subseteq A$. But $x \notin A \setminus B$, because if it were, it would imply that $x \notin B$, which we know is false. So $x \in A$, $x \notin A \setminus B$, so by definition $x \in A \setminus (A \setminus B)$.


1

Not the most elegant, but surely a good way to do this(and understand) is by using Venn-diagrams: A more elegant, "written" proof. We prove, that the two sides are equivalent. Suppose, that arbitrary $x \in A\setminus(A\setminus B)$. Then $x\in A$, and $x \notin (A\setminus B)$. If $x\notin (A\setminus B)$, then $x \notin A$, or $x \in B$. But we already ...


2

Because $x^2+3 > 0$ for every $x \in \mathbb{R}$, you can multiply inequality by $5(x^2+3)$. You will obtain inequality $0 < 4x^2 + 7$, which is true for every $x \in \mathbb{R}$ ($4x^2$ is nonnegative for every $x \in \mathbb{R}$ and if we add 7, then the expression is positive.


2

What to do next : Getting $0\ge 4x^2+7$ implies that $x^2\le -\frac 74$, which is impossible because $x^2\ge 0$ for $x\in\mathbb R$. We can prove it in the following way as well : For $x\in\mathbb R$, we have$$x^2\ge 0\Rightarrow x^2+3\ge 3\Rightarrow \frac{1}{x^2+3}\le\frac 13=\frac{5}{15}\lt\frac{12}{15}=\frac{4}{5}.$$ Note that $x=0$ can be ...


1

You are right Alternatively, for real $x\ne0,$ $$x^2>0\iff x^2+3>3\iff\dfrac1{x^2+3}<\dfrac13$$ But $\dfrac13<\dfrac45$ as $5<3\cdot4$


0

Another possible approach is to use the (much easier) Natural Deduction derivation and then "mimick" it with axioms+modus ponens. Natural Deduction derivation of : $\lnot (A \to B) \vdash (B \to C)$. 1) $\lnot (A \to B)$ --- premise 2) $B$ --- assumed [a] 3) $A \to B$ --- from 2) by $\to$-intro 4) $\bot$ --- from 1) and 3) by $\to$-elim ($\lnot ...


0

Although it may not help much, and although it's sneakily substituting constructive for classical logic, I enjoy thinking about this as a computer-science theorist might: namely, interpret the variables $P$ and $Q$ not as statements but as sets, and $P \implies Q$ as the set of functions from $P$ to $Q$. Then we have richer information than mere truth (the ...


0

To make it short (in classical logic): $P\implies Q$ is the same as $\lnot P \lor Q$ and your textbook is right.



Top 50 recent answers are included