Exploring Logic Symbols: Meaning of Upside-down A, V, and U

[Char. Limit]

A lot of times, when I look at something written in logic, there are these strange symbols popping out everywhere. Examples include an upside-down A, a giant V or U, or an upside-down V.

Could you point me to an article describing what these symbols mean?

 

[tiny-tim]

Hi Char. Limit!

Upside-down A is quite common, it means "for all" (as in "for all x, there is a y such that …")

See http://en.wikipedia.org/wiki/Logical_symbols" generally.

 

[tauon]

A lot of times, when I look at something written in logic, there are these strange symbols popping out everywhere. Examples include an upside-down A, a giant V or U, or an upside-down V.

Could you point me to an article describing what these symbols mean?

the wiki link posted by t-tim is pretty good.

also, since they're not mentioned there: the giant V is an equivalent notation for [tex]\exists[/tex] and the upside down giant V is an equivalent notation for [tex]\forall[/tex].

these symbols are used by some authors because saying [tex]\forall x, P(x)[/tex] is equivalent to [tex]P(x_1)\wedge P(x_2) \wedge ... \wedge P(x_i)\wedge ...[/tex].

it's similar for [tex]\exists[/tex] and the big V. this big V big upside down V notation is used because it shows the link between the quantifiers and logical conjunction and logical disjunction.

 

[Hurkyl]

That rewriting of forall as an iterated conjunction (and exists as disjunction) only works if you know the entire domain of the variable, and the domain is finite. (if you're using infinitary logic, you can extend this to infinite domains that aren't too big)

The giant conjunction and disjunction symbols are just iterations -- in exactly the same way that [itex]\Sigma[/itex] relates to addition, and [itex]\Pi[/itex] relates to multiplication.

 

[Char. Limit]

Did you just say "infinite domains that aren't too big"?

Are you saying something like "omega can work but aleph-one can't"?

Also, thanks for the Wikipedia article. I've bookmarked it.

 

[Hurkyl]

Yep.

Finitary logic only offers binary conjunctions and disjunctions. Of course, by iterating (and using "False" or "True" as the base case as appropriate) we can define the conjunction or disjunction of any finite number of things.

Infinitary logic, at its discretion, offers infinite versions of these repeated operations. What is actually provided depends upon the specific brand. I imagine that "countably many" and "any small^* amount" are the most common, but any restriction on classes could be used -- it doesn't even have to be based on size! For example, there is probably some logic related to nonstandard analysis that allows "hyperfinite" conjunctions/disjunctions, and none others.


It doesn't even have to be the same for conjunction and disjunction! e.g. The infinitary logic relevant to one of my interests (topos theory) only allows finite conjunctions, but all small disjunctions.


Now, to add a disclaimer -- I've never seen infinitary logic formally presented: in what I've read it winds up simply being something like "if we allow infinitely many disjunctions, we get infinitary logic". While what I've described above is consisteint with what that would mean, there may be some subtlety I am unaware of.



*: Small, here, means that it fits into a set. e.g. the real numbers are small. The class of all sets is not small

 

[Char. Limit]

Ah, yes... cardinality... it never makes sense to me, let it begone.

Do you have an example of infinitary logic?

 

[tiny-tim]

Do you have an example of infinitary logic?

I have discovered a truly marvellous example, but this universe is too narrow to contain it.

 

[Char. Limit]

Lol... I love references to FLT...

How can a universe be narrow, when the universe is flat, spherical, of uniform density, and with me at the center?

 

[tiny-tim]

you're the limit!

… and with me at the center?

It's the margin round you that's too narrow!

 

[Char. Limit]

Ah. In that case, let me just expand the universe a bit...

"There you go, one lightminute bigger.

 

[tiny-tim]

Wow! suddenly it's brighter!

 

[Hurkyl]

If you're willing to consider just propositional logic, the algebraic analog of "truth values, conjunction, and disjunction" is that of a distributive lattice.

For classical propositional logic, you want to consider Boolean lattices.

For infinitary propositional logic, you'd want to look at things like complete lattices.



The open sets in a topological space, incidentally, is an example of a complete lattice with finite meets and arbitrary joins. (meet ~ conjunction ~ intersection, join ~ disjunction ~ union). It's not boolean, though -- but it is Heyting.

(Such a lattice has arbitrary meets -- the "interior of intersection" operation -- but those aren't expected to behave properly algebraically. e.g. the distributive property need not hold, nor should they be preserved by homomorphisms)