Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
0answers
22 views

Math as Logic????

I just finished my studies in rudimentary symbolic logic (I can do first-order proofs with relations and identity), and I have heard that almost all of mathematics can be framed using first order ...
2
votes
5answers
32 views

What is negation of the following sentence?

What is negation of All birds can fly. The question seems bit funny but i don't know which of the following two sentences is correct: Some birds can not fly There is at least one bird which can not ...
6
votes
1answer
74 views

What axioms does ZF have, exactly?

While trying to find the list of axioms of ZF on the Web and in literature I noticed that the lists I had found varied quite a bit. Some included the axiom of empty set, while others didn't. That is ...
1
vote
1answer
26 views

Analyzing Set of all Perfect squares

I have been reading Velleman's How to Prove book and the following statement in the book confuses me: For example, suppose we wanted to define S to be the set of ...
2
votes
1answer
24 views

Inference Challenge in First Order Logic

I ran into old exercise on FOL in Artificial Intellegence. any one could help me? Suppose we have $ E \bigwedge R \Rightarrow B$ $ E \Rightarrow R \bigvee P\bigvee L $ $ K \Rightarrow B$ $ \neg ...
1
vote
2answers
74 views

Definition of “contradiction” and use of the term for “⊥”

If one looks in Internet for definition of “contradiction” (including respective words in other languages), one finds a mess. See for example this index of Wikipedia articles in various languages. The ...
0
votes
2answers
34 views

Show that this argument is valid.

¬p → C; ∴ p. Where C denotes a contradiction. What does it mean by ¬p → C;? Also another statement ¬p → F; ∴ p. Is there any differences between the two statement since from my understanding a ...
0
votes
1answer
23 views

Determine whether the argument is valid or invalid

. Determine whether the following argument is valid: $$\displaylines{ 1:p\cr 2:p ∨ q\cr 3:q → (r → s)\cr 4:t → r\cr ∴ ¬s → ¬t.}$$ Suppose $$\displaylines{¬s → ¬t.}$$ is False, we have s=F; t=T To ...
0
votes
1answer
32 views

Determine whether the argument is valid or invalid

$$\displaylines{ ¬p → (r ∧ ¬s)\cr t → s\cr u → ¬p\cr ¬w\cr u ∨ w\cr ∴ t → w\cr}$$ I have the solution which shows We start by noticing that we have (How did we know we have to start here?) ...
0
votes
0answers
23 views

Is this a valid proof of $(A∧B’) ∧C↔(A∧C) ∧B’$?

So I am supposed to prove $(A∧B’) ∧C↔(A∧C) ∧B’$ using wffs and equivalence rules. I have never done such proof, and I want to check if my steps are correct. This assignment is only graded based off of ...
0
votes
1answer
25 views

How do I write this statement using symbols?

Juan is a math major but not a computer science major. (m= "Juan is a math major.", c= "Juan is a computer science major.") How do I write this is symbolic form using the letters and (and, or, not)?
0
votes
1answer
28 views

Prove tautology without truth table

This has been asked before, but I have different problems. I’m asking because this was not discussed in class and I’m unsure of the procedure in obtaining the proof. The two in question are the ...
0
votes
0answers
25 views

Understanding why a disjunctive normal form is equivalent to the proposition

I'm having trouble understanding the equivalence relation bet. a proposition and its disjunctive normal form (DNF). For example, in the example on p.51 ...
2
votes
1answer
51 views

p implies q statement means that if p is true, q also has to be true

I don't understand this statement. Looking at the truth table, if p is false, the statement is always true. if p is true and q is true, the statement is true. if p is true and q is false, the ...
1
vote
0answers
39 views

In Whitehead and Russell's PM, are homogenous relations the only ones that have relation numbers?

Given the definition of ordinal similarity: ✳151.01 $P \overline{smor} Q = \hat{S}\{ S\in 1\rightarrow 1. C‘Q=ConverseD‘S. P=S^;Q\}$ Df. $Q$ has to be homogeneous, otherwise $C‘Q$ is meaningless. ...
0
votes
2answers
23 views

Sorting out logic homework with a friend.

My friend and I were looking over my homework and he pointed out something that he thought was incorrect. I was to write sentances using logical connectives. The original sentance was: "To get ...
1
vote
0answers
29 views

Interpreting logical forms involving quantifiers

I have been trying to translate these two logical form into English statements without using any quantifier laws: (a) ∃x∀y ¬L(x,y) (b) ¬(∃x∀y L(x,y)) where ...
0
votes
0answers
18 views

$P \Rightarrow Q$ and Skolem Functions [on hold]

We know if $P \Rightarrow Q$ (it means be true), Predicate Q is Weaker than P. which of the following is Weaker? F1 is a Skolem Function, and F2 is a Skolem constant. 1) $\exists y \forall x ...
0
votes
2answers
39 views

Expressing statements in positive way

I have been working on this problem from Velleman's How to prove book: Negate these statements and then reexpress the results as equivalent positive ...
0
votes
2answers
59 views

Why does the author define these “logical notations” for set logic with “if then” and &?

In Section 1.1 of "Set Theory for Computer Science", the author defines $ \forall x \in X. P(x) $ and $ \exists x \in X.P(x) $ as shorthand for $ \forall x.(x \in X \Rightarrow P(x)) $ and $ \exists ...
1
vote
1answer
33 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
2
votes
0answers
110 views

Is mathematics invented or discovered? [on hold]

A google search yields millions of results, most of which are made by laymen who have nothing to do with math and it's "just another article" for the authors, so I assume here with so much passion in ...
5
votes
0answers
71 views

complete, finitely axiomatizable, theory with 3 countable models

Does it exist a complete, finitely axiomatizable, first-order theory $T$ with exactly 3 countable non-isomorphic models? A few relevant comments: There is a classical example of a complete theory ...
3
votes
0answers
48 views

What is the most expressive logic such that presentations of algebraic structures “work”?

I feel like this is one of the best questions I've asked in a while. Hope you enjoy it. In my opinion, one of the most important ideas in modern algebra is the idea that we can present algebraic ...
3
votes
2answers
74 views

Is it meaningless to say $M\prec N$ for two proper class models?

Kunen in page 88 of his "Set Theory" book says: ... For a specific given $\varphi$, the notion $M\prec_{\varphi}N$ (i.e. $\forall \overline{a}\in M~~~M\models \varphi ...
-4
votes
0answers
48 views

What is the pure essence of a definition of semantics? [on hold]

What is the very essence of the definition of semantics (and interpretation, structure, model) for a logician or for an algebraist? We all know the usual definitions. But is it not the essence of ...
-1
votes
2answers
25 views

One output for input of $n$-tuples using AND, OR, NOT

Let $B$ be set of $\{0,1\}$ and $B_n$ be the set of all strings of length $n$. How many functions can be constructed from $B_n$ to $B$ using logical operators like AND, OR, NOT. Help $\rightarrow$ ...
1
vote
1answer
64 views

What actually constitutes a *definition* for a function?

I'm reading Enderton's text on logic trying to justify ( to myself ) the use of induction on recursively defined sets. This is of course used repeatedly in trying to prove results about well-formed ...
3
votes
2answers
109 views

Can one prove existence of incommensurables without the Pythagorean theorem?

Euclid's proof that the side and the diagonal of a square have no common measure, probably going back to Pythagoreans, reduces it to proving the irrationality of $\sqrt{2}$. This reduction uses the ...
0
votes
0answers
25 views

LUB property in a predicative logic

Is there a formulation of real analysis in a predicative logical system such that the LUB property is available? Here is a quote from http://en.wikipedia.org/wiki/Impredicativity : "Kleene uses the ...
3
votes
2answers
55 views

Checking understanding on proving uniqueness of identity and inverse elements of a group.

Sorry for such a trivial question, but just wanted to check my understanding. When proving a statement, for example, that the inverse of a group element is unique (in elementary group theory) one ...
2
votes
2answers
84 views

Example of a proof using the axiom of commensurability

I'm teaching our intro to proofs course (well, one of them) and one of the classic illustrations of an overturned "axiom" is the Greek axiom of commensurability, which stated in geometric terms the ...
4
votes
2answers
167 views

How much set theory is necessary for serious logic?

I'm currently studying logic at my university and I have been trying to squeeze in as much set theory on the side as possible. Considering that I am spending quite a lot of time studying set theory ...
0
votes
4answers
55 views

Formulating a recursive definition

Let Σ(k) = 1 + 3 + 5 + ... + (2k+1) be the sum of all odd natural numbers from 1 up to and including (2k+1). Formulate a recursive definition for Σ including both the base case Σ(0) = 1 and a (k+1)th ...
2
votes
2answers
93 views

Equivalence between middle excluded law and double negation elimination in Heyting algebra

It's well-know that in intuitionistic logic, middle excluded law and double negation elimination are equivalent. For example, in Johnstone - Topo theory, I read that, in a Heyting algebra, $p\vee\neg ...
1
vote
1answer
55 views

Contrapostive/Law of Excluded Middle

I remember that during my first proofs class the hardest thing I had accepting were the logic we had to learn, and it seems I still have questions about. So I was thinking about why when ...
1
vote
1answer
62 views

Countable Set & Formal Grammar

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. I try to summarize my though. I think the following proposition is true. suppose $\Sigma$ is arbitrary ...
2
votes
0answers
26 views

Does there exist a finite axiomatization of the quasi-algebraic theory of real matrix rings?

Some definitions. Let us take the signature of ring theory to consist of the function symbols $\{+,-,0,\cdot,1\}$ equipped with their usual airities, where the minus symbol represents a unary ...
2
votes
1answer
50 views

Suppose $R \sim_\omega R'$. Then for every $k$-tuple $a$ in $E$ and every natural number $p$, there is a $k$-tuple $b$ in $E'$ such that $a \sim_p b$

Sorry to bother you guys again with a Poizat question, but I'm struggling a little bit with the material (as it must be obvious) and I want to check if I got the main idea correctly or if I'm totally ...
0
votes
0answers
49 views

Inference in First Order Logic [closed]

Suppose we have $ E \bigwedge R \Rightarrow B$ $ E \Rightarrow R \bigvee P\bigvee L $ $ K \Rightarrow B$ $ \neg (L \bigwedge B ) $ $ P \Rightarrow \neg K $ which of them cannot inference from ...
4
votes
1answer
62 views

Elementary Model Theory

I'm working through section 4.3. on model theory from Dirk van Dalen's Logic and Structure (fifth ed.) and am struggling with van Dalen's sometimes sloppy way of presenting proofs. As usual let a ...
2
votes
1answer
54 views

Transfinite Cardinals and Expressive Power

Consider a language with a sufficiently rich lexicon such that, for every (finite and transfinite) cardinal K, it's possible to express the statement that there exist K-many objects. Two general ...
2
votes
1answer
33 views

Equality of sets of local isomorphisms between relations

I'm still working on the first pages of Poizat's A Course in Model Theory. I'll state the basic definitions again, in order to avoid referring back to an early question: Poizat defines an isomorphism ...
1
vote
2answers
56 views

About well formed formula

Axiom of specification is schema because it talks about definite condition(or wff) which use notion of finite but this again we define from sets. But in logic we defined wff using consept of tuple and ...
2
votes
1answer
41 views

Deciding between implication and conjunction

This is one of the solved problems in Velleman's How to prove book: Analyze the logical forms of the following statements: 1) John likes exactly one person. ...
0
votes
1answer
29 views

Two events depending on each other.

Person A goes to a party P only if person B goes, but B also only goes if A goes. Is this an uncertain statement or do they not go at all? I can think of two argumentations, of which the second is ...
0
votes
0answers
31 views

Extensions by recursive definitions

In the Wikipedia entry on Extension by definitions I learn that an explicit definition in the language of a theory $T$ yields a conservative extension $T'$ of $T$. I wonder if this eventually does ...
1
vote
1answer
82 views

Quantifier problems of equations in physics [closed]

Equations in physics are often written without quantifiers. For instance, from time to time we can see the equation $$E = mc^2$$ is casually written down. To assert that static energy equals mass ...
2
votes
0answers
37 views

Proposition into spoken language

Given: $\sim( p \leftrightarrow (q \vee r) )$ $p:$ It's raining $q:$ The sun is shining $r:$ There are clouds in the sky. Translate the proposition into spoken language. ...
1
vote
1answer
56 views

Is it possible to iterate a function transfinite times?

Let $f:A\rightarrow A$ be a function. We can simply define $f\circ f$, $f\circ f\circ f$, etc., for each given natural number inductively. $f^{(0)}=id_A$ $\forall n\in\omega \qquad f^{(n+1)}=f\circ ...