Tag Info

New answers tagged

0

As Levon Haykazyan pointed out in a comment, since there are uncountably many analytic functions, the language is uncountable. In order to discuss whether a theory is decidable, the appropriate definitions require that the language in question be presented computably: that is, the function and relation symbols are given by natural numbers, and the arity ...


1

Community wiki answer so the question can be marked as answered: Everyone has at least $1$ acquaintance and at most $29$. Thus there are $29$ different numbers of acquaintances, but $30$ people, so at least two people must have the same number of acquaintances. As André rightly pointed out, the assumption that everyone has at least $1$ acquaintance is ...


0

=> Y'Z(X+X')+XZ(Y+Y') //BY DISTRIBUTIVE AND ASSOCIATIVE PROPERTY => Y'Z+XZ //X+X'=1 AND Y+Y'=1 USING BOOLEAN TABLE PROOF => Z(Y'+X) //BY DISTRIBUTIVE PROPERTY


0

See : George Tourlakis, Lectures in Logic and Set Theory. Volume 1 : Mathematical Logic (2003), page 50 : I.4.23 Metatheorem (Distributivity or Monotonicity of ∃). For any $x,A,B$, $$A \to B \vdash (∃x)A \to (∃x)B.$$ Proof : (1) $A \to B$ --- given (2) $B \to \exists x B$ --- Ax2 (3) $A \to \exists x B$ --- (19, (2) and I.4.1 ...


1

First let me restate the question: it's to show that if $\phi$ and $\psi$ have no propositional variables in common, then $\phi\to \psi$ is a tautology iff either $\phi$ is a contradiction or $\psi$ is a tautology. So suppose $\phi,\psi$ have no variables in common. Now in one direction, suppose that $\phi\to\psi$ is not a tautology. Then, there's a ...


0

Recall that, order-theoretically speaking, the classical $\text{and}$ operator, $\phi \land \psi$, corresponds to the a meet of two elements of a Boolean algebra $\langle \{0,1\},\leq \rangle$, so that we usually define $$v(\phi \land \psi) = \text{min}\{v(\phi),v(\psi)\}$$ Knowing this, it's easy to see that for any tautology $\alpha$ and contingency ...


0

If I said For any woman, there is a food that she loves. $$\forall W \in \text{ Women } \exists F \in \text{ Food } ~:~ W \text{ Loves } F$$ would you answer with "Ok, which food?" Hopefully not, because my response would be "it depends on the woman." Some women like cake, some like wine, some like ice cream-- it depends on the woman. If I say ...


2

If you use the definitions in the Wikipedia article to which you linked, you have $$\begin{align*} \Sigma^+&=\bigcup_{k\ge 1}\Sigma_k\\ &=\bigcup_{k\ge 0}\Sigma_{k+1}\\ &=\bigcup_{k\ge 0}\left(\Sigma_k\Sigma\right)\\ &=\left(\bigcup_{k\ge 0}\Sigma_k\right)\Sigma\\ &=\Sigma^*\Sigma\;. \end{align*}$$


1

If we allow strings of infinite length then we have no way to explicitly describe any well-order of that set, and especially the lexical order is not a well-order. The reason is that even if we pick just two letter $a,b\in\Sigma$, then the (countably) infinite strings over these letters can be bijected with the power set of $\mathbb N$ (per ...


0

Velleman is correct. Just found his book online here. On page 226, he defines functional relations in terms of ordered pairs. In the next line, he introduces the arrow notation $F: A\to B$. At the end of page 227, he introduces the $f(a)$ notation for the unique image of $a$ under functional relation $f$. On page 228, in the section you quote, he ...


0

No, the version in the book is correct. The point is that the set $f$ specifies the function f. It means that if $(a,b) \in f$ then $f(a) = b$ but also vice versa $f(a) = b \Rightarrow (a,b) \in f$. Furthermore, and I guess that where your confusion comes from, $f(a) \neq b$ then $(a,b) \not \in f$ and vice versa. Maybe an example helps. $f: \mathbb{N} ...


2

The word "some" means "there exists" - "some" is an existential quantifier. It is very unlikely that you want the sentence For every $a$, there is a $b$ such that $b = f(a)$ if and only if $(a,b) \in f$. This is because we could take any $b$ that is not $f(a)$, and it would make that sentence true. So for example, if both $(a,c_1)$ and $(a,c_2)$ were ...


1

You can if your universe is finite$^\dagger$. If it is, then $$\forall x \in X.\ \Phi(x)\quad\text{ is equivalent to }\quad\bigwedge_{x \in X}\Phi(x),$$ that is, a big conjunction of $\Phi$'s for each element of $X$. However, if $X$ is infinite, then that would give you infinitely long formula, which we would have trouble valuating. Precisely for this ...


1

The statement $$\exists n\forall m: P(m,n)$$ reads There exists such a value $n$ that for every value $m$, the statement $P(m,n)$ is true. While the statement $$\forall m\exists n: P(m,n)$$ reads For every value of $m$, there exists such a value $n$ that $P(m,n)$ is true. The difference between these statements can be best seen in an example. ...


2

This is a neat little identity. I would put it like this: there's a red button that sets off the bomb. If either Angie or Bill pushes it, then the bomb will go off. $$(\text{Angie pushes the button}) \vee (\text{Bill pushes the button}) \implies (\text{explosion})$$ But we also know that, independently, if Angie pushes the button then the bomb will go off ...


1

It helps to think of examples. Let $p$ be "Alfred wants to play basketball," $q$ be "Bertrand wants to play basketball," and $r$ be "We will play basketball." The first statement reads "If either Alfred or Bertrand want to play basketball, we will play basketball." The second statement reads "If Alfred wants to play basketball we will play basketball; if ...


1

Perhaps it's best to think about the only way an implication can fail: The hypothesis must be true and the conclusion false. So the left statement fails if and only if $P\vee Q$ is true and $R$ is false, i.e., if at least one of $P$ and $Q$ is true and $R$ is false. The right statement fails if and only if (at least) one of $P\implies R$ and $Q\implies R$ is ...


1

This is sometimes referred to as Inference by Cases. It's easy if you bear in mind that $\mathcal{S} \Rightarrow \mathcal{T}$ is equivalent to $(\lnot \mathcal{S}) \lor \mathcal{T}$ where $\mathcal{S}$ and $\mathcal{T}$ are any wffs. \begin{align} [(P \lor Q) \Rightarrow R] &\Leftrightarrow [\lnot(P \lor Q) \lor R] \\ &\Leftrightarrow [(\lnot P ...


1

HINT: I’ll write $F\preceq G$ instead of $F\mathrel{R}G$. You can’t assume that $H$ is the greatest lower bound, because at this point in the argument you don’t know that the set $\{F,G\}$ necessarily even has a greatest lower bound. What you need to do is show that if $H$ is any lower bound for $\{F,G\}$, then $H\preceq F\cdot G$. In order to do this, you ...


2

The definition you've given of $A$ is doesn't actually say what $A$ is. $A$ is presumably supposed to be a set. To say which set it is is to say what things are members of it. Can you name one thing that is a member of $A$ that you have clearly defined? There is something somewhat similar to this that is in somewhat standard use: the von Neumann ...


11

I think there are two separate questions here: Why does the sequence of sets $\{\}, \{\{\}\}, \{\{\{\}\}\}$, . . . not "approach a limit"? Is it possible to have a set $A$ such that $A\in A$? The second one is more easily dealt with, since it a precise question. The usual axioms of set theory, ZFC, rule out any such set; specifically, the axiom of ...


5

You are trying to use intuition to define a set. Which is where your problem is. It almost seems like you want to write something like this, $$A_0 = \emptyset$$ $$A_n = \{ A_{n - 1} \}$$ $$A = \lim_{n \to \infty} A_n$$ But what does that limit mean? It needs to be defined itself, and it isn't in your definition. TLDR: You can't do that! :P


-2

Set theory forbids the existence of a set $A$ such that $A \in A$, as that kind of construction easily leads to paradoxes, such as Russell's paradox. In ZFC, the axiom of regularity has this immediate consequence.


0

you can prove that: (p∨q)∧(∼p∧q) => ∼p∧q < simplification > ∼p∧q => q => p∨q => (p∨q)∧(∼p∧q) < simplification > < addition > < conjunction > Therfore, (p∨q)∧(∼p∧q) <=> ∼p∧q


4

Gödel did epoch-making work in a number of fields: In pure logic, he was the first to prove the completeness of a system of the predicate calculus. In what we might call the proof theory of formal systems, he proved the incompleteness [different sense!] of any formal system strong enough to encode a certain amount of arithmetic. (This required developing ...


1

Try the book Gödel's Theorem: An Incomplete Guide to Its Use and Abuse.


1

You can note that: $$p\lor q=(\lnot p\land q)\lor (p\land\lnot q)\lor (p\land q)$$ and: $$((\lnot p\land q)\lor (p\land\lnot q)\lor (p\land q)) \land (\lnot p\land q)=\lnot p\land q$$.


2

There is more to this question than just the fact that we do not know who will win medals at the 2016 olympics. The question is actually philosophical. But, rather than addressing the philosophy, which is arguably off-topic here, I will discuss two more mathematical issues, although they are still related to philosophy. 1. Definitions in naive set theory ...


1

Write $X*Y$ for the connective described in the question. Suppose that there are only two inputs, $X$ and $Y$. Say that a gate with a certain outcome for each possible input is determinate. Then all determinate gates constructable out of $\neg$ and $*$ will either be functions of both $X$ and $Y$, or just $X$ or just $Y$, or neither. Say that a ...


2

Fitch-style notation is a particular approach to a more general method of proof, called natural deduction. One appealing feature of natural deduction is that it mirrors the structure of deductive argumentation. For example, an argument for a statement of the form "if $p$ then $q$" may begin with an assumption of the truth of $p$, followed by inferences ...


0

It's well after this post has been published and I know only a little about the topic, but if the question is only where to start the program that should be pretty simple: First note the formula to solve the problem in two variables: Find the minimal N such that $$ ax + by \neq N $$ Theorem: N = ab - a - b = (a - 1)*(b - 1) - 1 WLOG assume a < b. ...


6

(a) Adding the minimization operator $\mu$ to primitive recursion in effect adds computation with open-ended searches ("do until" loops) to fixed-depth searches ("for" loops). So that's what gives us access to full-power, unrestricted computation. (b) Rosza Péter gives a beautiful example of a function which is computable, takes only the values $0$ and $1$, ...


0

The symbols means the basic relation of derivability : "the formula $B$ is derivable from the set $\Gamma$ of formulae". See : Ian Chiswell & Wilfrid Hodges, Mathematical Logic (2007), page 7 : Definition 2.1.2 A sequent is an expression $(\Gamma \vdash \psi)$ (or $\Gamma \vdash \psi$ when there is no ambiguity) where ...


0

The usual terminology is that a propositional formula (in variables $P_1, P_2, \ldots P_n$) is satisfiable if there is at least one assignment of truth-values to its variables on which it is true. Another useful notion in the vicinity is that of a contingent formula, which is true on at least one assignment, and false on at least one. So: tautologies are ...


0

I think your "workable formula" is what I would call an "open sentence"- a statement with one or more variables that are "true" or "false" depending upon the values of the variables. A "tautology" is true for all values of the variables, a "contradiction" is false for all values of the variables.


1

Disclaimer: I suspect that the point of your exercise is to practice various logical equivalences, like the double negation elimination, distributive properties of $\land$ and $\lor$ and the De Morgan's laws. If that's the case, i.e., the problem statement exactly asks you to do that (for example, "using various logical equivalences convert the following ...


3

The argument alluded to in the question is sound. Specifically: Turing's thesis says that, if a human computer can perform a given algorithm, then there is a Turing machine to do it. A human computer can certainly simulate the computation of a Turing machine, given the code for the machine. Therefore, by Turing's thesis, there must be a universal Turing ...


2

One way to circumvent the logical implications outlined in the other answers would be to define a time dependent set as a map $\mathbb{R} \to \text{Sets}$. Then the object you define could be modeled as a time dependent set $$GM2016(t) = \{\text{people who have won a gold medal at the 2016 Olympics until time $t$}\}.$$ which is a subset of the time ...


13

(1) Note that all 2016 Olympic winners are currently existing people (you can't win an Olympic medal aged one!). We don't know who they are. They might be Usain, Jessica, ... or they might be Justin, Katerina ... Assume for the moment, that sets can have non-mathematical objects as members. Then the set {Usain, Jessica, ...} exists -- it is a set of ...


0

Turing's thesis asserts that every "effectively computable" function is computable by a Turing machine. It is not necessary to sharply define "effective computability" to get the converse implication. This amounts to showing that there is a partial enumeration $F$ (possibly nonterminating) of the effectively computable functions such that the value of $F$ on ...


6

Think of this example: long time ago we did not know if $\pi$ or $e$ is in the set of rational numbers.


1

Now from $∀x∈A(P(x))$ using universal instantiation, I get $P(c)$ where $c$ is an arbitrary element in A . Now my doubt is, if using $∃y∈A(Q(y))$ , can I conclude $Q(c)$ ?. No. My reasoning says yes, because $c$ is an arbitrary element in $A$ and $y∈A$ . Is this type of instantiation from universal to existential has a special name ? Your ...


0

Maybe you are interested into the "algebraic" approach to logic ... See Abstract algebraic logic and Propositional Consequence Relations and Algebraic Logic with bibliography. You can see also : H.Andréka, J.D.Monk, I.Németi (eds.), Algebraic logic (1991) Dov M.Gabbay & F.Guenthner (editors), Handbook of Philosophical Logic : 2nd ed. Vol.2 (2013), ...


2

HINT: Start with an $X\in F$. Since $F\mathrel{R}G$, there is a $Y\in G$ such that $X\subseteq Y$. Then since $G\mathrel{R}F$, there is an $X'\in F$ such that $Y\subseteq X'$, and it follows that $X\subseteq X'$. But $X$ and $X'$ are both members of the partition $F$, so what does that tell you about them? What can you then infer about $X$ and $Y$?


0

Your argument is correct but the point is that you do not have to appeal to Godel's 2nd incompleteness theorem to prove this and Jech does that.


0

Hint The first step, as per Peter Smith's comment above, is a suitable "formalization" of the two sentences. My suggestion is : a) $\exists x (J(x) \land \lnot \exists y F(y,x))$ --- premise b) $\forall x (\lnot J(x) \to \exists y F(y,x))$ --- conclusion. If we rewrite the negation of the conclusion as : b') $\exists x \lnot (\lnot J(x) \to \exists y ...


5

First, a bit of terminology. There is a particular combinatorial result, a strengthened form of Ramsey's theorem. That result is provable in many systems, including ZF set theory. Let's call this combinatorial result $R$. The Paris-Harrington theorem shows that result $R$ is not provable in Peano Arithmetic. In what I believe is the most common terminology ...


1

$\textbf{Hint}$: Let $p_n$ be a prime divisor of $R_n=n!+1$, and show that $p_n$ must be larger than n. Then conclude from this that there are infinitely many primes.


1

I believe you meant to say that if the sequence of prime numbers is finite, then the values of $n$ for which $R_n$ is prime must also be finite. From here, you can simply take $n$ to be the product of all the primes (only finitely many by assumption), and then following the same argument as in Euclid's proof, there must be some prime that divides $R_n$ but ...


3

Your wording is completely confusing. Your statement: Suppose that the sequence of prime numbers is finite, so the sequence $R_n$ is finite is wrong. Also, you then say that $R_{n+1}$ is not a prime number, but you did not determine what the value of $n$ is. Furthermore, you then proved that $R_{n+1}$ is divided by $1$ and itself, and concluded that ...



Top 50 recent answers are included