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
11 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
18 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
21 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
15 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 ...
1
vote
1answer
23 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
55 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
28 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
103 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 ...
4
votes
0answers
68 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
44 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
69 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
47 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
62 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
104 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 ...
-2
votes
1answer
35 views

Recurring Decimals [duplicate]

If: x = 0.999... 10x = 9.999... [Multiply by 10 on both sides] 9x = 9 [Subtract x, or 0.999... from both sides] x = 1 [Divide by 9 on both sides] Therefore, 0.999... = 1 Why is this? How is it ...
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
83 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
161 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
91 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
49 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
46 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
60 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
votes
0answers
56 views

Inner Models of ZFC which satisfy V=L [closed]

Let $M$ be an inner model of ZFC which satisfies the Axiom of Constructibilty ($V=L$). What is known about general form of such a model? Should it be similar to Godel's constructible universe ($L$) in ...
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 ...
1
vote
1answer
96 views

Miller's Construction, Partition Principle and Failure of Axiom of Choice

Partition Principle ($PP$) is the following statement: For all sets $a$, $b$ there is an injection $f:a\rightarrow b$ iff there is a surjection $g:b\rightarrow a$ It is known that $ZF\vdash ...
1
vote
3answers
78 views

Can we make illegitimate operations with $0$ legitimate by adding a few more axioms? [duplicate]

Just out of curiosity, can we make illegitimate operations with $0$, say, division by $0$ legitimate simply by imposing additional axioms? If so, then what consequences may follow? If the answer is ...
2
votes
4answers
74 views

Analyzing the logical form of “All married couples fight”

This is one of the example problems in Velleman's How to Prove book: Analyze the logical forms of the following statements. All married couples have ...
0
votes
1answer
38 views

complements of a powerset

I have a function $Q(n)=p(\{1,\ldots,n\})\setminus\{\{\}\}$ such that it won't have the empty set in it. Note, if you are going to change out my equations for Latex, I would greatly appreciate it ...
-2
votes
1answer
63 views

Inference in First Order Logic Problem [closed]

I read one logic note by Michle Sipser from MUT. I get stuck in inference. please help me in step by step inference? By using First order logic and Resolution Rules, and Proof by contradiction from ...
3
votes
5answers
143 views

Is $'' \sum_{n = 1}^{\infty} (-1)^n \; \text{is a real number}''$ an invalid statement or a false proposition?

So we're beginning an introductory logic course and my professor is giving examples for valid statements/ propositions - meaningful statements that are either true or false but not both. So he puts ...
4
votes
1answer
189 views

Replacing the “if $x ≤ y$, then $x + z ≤ y + z$” axiom in Reals.

How can I prove that we cannot (or maybe can) replace preservation of order under addition i.e. "If $x \leq y$, then $x + z \leq y + z$ with "if $0<x$ and $0<y$ , then $0<x+y$" in axioms ...
2
votes
0answers
47 views

On the back and forth conditions for a set of partial isomorphisms

I've recently begun reading Poizat's A Course in Model Theory and already in the first pages I had some doubts. One odd (not necessarily bad) thing is that he defines notions such as isomorphism only ...
1
vote
2answers
163 views

How many undecidable statements are there in ZFC?

There are several statements known to be undecidable in ZFC, with the continuum hypothesis probably being the most "popular" one. Is it known how many undecidable statements are there in ZFC? I.e. ...
8
votes
0answers
92 views

Does such a first-order theory exist? A question pertaining to transitive models of ZFC.

Assume a proper class of inaccessibles. Does there exist a first-order theory $T$ subject to the following conditions? $T$ admits an infinite model Whenever $M$ is a transitive model of ZFC with $T ...
-1
votes
1answer
42 views

looking at the alphabet ,the letters are numbered 1-26 ,

looking at the alphabet ,the letters are numbered 1-26 , such that 1 =one=15+14+5=34 (O=15, N=14, E =5 ) 2=two=20+23+15=58 (T=20, W=23, 0=15) 3=three =56 4=four=60 ...
1
vote
1answer
34 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.